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