- change max threads from 8 to 64, need to keep an eye on stack memory use here.
[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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, 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= ob->lay;
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
1929         for(base= sce->base.first; base; base= base->next) {
1930                 node= dag_get_node(sce->theDag, base->object);
1931                 if(node)
1932                         node->scelay= base->object->lay;
1933                 else
1934                         node->scelay= 0;
1935         }
1936
1937         for(itA = firstnode->child; itA; itA= itA->next)
1938                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
1939                         flush_layer_node(sce, itA->node, lasttime);
1940         
1941         /* then we use the relationships + layer info to flush update events */
1942         sce->theDag->time++;    // so we know which nodes were accessed
1943         lasttime= sce->theDag->time;
1944         for(itA = firstnode->child; itA; itA= itA->next)
1945                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)
1946                         flush_update_node(itA->node, lay, lasttime);
1947
1948         /* if update is not due to time change, do pointcache clears */
1949         if(!time) {
1950                 sce->theDag->time++;    // so we know which nodes were accessed
1951                 lasttime= sce->theDag->time;
1952                 for(itA = firstnode->child; itA; itA= itA->next) {
1953                         if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)  {
1954                                 ob= (Object*)(itA->node->ob);
1955
1956                                 if(ob->recalc & OB_RECALC) {
1957                                         if(BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH))
1958                                                 ob->recalc |= OB_RECALC_DATA;
1959
1960                                         flush_pointcache_reset(sce, itA->node, lasttime, 1);
1961                                 }
1962                                 else
1963                                         flush_pointcache_reset(sce, itA->node, lasttime, 0);
1964                         }
1965                 }
1966         }
1967 }
1968
1969 static int object_modifiers_use_time(Object *ob)
1970 {
1971         ModifierData *md;
1972
1973         for (md=ob->modifiers.first; md; md=md->next)
1974                 if (modifier_dependsOnTime(md))
1975                         return 1;
1976
1977         return 0;
1978 }
1979
1980 static short animdata_use_time(AnimData *adt)
1981 {
1982         NlaTrack *nlt;
1983         
1984         if(adt==NULL) return 0;
1985         
1986         /* check action - only if assigned, and it has anim curves */
1987         if (adt->action && adt->action->curves.first)
1988                 return 1;
1989         
1990         /* check NLA tracks + strips */
1991         for (nlt= adt->nla_tracks.first; nlt; nlt= nlt->next) {
1992                 if (nlt->strips.first)
1993                         return 1;
1994         }
1995         
1996         return 0;
1997 }
1998
1999 static void dag_object_time_update_flags(Object *ob)
2000 {
2001         if(ob->constraints.first) {
2002                 bConstraint *con;
2003                 for (con = ob->constraints.first; con; con=con->next) {
2004                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2005                         ListBase targets = {NULL, NULL};
2006                         bConstraintTarget *ct;
2007                         
2008                         if (cti && cti->get_constraint_targets) {
2009                                 cti->get_constraint_targets(con, &targets);
2010                                 
2011                                 for (ct= targets.first; ct; ct= ct->next) {
2012                                         if (ct->tar) {
2013                                                 ob->recalc |= OB_RECALC_OB;
2014                                                 break;
2015                                         }
2016                                 }
2017                                 
2018                                 if (cti->flush_constraint_targets)
2019                                         cti->flush_constraint_targets(con, &targets, 1);
2020                         }
2021                 }
2022         }
2023         
2024         if(ob->parent) {
2025                 /* motion path or bone child */
2026                 if(ob->parent->type==OB_CURVE || ob->parent->type==OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
2027         }
2028         
2029 #if 0 // XXX old animation system
2030         if(ob->nlastrips.first) {
2031                 if(ob->dup_group) {
2032                         bActionStrip *strip;
2033                         /* this case is for groups with nla, whilst nla target has no action or nla */
2034                         for(strip= ob->nlastrips.first; strip; strip= strip->next) {
2035                                 if(strip->object)
2036                                         strip->object->recalc |= OB_RECALC;
2037                         }
2038                 }
2039         }
2040 #endif // XXX old animation system
2041         
2042         if(animdata_use_time(ob->adt)) {
2043                 ob->recalc |= OB_RECALC;
2044                 ob->adt->recalc |= ADT_RECALC_ANIM;
2045         }
2046         
2047         if((ob->adt) && (ob->type==OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA;
2048         
2049         if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
2050         if((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->recalc |= OB_RECALC_DATA;
2051         
2052         {
2053                 AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
2054                 Mesh *me;
2055                 Curve *cu;
2056                 Lattice *lt;
2057                 
2058                 switch(ob->type) {
2059                         case OB_MESH:
2060                                 me= ob->data;
2061                                 if(me->key) {
2062                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2063                                                 ob->recalc |= OB_RECALC_DATA;
2064                                         }
2065                                 }
2066                                 if(ob->particlesystem.first)
2067                                         ob->recalc |= OB_RECALC_DATA;
2068                                 break;
2069                         case OB_CURVE:
2070                         case OB_SURF:
2071                                 cu= ob->data;
2072                                 if(cu->key) {
2073                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2074                                                 ob->recalc |= OB_RECALC_DATA;
2075                                         }
2076                                 }
2077                                 break;
2078                         case OB_FONT:
2079                                 cu= ob->data;
2080                                 if(cu->nurb.first==NULL && cu->str && cu->vfont)
2081                                         ob->recalc |= OB_RECALC_DATA;
2082                                 break;
2083                         case OB_LATTICE:
2084                                 lt= ob->data;
2085                                 if(lt->key) {
2086                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2087                                                 ob->recalc |= OB_RECALC_DATA;
2088                                         }
2089                                 }
2090                                         break;
2091                         case OB_MBALL:
2092                                 if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
2093                                 break;
2094                 }
2095                 
2096                 if(animdata_use_time(adt)) {
2097                         ob->recalc |= OB_RECALC_DATA;
2098                         adt->recalc |= ADT_RECALC_ANIM;
2099                 }
2100
2101                 if(ob->particlesystem.first) {
2102                         ParticleSystem *psys= ob->particlesystem.first;
2103
2104                         for(; psys; psys=psys->next) {
2105                                 if(psys_check_enabled(ob, psys)) {
2106                                         ob->recalc |= OB_RECALC_DATA;
2107                                         break;
2108                                 }
2109                         }
2110                 }
2111         }               
2112 }
2113 /* flag all objects that need recalc, for changes in time for example */
2114 void DAG_scene_update_flags(Scene *scene, unsigned int lay)
2115 {
2116         Base *base;
2117         Object *ob;
2118         Group *group;
2119         GroupObject *go;
2120         Scene *sce;
2121         
2122         /* set ob flags where animated systems are */
2123         for(SETLOOPER(scene, base)) {
2124                 ob= base->object;
2125                 
2126                 /* now if DagNode were part of base, the node->lay could be checked... */
2127                 /* we do all now, since the scene_flush checks layers and clears recalc flags even */
2128                 dag_object_time_update_flags(ob);
2129                 
2130                 /* handled in next loop */
2131                 if(ob->dup_group) 
2132                         ob->dup_group->id.flag |= LIB_DOIT;
2133         }       
2134         
2135         /* we do groups each once */
2136         for(group= G.main->group.first; group; group= group->id.next) {
2137                 if(group->id.flag & LIB_DOIT) {
2138                         for(go= group->gobject.first; go; go= go->next) {
2139                                 dag_object_time_update_flags(go->ob);
2140                         }
2141                 }
2142         }
2143         
2144         for(sce= scene; sce; sce= sce->set)
2145                 DAG_scene_flush_update(sce, lay, 1);
2146         
2147         /* test: set time flag, to disable baked systems to update */
2148         for(SETLOOPER(scene, base)) {
2149                 ob= base->object;
2150                 if(ob->recalc)
2151                         ob->recalc |= OB_RECALC_TIME;
2152         }
2153         
2154         /* hrmf... an exception to look at once, for invisible camera object we do it over */
2155         if(scene->camera)
2156                 dag_object_time_update_flags(scene->camera);
2157         
2158         /* and store the info in groupobject */
2159         for(group= G.main->group.first; group; group= group->id.next) {
2160                 if(group->id.flag & LIB_DOIT) {
2161                         for(go= group->gobject.first; go; go= go->next) {
2162                                 go->recalc= go->ob->recalc;
2163                                 // printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
2164                         }
2165                         group->id.flag &= ~LIB_DOIT;
2166                 }
2167         }
2168         
2169 }
2170
2171 static void dag_current_scene_layers(Main *bmain, Scene **sce, unsigned int *lay)
2172 {
2173         wmWindowManager *wm;
2174         wmWindow *win;
2175
2176         /* only one scene supported currently, making more scenes work
2177            correctly requires changes beyond just the dependency graph */
2178
2179         *sce= NULL;
2180         *lay= 0;
2181
2182         if((wm= bmain->wm.first)) {
2183                 /* if we have a windowmanager, look into windows */
2184                 for(win=wm->windows.first; win; win=win->next) {
2185                         if(win->screen) {
2186                                 if(!*sce) *sce= win->screen->scene;
2187                                 *lay |= BKE_screen_visible_layers(win->screen, win->screen->scene);
2188                         }
2189                 }
2190         }
2191         else {
2192                 /* if not, use the first sce */
2193                 *sce= bmain->scene.first;
2194                 if(*sce) *lay= (*sce)->lay;
2195
2196                 /* XXX for background mode, we should get the scen
2197                    from somewhere, for the -S option, but it's in
2198                    the context, how to get it here? */
2199         }
2200 }
2201
2202 void DAG_ids_flush_update(int time)
2203 {
2204         Main *bmain= G.main;
2205         Scene *sce;
2206         unsigned int lay;
2207
2208         dag_current_scene_layers(bmain, &sce, &lay);
2209
2210         if(sce)
2211                 DAG_scene_flush_update(sce, lay, time);
2212 }
2213
2214 void DAG_id_flush_update(ID *id, short flag)
2215 {
2216         Main *bmain= G.main;
2217         Scene *sce;
2218         Object *obt, *ob= NULL;
2219         short idtype;
2220         unsigned int lay;
2221
2222         dag_current_scene_layers(bmain, &sce, &lay);
2223
2224         if(!id || !sce || !sce->theDag)
2225                 return;
2226
2227         /* set flags & pointcache for object */
2228         if(GS(id->name) == ID_OB) {
2229                 ob= (Object*)id;
2230                 ob->recalc |= (flag & OB_RECALC);
2231                 BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH);
2232
2233                 if(flag & OB_RECALC_DATA) {
2234                         /* all users of this ob->data should be checked */
2235                         id= ob->data;
2236
2237                         /* no point in trying in this cases */
2238                         if(!id || id->us <= 1)
2239                                 id= NULL;
2240                         /* curves and surfaces only need to mark one object, since
2241                            otherwise cu->displist would be computed multiple times */
2242                         else if(ob->type==OB_CURVE || ob->type==OB_SURF)
2243                                 id= NULL;
2244                         /* also for locked shape keys we make an exception */
2245                         else if(ob_get_key(ob) && (ob->shapeflag & OB_SHAPE_LOCK))
2246                                 id= NULL;
2247                 }
2248         }
2249
2250         /* set flags & pointcache for object data */
2251         if(id) {
2252                 idtype= GS(id->name);
2253
2254                 if(ELEM7(idtype, ID_ME, ID_CU, ID_MB, ID_LA, ID_LT, ID_CA, ID_AR)) {
2255                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2256                                 if(!(ob && obt == ob) && obt->data == id) {
2257                                         obt->recalc |= OB_RECALC_DATA;
2258                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2259
2260                                         /* for these we only flag one object, otherwise cu->displist
2261                                            would be computed multiple times */
2262                                         if(obt->type==OB_CURVE || obt->type==OB_SURF)
2263                                                 break;
2264                                 }
2265                         }
2266                 }
2267                 
2268                 /* set flags based on ShapeKey */
2269                 if(idtype == ID_KE) {
2270                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2271                                 Key *key= ob_get_key(obt);
2272                                 if(!(ob && obt == ob) && ((ID *)key == id)) {
2273                                         obt->flag |= (OB_RECALC|OB_RECALC_DATA);
2274                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2275                                 }
2276                         }
2277                 }
2278                 
2279                 /* set flags based on particle settings */
2280                 if(idtype == ID_PA) {
2281                         ParticleSystem *psys;
2282                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2283                                 for(psys=obt->particlesystem.first; psys; psys=psys->next) {
2284                                         if(&psys->part->id == id) {
2285                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2286                                                 obt->recalc |= (flag & OB_RECALC);
2287                                                 psys->recalc |= (flag & PSYS_RECALC);
2288                                         }
2289                                 }
2290                         }
2291                 }
2292
2293                 /* update editors */
2294                 dag_editors_update(bmain, id);
2295         }
2296
2297         /* flush to other objects that depend on this one */
2298         DAG_scene_flush_update(sce, lay, 0);
2299 }
2300
2301 /* recursively descends tree, each node only checked once */
2302 /* node is checked to be of type object */
2303 static int parent_check_node(DagNode *node, int curtime)
2304 {
2305         DagAdjList *itA;
2306         
2307         node->lasttime= curtime;
2308         
2309         if(node->color==DAG_GRAY)
2310                 return DAG_GRAY;
2311         
2312         for(itA = node->child; itA; itA= itA->next) {
2313                 if(itA->node->type==ID_OB) {
2314                         
2315                         if(itA->node->color==DAG_GRAY)
2316                                 return DAG_GRAY;
2317
2318                         /* descend if not done */
2319                         if(itA->node->lasttime!=curtime) {
2320                                 itA->node->color= parent_check_node(itA->node, curtime);
2321                         
2322                                 if(itA->node->color==DAG_GRAY)
2323                                         return DAG_GRAY;
2324                         }
2325                 }
2326         }
2327         
2328         return DAG_WHITE;
2329 }
2330
2331 /* all nodes that influence this object get tagged, for calculating the exact
2332    position of this object at a given timeframe */
2333 void DAG_id_update_flags(ID *id)
2334 {
2335         Main *bmain= G.main;
2336         Scene *sce;
2337         DagNode *node;
2338         DagAdjList *itA;
2339         Object *ob;
2340         unsigned int lay;
2341
2342         dag_current_scene_layers(bmain, &sce, &lay);
2343
2344         if(!id || !sce || !sce->theDag)
2345                 return;
2346         
2347         /* objects only currently */
2348         if(GS(id->name) != ID_OB)
2349                 return;
2350         
2351         ob= (Object*)id;
2352         
2353         /* tag nodes unchecked */
2354         for(node = sce->theDag->DagNode.first; node; node= node->next) 
2355                 node->color = DAG_WHITE;
2356         
2357         node= dag_find_node(sce->theDag, ob);
2358         
2359         /* object not in scene? then handle group exception. needs to be dagged once too */
2360         if(node==NULL) {
2361                 Group *group= NULL;
2362                 while( (group = find_group(ob, group)) ) {
2363                         GroupObject *go;
2364                         /* primitive; tag all... this call helps building groups for particles */
2365                         for(go= group->gobject.first; go; go= go->next)
2366                                 go->ob->recalc= OB_RECALC;
2367                 }
2368         }
2369         else {
2370                 
2371                 node->color = DAG_GRAY;
2372                 
2373                 sce->theDag->time++;
2374                 node= sce->theDag->DagNode.first;
2375                 for(itA = node->child; itA; itA= itA->next) {
2376                         if(itA->node->type==ID_OB && itA->node->lasttime!=sce->theDag->time)
2377                                 itA->node->color= parent_check_node(itA->node, sce->theDag->time);
2378                 }
2379                 
2380                 /* set recalcs and flushes */
2381                 DAG_scene_update_flags(sce, lay);
2382                 
2383                 /* now we clear recalcs, unless color is set */
2384                 for(node = sce->theDag->DagNode.first; node; node= node->next) {
2385                         if(node->type==ID_OB && node->color==DAG_WHITE) {
2386                                 Object *ob= node->ob;
2387                                 ob->recalc= 0;
2388                         }
2389                 }
2390         }
2391 }
2392
2393 /* ******************* DAG FOR ARMATURE POSE ***************** */
2394
2395 /* we assume its an armature with pose */
2396 void DAG_pose_sort(Object *ob)
2397 {
2398         bPose *pose= ob->pose;
2399         bPoseChannel *pchan;
2400         bConstraint *con;
2401         DagNode *node;
2402         DagNode *node2, *node3;
2403         DagNode *rootnode;
2404         DagForest *dag;
2405         DagNodeQueue *nqueue;
2406         DagAdjList *itA;
2407         ListBase tempbase;
2408         int skip = 0;
2409         
2410         dag = dag_init();
2411         ugly_hack_sorry= 0;     // no ID structs
2412
2413         rootnode = dag_add_node(dag, NULL);     // node->ob becomes NULL
2414         
2415         /* we add the hierarchy and the constraints */
2416         for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2417                 int addtoroot = 1;
2418                 
2419                 node = dag_get_node(dag, pchan);
2420                 
2421                 if(pchan->parent) {
2422                         node2 = dag_get_node(dag, pchan->parent);
2423                         dag_add_relation(dag, node2, node, 0, "Parent Relation");
2424                         addtoroot = 0;
2425                 }
2426                 for (con = pchan->constraints.first; con; con=con->next) {
2427                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2428                         ListBase targets = {NULL, NULL};
2429                         bConstraintTarget *ct;
2430                         
2431                         if (cti && cti->get_constraint_targets) {
2432                                 cti->get_constraint_targets(con, &targets);
2433                                 
2434                                 for (ct= targets.first; ct; ct= ct->next) {
2435                                         if (ct->tar==ob && ct->subtarget[0]) {
2436                                                 bPoseChannel *target= get_pose_channel(ob->pose, ct->subtarget);
2437                                                 if (target) {
2438                                                         node2= dag_get_node(dag, target);
2439                                                         dag_add_relation(dag, node2, node, 0, "Pose Constraint");
2440                                                         
2441                                                         if (con->type==CONSTRAINT_TYPE_KINEMATIC) {
2442                                                                 bKinematicConstraint *data = (bKinematicConstraint *)con->data;
2443                                                                 bPoseChannel *parchan;
2444                                                                 int segcount= 0;
2445                                                                 
2446                                                                 /* exclude tip from chain? */
2447                                                                 if(!(data->flag & CONSTRAINT_IK_TIP))
2448                                                                         parchan= pchan->parent;
2449                                                                 else
2450                                                                         parchan= pchan;
2451                                                                 
2452                                                                 /* Walk to the chain's root */
2453                                                                 while (parchan) {
2454                                                                         node3= dag_get_node(dag, parchan);
2455                                                                         dag_add_relation(dag, node2, node3, 0, "IK Constraint");
2456                                                                         
2457                                                                         segcount++;
2458                                                                         if (segcount==data->rootbone || segcount>255) break; // 255 is weak
2459                                                                         parchan= parchan->parent;
2460                                                                 }
2461                                                         }
2462                                                 }
2463                                         }
2464                                 }
2465                                 
2466                                 if (cti->flush_constraint_targets)
2467                                         cti->flush_constraint_targets(con, &targets, 1);
2468                         }
2469                 }
2470                 if (addtoroot == 1 ) {
2471                         dag_add_relation(dag, rootnode, node, 0, "Root Bone Relation");
2472                 }
2473         }
2474
2475         dag_check_cycle(dag);
2476         
2477         /* now we try to sort... */
2478         tempbase.first= tempbase.last= NULL;
2479
2480         nqueue = queue_create(DAGQUEUEALLOC);
2481         
2482         /* tag nodes unchecked */
2483         for(node = dag->DagNode.first; node; node= node->next) 
2484                 node->color = DAG_WHITE;
2485         
2486         node = dag->DagNode.first;
2487         
2488         node->color = DAG_GRAY;
2489         push_stack(nqueue, node);  
2490         
2491         while(nqueue->count) {
2492                 
2493                 skip = 0;
2494                 node = get_top_node_queue(nqueue);
2495                 
2496                 itA = node->child;
2497                 while(itA != NULL) {
2498                         if((itA->node->color == DAG_WHITE) ) {
2499                                 itA->node->color = DAG_GRAY;
2500                                 push_stack(nqueue,itA->node);
2501                                 skip = 1;
2502                                 break;
2503                         } 
2504                         itA = itA->next;
2505                 }                       
2506                 
2507                 if (!skip) {
2508                         if (node) {
2509                                 node = pop_queue(nqueue);
2510                                 if (node->ob == NULL)   // we are done
2511                                         break ;
2512                                 node->color = DAG_BLACK;
2513                                 
2514                                 /* put node in new list */
2515                                 BLI_remlink(&pose->chanbase, node->ob);
2516                                 BLI_addhead(&tempbase, node->ob);
2517                         }       
2518                 }
2519         }
2520         
2521         // temporal correction for circular dependancies
2522         while(pose->chanbase.first) {
2523                 pchan= pose->chanbase.first;
2524                 BLI_remlink(&pose->chanbase, pchan);
2525                 BLI_addhead(&tempbase, pchan);
2526
2527                 printf("cyclic %s\n", pchan->name);
2528         }
2529         
2530         pose->chanbase = tempbase;
2531         queue_delete(nqueue);
2532         
2533 //      printf("\nordered\n");
2534 //      for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2535 //              printf(" %s\n", pchan->name);
2536 //      }
2537         
2538         free_forest( dag );
2539         MEM_freeN( dag );
2540         
2541         ugly_hack_sorry= 1;
2542 }
2543
2544
2545