quiet some clang warnings.
[blender.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 "MEM_guardedalloc.h"
33
34 #include "BLI_winstuff.h"
35 #include "BLI_utildefines.h"
36 #include "BLI_ghash.h"
37
38 #include "DNA_anim_types.h"
39 #include "DNA_camera_types.h"
40 #include "DNA_group_types.h"
41 #include "DNA_lattice_types.h"
42 #include "DNA_key_types.h"
43 #include "DNA_mesh_types.h"
44 #include "DNA_node_types.h"
45 #include "DNA_scene_types.h"
46 #include "DNA_screen_types.h"
47 #include "DNA_windowmanager_types.h"
48
49 #include "BKE_animsys.h"
50 #include "BKE_action.h"
51 #include "BKE_effect.h"
52 #include "BKE_fcurve.h"
53 #include "BKE_global.h"
54 #include "BKE_group.h"
55 #include "BKE_key.h"
56 #include "BKE_library.h"
57 #include "BKE_main.h"
58 #include "BKE_node.h"
59 #include "BKE_mball.h"
60 #include "BKE_modifier.h"
61 #include "BKE_object.h"
62 #include "BKE_particle.h"
63 #include "BKE_pointcache.h"
64 #include "BKE_scene.h"
65 #include "BKE_screen.h"
66 #include "BKE_utildefines.h"
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(Main *bmain, 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= bmain->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, "dag_add_node gh");
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 *UNUSED(forest), DagNode *fob1, DagNode *fob2, short rel, const 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, const 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 const 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, const 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(Main *bmain, 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= bmain->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= bmain->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(Main *bmain, 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(bmain, 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(bmain, 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_ALL)) {
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_ALL;
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_ALL)==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*)(itA->node->ob);
1866
1867                                 if(reset || (ob->recalc & OB_RECALC_ALL)) {
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 /* flush layer flags to dependencies */
1881 static void dag_scene_flush_layers(Scene *sce, int lay)
1882 {
1883         DagNode *node, *firstnode;
1884         DagAdjList *itA;
1885         Base *base;
1886         int lasttime;
1887
1888         firstnode= sce->theDag->DagNode.first;  // always scene node
1889
1890         for(itA = firstnode->child; itA; itA= itA->next)
1891                 itA->lay= 0;
1892
1893         sce->theDag->time++;    // so we know which nodes were accessed
1894         lasttime= sce->theDag->time;
1895
1896         /* update layer flags in nodes */
1897         for(base= sce->base.first; base; base= base->next) {
1898                 node= dag_get_node(sce->theDag, base->object);
1899                 node->scelay= base->object->lay;
1900         }
1901
1902         /* ensure cameras are set as if they are on a visible layer, because
1903            they ared still used for rendering or setting the camera view */
1904         if(sce->camera) {
1905                 node= dag_get_node(sce->theDag, sce->camera);
1906                 node->scelay |= lay;
1907         }
1908
1909 #ifdef DURIAN_CAMERA_SWITCH
1910         {
1911                 TimeMarker *m;
1912
1913                 for(m= sce->markers.first; m; m= m->next) {
1914                         if(m->camera) {
1915                                 node= dag_get_node(sce->theDag, m->camera);
1916                                 node->scelay |= lay;
1917                         }
1918                 }
1919         }
1920 #endif
1921
1922         /* flush layer nodes to dependencies */
1923         for(itA = firstnode->child; itA; itA= itA->next)
1924                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
1925                         flush_layer_node(sce, itA->node, lasttime);
1926 }
1927
1928 static void dag_tag_renderlayers(Scene *sce, unsigned int lay)
1929 {
1930         if(sce->nodetree) {
1931                 bNode *node;
1932                 Base *base;
1933                 unsigned int lay_changed= 0;
1934                 
1935                 for(base= sce->base.first; base; base= base->next)
1936                         if(base->lay & lay)
1937                                 if(base->object->recalc)
1938                                         lay_changed |= base->lay;
1939                         
1940                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
1941                         if(node->id==(ID *)sce) {
1942                                 SceneRenderLayer *srl= BLI_findlink(&sce->r.layers, node->custom1);
1943                                 if(srl && (srl->lay & lay_changed))
1944                                         NodeTagChanged(sce->nodetree, node);
1945                         }
1946                 }
1947         }
1948 }
1949
1950 /* flushes all recalc flags in objects down the dependency tree */
1951 void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const short time)
1952 {
1953         DagNode *firstnode;
1954         DagAdjList *itA;
1955         Object *ob;
1956         int lasttime;
1957         
1958         if(sce->theDag==NULL) {
1959                 printf("DAG zero... not allowed to happen!\n");
1960                 DAG_scene_sort(bmain, sce);
1961         }
1962         
1963         firstnode= sce->theDag->DagNode.first;  // always scene node
1964
1965         /* first we flush the layer flags */
1966         dag_scene_flush_layers(sce, lay);
1967
1968         /* then we use the relationships + layer info to flush update events */
1969         sce->theDag->time++;    // so we know which nodes were accessed
1970         lasttime= sce->theDag->time;
1971         for(itA = firstnode->child; itA; itA= itA->next)
1972                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)
1973                         flush_update_node(itA->node, lay, lasttime);
1974
1975         /* if update is not due to time change, do pointcache clears */
1976         if(!time) {
1977                 sce->theDag->time++;    // so we know which nodes were accessed
1978                 lasttime= sce->theDag->time;
1979                 for(itA = firstnode->child; itA; itA= itA->next) {
1980                         if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)  {
1981                                 ob= (Object*)(itA->node->ob);
1982
1983                                 if(ob->recalc & OB_RECALC_ALL) {
1984                                         if(BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH))
1985                                                 ob->recalc |= OB_RECALC_DATA;
1986
1987                                         flush_pointcache_reset(sce, itA->node, lasttime, 1);
1988                                 }
1989                                 else
1990                                         flush_pointcache_reset(sce, itA->node, lasttime, 0);
1991                         }
1992                 }
1993         }
1994         
1995         dag_tag_renderlayers(sce, lay);
1996 }
1997
1998 static int object_modifiers_use_time(Object *ob)
1999 {
2000         ModifierData *md;
2001         
2002         /* check if a modifier in modifier stack needs time input */
2003         for (md=ob->modifiers.first; md; md=md->next)
2004                 if (modifier_dependsOnTime(md))
2005                         return 1;
2006         
2007         /* check whether any modifiers are animated */
2008         if (ob->adt) {
2009                 AnimData *adt = ob->adt;
2010                 
2011                 /* action - check for F-Curves with paths containing 'modifiers[' */
2012                 if (adt->action) {
2013                         FCurve *fcu;
2014                         
2015                         for (fcu = adt->action->curves.first; fcu; fcu = fcu->next) {
2016                                 if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
2017                                         return 1;
2018                         }
2019                 }
2020                 
2021                 // XXX: also, should check NLA strips, though for now assume that nobody uses
2022                 // that and we can omit that for performance reasons...
2023         }
2024         
2025         return 0;
2026 }
2027
2028 static short animdata_use_time(AnimData *adt)
2029 {
2030         NlaTrack *nlt;
2031         
2032         if(adt==NULL) return 0;
2033         
2034         /* check action - only if assigned, and it has anim curves */
2035         if (adt->action && adt->action->curves.first)
2036                 return 1;
2037         
2038         /* check NLA tracks + strips */
2039         for (nlt= adt->nla_tracks.first; nlt; nlt= nlt->next) {
2040                 if (nlt->strips.first)
2041                         return 1;
2042         }
2043         
2044         return 0;
2045 }
2046
2047 static void dag_object_time_update_flags(Object *ob)
2048 {
2049         if(ob->constraints.first) {
2050                 bConstraint *con;
2051                 for (con = ob->constraints.first; con; con=con->next) {
2052                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2053                         ListBase targets = {NULL, NULL};
2054                         bConstraintTarget *ct;
2055                         
2056                         if (cti && cti->get_constraint_targets) {
2057                                 cti->get_constraint_targets(con, &targets);
2058                                 
2059                                 for (ct= targets.first; ct; ct= ct->next) {
2060                                         if (ct->tar) {
2061                                                 ob->recalc |= OB_RECALC_OB;
2062                                                 break;
2063                                         }
2064                                 }
2065                                 
2066                                 if (cti->flush_constraint_targets)
2067                                         cti->flush_constraint_targets(con, &targets, 1);
2068                         }
2069                 }
2070         }
2071         
2072         if(ob->parent) {
2073                 /* motion path or bone child */
2074                 if(ob->parent->type==OB_CURVE || ob->parent->type==OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
2075         }
2076         
2077 #if 0 // XXX old animation system
2078         if(ob->nlastrips.first) {
2079                 if(ob->dup_group) {
2080                         bActionStrip *strip;
2081                         /* this case is for groups with nla, whilst nla target has no action or nla */
2082                         for(strip= ob->nlastrips.first; strip; strip= strip->next) {
2083                                 if(strip->object)
2084                                         strip->object->recalc |= OB_RECALC_ALL;
2085                         }
2086                 }
2087         }
2088 #endif // XXX old animation system
2089         
2090         if(animdata_use_time(ob->adt)) {
2091                 ob->recalc |= OB_RECALC_OB;
2092                 ob->adt->recalc |= ADT_RECALC_ANIM;
2093         }
2094         
2095         if((ob->adt) && (ob->type==OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA;
2096         
2097         if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
2098         if((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->recalc |= OB_RECALC_DATA;
2099         
2100         {
2101                 AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
2102                 Mesh *me;
2103                 Curve *cu;
2104                 Lattice *lt;
2105                 
2106                 switch(ob->type) {
2107                         case OB_MESH:
2108                                 me= ob->data;
2109                                 if(me->key) {
2110                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2111                                                 ob->recalc |= OB_RECALC_DATA;
2112                                         }
2113                                 }
2114                                 if(ob->particlesystem.first)
2115                                         ob->recalc |= OB_RECALC_DATA;
2116                                 break;
2117                         case OB_CURVE:
2118                         case OB_SURF:
2119                                 cu= ob->data;
2120                                 if(cu->key) {
2121                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2122                                                 ob->recalc |= OB_RECALC_DATA;
2123                                         }
2124                                 }
2125                                 break;
2126                         case OB_FONT:
2127                                 cu= ob->data;
2128                                 if(cu->nurb.first==NULL && cu->str && cu->vfont)
2129                                         ob->recalc |= OB_RECALC_DATA;
2130                                 break;
2131                         case OB_LATTICE:
2132                                 lt= ob->data;
2133                                 if(lt->key) {
2134                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2135                                                 ob->recalc |= OB_RECALC_DATA;
2136                                         }
2137                                 }
2138                                         break;
2139                         case OB_MBALL:
2140                                 if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
2141                                 break;
2142                 }
2143                 
2144                 if(animdata_use_time(adt)) {
2145                         ob->recalc |= OB_RECALC_DATA;
2146                         adt->recalc |= ADT_RECALC_ANIM;
2147                 }
2148
2149                 if(ob->particlesystem.first) {
2150                         ParticleSystem *psys= ob->particlesystem.first;
2151
2152                         for(; psys; psys=psys->next) {
2153                                 if(psys_check_enabled(ob, psys)) {
2154                                         ob->recalc |= OB_RECALC_DATA;
2155                                         break;
2156                                 }
2157                         }
2158                 }
2159         }               
2160 }
2161 /* flag all objects that need recalc, for changes in time for example */
2162 /* do_time: make this optional because undo resets objects to their animated locations without this */
2163 void DAG_scene_update_flags(Main *bmain, Scene *scene, unsigned int lay, const short do_time)
2164 {
2165         Base *base;
2166         Object *ob;
2167         Group *group;
2168         GroupObject *go;
2169         Scene *sce_iter;
2170
2171         /* set ob flags where animated systems are */
2172         for(SETLOOPER(scene, sce_iter, base)) {
2173                 ob= base->object;
2174
2175                 if(do_time) {
2176                         /* now if DagNode were part of base, the node->lay could be checked... */
2177                         /* we do all now, since the scene_flush checks layers and clears recalc flags even */
2178                         dag_object_time_update_flags(ob);
2179                 }
2180
2181                 /* handled in next loop */
2182                 if(ob->dup_group)
2183                         ob->dup_group->id.flag |= LIB_DOIT;
2184         }
2185
2186         if(do_time) {
2187                 /* we do groups each once */
2188                 for(group= bmain->group.first; group; group= group->id.next) {
2189                         if(group->id.flag & LIB_DOIT) {
2190                                 for(go= group->gobject.first; go; go= go->next) {
2191                                         dag_object_time_update_flags(go->ob);
2192                                 }
2193                         }
2194                 }
2195         }
2196
2197         for(sce_iter= scene; sce_iter; sce_iter= sce_iter->set)
2198                 DAG_scene_flush_update(bmain, sce_iter, lay, 1);
2199         
2200         if(do_time) {
2201                 /* test: set time flag, to disable baked systems to update */
2202                 for(SETLOOPER(scene, sce_iter, base)) {
2203                         ob= base->object;
2204                         if(ob->recalc)
2205                                 ob->recalc |= OB_RECALC_TIME;
2206                 }
2207
2208                 /* hrmf... an exception to look at once, for invisible camera object we do it over */
2209                 if(scene->camera)
2210                         dag_object_time_update_flags(scene->camera);
2211         }
2212
2213         /* and store the info in groupobject */
2214         for(group= bmain->group.first; group; group= group->id.next) {
2215                 if(group->id.flag & LIB_DOIT) {
2216                         for(go= group->gobject.first; go; go= go->next) {
2217                                 go->recalc= go->ob->recalc;
2218                                 // printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
2219                         }
2220                         group->id.flag &= ~LIB_DOIT;
2221                 }
2222         }
2223         
2224 }
2225
2226 static void dag_current_scene_layers(Main *bmain, Scene **sce, unsigned int *lay)
2227 {
2228         wmWindowManager *wm;
2229         wmWindow *win;
2230
2231         /* only one scene supported currently, making more scenes work
2232            correctly requires changes beyond just the dependency graph */
2233
2234         *sce= NULL;
2235         *lay= 0;
2236
2237         if((wm= bmain->wm.first)) {
2238                 /* if we have a windowmanager, look into windows */
2239                 for(win=wm->windows.first; win; win=win->next) {
2240                         if(win->screen) {
2241                                 if(!*sce) *sce= win->screen->scene;
2242                                 *lay |= BKE_screen_visible_layers(win->screen, win->screen->scene);
2243                         }
2244                 }
2245         }
2246         else {
2247                 /* if not, use the first sce */
2248                 *sce= bmain->scene.first;
2249                 if(*sce) *lay= (*sce)->lay;
2250
2251                 /* XXX for background mode, we should get the scene
2252                    from somewhere, for the -S option, but it's in
2253                    the context, how to get it here? */
2254         }
2255 }
2256
2257 void DAG_ids_flush_update(Main *bmain, int time)
2258 {
2259         Scene *sce;
2260         unsigned int lay;
2261
2262         dag_current_scene_layers(bmain, &sce, &lay);
2263
2264         if(sce)
2265                 DAG_scene_flush_update(bmain, sce, lay, time);
2266 }
2267
2268 void DAG_on_load_update(Main *bmain, const short do_time)
2269 {
2270         Scene *scene;
2271         Base *base;
2272         Object *ob;
2273         Group *group;
2274         GroupObject *go;
2275         DagNode *node;
2276         unsigned int lay, oblay;
2277
2278         dag_current_scene_layers(bmain, &scene, &lay);
2279
2280         if(scene && scene->theDag) {
2281                 Scene *sce_iter;
2282                 /* derivedmeshes and displists are not saved to file so need to be
2283                    remade, tag them so they get remade in the scene update loop,
2284                    note armature poses or object matrices are preserved and do not
2285                    require updates, so we skip those */
2286                 dag_scene_flush_layers(scene, lay);
2287
2288                 for(SETLOOPER(scene, sce_iter, base)) {
2289                         ob= base->object;
2290                         node= (sce_iter->theDag)? dag_get_node(sce_iter->theDag, ob): NULL;
2291                         oblay= (node)? node->lay: ob->lay;
2292
2293                         if(oblay & lay) {
2294                                 if(ELEM6(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2295                                         ob->recalc |= OB_RECALC_DATA;
2296                                 if(ob->dup_group) 
2297                                         ob->dup_group->id.flag |= LIB_DOIT;
2298                         }
2299                 }
2300
2301                 for(group= bmain->group.first; group; group= group->id.next) {
2302                         if(group->id.flag & LIB_DOIT) {
2303                                 for(go= group->gobject.first; go; go= go->next) {
2304                                         if(ELEM6(go->ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2305                                                 go->ob->recalc |= OB_RECALC_DATA;
2306                                         if(go->ob->proxy_from)
2307                                                 go->ob->recalc |= OB_RECALC_OB;
2308                                 }
2309                                 
2310                                 group->id.flag &= ~LIB_DOIT;
2311                         }
2312                 }
2313
2314                 /* now tag update flags, to ensure deformers get calculated on redraw */
2315                 DAG_scene_update_flags(bmain, scene, lay, do_time);
2316         }
2317 }
2318
2319 static void dag_id_flush_update__isDependentTexture(void *userData, Object *UNUSED(ob), ID **idpoin)
2320 {
2321         struct { ID *id; int is_dependent; } *data = userData;
2322         
2323         if(*idpoin && GS((*idpoin)->name)==ID_TE) {
2324                 if (data->id == (*idpoin))
2325                         data->is_dependent = 1;
2326         }
2327 }
2328
2329 static void dag_id_flush_update(Scene *sce, ID *id)
2330 {
2331         Main *bmain= G.main;
2332         Object *obt, *ob= NULL;
2333         short idtype;
2334
2335         /* here we flush a few things before actual scene wide flush, mostly
2336            due to only objects and not other datablocks being in the depsgraph */
2337
2338         /* set flags & pointcache for object */
2339         if(GS(id->name) == ID_OB) {
2340                 ob= (Object*)id;
2341                 BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH);
2342
2343                 if(ob->recalc & OB_RECALC_DATA) {
2344                         /* all users of this ob->data should be checked */
2345                         id= ob->data;
2346
2347                         /* no point in trying in this cases */
2348                         if(id && id->us <= 1) {
2349                                 dag_editors_update(bmain, id);
2350                                 id= NULL;
2351                         }
2352                 }
2353         }
2354
2355         /* set flags & pointcache for object data */
2356         if(id) {
2357                 idtype= GS(id->name);
2358
2359                 if(ELEM7(idtype, ID_ME, ID_CU, ID_MB, ID_LA, ID_LT, ID_CA, ID_AR)) {
2360                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2361                                 if(!(ob && obt == ob) && obt->data == id) {
2362                                         obt->recalc |= OB_RECALC_DATA;
2363                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2364                                 }
2365                         }
2366                 }
2367                 
2368                 /* set flags based on textures - can influence depgraph via modifiers */
2369                 if(idtype == ID_TE) {
2370                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2371                                 struct { ID *id; int is_dependent; } data;
2372                                 data.id= id;
2373                                 data.is_dependent= 0;
2374
2375                                 modifiers_foreachIDLink(obt, dag_id_flush_update__isDependentTexture, &data);
2376                                 if (data.is_dependent)
2377                                         obt->recalc |= OB_RECALC_DATA;
2378                         }
2379                 }
2380                 
2381                 /* set flags based on ShapeKey */
2382                 if(idtype == ID_KE) {
2383                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2384                                 Key *key= ob_get_key(obt);
2385                                 if(!(ob && obt == ob) && ((ID *)key == id)) {
2386                                         obt->flag |= (OB_RECALC_OB|OB_RECALC_DATA);
2387                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2388                                 }
2389                         }
2390                 }
2391                 
2392                 /* set flags based on particle settings */
2393                 if(idtype == ID_PA) {
2394                         ParticleSystem *psys;
2395                         for(obt=bmain->object.first; obt; obt= obt->id.next)
2396                                 for(psys=obt->particlesystem.first; psys; psys=psys->next)
2397                                         if(&psys->part->id == id)
2398                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2399                 }
2400
2401                 /* update editors */
2402                 dag_editors_update(bmain, id);
2403         }
2404 }
2405
2406 void DAG_ids_flush_tagged(Main *bmain)
2407 {
2408         ListBase *lbarray[MAX_LIBARRAY];
2409         Scene *sce;
2410         unsigned int lay;
2411         int a, have_tag = 0;
2412
2413         dag_current_scene_layers(bmain, &sce, &lay);
2414
2415         if(!sce || !sce->theDag)
2416                 return;
2417
2418         /* loop over all ID types */
2419         a  = set_listbasepointers(bmain, lbarray);
2420
2421         while(a--) {
2422                 ListBase *lb = lbarray[a];
2423                 ID *id = lb->first;
2424
2425                 /* we tag based on first ID type character to avoid 
2426                    looping over all ID's in case there are no tags */
2427                 if(id && bmain->id_tag_update[id->name[0]]) {
2428                         for(; id; id=id->next) {
2429                                 if(id->flag & LIB_ID_RECALC) {
2430                                         dag_id_flush_update(sce, id);
2431                                         id->flag &= ~LIB_ID_RECALC;
2432                                 }
2433                         }
2434
2435                         have_tag = 1;
2436                 }
2437         }
2438
2439         if(have_tag) {
2440                 /* clear tags */
2441                 memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update));
2442
2443                 /* flush changes to other objects */
2444                 DAG_scene_flush_update(bmain, sce, lay, 0);
2445         }
2446 }
2447
2448 void DAG_id_tag_update(ID *id, short flag)
2449 {
2450         Main *bmain= G.main;
2451
2452         if(id==NULL) return;
2453         
2454         /* tag ID for update */
2455         id->flag |= LIB_ID_RECALC;
2456         bmain->id_tag_update[id->name[0]] = 1;
2457
2458         /* flag is for objects and particle systems */
2459         if(flag) {
2460                 Object *ob;
2461                 ParticleSystem *psys;
2462                 short idtype = GS(id->name);
2463
2464                 if(idtype == ID_OB) {
2465                         /* only quick tag */
2466                         ob = (Object*)id;
2467                         ob->recalc |= (flag & OB_RECALC_ALL);
2468                 }
2469                 else if(idtype == ID_PA) {
2470                         /* this is weak still, should be done delayed as well */
2471                         for(ob=bmain->object.first; ob; ob=ob->id.next) {
2472                                 for(psys=ob->particlesystem.first; psys; psys=psys->next) {
2473                                         if(&psys->part->id == id) {
2474                                                 ob->recalc |= (flag & OB_RECALC_ALL);
2475                                                 psys->recalc |= (flag & PSYS_RECALC);
2476                                         }
2477                                 }
2478                         }
2479                 }
2480                 else {
2481                         /* disable because this is called on various ID types automatically.
2482                          * where printing warning is not useful. for now just ignore */
2483                         /* BLI_assert(!"invalid flag for this 'idtype'"); */
2484                 }
2485         }
2486 }
2487
2488 #if 0 // UNUSED
2489 /* recursively descends tree, each node only checked once */
2490 /* node is checked to be of type object */
2491 static int parent_check_node(DagNode *node, int curtime)
2492 {
2493         DagAdjList *itA;
2494         
2495         node->lasttime= curtime;
2496         
2497         if(node->color==DAG_GRAY)
2498                 return DAG_GRAY;
2499         
2500         for(itA = node->child; itA; itA= itA->next) {
2501                 if(itA->node->type==ID_OB) {
2502                         
2503                         if(itA->node->color==DAG_GRAY)
2504                                 return DAG_GRAY;
2505
2506                         /* descend if not done */
2507                         if(itA->node->lasttime!=curtime) {
2508                                 itA->node->color= parent_check_node(itA->node, curtime);
2509                         
2510                                 if(itA->node->color==DAG_GRAY)
2511                                         return DAG_GRAY;
2512                         }
2513                 }
2514         }
2515         
2516         return DAG_WHITE;
2517 }
2518 #endif
2519
2520 /* ******************* DAG FOR ARMATURE POSE ***************** */
2521
2522 /* we assume its an armature with pose */
2523 void DAG_pose_sort(Object *ob)
2524 {
2525         bPose *pose= ob->pose;
2526         bPoseChannel *pchan;
2527         bConstraint *con;
2528         DagNode *node;
2529         DagNode *node2, *node3;
2530         DagNode *rootnode;
2531         DagForest *dag;
2532         DagNodeQueue *nqueue;
2533         DagAdjList *itA;
2534         ListBase tempbase;
2535         int skip = 0;
2536         
2537         dag = dag_init();
2538         ugly_hack_sorry= 0;     // no ID structs
2539
2540         rootnode = dag_add_node(dag, NULL);     // node->ob becomes NULL
2541         
2542         /* we add the hierarchy and the constraints */
2543         for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2544                 int addtoroot = 1;
2545                 
2546                 node = dag_get_node(dag, pchan);
2547                 
2548                 if(pchan->parent) {
2549                         node2 = dag_get_node(dag, pchan->parent);
2550                         dag_add_relation(dag, node2, node, 0, "Parent Relation");
2551                         addtoroot = 0;
2552                 }
2553                 for (con = pchan->constraints.first; con; con=con->next) {
2554                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2555                         ListBase targets = {NULL, NULL};
2556                         bConstraintTarget *ct;
2557                         
2558                         if (cti && cti->get_constraint_targets) {
2559                                 cti->get_constraint_targets(con, &targets);
2560                                 
2561                                 for (ct= targets.first; ct; ct= ct->next) {
2562                                         if (ct->tar==ob && ct->subtarget[0]) {
2563                                                 bPoseChannel *target= get_pose_channel(ob->pose, ct->subtarget);
2564                                                 if (target) {
2565                                                         node2= dag_get_node(dag, target);
2566                                                         dag_add_relation(dag, node2, node, 0, "Pose Constraint");
2567                                                         
2568                                                         if (con->type==CONSTRAINT_TYPE_KINEMATIC) {
2569                                                                 bKinematicConstraint *data = (bKinematicConstraint *)con->data;
2570                                                                 bPoseChannel *parchan;
2571                                                                 int segcount= 0;
2572                                                                 
2573                                                                 /* exclude tip from chain? */
2574                                                                 if(!(data->flag & CONSTRAINT_IK_TIP))
2575                                                                         parchan= pchan->parent;
2576                                                                 else
2577                                                                         parchan= pchan;
2578                                                                 
2579                                                                 /* Walk to the chain's root */
2580                                                                 while (parchan) {
2581                                                                         node3= dag_get_node(dag, parchan);
2582                                                                         dag_add_relation(dag, node2, node3, 0, "IK Constraint");
2583                                                                         
2584                                                                         segcount++;
2585                                                                         if (segcount==data->rootbone || segcount>255) break; // 255 is weak
2586                                                                         parchan= parchan->parent;
2587                                                                 }
2588                                                         }
2589                                                 }
2590                                         }
2591                                 }
2592                                 
2593                                 if (cti->flush_constraint_targets)
2594                                         cti->flush_constraint_targets(con, &targets, 1);
2595                         }
2596                 }
2597                 if (addtoroot == 1 ) {
2598                         dag_add_relation(dag, rootnode, node, 0, "Root Bone Relation");
2599                 }
2600         }
2601
2602         dag_check_cycle(dag);
2603         
2604         /* now we try to sort... */
2605         tempbase.first= tempbase.last= NULL;
2606
2607         nqueue = queue_create(DAGQUEUEALLOC);
2608         
2609         /* tag nodes unchecked */
2610         for(node = dag->DagNode.first; node; node= node->next) 
2611                 node->color = DAG_WHITE;
2612         
2613         node = dag->DagNode.first;
2614         
2615         node->color = DAG_GRAY;
2616         push_stack(nqueue, node);  
2617         
2618         while(nqueue->count) {
2619                 
2620                 skip = 0;
2621                 node = get_top_node_queue(nqueue);
2622                 
2623                 itA = node->child;
2624                 while(itA != NULL) {
2625                         if(itA->node->color == DAG_WHITE) {
2626                                 itA->node->color = DAG_GRAY;
2627                                 push_stack(nqueue,itA->node);
2628                                 skip = 1;
2629                                 break;
2630                         } 
2631                         itA = itA->next;
2632                 }                       
2633                 
2634                 if (!skip) {
2635                         if (node) {
2636                                 node = pop_queue(nqueue);
2637                                 if (node->ob == NULL)   // we are done
2638                                         break ;
2639                                 node->color = DAG_BLACK;
2640                                 
2641                                 /* put node in new list */
2642                                 BLI_remlink(&pose->chanbase, node->ob);
2643                                 BLI_addhead(&tempbase, node->ob);
2644                         }       
2645                 }
2646         }
2647         
2648         // temporal correction for circular dependancies
2649         while(pose->chanbase.first) {
2650                 pchan= pose->chanbase.first;
2651                 BLI_remlink(&pose->chanbase, pchan);
2652                 BLI_addhead(&tempbase, pchan);
2653
2654                 printf("cyclic %s\n", pchan->name);
2655         }
2656         
2657         pose->chanbase = tempbase;
2658         queue_delete(nqueue);
2659         
2660 //      printf("\nordered\n");
2661 //      for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2662 //              printf(" %s\n", pchan->name);
2663 //      }
2664         
2665         free_forest( dag );
2666         MEM_freeN( dag );
2667         
2668         ugly_hack_sorry= 1;
2669 }
2670
2671
2672