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