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