Fix #29146: object used for particle instancing did not update when affected
[blender.git] / source / blender / blenkernel / intern / depsgraph.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2004 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): none yet.
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/depsgraph.c
27  *  \ingroup bke
28  */
29
30  
31 #include <stdio.h>
32 #include <string.h>
33 #include <math.h>
34
35 #include "MEM_guardedalloc.h"
36
37 #include "BLI_winstuff.h"
38 #include "BLI_utildefines.h"
39 #include "BLI_listbase.h"
40 #include "BLI_ghash.h"
41
42 #include "DNA_anim_types.h"
43 #include "DNA_camera_types.h"
44 #include "DNA_group_types.h"
45 #include "DNA_lattice_types.h"
46 #include "DNA_key_types.h"
47 #include "DNA_material_types.h"
48 #include "DNA_mesh_types.h"
49 #include "DNA_node_types.h"
50 #include "DNA_scene_types.h"
51 #include "DNA_screen_types.h"
52 #include "DNA_windowmanager_types.h"
53
54 #include "BKE_animsys.h"
55 #include "BKE_action.h"
56 #include "BKE_effect.h"
57 #include "BKE_fcurve.h"
58 #include "BKE_global.h"
59 #include "BKE_group.h"
60 #include "BKE_key.h"
61 #include "BKE_library.h"
62 #include "BKE_main.h"
63 #include "BKE_node.h"
64 #include "BKE_mball.h"
65 #include "BKE_modifier.h"
66 #include "BKE_object.h"
67 #include "BKE_particle.h"
68 #include "BKE_pointcache.h"
69 #include "BKE_scene.h"
70 #include "BKE_screen.h"
71 #include "BKE_utildefines.h"
72
73 #include "depsgraph_private.h"
74  
75 /* Queue and stack operations for dag traversal 
76  *
77  * the queue store a list of freenodes to avoid successives alloc/dealloc
78  */
79
80 DagNodeQueue * queue_create (int slots) 
81 {
82         DagNodeQueue * queue;
83         DagNodeQueueElem * elem;
84         int i;
85         
86         queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
87         queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
88         queue->count = 0;
89         queue->maxlevel = 0;
90         queue->first = queue->last = NULL;
91         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3");
92         elem->node = NULL;
93         elem->next = NULL;
94         queue->freenodes->first = queue->freenodes->last = elem;
95         
96         for (i = 1; i <slots;i++) {
97                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4");
98                 elem->node = NULL;
99                 elem->next = NULL;
100                 queue->freenodes->last->next = elem;
101                 queue->freenodes->last = elem;
102         }
103         queue->freenodes->count = slots;
104         return queue;
105 }
106
107 void queue_raz(DagNodeQueue *queue)
108 {
109         DagNodeQueueElem * elem;
110         
111         elem = queue->first;
112         if (queue->freenodes->last)
113                 queue->freenodes->last->next = elem;
114         else
115                 queue->freenodes->first = queue->freenodes->last = elem;
116         
117         elem->node = NULL;
118         queue->freenodes->count++;
119         while (elem->next) {
120                 elem = elem->next;
121                 elem->node = NULL;
122                 queue->freenodes->count++;
123         }
124         queue->freenodes->last = elem;
125         queue->count = 0;
126 }
127
128 void queue_delete(DagNodeQueue *queue)
129 {
130         DagNodeQueueElem * elem;
131         DagNodeQueueElem * temp;
132         
133         elem = queue->first;
134         while (elem) {
135                 temp = elem;
136                 elem = elem->next;
137                 MEM_freeN(temp);
138         }
139         
140         elem = queue->freenodes->first;
141         while (elem) {
142                 temp = elem;
143                 elem = elem->next;
144                 MEM_freeN(temp);
145         }
146         
147         MEM_freeN(queue->freenodes);                    
148         MEM_freeN(queue);                       
149 }
150
151 /* insert in queue, remove in front */
152 void push_queue(DagNodeQueue *queue, DagNode *node)
153 {
154         DagNodeQueueElem * elem;
155         int i;
156
157         if (node == NULL) {
158                 fprintf(stderr,"pushing null node \n");
159                 return;
160         }
161         /*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->count);*/
162
163         elem = queue->freenodes->first;
164         if (elem != NULL) {
165                 queue->freenodes->first = elem->next;
166                 if ( queue->freenodes->last == elem) {
167                         queue->freenodes->last = NULL;
168                         queue->freenodes->first = NULL;
169                 }
170                 queue->freenodes->count--;
171         } else { /* alllocating more */         
172                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
173                 elem->node = NULL;
174                 elem->next = NULL;
175                 queue->freenodes->first = queue->freenodes->last = elem;
176
177                 for (i = 1; i <DAGQUEUEALLOC;i++) {
178                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
179                         elem->node = NULL;
180                         elem->next = NULL;
181                         queue->freenodes->last->next = elem;
182                         queue->freenodes->last = elem;
183                 }
184                 queue->freenodes->count = DAGQUEUEALLOC;
185                         
186                 elem = queue->freenodes->first; 
187                 queue->freenodes->first = elem->next;   
188         }
189         elem->next = NULL;
190         elem->node = node;
191         if (queue->last != NULL)
192                 queue->last->next = elem;
193         queue->last = elem;
194         if (queue->first == NULL) {
195                 queue->first = elem;
196         }
197         queue->count++;
198 }
199
200
201 /* insert in front, remove in front */
202 void push_stack(DagNodeQueue *queue, DagNode *node)
203 {
204         DagNodeQueueElem * elem;
205         int i;
206
207         elem = queue->freenodes->first; 
208         if (elem != NULL) {
209                 queue->freenodes->first = elem->next;
210                 if ( queue->freenodes->last == elem) {
211                         queue->freenodes->last = NULL;
212                         queue->freenodes->first = NULL;
213                 }
214                 queue->freenodes->count--;
215         } else { /* alllocating more */
216                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
217                 elem->node = NULL;
218                 elem->next = NULL;
219                 queue->freenodes->first = queue->freenodes->last = elem;
220
221                 for (i = 1; i <DAGQUEUEALLOC;i++) {
222                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
223                         elem->node = NULL;
224                         elem->next = NULL;
225                         queue->freenodes->last->next = elem;
226                         queue->freenodes->last = elem;
227                 }
228                 queue->freenodes->count = DAGQUEUEALLOC;
229                         
230                 elem = queue->freenodes->first; 
231                 queue->freenodes->first = elem->next;   
232         }
233         elem->next = queue->first;
234         elem->node = node;
235         queue->first = elem;
236         if (queue->last == NULL)
237                 queue->last = elem;
238         queue->count++;
239 }
240
241
242 DagNode * pop_queue(DagNodeQueue *queue)
243 {
244         DagNodeQueueElem * elem;
245         DagNode *node;
246
247         elem = queue->first;
248         if (elem) {
249                 queue->first = elem->next;
250                 if (queue->last == elem) {
251                         queue->last=NULL;
252                         queue->first=NULL;
253                 }
254                 queue->count--;
255                 if (queue->freenodes->last)
256                         queue->freenodes->last->next=elem;
257                 queue->freenodes->last=elem;
258                 if (queue->freenodes->first == NULL)
259                         queue->freenodes->first=elem;
260                 node = elem->node;
261                 elem->node = NULL;
262                 elem->next = NULL;
263                 queue->freenodes->count++;
264                 return node;
265         } else {
266                 fprintf(stderr,"return null \n");
267                 return NULL;
268         }
269 }
270
271 void    *pop_ob_queue(struct DagNodeQueue *queue) {
272         return(pop_queue(queue)->ob);
273 }
274
275 DagNode * get_top_node_queue(DagNodeQueue *queue) 
276 {
277         return queue->first->node;
278 }
279
280 int             queue_count(struct DagNodeQueue *queue){
281         return queue->count;
282 }
283
284
285 DagForest *dag_init(void)
286 {
287         DagForest *forest;
288         /* use callocN to init all zero */
289         forest = MEM_callocN(sizeof(DagForest),"DAG root");
290         return forest;
291 }
292
293 /* isdata = object data... */
294 // XXX this needs to be extended to be more flexible (so that not only objects are evaluated via depsgraph)...
295 static void dag_add_driver_relation(AnimData *adt, DagForest *dag, DagNode *node, int isdata)
296 {
297         FCurve *fcu;
298         DagNode *node1;
299         
300         for (fcu= adt->drivers.first; fcu; fcu= fcu->next) {
301                 ChannelDriver *driver= fcu->driver;
302                 DriverVar *dvar;
303                 int isdata_fcu = isdata || (fcu->rna_path && strstr(fcu->rna_path, "modifiers["));
304                 
305                 /* loop over variables to get the target relationships */
306                 for (dvar= driver->variables.first; dvar; dvar= dvar->next) {
307                         /* only used targets */
308                         DRIVER_TARGETS_USED_LOOPER(dvar) 
309                         {
310                                 if (dtar->id) {
311                                         // FIXME: other data types need to be added here so that they can work!
312                                         if (GS(dtar->id->name)==ID_OB) {
313                                                 Object *ob= (Object *)dtar->id;
314                                                 
315                                                 /* normal channel-drives-channel */
316                                                 node1 = dag_get_node(dag, dtar->id);
317                                                 
318                                                 /* check if bone... */
319                                                 if ((ob->type==OB_ARMATURE) && 
320                                                         ( ((dtar->rna_path) && strstr(dtar->rna_path, "pose.bones[")) || 
321                                                           ((dtar->flag & DTAR_FLAG_STRUCT_REF) && (dtar->pchan_name[0])) )) 
322                                                 {
323                                                         dag_add_relation(dag, node1, node, isdata_fcu?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver");
324                                                 }
325                                                 /* check if ob data */
326                                                 else if (dtar->rna_path && strstr(dtar->rna_path, "data."))
327                                                         dag_add_relation(dag, node1, node, isdata_fcu?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver");
328                                                 /* normal */
329                                                 else
330                                                         dag_add_relation(dag, node1, node, isdata_fcu?DAG_RL_OB_DATA:DAG_RL_OB_OB, "Driver");
331                                         }
332                                 }
333                         }
334                         DRIVER_TARGETS_LOOPER_END
335                 }
336         }
337 }
338
339 static void dag_add_collision_field_relation(DagForest *dag, Scene *scene, Object *ob, DagNode *node)
340 {
341         Base *base;
342         DagNode *node2;
343
344         // would be nice to have a list of colliders here
345         // so for now walk all objects in scene check 'same layer rule'
346         for(base = scene->base.first; base; base= base->next) {
347                 if((base->lay & ob->lay) && base->object->pd) {
348                         Object *ob1= base->object;
349                         if((ob1->pd->deflect || ob1->pd->forcefield) && (ob1 != ob))  {
350                                 node2 = dag_get_node(dag, ob1);                                 
351                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Field Collision");
352                         }
353                 }
354         }
355 }
356
357 static void build_dag_object(DagForest *dag, DagNode *scenenode, Scene *scene, Object *ob, int mask)
358 {
359         bConstraint *con;
360         DagNode * node;
361         DagNode * node2;
362         DagNode * node3;
363         Key *key;
364         ParticleSystem *psys;
365         int addtoroot= 1;
366         
367         node = dag_get_node(dag, ob);
368         
369         if ((ob->data) && (mask&DAG_RL_DATA)) {
370                 node2 = dag_get_node(dag,ob->data);
371                 dag_add_relation(dag,node,node2,DAG_RL_DATA, "Object-Data Relation");
372                 node2->first_ancestor = ob;
373                 node2->ancestor_count += 1;
374         }
375
376         /* also build a custom data mask for dependencies that need certain layers */
377         node->customdata_mask= 0;
378         
379         if (ob->type == OB_ARMATURE) {
380                 if (ob->pose){
381                         bPoseChannel *pchan;
382                         bConstraint *con;
383                         
384                         for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next) {
385                                 for (con = pchan->constraints.first; con; con=con->next) {
386                                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
387                                         ListBase targets = {NULL, NULL};
388                                         bConstraintTarget *ct;
389                                         
390                                         if (cti && cti->get_constraint_targets) {
391                                                 cti->get_constraint_targets(con, &targets);
392                                                 
393                                                 for (ct= targets.first; ct; ct= ct->next) {
394                                                         if (ct->tar && ct->tar != ob) {
395                                                                 // fprintf(stderr,"armature %s target :%s \n", ob->id.name, target->id.name);
396                                                                 node3 = dag_get_node(dag, ct->tar);
397                                                                 
398                                                                 if (ct->subtarget[0])
399                                                                         dag_add_relation(dag,node3,node, DAG_RL_OB_DATA|DAG_RL_DATA_DATA, cti->name);
400                                                                 else if(ELEM3(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO, CONSTRAINT_TYPE_SPLINEIK))        
401                                                                         dag_add_relation(dag,node3,node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, cti->name);
402                                                                 else
403                                                                         dag_add_relation(dag,node3,node, DAG_RL_OB_DATA, cti->name);
404                                                         }
405                                                 }
406                                                 
407                                                 if (cti->flush_constraint_targets)
408                                                         cti->flush_constraint_targets(con, &targets, 1);
409                                         }
410                                         
411                                 }
412                         }
413                 }
414         }
415         
416         /* driver dependencies, nla modifiers */
417 #if 0 // XXX old animation system
418         if(ob->nlastrips.first) {
419                 bActionStrip *strip;
420                 bActionChannel *chan;
421                 for(strip= ob->nlastrips.first; strip; strip= strip->next) {
422                         if(strip->modifiers.first) {
423                                 bActionModifier *amod;
424                                 for(amod= strip->modifiers.first; amod; amod= amod->next) {
425                                         if(amod->ob) {
426                                                 node2 = dag_get_node(dag, amod->ob);
427                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "NLA Strip Modifier");
428                                         }
429                                 }
430                         }
431                 }
432         }
433 #endif // XXX old animation system
434         if (ob->adt)
435                 dag_add_driver_relation(ob->adt, dag, node, (ob->type == OB_ARMATURE)); // XXX isdata arg here doesn't give an accurate picture of situation
436                 
437         key= ob_get_key(ob);
438         if (key && key->adt)
439                 dag_add_driver_relation(key->adt, dag, node, 1);
440
441         if (ob->modifiers.first) {
442                 ModifierData *md;
443                 
444                 for(md=ob->modifiers.first; md; md=md->next) {
445                         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
446                         
447                         if (mti->updateDepgraph) mti->updateDepgraph(md, dag, scene, ob, node);
448                 }
449         }
450         if (ob->parent) {
451                 node2 = dag_get_node(dag,ob->parent);
452                 
453                 switch(ob->partype) {
454                         case PARSKEL:
455                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Parent");
456                                 break;
457                         case PARVERT1: case PARVERT3:
458                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Vertex Parent");
459                                 node2->customdata_mask |= CD_MASK_ORIGINDEX;
460                                 break;
461                         case PARBONE:
462                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Bone Parent");
463                                 break;
464                         default:
465                                 if(ob->parent->type==OB_LATTICE) 
466                                         dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Lattice Parent");
467                                 else if(ob->parent->type==OB_CURVE) {
468                                         Curve *cu= ob->parent->data;
469                                         if(cu->flag & CU_PATH) 
470                                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Curve Parent");
471                                         else
472                                                 dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Curve Parent");
473                                 }
474                                 else
475                                         dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Parent");
476                 }
477                 /* exception case: parent is duplivert */
478                 if(ob->type==OB_MBALL && (ob->parent->transflag & OB_DUPLIVERTS)) {
479                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Duplivert");
480                 }
481                 
482                 addtoroot = 0;
483         }
484         if (ob->proxy) {
485                 node2 = dag_get_node(dag, ob->proxy);
486                 dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Proxy");
487                 /* inverted relation, so addtoroot shouldn't be set to zero */
488         }
489         
490         if (ob->transflag & OB_DUPLI) {
491                 if((ob->transflag & OB_DUPLIGROUP) && ob->dup_group) {
492                         GroupObject *go;
493                         for(go= ob->dup_group->gobject.first; go; go= go->next) {
494                                 if(go->ob) {
495                                         node2 = dag_get_node(dag, go->ob);
496                                         /* node2 changes node1, this keeps animations updated in groups?? not logical? */
497                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Dupligroup");
498                                 }
499                         }
500                 }
501         }
502
503         /* softbody collision  */
504         if ((ob->type==OB_MESH) || (ob->type==OB_CURVE) || (ob->type==OB_LATTICE)) {
505                 if(modifiers_isSoftbodyEnabled(ob) || modifiers_isClothEnabled(ob) || ob->particlesystem.first)
506                         dag_add_collision_field_relation(dag, scene, ob, node); /* TODO: use effectorweight->group */
507         }
508         
509         /* object data drivers */
510         if (ob->data) {
511                 AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
512                 if (adt)
513                         dag_add_driver_relation(adt, dag, node, 1);
514         }
515         
516         /* object type/data relationships */
517         switch (ob->type) {
518                 case OB_CAMERA:
519                 {
520                         Camera *cam = (Camera *)ob->data;
521                         
522                         if (cam->dof_ob) {
523                                 node2 = dag_get_node(dag, cam->dof_ob);
524                                 dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Camera DoF");
525                         }
526                 }
527                         break;
528                 case OB_MBALL: 
529                 {
530                         Object *mom= find_basis_mball(scene, ob);
531                         
532                         if(mom!=ob) {
533                                 node2 = dag_get_node(dag, mom);
534                                 dag_add_relation(dag,node,node2,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Metaball");  // mom depends on children!
535                         }
536                 }
537                         break;
538                 case OB_CURVE:
539                 {
540                         Curve *cu= ob->data;
541                         
542                         if(cu->bevobj) {
543                                 node2 = dag_get_node(dag, cu->bevobj);
544                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Curve Bevel");
545                         }
546                         if(cu->taperobj) {
547                                 node2 = dag_get_node(dag, cu->taperobj);
548                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Curve Taper");
549                         }
550                 }
551                         break;
552                 case OB_FONT: 
553                 {
554                         Curve *cu= ob->data;
555                         
556                         if(cu->textoncurve) {
557                                 node2 = dag_get_node(dag, cu->textoncurve);
558                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Texture On Curve");
559                         }
560                 }
561                         break;
562         }
563         
564         /* particles */
565         psys= ob->particlesystem.first;
566         if(psys) {
567                 GroupObject *go;
568
569                 for(; psys; psys=psys->next) {
570                         BoidRule *rule = NULL;
571                         BoidState *state = NULL;
572                         ParticleSettings *part= psys->part;
573                         ListBase *effectors = NULL;
574                         EffectorCache *eff;
575
576                         dag_add_relation(dag, node, node, DAG_RL_OB_DATA, "Particle-Object Relation");
577
578                         if(!psys_check_enabled(ob, psys))
579                                 continue;
580
581                         if(ELEM(part->phystype,PART_PHYS_KEYED,PART_PHYS_BOIDS)) {
582                                 ParticleTarget *pt = psys->targets.first;
583
584                                 for(; pt; pt=pt->next) {
585                                         if(pt->ob && BLI_findlink(&pt->ob->particlesystem, pt->psys-1)) {
586                                                 node2 = dag_get_node(dag, pt->ob);
587                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Particle Targets");
588                                         }
589                            }
590                         }
591
592                         if(part->ren_as == PART_DRAW_OB && part->dup_ob) {
593                                 node2 = dag_get_node(dag, part->dup_ob);
594                                 dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Particle Object Visualisation");
595                                 if(part->dup_ob->type == OB_MBALL)
596                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA, "Particle Object Visualisation");
597                         }
598
599                         if(part->ren_as == PART_DRAW_GR && part->dup_group) {
600                                 for(go=part->dup_group->gobject.first; go; go=go->next) {
601                                         node2 = dag_get_node(dag, go->ob);
602                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Particle Group Visualisation");
603                                 }
604                         }
605
606                         effectors = pdInitEffectors(scene, ob, psys, part->effector_weights);
607
608                         if(effectors) for(eff = effectors->first; eff; eff=eff->next) {
609                                 if(eff->psys) {
610                                         node2 = dag_get_node(dag, eff->ob);
611                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Particle Field");
612                                 }
613                         }
614
615                         pdEndEffectors(&effectors);
616
617                         if(part->boids) {
618                                 for(state = part->boids->states.first; state; state=state->next) {
619                                         for(rule = state->rules.first; rule; rule=rule->next) {
620                                                 Object *ruleob = NULL;
621                                                 if(rule->type==eBoidRuleType_Avoid)
622                                                         ruleob = ((BoidRuleGoalAvoid*)rule)->ob;
623                                                 else if(rule->type==eBoidRuleType_FollowLeader)
624                                                         ruleob = ((BoidRuleFollowLeader*)rule)->ob;
625
626                                                 if(ruleob) {
627                                                         node2 = dag_get_node(dag, ruleob);
628                                                         dag_add_relation(dag, node2, node, DAG_RL_OB_DATA, "Boid Rule");
629                                                 }
630                                         }
631                                 }
632                         }
633                 }
634         }
635         
636         /* object constraints */
637         for (con = ob->constraints.first; con; con=con->next) {
638                 bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
639                 ListBase targets = {NULL, NULL};
640                 bConstraintTarget *ct;
641                 
642                 if (cti && cti->get_constraint_targets) {
643                         cti->get_constraint_targets(con, &targets);
644                         
645                         for (ct= targets.first; ct; ct= ct->next) {
646                                 Object *obt;
647                                 
648                                 if (ct->tar)
649                                         obt= ct->tar;
650                                 else
651                                         continue;
652                                 
653                                 node2 = dag_get_node(dag, obt);
654                                 if (ELEM(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO))
655                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name);
656                                 else {
657                                         if (ELEM3(obt->type, OB_ARMATURE, OB_MESH, OB_LATTICE) && (ct->subtarget[0])) {
658                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name);
659                                                 if (obt->type == OB_MESH)
660                                                         node2->customdata_mask |= CD_MASK_MDEFORMVERT;
661                                         }
662                                         else
663                                                 dag_add_relation(dag, node2, node, DAG_RL_OB_OB, cti->name);
664                                 }
665                                 addtoroot = 0;
666                         }
667                         
668                         if (cti->flush_constraint_targets)
669                                 cti->flush_constraint_targets(con, &targets, 1);
670                 }
671         }
672
673         if (addtoroot == 1 )
674                 dag_add_relation(dag,scenenode,node,DAG_RL_SCENE, "Scene Relation");
675 }
676
677 struct DagForest *build_dag(Main *bmain, Scene *sce, short mask) 
678 {
679         Base *base;
680         Object *ob;
681         Group *group;
682         GroupObject *go;
683         DagNode *node;
684         DagNode *scenenode;
685         DagForest *dag;
686         DagAdjList *itA;
687
688         dag = sce->theDag;
689         sce->dagisvalid=1;
690         if ( dag)
691                 free_forest( dag ); 
692         else {
693                 dag = dag_init();
694                 sce->theDag = dag;
695         }
696         
697         /* add base node for scene. scene is always the first node in DAG */
698         scenenode = dag_add_node(dag, sce);     
699         
700         /* add current scene objects */
701         for(base = sce->base.first; base; base= base->next) {
702                 ob= base->object;
703                 
704                 build_dag_object(dag, scenenode, sce, ob, mask);
705                 if(ob->proxy)
706                         build_dag_object(dag, scenenode, sce, ob->proxy, mask);
707                 
708                 /* handled in next loop */
709                 if(ob->dup_group) 
710                         ob->dup_group->id.flag |= LIB_DOIT;
711         }
712         
713         /* add groups used in current scene objects */
714         for(group= bmain->group.first; group; group= group->id.next) {
715                 if(group->id.flag & LIB_DOIT) {
716                         for(go= group->gobject.first; go; go= go->next) {
717                                 build_dag_object(dag, scenenode, sce, go->ob, mask);
718                         }
719                         group->id.flag &= ~LIB_DOIT;
720                 }
721         }
722         
723         /* Now all relations were built, but we need to solve 1 exceptional case;
724            When objects have multiple "parents" (for example parent + constraint working on same object)
725            the relation type has to be synced. One of the parents can change, and should give same event to child */
726         
727         /* nodes were callocced, so we can use node->color for temporal storage */
728         for(node = sce->theDag->DagNode.first; node; node= node->next) {
729                 if(node->type==ID_OB) {
730                         for(itA = node->child; itA; itA= itA->next) {
731                                 if(itA->node->type==ID_OB) {
732                                         itA->node->color |= itA->type;
733                                 }
734                         }
735
736                         /* also flush custom data mask */
737                         ((Object*)node->ob)->customdata_mask= node->customdata_mask;
738                 }
739         }
740         /* now set relations equal, so that when only one parent changes, the correct recalcs are found */
741         for(node = sce->theDag->DagNode.first; node; node= node->next) {
742                 if(node->type==ID_OB) {
743                         for(itA = node->child; itA; itA= itA->next) {
744                                 if(itA->node->type==ID_OB) {
745                                         itA->type |= itA->node->color;
746                                 }
747                         }
748                 }
749         }
750         
751         // cycle detection and solving
752         // solve_cycles(dag);   
753         
754         return dag;
755 }
756
757
758 void free_forest(DagForest *Dag) 
759 {  /* remove all nodes and deps */
760         DagNode *tempN;
761         DagAdjList *tempA;      
762         DagAdjList *itA;
763         DagNode *itN = Dag->DagNode.first;
764         
765         while (itN) {
766                 itA = itN->child;       
767                 while (itA) {
768                         tempA = itA;
769                         itA = itA->next;
770                         MEM_freeN(tempA);                       
771                 }
772                 
773                 itA = itN->parent;      
774                 while (itA) {
775                         tempA = itA;
776                         itA = itA->next;
777                         MEM_freeN(tempA);                       
778                 }
779                 
780                 tempN = itN;
781                 itN = itN->next;
782                 MEM_freeN(tempN);
783         }
784
785         BLI_ghash_free(Dag->nodeHash, NULL, NULL);
786         Dag->nodeHash= NULL;
787         Dag->DagNode.first = NULL;
788         Dag->DagNode.last = NULL;
789         Dag->numNodes = 0;
790
791 }
792
793 DagNode * dag_find_node (DagForest *forest,void * fob)
794 {
795         if(forest->nodeHash)
796                 return BLI_ghash_lookup(forest->nodeHash, fob);
797
798         return NULL;
799 }
800
801 static int ugly_hack_sorry= 1;  // prevent type check
802
803 /* no checking of existence, use dag_find_node first or dag_get_node */
804 DagNode * dag_add_node (DagForest *forest, void * fob)
805 {
806         DagNode *node;
807                 
808         node = MEM_callocN(sizeof(DagNode),"DAG node");
809         if (node) {
810                 node->ob = fob;
811                 node->color = DAG_WHITE;
812
813                 if(ugly_hack_sorry) node->type = GS(((ID *) fob)->name);        // sorry, done for pose sorting
814                 if (forest->numNodes) {
815                         ((DagNode *) forest->DagNode.last)->next = node;
816                         forest->DagNode.last = node;
817                         forest->numNodes++;
818                 } else {
819                         forest->DagNode.last = node;
820                         forest->DagNode.first = node;
821                         forest->numNodes = 1;
822                 }
823
824                 if(!forest->nodeHash)
825                         forest->nodeHash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "dag_add_node gh");
826                 BLI_ghash_insert(forest->nodeHash, fob, node);
827         }
828
829         return node;
830 }
831
832 DagNode * dag_get_node (DagForest *forest,void * fob)
833 {
834         DagNode *node;
835         
836         node = dag_find_node (forest, fob);     
837         if (!node) 
838                 node = dag_add_node(forest, fob);
839         return node;
840 }
841
842
843
844 DagNode * dag_get_sub_node (DagForest *forest,void * fob)
845 {
846         DagNode *node;
847         DagAdjList *mainchild, *prev=NULL;
848         
849         mainchild = ((DagNode *) forest->DagNode.first)->child;
850         /* remove from first node (scene) adj list if present */
851         while (mainchild) {
852                 if (mainchild->node == fob) {
853                         if (prev) {
854                                 prev->next = mainchild->next;
855                                 MEM_freeN(mainchild);
856                                 break;
857                         } else {
858                                 ((DagNode *) forest->DagNode.first)->child = mainchild->next;
859                                 MEM_freeN(mainchild);
860                                 break;
861                         }
862                 }
863                 prev = mainchild;
864                 mainchild = mainchild->next;
865         }
866         node = dag_find_node (forest, fob);     
867         if (!node) 
868                 node = dag_add_node(forest, fob);
869         return node;
870 }
871
872 static void dag_add_parent_relation(DagForest *UNUSED(forest), DagNode *fob1, DagNode *fob2, short rel, const char *name) 
873 {
874         DagAdjList *itA = fob2->parent;
875         
876         while (itA) { /* search if relation exist already */
877                 if (itA->node == fob1) {
878                         itA->type |= rel;
879                         itA->count += 1;
880                         return;
881                 }
882                 itA = itA->next;
883         }
884         /* create new relation and insert at head. MALLOC alert! */
885         itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
886         itA->node = fob1;
887         itA->type = rel;
888         itA->count = 1;
889         itA->next = fob2->parent;
890         itA->name = name;
891         fob2->parent = itA;
892 }
893
894 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel, const char *name) 
895 {
896         DagAdjList *itA = fob1->child;
897         
898         /* parent relation is for cycle checking */
899         dag_add_parent_relation(forest, fob1, fob2, rel, name);
900
901         while (itA) { /* search if relation exist already */
902                 if (itA->node == fob2) {
903                         itA->type |= rel;
904                         itA->count += 1;
905                         return;
906                 }
907                 itA = itA->next;
908         }
909         /* create new relation and insert at head. MALLOC alert! */
910         itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
911         itA->node = fob2;
912         itA->type = rel;
913         itA->count = 1;
914         itA->next = fob1->child;
915         itA->name = name;
916         fob1->child = itA;
917 }
918
919 static const char *dag_node_name(DagNode *node)
920 {
921         if(node->ob == NULL)
922                 return "null";
923         else if(ugly_hack_sorry)
924                 return ((ID*)(node->ob))->name+2;
925         else
926                 return ((bPoseChannel*)(node->ob))->name;
927 }
928
929 #if 0
930 static void dag_node_print_dependencies(DagNode *node)
931 {
932         DagAdjList *itA;
933
934         printf("%s depends on:\n", dag_node_name(node));
935
936         for(itA= node->parent; itA; itA= itA->next)
937                 printf("  %s through %s\n", dag_node_name(itA->node), itA->name);
938         printf("\n");
939 }
940 #endif
941
942 static int dag_node_print_dependency_recurs(DagNode *node, DagNode *endnode)
943 {
944         DagAdjList *itA;
945
946         if(node->color == DAG_BLACK)
947                 return 0;
948
949         node->color= DAG_BLACK;
950
951         if(node == endnode)
952                 return 1;
953
954         for(itA= node->parent; itA; itA= itA->next) {
955                 if(dag_node_print_dependency_recurs(itA->node, endnode)) {
956                         printf("  %s depends on %s through %s.\n", dag_node_name(node), dag_node_name(itA->node), itA->name);
957                         return 1;
958                 }
959         }
960
961         return 0;
962 }
963
964 static void dag_node_print_dependency_cycle(DagForest *dag, DagNode *startnode, DagNode *endnode, const char *name)
965 {
966         DagNode *node;
967
968         for(node = dag->DagNode.first; node; node= node->next)
969                 node->color= DAG_WHITE;
970
971         printf("  %s depends on %s through %s.\n", dag_node_name(endnode), dag_node_name(startnode), name);
972         dag_node_print_dependency_recurs(startnode, endnode);
973         printf("\n");
974 }
975
976 static int dag_node_recurs_level(DagNode *node, int level)
977 {
978         DagAdjList *itA;
979         int newlevel;
980
981         node->color= DAG_BLACK; /* done */
982         newlevel= ++level;
983         
984         for(itA= node->parent; itA; itA= itA->next) {
985                 if(itA->node->color==DAG_WHITE) {
986                         itA->node->ancestor_count= dag_node_recurs_level(itA->node, level);
987                         newlevel= MAX2(newlevel, level+itA->node->ancestor_count);
988                 }
989                 else
990                         newlevel= MAX2(newlevel, level+itA->node->ancestor_count);
991         }
992         
993         return newlevel;
994 }
995
996 static void dag_check_cycle(DagForest *dag)
997 {
998         DagNode *node;
999         DagAdjList *itA;
1000
1001         /* tag nodes unchecked */
1002         for(node = dag->DagNode.first; node; node= node->next)
1003                 node->color= DAG_WHITE;
1004         
1005         for(node = dag->DagNode.first; node; node= node->next) {
1006                 if(node->color==DAG_WHITE) {
1007                         node->ancestor_count= dag_node_recurs_level(node, 0);
1008                 }
1009         }
1010         
1011         /* check relations, and print errors */
1012         for(node = dag->DagNode.first; node; node= node->next) {
1013                 for(itA= node->parent; itA; itA= itA->next) {
1014                         if(itA->node->ancestor_count > node->ancestor_count) {
1015                                 if(node->ob && itA->node->ob) {
1016                                         printf("Dependency cycle detected:\n");
1017                                         dag_node_print_dependency_cycle(dag, itA->node, node, itA->name);
1018                                 }
1019                         }
1020                 }
1021         }
1022
1023         /* parent relations are only needed for cycle checking, so free now */
1024         for(node = dag->DagNode.first; node; node= node->next) {
1025                 while (node->parent) {
1026                         itA = node->parent->next;
1027                         MEM_freeN(node->parent);                        
1028                         node->parent = itA;
1029                 }
1030         }
1031 }
1032
1033 /*
1034  * MainDAG is the DAG of all objects in current scene
1035  * used only for drawing there is one also in each scene
1036  */
1037 static DagForest * MainDag = NULL;
1038
1039 DagForest *getMainDag(void)
1040 {
1041         return MainDag;
1042 }
1043
1044
1045 void setMainDag(DagForest *dag)
1046 {
1047         MainDag = dag;
1048 }
1049
1050
1051 /*
1052  * note for BFS/DFS
1053  * in theory we should sweep the whole array
1054  * but in our case the first node is the scene
1055  * and is linked to every other object
1056  *
1057  * for general case we will need to add outer loop
1058  */
1059
1060 /*
1061  * ToDo : change pos kludge
1062  */
1063
1064 /* adjust levels for drawing in oops space */
1065 void graph_bfs(void)
1066 {
1067         DagNode *node;
1068         DagNodeQueue *nqueue;
1069         int pos[50];
1070         int i;
1071         DagAdjList *itA;
1072         int minheight;
1073         
1074         /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
1075         nqueue = queue_create(DAGQUEUEALLOC);
1076         for ( i=0; i<50; i++)
1077                 pos[i] = 0;
1078         
1079         /* Init
1080          * dagnode.first is alway the root (scene) 
1081          */
1082         node = MainDag->DagNode.first;
1083         while(node) {
1084                 node->color = DAG_WHITE;
1085                 node->BFS_dist = 9999;
1086                 node->k = 0;
1087                 node = node->next;
1088         }
1089         
1090         node = MainDag->DagNode.first;
1091         if (node->color == DAG_WHITE) {
1092                 node->color = DAG_GRAY;
1093                 node->BFS_dist = 1;
1094                 push_queue(nqueue,node);  
1095                 while(nqueue->count) {
1096                         node = pop_queue(nqueue);
1097                         
1098                         minheight = pos[node->BFS_dist];
1099                         itA = node->child;
1100                         while(itA != NULL) {
1101                                 if(itA->node->color == DAG_WHITE) {
1102                                         itA->node->color = DAG_GRAY;
1103                                         itA->node->BFS_dist = node->BFS_dist + 1;
1104                                         itA->node->k = (float) minheight;
1105                                         push_queue(nqueue,itA->node);
1106                                 }
1107                                 
1108                                 else {
1109                                         fprintf(stderr,"bfs not dag tree edge color :%i \n",itA->node->color);
1110                                 }
1111
1112                                 
1113                                 itA = itA->next;
1114                         }
1115                         if (pos[node->BFS_dist] > node->k ) {
1116                                 pos[node->BFS_dist] += 1;                               
1117                                 node->k = (float) pos[node->BFS_dist];
1118                         } else {
1119                                 pos[node->BFS_dist] = (int) node->k +1;
1120                         }
1121                         set_node_xy(node, node->BFS_dist*DEPSX*2, pos[node->BFS_dist]*DEPSY*2);
1122                         node->color = DAG_BLACK;
1123                         /*
1124                          fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
1125                          */
1126                 }
1127         }
1128         queue_delete(nqueue);
1129 }
1130
1131 int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
1132         DagNode *node;
1133         
1134         node = dag->DagNode.first;
1135         return pre_and_post_source_BFS(dag, mask,  node,  pre_func,  post_func, data);
1136 }
1137
1138
1139 int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
1140 {
1141         DagNode *node;
1142         DagNodeQueue *nqueue;
1143         DagAdjList *itA;
1144         int     retval = 0;
1145         /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
1146         
1147         /* Init
1148                 * dagnode.first is alway the root (scene) 
1149                 */
1150         node = dag->DagNode.first;
1151         nqueue = queue_create(DAGQUEUEALLOC);
1152         while(node) {
1153                 node->color = DAG_WHITE;
1154                 node->BFS_dist = 9999;
1155                 node = node->next;
1156         }
1157         
1158         node = source;
1159         if (node->color == DAG_WHITE) {
1160                 node->color = DAG_GRAY;
1161                 node->BFS_dist = 1;
1162                 pre_func(node->ob,data);
1163                 
1164                 while(nqueue->count) {
1165                         node = pop_queue(nqueue);
1166                         
1167                         itA = node->child;
1168                         while(itA != NULL) {
1169                                 if((itA->node->color == DAG_WHITE) && (itA->type & mask)) {
1170                                         itA->node->color = DAG_GRAY;
1171                                         itA->node->BFS_dist = node->BFS_dist + 1;
1172                                         push_queue(nqueue,itA->node);
1173                                         pre_func(node->ob,data);
1174                                 }
1175                                 
1176                                 else { // back or cross edge
1177                                         retval = 1;
1178                                 }
1179                                 itA = itA->next;
1180                         }
1181                         post_func(node->ob,data);
1182                         node->color = DAG_BLACK;
1183                         /*
1184                          fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
1185                          */
1186                 }
1187         }
1188         queue_delete(nqueue);
1189         return retval;
1190 }
1191
1192 /* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/
1193 DagNodeQueue * graph_dfs(void)
1194 {
1195         DagNode *node;
1196         DagNodeQueue *nqueue;
1197         DagNodeQueue *retqueue;
1198         int pos[50];
1199         int i;
1200         DagAdjList *itA;
1201         int time;
1202         int skip = 0;
1203         int minheight;
1204         int maxpos=0;
1205         /* int  is_cycle = 0; */ /* UNUSED */
1206         /*
1207          *fprintf(stderr,"starting DFS \n ------------\n");
1208          */     
1209         nqueue = queue_create(DAGQUEUEALLOC);
1210         retqueue = queue_create(MainDag->numNodes);
1211         for ( i=0; i<50; i++)
1212                 pos[i] = 0;
1213         
1214         /* Init
1215          * dagnode.first is alway the root (scene) 
1216          */
1217         node = MainDag->DagNode.first;
1218         while(node) {
1219                 node->color = DAG_WHITE;
1220                 node->DFS_dist = 9999;
1221                 node->DFS_dvtm = node->DFS_fntm = 9999;
1222                 node->k = 0;
1223                 node =  node->next;
1224         }
1225         
1226         time = 1;
1227         
1228         node = MainDag->DagNode.first;
1229
1230         do {
1231         if (node->color == DAG_WHITE) {
1232                 node->color = DAG_GRAY;
1233                 node->DFS_dist = 1;
1234                 node->DFS_dvtm = time;
1235                 time++;
1236                 push_stack(nqueue,node);  
1237                         
1238                 while(nqueue->count) {
1239                         //graph_print_queue(nqueue);
1240
1241                         skip = 0;
1242                         node = get_top_node_queue(nqueue);
1243                         
1244                         minheight = pos[node->DFS_dist];
1245
1246                         itA = node->child;
1247                         while(itA != NULL) {
1248                                 if(itA->node->color == DAG_WHITE) {
1249                                         itA->node->DFS_dvtm = time;
1250                                         itA->node->color = DAG_GRAY;
1251
1252                                         time++;
1253                                         itA->node->DFS_dist = node->DFS_dist + 1;
1254                                         itA->node->k = (float) minheight;
1255                                         push_stack(nqueue,itA->node);
1256                                         skip = 1;
1257                                         break;
1258                                 } else { 
1259                                         if (itA->node->color == DAG_GRAY) { // back edge
1260                                                 fprintf(stderr,"dfs back edge :%15s %15s \n",((ID *) node->ob)->name, ((ID *) itA->node->ob)->name);
1261                                                 /* is_cycle = 1; */ /* UNUSED */
1262                                         } else if (itA->node->color == DAG_BLACK) {
1263                                                 ;
1264                                                 /* already processed node but we may want later to change distance either to shorter to longer.
1265                                                  * DFS_dist is the first encounter  
1266                                                 */
1267                                                 /*if (node->DFS_dist >= itA->node->DFS_dist)
1268                                                         itA->node->DFS_dist = node->DFS_dist + 1;
1269
1270                                                         fprintf(stderr,"dfs forward or cross edge :%15s %i-%i %15s %i-%i \n",
1271                                                                 ((ID *) node->ob)->name,
1272                                                                 node->DFS_dvtm, 
1273                                                                 node->DFS_fntm, 
1274                                                                 ((ID *) itA->node->ob)->name, 
1275                                                                 itA->node->DFS_dvtm,
1276                                                                 itA->node->DFS_fntm);
1277                                         */
1278                                         } else 
1279                                                 fprintf(stderr,"dfs unknown edge \n");
1280                                 }
1281                                 itA = itA->next;
1282                         }                       
1283
1284                         if (!skip) {
1285                                 node = pop_queue(nqueue);
1286                                 node->color = DAG_BLACK;
1287
1288                                 node->DFS_fntm = time;
1289                                 time++;
1290                                 if (node->DFS_dist > maxpos)
1291                                         maxpos = node->DFS_dist;
1292                                 if (pos[node->DFS_dist] > node->k ) {
1293                                         pos[node->DFS_dist] += 1;                               
1294                                         node->k = (float) pos[node->DFS_dist];
1295                                 } else {
1296                                         pos[node->DFS_dist] = (int) node->k +1;
1297                                 }
1298                                 set_node_xy(node, node->DFS_dist*DEPSX*2, pos[node->DFS_dist]*DEPSY*2);
1299                                 
1300                                 /*
1301                                  fprintf(stderr,"DFS node : %20s %i %i %i %i\n",((ID *) node->ob)->name,node->BFS_dist, node->DFS_dist, node->DFS_dvtm, node->DFS_fntm );       
1302                                 */
1303                                 push_stack(retqueue,node);
1304                                 
1305                         }
1306                 }
1307         }
1308                 node = node->next;
1309         } while (node);
1310 //      fprintf(stderr,"i size : %i \n", maxpos);
1311
1312         queue_delete(nqueue);
1313         return(retqueue);
1314 }
1315
1316 /* unused */
1317 int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
1318         DagNode *node;
1319
1320         node = dag->DagNode.first;
1321         return pre_and_post_source_DFS(dag, mask,  node,  pre_func,  post_func, data);
1322 }
1323
1324 int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
1325 {
1326         DagNode *node;
1327         DagNodeQueue *nqueue;
1328         DagAdjList *itA;
1329         int time;
1330         int skip = 0;
1331         int retval = 0;
1332         /*
1333          *fprintf(stderr,"starting DFS \n ------------\n");
1334          */     
1335         nqueue = queue_create(DAGQUEUEALLOC);
1336         
1337         /* Init
1338                 * dagnode.first is alway the root (scene) 
1339                 */
1340         node = dag->DagNode.first;
1341         while(node) {
1342                 node->color = DAG_WHITE;
1343                 node->DFS_dist = 9999;
1344                 node->DFS_dvtm = node->DFS_fntm = 9999;
1345                 node->k = 0;
1346                 node =  node->next;
1347         }
1348         
1349         time = 1;
1350         
1351         node = source;
1352         do {
1353                 if (node->color == DAG_WHITE) {
1354                         node->color = DAG_GRAY;
1355                         node->DFS_dist = 1;
1356                         node->DFS_dvtm = time;
1357                         time++;
1358                         push_stack(nqueue,node);  
1359                         pre_func(node->ob,data);
1360
1361                         while(nqueue->count) {
1362                                 skip = 0;
1363                                 node = get_top_node_queue(nqueue);
1364                                                                 
1365                                 itA = node->child;
1366                                 while(itA != NULL) {
1367                                         if((itA->node->color == DAG_WHITE) && (itA->type & mask) ) {
1368                                                 itA->node->DFS_dvtm = time;
1369                                                 itA->node->color = DAG_GRAY;
1370                                                 
1371                                                 time++;
1372                                                 itA->node->DFS_dist = node->DFS_dist + 1;
1373                                                 push_stack(nqueue,itA->node);
1374                                                 pre_func(node->ob,data);
1375
1376                                                 skip = 1;
1377                                                 break;
1378                                         } else {
1379                                                 if (itA->node->color == DAG_GRAY) {// back edge
1380                                                         retval = 1;
1381                                                 }
1382 //                                              else if (itA->node->color == DAG_BLACK) { // cross or forward
1383 //                                                      ;
1384                                         }
1385                                         itA = itA->next;
1386                                 }                       
1387                                 
1388                                 if (!skip) {
1389                                         node = pop_queue(nqueue);
1390                                         node->color = DAG_BLACK;
1391                                         
1392                                         node->DFS_fntm = time;
1393                                         time++;
1394                                         post_func(node->ob,data);
1395                                 }
1396                         }
1397                 }
1398                 node = node->next;
1399         } while (node);
1400         queue_delete(nqueue);
1401         return(retval);
1402 }
1403
1404
1405 // used to get the obs owning a datablock
1406 struct DagNodeQueue *get_obparents(struct DagForest     *dag, void *ob) 
1407 {
1408         DagNode * node, *node1;
1409         DagNodeQueue *nqueue;
1410         DagAdjList *itA;
1411
1412         node = dag_find_node(dag,ob);
1413         if(node==NULL) {
1414                 return NULL;
1415         }
1416         else if (node->ancestor_count == 1) { // simple case
1417                 nqueue = queue_create(1);
1418                 push_queue(nqueue,node);
1419         } else {        // need to go over the whole dag for adj list
1420                 nqueue = queue_create(node->ancestor_count);
1421                 
1422                 node1 = dag->DagNode.first;
1423                 do {
1424                         if (node1->DFS_fntm > node->DFS_fntm) { // a parent is finished after child. must check adj list
1425                                 itA = node->child;
1426                                 while(itA != NULL) {
1427                                         if ((itA->node == node) && (itA->type == DAG_RL_DATA)) {
1428                                                 push_queue(nqueue,node);
1429                                         }
1430                                         itA = itA->next;
1431                                 }
1432                         }
1433                         node1 = node1->next;
1434                 } while (node1);
1435         }
1436         return nqueue;
1437 }
1438
1439 struct DagNodeQueue *get_first_ancestors(struct DagForest       *dag, void *ob)
1440 {
1441         DagNode * node, *node1;
1442         DagNodeQueue *nqueue;
1443         DagAdjList *itA;
1444         
1445         node = dag_find_node(dag,ob);
1446         
1447         // need to go over the whole dag for adj list
1448         nqueue = queue_create(node->ancestor_count);
1449         
1450         node1 = dag->DagNode.first;
1451         do {
1452                 if (node1->DFS_fntm > node->DFS_fntm) { 
1453                         itA = node->child;
1454                         while(itA != NULL) {
1455                                 if (itA->node == node) {
1456                                         push_queue(nqueue,node);
1457                                 }
1458                                 itA = itA->next;
1459                         }
1460                 }
1461                 node1 = node1->next;
1462         } while (node1);
1463         
1464         return nqueue;  
1465 }
1466
1467 // standard DFS list
1468 struct DagNodeQueue *get_all_childs(struct DagForest    *dag, void *ob)
1469 {
1470         DagNode *node;
1471         DagNodeQueue *nqueue;
1472         DagNodeQueue *retqueue;
1473         DagAdjList *itA;
1474         int time;
1475         int skip = 0;
1476
1477         nqueue = queue_create(DAGQUEUEALLOC);
1478         retqueue = queue_create(dag->numNodes); // was MainDag... why? (ton)
1479         
1480         node = dag->DagNode.first;
1481         while(node) {
1482                 node->color = DAG_WHITE;
1483                 node =  node->next;
1484         }
1485         
1486         time = 1;
1487         
1488         node = dag_find_node(dag, ob);   // could be done in loop above (ton)
1489         if(node) { // can be null for newly added objects
1490                 
1491                 node->color = DAG_GRAY;
1492                 time++;
1493                 push_stack(nqueue,node);  
1494                 
1495                 while(nqueue->count) {
1496                         
1497                         skip = 0;
1498                         node = get_top_node_queue(nqueue);
1499                                         
1500                         itA = node->child;
1501                         while(itA != NULL) {
1502                                 if(itA->node->color == DAG_WHITE) {
1503                                         itA->node->DFS_dvtm = time;
1504                                         itA->node->color = DAG_GRAY;
1505                                         
1506                                         time++;
1507                                         push_stack(nqueue,itA->node);
1508                                         skip = 1;
1509                                         break;
1510                                 } 
1511                                 itA = itA->next;
1512                         }                       
1513                         
1514                         if (!skip) {
1515                                 node = pop_queue(nqueue);
1516                                 node->color = DAG_BLACK;
1517                                 
1518                                 time++;
1519                                 push_stack(retqueue,node);                      
1520                         }
1521                 }
1522         }
1523         queue_delete(nqueue);
1524         return(retqueue);
1525 }
1526
1527 /* unused */
1528 short   are_obs_related(struct DagForest        *dag, void *ob1, void *ob2) {
1529         DagNode * node;
1530         DagAdjList *itA;
1531         
1532         node = dag_find_node(dag, ob1);
1533         
1534         itA = node->child;
1535         while(itA != NULL) {
1536                 if(itA->node->ob == ob2) {
1537                         return itA->node->type;
1538                 } 
1539                 itA = itA->next;
1540         }
1541         return DAG_NO_RELATION;
1542 }
1543
1544 int     is_acyclic( DagForest   *dag) {
1545         return dag->is_acyclic;
1546 }
1547
1548 void set_node_xy(DagNode *node, float x, float y)
1549 {
1550          node->x = x;
1551         node->y = y;
1552 }
1553
1554
1555 /* debug test functions */
1556
1557 void graph_print_queue(DagNodeQueue *nqueue)
1558 {       
1559         DagNodeQueueElem *queueElem;
1560         
1561         queueElem = nqueue->first;
1562         while(queueElem) {
1563                 fprintf(stderr,"** %s %i %i-%i ",((ID *) queueElem->node->ob)->name,queueElem->node->color,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
1564                 queueElem = queueElem->next;            
1565         }
1566         fprintf(stderr,"\n");
1567 }
1568
1569 void graph_print_queue_dist(DagNodeQueue *nqueue)
1570 {       
1571         DagNodeQueueElem *queueElem;
1572         int count;
1573         
1574         queueElem = nqueue->first;
1575         count = 0;
1576         while(queueElem) {
1577                 fprintf(stderr,"** %25s %2.2i-%2.2i ",((ID *) queueElem->node->ob)->name,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
1578                 while (count < queueElem->node->DFS_dvtm-1) { fputc(' ',stderr); count++;}
1579                 fputc('|',stderr); 
1580                 while (count < queueElem->node->DFS_fntm-2) { fputc('-',stderr); count++;}
1581                 fputc('|',stderr);
1582                 fputc('\n',stderr);
1583                 count = 0;
1584                 queueElem = queueElem->next;            
1585         }
1586         fprintf(stderr,"\n");
1587 }
1588
1589 void graph_print_adj_list(void)
1590 {
1591         DagNode *node;
1592         DagAdjList *itA;
1593         
1594         node = (getMainDag())->DagNode.first;
1595         while(node) {
1596                 fprintf(stderr,"node : %s col: %i",((ID *) node->ob)->name, node->color);               
1597                 itA = node->child;
1598                 while (itA) {
1599                         fprintf(stderr,"-- %s ",((ID *) itA->node->ob)->name);
1600                         
1601                         itA = itA->next;
1602                 }
1603                 fprintf(stderr,"\n");
1604                 node = node->next;
1605         }
1606 }
1607
1608 /* ************************ API *********************** */
1609
1610 /* mechanism to allow editors to be informed of depsgraph updates,
1611    to do their own updates based on changes... */
1612 static void (*EditorsUpdateCb)(Main *bmain, ID *id)= NULL;
1613
1614 void DAG_editors_update_cb(void (*func)(Main *bmain, ID *id))
1615 {
1616         EditorsUpdateCb= func;
1617 }
1618
1619 static void dag_editors_update(Main *bmain, ID *id)
1620 {
1621         if(EditorsUpdateCb)
1622                 EditorsUpdateCb(bmain, id);
1623 }
1624
1625 /* groups with objects in this scene need to be put in the right order as well */
1626 static void scene_sort_groups(Main *bmain, Scene *sce)
1627 {
1628         Base *base;
1629         Group *group;
1630         GroupObject *go;
1631         Object *ob;
1632         
1633         /* test; are group objects all in this scene? */
1634         for(ob= bmain->object.first; ob; ob= ob->id.next) {
1635                 ob->id.flag &= ~LIB_DOIT;
1636                 ob->id.newid= NULL;     /* newid abuse for GroupObject */
1637         }
1638         for(base = sce->base.first; base; base= base->next)
1639                 base->object->id.flag |= LIB_DOIT;
1640         
1641         for(group= bmain->group.first; group; group= group->id.next) {
1642                 for(go= group->gobject.first; go; go= go->next) {
1643                         if((go->ob->id.flag & LIB_DOIT)==0)
1644                                 break;
1645                 }
1646                 /* this group is entirely in this scene */
1647                 if(go==NULL) {
1648                         ListBase listb= {NULL, NULL};
1649                         
1650                         for(go= group->gobject.first; go; go= go->next)
1651                                 go->ob->id.newid= (ID *)go;
1652                         
1653                         /* in order of sorted bases we reinsert group objects */
1654                         for(base = sce->base.first; base; base= base->next) {
1655                                 
1656                                 if(base->object->id.newid) {
1657                                         go= (GroupObject *)base->object->id.newid;
1658                                         base->object->id.newid= NULL;
1659                                         BLI_remlink( &group->gobject, go);
1660                                         BLI_addtail( &listb, go);
1661                                 }
1662                         }
1663                         /* copy the newly sorted listbase */
1664                         group->gobject= listb;
1665                 }
1666         }
1667 }
1668
1669 /* sort the base list on dependency order */
1670 void DAG_scene_sort(Main *bmain, Scene *sce)
1671 {
1672         DagNode *node;
1673         DagNodeQueue *nqueue;
1674         DagAdjList *itA;
1675         int time;
1676         int skip = 0;
1677         ListBase tempbase;
1678         Base *base;
1679         
1680         tempbase.first= tempbase.last= NULL;
1681         
1682         build_dag(bmain, sce, DAG_RL_ALL_BUT_DATA);
1683         
1684         dag_check_cycle(sce->theDag);
1685
1686         nqueue = queue_create(DAGQUEUEALLOC);
1687         
1688         for(node = sce->theDag->DagNode.first; node; node= node->next) {
1689                 node->color = DAG_WHITE;
1690         }
1691         
1692         time = 1;
1693         
1694         node = sce->theDag->DagNode.first;
1695         
1696         node->color = DAG_GRAY;
1697         time++;
1698         push_stack(nqueue,node);  
1699         
1700         while(nqueue->count) {
1701                 
1702                 skip = 0;
1703                 node = get_top_node_queue(nqueue);
1704                 
1705                 itA = node->child;
1706                 while(itA != NULL) {
1707                         if(itA->node->color == DAG_WHITE) {
1708                                 itA->node->DFS_dvtm = time;
1709                                 itA->node->color = DAG_GRAY;
1710                                 
1711                                 time++;
1712                                 push_stack(nqueue,itA->node);
1713                                 skip = 1;
1714                                 break;
1715                         } 
1716                         itA = itA->next;
1717                 }                       
1718                 
1719                 if (!skip) {
1720                         if (node) {
1721                                 node = pop_queue(nqueue);
1722                                 if (node->ob == sce)    // we are done
1723                                         break ;
1724                                 node->color = DAG_BLACK;
1725                                 
1726                                 time++;
1727                                 base = sce->base.first;
1728                                 while (base && base->object != node->ob)
1729                                         base = base->next;
1730                                 if(base) {
1731                                         BLI_remlink(&sce->base,base);
1732                                         BLI_addhead(&tempbase,base);
1733                                 }
1734                         }       
1735                 }
1736         }
1737         
1738         // temporal correction for circular dependancies
1739         base = sce->base.first;
1740         while (base) {
1741                 BLI_remlink(&sce->base,base);
1742                 BLI_addhead(&tempbase,base);
1743                 //if(G.f & G_DEBUG) 
1744                         printf("cyclic %s\n", base->object->id.name);
1745                 base = sce->base.first;
1746         }
1747         
1748         sce->base = tempbase;
1749         queue_delete(nqueue);
1750         
1751         /* all groups with objects in this scene gets resorted too */
1752         scene_sort_groups(bmain, sce);
1753         
1754         if(G.f & G_DEBUG) {
1755                 printf("\nordered\n");
1756                 for(base = sce->base.first; base; base= base->next) {
1757                         printf(" %s\n", base->object->id.name);
1758                 }
1759         }
1760         /* temporal...? */
1761         sce->recalc |= SCE_PRV_CHANGED; /* test for 3d preview */
1762 }
1763
1764 static void lib_id_recalc_tag(Main *bmain, ID *id)
1765 {
1766         id->flag |= LIB_ID_RECALC;
1767         bmain->id_tag_update[id->name[0]] = 1;
1768 }
1769
1770 static void lib_id_recalc_data_tag(Main *bmain, ID *id)
1771 {
1772         id->flag |= LIB_ID_RECALC_DATA;
1773         bmain->id_tag_update[id->name[0]] = 1;
1774 }
1775
1776 /* node was checked to have lasttime != curtime and is if type ID_OB */
1777 static void flush_update_node(DagNode *node, unsigned int layer, int curtime)
1778 {
1779         Main *bmain= G.main;
1780         DagAdjList *itA;
1781         Object *ob, *obc;
1782         int oldflag, changed=0;
1783         unsigned int all_layer;
1784         
1785         node->lasttime= curtime;
1786         
1787         ob= node->ob;
1788         if(ob && (ob->recalc & OB_RECALC_ALL)) {
1789                 all_layer= node->scelay;
1790
1791                 /* got an object node that changes, now check relations */
1792                 for(itA = node->child; itA; itA= itA->next) {
1793                         all_layer |= itA->lay;
1794                         /* the relationship is visible */
1795                         if((itA->lay & layer)) { // XXX || (itA->node->ob == obedit)
1796                                 if(itA->node->type==ID_OB) {
1797                                         obc= itA->node->ob;
1798                                         oldflag= obc->recalc;
1799                                         
1800                                         /* got a ob->obc relation, now check if flag needs flush */
1801                                         if(ob->recalc & OB_RECALC_OB) {
1802                                                 if(itA->type & DAG_RL_OB_OB) {
1803                                                         //printf("ob %s changes ob %s\n", ob->id.name, obc->id.name);
1804                                                         obc->recalc |= OB_RECALC_OB;
1805                                                         lib_id_recalc_tag(bmain, &obc->id);
1806                                                 }
1807                                                 if(itA->type & DAG_RL_OB_DATA) {
1808                                                         //printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name);
1809                                                         obc->recalc |= OB_RECALC_DATA;
1810                                                         lib_id_recalc_data_tag(bmain, &obc->id);
1811                                                 }
1812                                         }
1813                                         if(ob->recalc & OB_RECALC_DATA) {
1814                                                 if(itA->type & DAG_RL_DATA_OB) {
1815                                                         //printf("obdata %s changes ob %s\n", ob->id.name, obc->id.name);
1816                                                         obc->recalc |= OB_RECALC_OB;
1817                                                         lib_id_recalc_tag(bmain, &obc->id);
1818                                                 }
1819                                                 if(itA->type & DAG_RL_DATA_DATA) {
1820                                                         //printf("obdata %s changes obdata %s\n", ob->id.name, obc->id.name);
1821                                                         obc->recalc |= OB_RECALC_DATA;
1822                                                         lib_id_recalc_data_tag(bmain, &obc->id);
1823                                                 }
1824                                         }
1825                                         if(oldflag!=obc->recalc) changed= 1;
1826                                 }
1827                         }
1828                 }
1829                 /* even nicer, we can clear recalc flags...  */
1830                 if((all_layer & layer)==0) { // XXX && (ob != obedit)) {
1831                         /* but existing displaylists or derivedmesh should be freed */
1832                         if(ob->recalc & OB_RECALC_DATA)
1833                                 object_free_display(ob);
1834                         
1835                         ob->recalc &= ~OB_RECALC_ALL;
1836                 }
1837         }
1838         
1839         /* check case where child changes and parent forcing obdata to change */
1840         /* should be done regardless if this ob has recalc set */
1841         /* could merge this in with loop above...? (ton) */
1842         for(itA = node->child; itA; itA= itA->next) {
1843                 /* the relationship is visible */
1844                 if((itA->lay & layer)) {                // XXX  || (itA->node->ob == obedit)
1845                         if(itA->node->type==ID_OB) {
1846                                 obc= itA->node->ob;
1847                                 /* child moves */
1848                                 if((obc->recalc & OB_RECALC_ALL)==OB_RECALC_OB) {
1849                                         /* parent has deforming info */
1850                                         if(itA->type & (DAG_RL_OB_DATA|DAG_RL_DATA_DATA)) {
1851                                                 // printf("parent %s changes ob %s\n", ob->id.name, obc->id.name);
1852                                                 obc->recalc |= OB_RECALC_DATA;
1853                                                 lib_id_recalc_data_tag(bmain, &obc->id);
1854                                         }
1855                                 }
1856                         }
1857                 }
1858         }
1859         
1860         /* we only go deeper if node not checked or something changed  */
1861         for(itA = node->child; itA; itA= itA->next) {
1862                 if(changed || itA->node->lasttime!=curtime) 
1863                         flush_update_node(itA->node, layer, curtime);
1864         }
1865         
1866 }
1867
1868 /* node was checked to have lasttime != curtime , and is of type ID_OB */
1869 static unsigned int flush_layer_node(Scene *sce, DagNode *node, int curtime)
1870 {
1871         DagAdjList *itA;
1872         
1873         node->lasttime= curtime;
1874         node->lay= node->scelay;
1875         
1876         for(itA = node->child; itA; itA= itA->next) {
1877                 if(itA->node->type==ID_OB) {
1878                         if(itA->node->lasttime!=curtime) {
1879                                 itA->lay= flush_layer_node(sce, itA->node, curtime);  // lay is only set once for each relation
1880                         }
1881                         else itA->lay= itA->node->lay;
1882                         
1883                         node->lay |= itA->lay;
1884                 }
1885         }
1886
1887         return node->lay;
1888 }
1889
1890 /* node was checked to have lasttime != curtime , and is of type ID_OB */
1891 static void flush_pointcache_reset(Scene *scene, DagNode *node, int curtime, int reset)
1892 {
1893         Main *bmain= G.main;
1894         DagAdjList *itA;
1895         Object *ob;
1896         
1897         node->lasttime= curtime;
1898         
1899         for(itA = node->child; itA; itA= itA->next) {
1900                 if(itA->node->type==ID_OB) {
1901                         if(itA->node->lasttime!=curtime) {
1902                                 ob= (Object*)(itA->node->ob);
1903
1904                                 if(reset || (ob->recalc & OB_RECALC_ALL)) {
1905                                         if(BKE_ptcache_object_reset(scene, ob, PTCACHE_RESET_DEPSGRAPH)) {
1906                                                 ob->recalc |= OB_RECALC_DATA;
1907                                                 lib_id_recalc_data_tag(bmain, &ob->id);
1908                                         }
1909
1910                                         flush_pointcache_reset(scene, itA->node, curtime, 1);
1911                                 }
1912                                 else
1913                                         flush_pointcache_reset(scene, itA->node, curtime, 0);
1914                         }
1915                 }
1916         }
1917 }
1918
1919 /* flush layer flags to dependencies */
1920 static void dag_scene_flush_layers(Scene *sce, int lay)
1921 {
1922         DagNode *node, *firstnode;
1923         DagAdjList *itA;
1924         Base *base;
1925         int lasttime;
1926
1927         firstnode= sce->theDag->DagNode.first;  // always scene node
1928
1929         for(itA = firstnode->child; itA; itA= itA->next)
1930                 itA->lay= 0;
1931
1932         sce->theDag->time++;    // so we know which nodes were accessed
1933         lasttime= sce->theDag->time;
1934
1935         /* update layer flags in nodes */
1936         for(base= sce->base.first; base; base= base->next) {
1937                 node= dag_get_node(sce->theDag, base->object);
1938                 node->scelay= base->object->lay;
1939         }
1940
1941         /* ensure cameras are set as if they are on a visible layer, because
1942          * they ared still used for rendering or setting the camera view
1943          *
1944          * XXX, this wont work for local view / unlocked camera's */
1945         if(sce->camera) {
1946                 node= dag_get_node(sce->theDag, sce->camera);
1947                 node->scelay |= lay;
1948         }
1949
1950 #ifdef DURIAN_CAMERA_SWITCH
1951         {
1952                 TimeMarker *m;
1953
1954                 for(m= sce->markers.first; m; m= m->next) {
1955                         if(m->camera) {
1956                                 node= dag_get_node(sce->theDag, m->camera);
1957                                 node->scelay |= lay;
1958                         }
1959                 }
1960         }
1961 #endif
1962
1963         /* flush layer nodes to dependencies */
1964         for(itA = firstnode->child; itA; itA= itA->next)
1965                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
1966                         flush_layer_node(sce, itA->node, lasttime);
1967 }
1968
1969 static void dag_tag_renderlayers(Scene *sce, unsigned int lay)
1970 {
1971         if(sce->nodetree) {
1972                 bNode *node;
1973                 Base *base;
1974                 unsigned int lay_changed= 0;
1975                 
1976                 for(base= sce->base.first; base; base= base->next)
1977                         if(base->lay & lay)
1978                                 if(base->object->recalc)
1979                                         lay_changed |= base->lay;
1980                         
1981                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
1982                         if(node->id==(ID *)sce) {
1983                                 SceneRenderLayer *srl= BLI_findlink(&sce->r.layers, node->custom1);
1984                                 if(srl && (srl->lay & lay_changed))
1985                                         nodeUpdate(sce->nodetree, node);
1986                         }
1987                 }
1988         }
1989 }
1990
1991 /* flushes all recalc flags in objects down the dependency tree */
1992 void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const short time)
1993 {
1994         DagNode *firstnode;
1995         DagAdjList *itA;
1996         Object *ob;
1997         int lasttime;
1998         
1999         if(sce->theDag==NULL) {
2000                 printf("DAG zero... not allowed to happen!\n");
2001                 DAG_scene_sort(bmain, sce);
2002         }
2003         
2004         firstnode= sce->theDag->DagNode.first;  // always scene node
2005
2006         /* first we flush the layer flags */
2007         dag_scene_flush_layers(sce, lay);
2008
2009         /* then we use the relationships + layer info to flush update events */
2010         sce->theDag->time++;    // so we know which nodes were accessed
2011         lasttime= sce->theDag->time;
2012         for(itA = firstnode->child; itA; itA= itA->next)
2013                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)
2014                         flush_update_node(itA->node, lay, lasttime);
2015
2016         /* if update is not due to time change, do pointcache clears */
2017         if(!time) {
2018                 sce->theDag->time++;    // so we know which nodes were accessed
2019                 lasttime= sce->theDag->time;
2020                 for(itA = firstnode->child; itA; itA= itA->next) {
2021                         if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)  {
2022                                 ob= (Object*)(itA->node->ob);
2023
2024                                 if(ob->recalc & OB_RECALC_ALL) {
2025                                         if(BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH)) {
2026                                                 ob->recalc |= OB_RECALC_DATA;
2027                                                 lib_id_recalc_data_tag(bmain, &ob->id);
2028                                         }
2029
2030                                         flush_pointcache_reset(sce, itA->node, lasttime, 1);
2031                                 }
2032                                 else
2033                                         flush_pointcache_reset(sce, itA->node, lasttime, 0);
2034                         }
2035                 }
2036         }
2037         
2038         dag_tag_renderlayers(sce, lay);
2039 }
2040
2041 static int object_modifiers_use_time(Object *ob)
2042 {
2043         ModifierData *md;
2044         
2045         /* check if a modifier in modifier stack needs time input */
2046         for (md=ob->modifiers.first; md; md=md->next)
2047                 if (modifier_dependsOnTime(md))
2048                         return 1;
2049         
2050         /* check whether any modifiers are animated */
2051         if (ob->adt) {
2052                 AnimData *adt = ob->adt;
2053                 FCurve *fcu;
2054                 
2055                 /* action - check for F-Curves with paths containing 'modifiers[' */
2056                 if (adt->action) {
2057                         for (fcu = adt->action->curves.first; fcu; fcu = fcu->next) {
2058                                 if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
2059                                         return 1;
2060                         }
2061                 }
2062                 
2063                 /* This here allows modifier properties to get driven and still update properly
2064                  *
2065                  * Workaround to get [#26764] (e.g. subsurf levels not updating when animated/driven)
2066                  * working, without the updating problems ([#28525] [#28690] [#28774] [#28777]) caused
2067                  * by the RNA updates cache introduced in r.38649
2068                  */
2069                 for (fcu = adt->drivers.first; fcu; fcu = fcu->next) {
2070                         if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
2071                                 return 1;
2072                 }
2073                 
2074                 // XXX: also, should check NLA strips, though for now assume that nobody uses
2075                 // that and we can omit that for performance reasons...
2076         }
2077         
2078         return 0;
2079 }
2080
2081 static short animdata_use_time(AnimData *adt)
2082 {
2083         NlaTrack *nlt;
2084         
2085         if(adt==NULL) return 0;
2086         
2087         /* check action - only if assigned, and it has anim curves */
2088         if (adt->action && adt->action->curves.first)
2089                 return 1;
2090         
2091         /* check NLA tracks + strips */
2092         for (nlt= adt->nla_tracks.first; nlt; nlt= nlt->next) {
2093                 if (nlt->strips.first)
2094                         return 1;
2095         }
2096         
2097         /* If we have drivers, more likely than not, on a frame change
2098          * they'll need updating because their owner changed
2099          * 
2100          * This is kindof a hack to get around a whole host of problems
2101          * involving drivers using non-object datablock data (which the 
2102          * depsgraph currently has no way of representing let alone correctly
2103          * dependency sort+tagging). By doing this, at least we ensure that 
2104          * some commonly attempted drivers (such as scene -> current frame;
2105          * see "Driver updates fail" thread on Bf-committers dated July 2)
2106          * will work correctly, and that other non-object datablocks will have
2107          * their drivers update at least on frame change.
2108          *
2109          * -- Aligorith, July 4 2011
2110          */
2111         if (adt->drivers.first)
2112                 return 1;
2113         
2114         return 0;
2115 }
2116
2117 static void dag_object_time_update_flags(Object *ob)
2118 {
2119         if(ob->constraints.first) {
2120                 bConstraint *con;
2121                 for (con = ob->constraints.first; con; con=con->next) {
2122                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2123                         ListBase targets = {NULL, NULL};
2124                         bConstraintTarget *ct;
2125                         
2126                         if (cti && cti->get_constraint_targets) {
2127                                 cti->get_constraint_targets(con, &targets);
2128                                 
2129                                 for (ct= targets.first; ct; ct= ct->next) {
2130                                         if (ct->tar) {
2131                                                 ob->recalc |= OB_RECALC_OB;
2132                                                 break;
2133                                         }
2134                                 }
2135                                 
2136                                 if (cti->flush_constraint_targets)
2137                                         cti->flush_constraint_targets(con, &targets, 1);
2138                         }
2139                 }
2140         }
2141         
2142         if(ob->parent) {
2143                 /* motion path or bone child */
2144                 if(ob->parent->type==OB_CURVE || ob->parent->type==OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
2145         }
2146         
2147 #if 0 // XXX old animation system
2148         if(ob->nlastrips.first) {
2149                 if(ob->dup_group) {
2150                         bActionStrip *strip;
2151                         /* this case is for groups with nla, whilst nla target has no action or nla */
2152                         for(strip= ob->nlastrips.first; strip; strip= strip->next) {
2153                                 if(strip->object)
2154                                         strip->object->recalc |= OB_RECALC_ALL;
2155                         }
2156                 }
2157         }
2158 #endif // XXX old animation system
2159         
2160         if(animdata_use_time(ob->adt)) {
2161                 ob->recalc |= OB_RECALC_OB;
2162                 ob->adt->recalc |= ADT_RECALC_ANIM;
2163         }
2164         
2165         if((ob->adt) && (ob->type==OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA;
2166         
2167         if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
2168         if((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->recalc |= OB_RECALC_DATA;
2169         
2170         {
2171                 AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
2172                 Mesh *me;
2173                 Curve *cu;
2174                 Lattice *lt;
2175                 
2176                 switch(ob->type) {
2177                         case OB_MESH:
2178                                 me= ob->data;
2179                                 if(me->key) {
2180                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2181                                                 ob->recalc |= OB_RECALC_DATA;
2182                                         }
2183                                 }
2184                                 if(ob->particlesystem.first)
2185                                         ob->recalc |= OB_RECALC_DATA;
2186                                 break;
2187                         case OB_CURVE:
2188                         case OB_SURF:
2189                                 cu= ob->data;
2190                                 if(cu->key) {
2191                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2192                                                 ob->recalc |= OB_RECALC_DATA;
2193                                         }
2194                                 }
2195                                 break;
2196                         case OB_FONT:
2197                                 cu= ob->data;
2198                                 if(cu->nurb.first==NULL && cu->str && cu->vfont)
2199                                         ob->recalc |= OB_RECALC_DATA;
2200                                 break;
2201                         case OB_LATTICE:
2202                                 lt= ob->data;
2203                                 if(lt->key) {
2204                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2205                                                 ob->recalc |= OB_RECALC_DATA;
2206                                         }
2207                                 }
2208                                         break;
2209                         case OB_MBALL:
2210                                 if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
2211                                 break;
2212                 }
2213                 
2214                 if(animdata_use_time(adt)) {
2215                         ob->recalc |= OB_RECALC_DATA;
2216                         adt->recalc |= ADT_RECALC_ANIM;
2217                 }
2218
2219                 if(ob->particlesystem.first) {
2220                         ParticleSystem *psys= ob->particlesystem.first;
2221
2222                         for(; psys; psys=psys->next) {
2223                                 if(psys_check_enabled(ob, psys)) {
2224                                         ob->recalc |= OB_RECALC_DATA;
2225                                         break;
2226                                 }
2227                         }
2228                 }
2229         }               
2230
2231         if(ob->recalc & OB_RECALC_OB)
2232                 lib_id_recalc_tag(G.main, &ob->id);
2233         if(ob->recalc & OB_RECALC_DATA)
2234                 lib_id_recalc_data_tag(G.main, &ob->id);
2235
2236 }
2237 /* flag all objects that need recalc, for changes in time for example */
2238 /* do_time: make this optional because undo resets objects to their animated locations without this */
2239 void DAG_scene_update_flags(Main *bmain, Scene *scene, unsigned int lay, const short do_time)
2240 {
2241         Base *base;
2242         Object *ob;
2243         Group *group;
2244         GroupObject *go;
2245         Scene *sce_iter;
2246
2247         /* set ob flags where animated systems are */
2248         for(SETLOOPER(scene, sce_iter, base)) {
2249                 ob= base->object;
2250
2251                 if(do_time) {
2252                         /* now if DagNode were part of base, the node->lay could be checked... */
2253                         /* we do all now, since the scene_flush checks layers and clears recalc flags even */
2254                         dag_object_time_update_flags(ob);
2255                 }
2256
2257                 /* handled in next loop */
2258                 if(ob->dup_group)
2259                         ob->dup_group->id.flag |= LIB_DOIT;
2260         }
2261
2262         if(do_time) {
2263                 /* we do groups each once */
2264                 for(group= bmain->group.first; group; group= group->id.next) {
2265                         if(group->id.flag & LIB_DOIT) {
2266                                 for(go= group->gobject.first; go; go= go->next) {
2267                                         dag_object_time_update_flags(go->ob);
2268                                 }
2269                         }
2270                 }
2271         }
2272
2273         for(sce_iter= scene; sce_iter; sce_iter= sce_iter->set)
2274                 DAG_scene_flush_update(bmain, sce_iter, lay, 1);
2275         
2276         if(do_time) {
2277                 /* test: set time flag, to disable baked systems to update */
2278                 for(SETLOOPER(scene, sce_iter, base)) {
2279                         ob= base->object;
2280                         if(ob->recalc)
2281                                 ob->recalc |= OB_RECALC_TIME;
2282                 }
2283
2284                 /* hrmf... an exception to look at once, for invisible camera object we do it over */
2285                 if(scene->camera)
2286                         dag_object_time_update_flags(scene->camera);
2287         }
2288
2289         /* and store the info in groupobject */
2290         for(group= bmain->group.first; group; group= group->id.next) {
2291                 if(group->id.flag & LIB_DOIT) {
2292                         for(go= group->gobject.first; go; go= go->next) {
2293                                 go->recalc= go->ob->recalc;
2294                                 // printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
2295                         }
2296                         group->id.flag &= ~LIB_DOIT;
2297                 }
2298         }
2299         
2300 }
2301
2302 static void dag_current_scene_layers(Main *bmain, Scene **sce, unsigned int *lay)
2303 {
2304         wmWindowManager *wm;
2305         wmWindow *win;
2306
2307         /* only one scene supported currently, making more scenes work
2308            correctly requires changes beyond just the dependency graph */
2309
2310         *sce= NULL;
2311         *lay= 0;
2312
2313         if((wm= bmain->wm.first)) {
2314                 /* if we have a windowmanager, look into windows */
2315                 for(win=wm->windows.first; win; win=win->next) {
2316                         if(win->screen) {
2317                                 if(!*sce) *sce= win->screen->scene;
2318                                 *lay |= BKE_screen_visible_layers(win->screen, win->screen->scene);
2319                         }
2320                 }
2321         }
2322         else {
2323                 /* if not, use the first sce */
2324                 *sce= bmain->scene.first;
2325                 if(*sce) *lay= (*sce)->lay;
2326
2327                 /* XXX for background mode, we should get the scene
2328                    from somewhere, for the -S option, but it's in
2329                    the context, how to get it here? */
2330         }
2331 }
2332
2333 void DAG_ids_flush_update(Main *bmain, int time)
2334 {
2335         Scene *sce;
2336         unsigned int lay;
2337
2338         dag_current_scene_layers(bmain, &sce, &lay);
2339
2340         if(sce)
2341                 DAG_scene_flush_update(bmain, sce, lay, time);
2342 }
2343
2344 void DAG_on_visible_update(Main *bmain, const short do_time)
2345 {
2346         Scene *scene;
2347         Base *base;
2348         Object *ob;
2349         Group *group;
2350         GroupObject *go;
2351         DagNode *node;
2352         unsigned int lay, oblay;
2353
2354         dag_current_scene_layers(bmain, &scene, &lay);
2355
2356         if(scene && scene->theDag) {
2357                 Scene *sce_iter;
2358                 /* derivedmeshes and displists are not saved to file so need to be
2359                    remade, tag them so they get remade in the scene update loop,
2360                    note armature poses or object matrices are preserved and do not
2361                    require updates, so we skip those */
2362                 dag_scene_flush_layers(scene, lay);
2363
2364                 for(SETLOOPER(scene, sce_iter, base)) {
2365                         ob= base->object;
2366                         node= (sce_iter->theDag)? dag_get_node(sce_iter->theDag, ob): NULL;
2367                         oblay= (node)? node->lay: ob->lay;
2368
2369                         if((oblay & lay) & ~scene->lay_updated) {
2370                                 if(ELEM6(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2371                                         ob->recalc |= OB_RECALC_DATA;
2372                                 if(ob->dup_group) 
2373                                         ob->dup_group->id.flag |= LIB_DOIT;
2374                         }
2375                 }
2376
2377                 for(group= bmain->group.first; group; group= group->id.next) {
2378                         if(group->id.flag & LIB_DOIT) {
2379                                 for(go= group->gobject.first; go; go= go->next) {
2380                                         if(ELEM6(go->ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2381                                                 go->ob->recalc |= OB_RECALC_DATA;
2382                                         if(go->ob->proxy_from)
2383                                                 go->ob->recalc |= OB_RECALC_OB;
2384                                 }
2385                                 
2386                                 group->id.flag &= ~LIB_DOIT;
2387                         }
2388                 }
2389
2390                 /* now tag update flags, to ensure deformers get calculated on redraw */
2391                 DAG_scene_update_flags(bmain, scene, lay, do_time);
2392                 scene->lay_updated |= lay;
2393         }
2394
2395         /* hack to get objects updating on layer changes */
2396         DAG_id_type_tag(bmain, ID_OB);
2397 }
2398
2399 static void dag_id_flush_update__isDependentTexture(void *userData, Object *UNUSED(ob), ID **idpoin)
2400 {
2401         struct { ID *id; int is_dependent; } *data = userData;
2402         
2403         if(*idpoin && GS((*idpoin)->name)==ID_TE) {
2404                 if (data->id == (*idpoin))
2405                         data->is_dependent = 1;
2406         }
2407 }
2408
2409 static void dag_id_flush_update(Scene *sce, ID *id)
2410 {
2411         Main *bmain= G.main;
2412         Object *obt, *ob= NULL;
2413         short idtype;
2414
2415         /* here we flush a few things before actual scene wide flush, mostly
2416            due to only objects and not other datablocks being in the depsgraph */
2417
2418         /* set flags & pointcache for object */
2419         if(GS(id->name) == ID_OB) {
2420                 ob= (Object*)id;
2421                 BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH);
2422
2423                 if(ob->recalc & OB_RECALC_DATA) {
2424                         /* all users of this ob->data should be checked */
2425                         id= ob->data;
2426
2427                         /* no point in trying in this cases */
2428                         if(id && id->us <= 1) {
2429                                 dag_editors_update(bmain, id);
2430                                 id= NULL;
2431                         }
2432                 }
2433         }
2434
2435         /* set flags & pointcache for object data */
2436         if(id) {
2437                 idtype= GS(id->name);
2438
2439                 if(ELEM8(idtype, ID_ME, ID_CU, ID_MB, ID_LA, ID_LT, ID_CA, ID_AR, ID_SPK)) {
2440                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2441                                 if(!(ob && obt == ob) && obt->data == id) {
2442                                         obt->recalc |= OB_RECALC_DATA;
2443                                         lib_id_recalc_data_tag(bmain, &obt->id);
2444                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2445                                 }
2446                         }
2447                 }
2448                 
2449                 /* set flags based on textures - can influence depgraph via modifiers */
2450                 if(idtype == ID_TE) {
2451                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2452                                 struct { ID *id; int is_dependent; } data;
2453                                 data.id= id;
2454                                 data.is_dependent= 0;
2455
2456                                 modifiers_foreachIDLink(obt, dag_id_flush_update__isDependentTexture, &data);
2457                                 if (data.is_dependent) {
2458                                         obt->recalc |= OB_RECALC_DATA;
2459                                         lib_id_recalc_data_tag(bmain, &obt->id);
2460                                 }
2461
2462                                 /* particle settings can use the texture as well */
2463                                 if(obt->particlesystem.first) {
2464                                         ParticleSystem *psys = obt->particlesystem.first;
2465                                         MTex **mtexp, *mtex;
2466                                         int a;
2467                                         for(; psys; psys=psys->next) {
2468                                                 mtexp = psys->part->mtex;
2469                                                 for(a=0; a<MAX_MTEX; a++, mtexp++) {
2470                                                         mtex = *mtexp;
2471                                                         if(mtex && mtex->tex == (Tex*)id) {
2472                                                                 obt->recalc |= OB_RECALC_DATA;
2473                                                                 lib_id_recalc_data_tag(bmain, &obt->id);
2474
2475                                                                 if(mtex->mapto & PAMAP_INIT)
2476                                                                         psys->recalc |= PSYS_RECALC_RESET;
2477                                                                 if(mtex->mapto & PAMAP_CHILD)
2478                                                                         psys->recalc |= PSYS_RECALC_CHILD;
2479
2480                                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2481                                                         }
2482                                                 }
2483                                         }
2484                                 }
2485                         }
2486                 }
2487                 
2488                 /* set flags based on ShapeKey */
2489                 if(idtype == ID_KE) {
2490                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2491                                 Key *key= ob_get_key(obt);
2492                                 if(!(ob && obt == ob) && ((ID *)key == id)) {
2493                                         obt->flag |= (OB_RECALC_OB|OB_RECALC_DATA);
2494                                         lib_id_recalc_tag(bmain, &obt->id);
2495                                         lib_id_recalc_data_tag(bmain, &obt->id);
2496                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2497                                 }
2498                         }
2499                 }
2500                 
2501                 /* set flags based on particle settings */
2502                 if(idtype == ID_PA) {
2503                         ParticleSystem *psys;
2504                         for(obt=bmain->object.first; obt; obt= obt->id.next)
2505                                 for(psys=obt->particlesystem.first; psys; psys=psys->next)
2506                                         if(&psys->part->id == id)
2507                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2508                 }
2509
2510                 /* update editors */
2511                 dag_editors_update(bmain, id);
2512         }
2513 }
2514
2515 void DAG_ids_flush_tagged(Main *bmain)
2516 {
2517         ListBase *lbarray[MAX_LIBARRAY];
2518         Scene *sce;
2519         unsigned int lay;
2520         int a, do_flush = 0;
2521
2522         dag_current_scene_layers(bmain, &sce, &lay);
2523
2524         if(!sce || !sce->theDag)
2525                 return;
2526
2527         /* loop over all ID types */
2528         a  = set_listbasepointers(bmain, lbarray);
2529
2530         while(a--) {
2531                 ListBase *lb = lbarray[a];
2532                 ID *id = lb->first;
2533
2534                 /* we tag based on first ID type character to avoid 
2535                    looping over all ID's in case there are no tags */
2536                 if(id && bmain->id_tag_update[id->name[0]]) {
2537                         for(; id; id=id->next) {
2538                                 if(id->flag & (LIB_ID_RECALC|LIB_ID_RECALC_DATA)) {
2539                                         dag_id_flush_update(sce, id);
2540                                         do_flush = 1;
2541                                 }
2542                         }
2543                 }
2544         }
2545
2546         /* flush changes to other objects */
2547         if(do_flush)
2548                 DAG_scene_flush_update(bmain, sce, lay, 0);
2549 }
2550
2551 void DAG_ids_check_recalc(Main *bmain)
2552 {
2553         ListBase *lbarray[MAX_LIBARRAY];
2554         int a;
2555
2556         /* loop over all ID types */
2557         a  = set_listbasepointers(bmain, lbarray);
2558
2559         while(a--) {
2560                 ListBase *lb = lbarray[a];
2561                 ID *id = lb->first;
2562
2563                 /* we tag based on first ID type character to avoid 
2564                    looping over all ID's in case there are no tags */
2565                 if(id && bmain->id_tag_update[id->name[0]]) {
2566                         /* do editors update */
2567                         dag_editors_update(bmain, NULL);
2568                         return;
2569                 }
2570         }
2571 }
2572
2573
2574 void DAG_ids_clear_recalc(Main *bmain)
2575 {
2576         ListBase *lbarray[MAX_LIBARRAY];
2577         int a;
2578
2579         /* loop over all ID types */
2580         a  = set_listbasepointers(bmain, lbarray);
2581
2582         while(a--) {
2583                 ListBase *lb = lbarray[a];
2584                 ID *id = lb->first;
2585
2586                 /* we tag based on first ID type character to avoid 
2587                    looping over all ID's in case there are no tags */
2588                 if(id && bmain->id_tag_update[id->name[0]]) {
2589                         for(; id; id=id->next)
2590                                 if(id->flag & (LIB_ID_RECALC|LIB_ID_RECALC_DATA))
2591                                         id->flag &= ~(LIB_ID_RECALC|LIB_ID_RECALC_DATA);
2592                 }
2593         }
2594
2595         memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update));
2596 }
2597
2598 void DAG_id_tag_update(ID *id, short flag)
2599 {
2600         Main *bmain= G.main;
2601
2602         if(id==NULL) return;
2603         
2604         /* tag ID for update */
2605         if(flag) {
2606                 if(flag & OB_RECALC_OB)
2607                         lib_id_recalc_tag(bmain, id);
2608                 if(flag & (OB_RECALC_DATA|PSYS_RECALC))
2609                         lib_id_recalc_data_tag(bmain, id);
2610         }
2611         else
2612                 lib_id_recalc_tag(bmain, id);
2613
2614         /* flag is for objects and particle systems */
2615         if(flag) {
2616                 Object *ob;
2617                 ParticleSystem *psys;
2618                 short idtype = GS(id->name);
2619
2620                 if(idtype == ID_OB) {
2621                         /* only quick tag */
2622                         ob = (Object*)id;
2623                         ob->recalc |= (flag & OB_RECALC_ALL);
2624                 }
2625                 else if(idtype == ID_PA) {
2626                         /* this is weak still, should be done delayed as well */
2627                         for(ob=bmain->object.first; ob; ob=ob->id.next) {
2628                                 for(psys=ob->particlesystem.first; psys; psys=psys->next) {
2629                                         if(&psys->part->id == id) {
2630                                                 ob->recalc |= (flag & OB_RECALC_ALL);
2631                                                 psys->recalc |= (flag & PSYS_RECALC);
2632                                         }
2633                                 }
2634                         }
2635                 }
2636                 else {
2637                         /* disable because this is called on various ID types automatically.
2638                          * where printing warning is not useful. for now just ignore */
2639                         /* BLI_assert(!"invalid flag for this 'idtype'"); */
2640                 }
2641         }
2642 }
2643
2644 void DAG_id_type_tag(struct Main *bmain, short idtype)
2645 {
2646         bmain->id_tag_update[((char*)&idtype)[0]] = 1;
2647 }
2648
2649 int DAG_id_type_tagged(Main *bmain, short idtype)
2650 {
2651         return bmain->id_tag_update[((char*)&idtype)[0]];
2652 }
2653
2654 #if 0 // UNUSED
2655 /* recursively descends tree, each node only checked once */
2656 /* node is checked to be of type object */
2657 static int parent_check_node(DagNode *node, int curtime)
2658 {
2659         DagAdjList *itA;
2660         
2661         node->lasttime= curtime;
2662         
2663         if(node->color==DAG_GRAY)
2664                 return DAG_GRAY;
2665         
2666         for(itA = node->child; itA; itA= itA->next) {
2667                 if(itA->node->type==ID_OB) {
2668                         
2669                         if(itA->node->color==DAG_GRAY)
2670                                 return DAG_GRAY;
2671
2672                         /* descend if not done */
2673                         if(itA->node->lasttime!=curtime) {
2674                                 itA->node->color= parent_check_node(itA->node, curtime);
2675                         
2676                                 if(itA->node->color==DAG_GRAY)
2677                                         return DAG_GRAY;
2678                         }
2679                 }
2680         }
2681         
2682         return DAG_WHITE;
2683 }
2684 #endif
2685
2686 /* ******************* DAG FOR ARMATURE POSE ***************** */
2687
2688 /* we assume its an armature with pose */
2689 void DAG_pose_sort(Object *ob)
2690 {
2691         bPose *pose= ob->pose;
2692         bPoseChannel *pchan;
2693         bConstraint *con;
2694         DagNode *node;
2695         DagNode *node2, *node3;
2696         DagNode *rootnode;
2697         DagForest *dag;
2698         DagNodeQueue *nqueue;
2699         DagAdjList *itA;
2700         ListBase tempbase;
2701         int skip = 0;
2702         
2703         dag = dag_init();
2704         ugly_hack_sorry= 0;     // no ID structs
2705
2706         rootnode = dag_add_node(dag, NULL);     // node->ob becomes NULL
2707         
2708         /* we add the hierarchy and the constraints */
2709         for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2710                 int addtoroot = 1;
2711                 
2712                 node = dag_get_node(dag, pchan);
2713                 
2714                 if(pchan->parent) {
2715                         node2 = dag_get_node(dag, pchan->parent);
2716                         dag_add_relation(dag, node2, node, 0, "Parent Relation");
2717                         addtoroot = 0;
2718                 }
2719                 for (con = pchan->constraints.first; con; con=con->next) {
2720                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2721                         ListBase targets = {NULL, NULL};
2722                         bConstraintTarget *ct;
2723                         
2724                         if (cti && cti->get_constraint_targets) {
2725                                 cti->get_constraint_targets(con, &targets);
2726                                 
2727                                 for (ct= targets.first; ct; ct= ct->next) {
2728                                         if (ct->tar==ob && ct->subtarget[0]) {
2729                                                 bPoseChannel *target= get_pose_channel(ob->pose, ct->subtarget);
2730                                                 if (target) {
2731                                                         node2= dag_get_node(dag, target);
2732                                                         dag_add_relation(dag, node2, node, 0, "Pose Constraint");
2733                                                         
2734                                                         if (con->type==CONSTRAINT_TYPE_KINEMATIC) {
2735                                                                 bKinematicConstraint *data = (bKinematicConstraint *)con->data;
2736                                                                 bPoseChannel *parchan;
2737                                                                 int segcount= 0;
2738                                                                 
2739                                                                 /* exclude tip from chain? */
2740                                                                 if(!(data->flag & CONSTRAINT_IK_TIP))
2741                                                                         parchan= pchan->parent;
2742                                                                 else
2743                                                                         parchan= pchan;
2744                                                                 
2745                                                                 /* Walk to the chain's root */
2746                                                                 while (parchan) {
2747                                                                         node3= dag_get_node(dag, parchan);
2748                                                                         dag_add_relation(dag, node2, node3, 0, "IK Constraint");
2749                                                                         
2750                                                                         segcount++;
2751                                                                         if (segcount==data->rootbone || segcount>255) break; // 255 is weak
2752                                                                         parchan= parchan->parent;
2753                                                                 }
2754                                                         }
2755                                                 }
2756                                         }
2757                                 }
2758                                 
2759                                 if (cti->flush_constraint_targets)
2760                                         cti->flush_constraint_targets(con, &targets, 1);
2761                         }
2762                 }
2763                 if (addtoroot == 1 ) {
2764                         dag_add_relation(dag, rootnode, node, 0, "Root Bone Relation");
2765                 }
2766         }
2767
2768         dag_check_cycle(dag);
2769         
2770         /* now we try to sort... */
2771         tempbase.first= tempbase.last= NULL;
2772
2773         nqueue = queue_create(DAGQUEUEALLOC);
2774         
2775         /* tag nodes unchecked */
2776         for(node = dag->DagNode.first; node; node= node->next) 
2777                 node->color = DAG_WHITE;
2778         
2779         node = dag->DagNode.first;
2780         
2781         node->color = DAG_GRAY;
2782         push_stack(nqueue, node);  
2783         
2784         while(nqueue->count) {
2785                 
2786                 skip = 0;
2787                 node = get_top_node_queue(nqueue);
2788                 
2789                 itA = node->child;
2790                 while(itA != NULL) {
2791                         if(itA->node->color == DAG_WHITE) {
2792                                 itA->node->color = DAG_GRAY;
2793                                 push_stack(nqueue,itA->node);
2794                                 skip = 1;
2795                                 break;
2796                         } 
2797                         itA = itA->next;
2798                 }                       
2799                 
2800                 if (!skip) {
2801                         if (node) {
2802                                 node = pop_queue(nqueue);
2803                                 if (node->ob == NULL)   // we are done
2804                                         break ;
2805                                 node->color = DAG_BLACK;
2806                                 
2807                                 /* put node in new list */
2808                                 BLI_remlink(&pose->chanbase, node->ob);
2809                                 BLI_addhead(&tempbase, node->ob);
2810                         }       
2811                 }
2812         }
2813         
2814         // temporal correction for circular dependancies
2815         while(pose->chanbase.first) {
2816                 pchan= pose->chanbase.first;
2817                 BLI_remlink(&pose->chanbase, pchan);
2818                 BLI_addhead(&tempbase, pchan);
2819
2820                 printf("cyclic %s\n", pchan->name);
2821         }
2822         
2823         pose->chanbase = tempbase;
2824         queue_delete(nqueue);
2825         
2826 //      printf("\nordered\n");
2827 //      for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2828 //              printf(" %s\n", pchan->name);
2829 //      }
2830         
2831         free_forest( dag );
2832         MEM_freeN( dag );
2833         
2834         ugly_hack_sorry= 1;
2835 }
2836
2837
2838