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