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