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