converted more mixed tab/space indentations to tabs. only whitespace changes.
[blender.git] / source / blender / blenkernel / intern / depsgraph.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2004 Blender Foundation.
21  * All rights reserved.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/depsgraph.c
29  *  \ingroup bke
30  */
31
32  
33 #include <stdio.h>
34 #include <string.h>
35 #include <math.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_winstuff.h"
40 #include "BLI_utildefines.h"
41 #include "BLI_ghash.h"
42
43 #include "DNA_anim_types.h"
44 #include "DNA_camera_types.h"
45 #include "DNA_group_types.h"
46 #include "DNA_lattice_types.h"
47 #include "DNA_key_types.h"
48 #include "DNA_material_types.h"
49 #include "DNA_mesh_types.h"
50 #include "DNA_node_types.h"
51 #include "DNA_scene_types.h"
52 #include "DNA_screen_types.h"
53 #include "DNA_windowmanager_types.h"
54
55 #include "BKE_animsys.h"
56 #include "BKE_action.h"
57 #include "BKE_effect.h"
58 #include "BKE_fcurve.h"
59 #include "BKE_global.h"
60 #include "BKE_group.h"
61 #include "BKE_key.h"
62 #include "BKE_library.h"
63 #include "BKE_main.h"
64 #include "BKE_node.h"
65 #include "BKE_mball.h"
66 #include "BKE_modifier.h"
67 #include "BKE_object.h"
68 #include "BKE_particle.h"
69 #include "BKE_pointcache.h"
70 #include "BKE_scene.h"
71 #include "BKE_screen.h"
72 #include "BKE_utildefines.h"
73
74 #include "depsgraph_private.h"
75  
76 /* Queue and stack operations for dag traversal 
77  *
78  * the queue store a list of freenodes to avoid successives alloc/dealloc
79  */
80
81 DagNodeQueue * queue_create (int slots) 
82 {
83         DagNodeQueue * queue;
84         DagNodeQueueElem * elem;
85         int i;
86         
87         queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
88         queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
89         queue->count = 0;
90         queue->maxlevel = 0;
91         queue->first = queue->last = NULL;
92         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3");
93         elem->node = NULL;
94         elem->next = NULL;
95         queue->freenodes->first = queue->freenodes->last = elem;
96         
97         for (i = 1; i <slots;i++) {
98                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4");
99                 elem->node = NULL;
100                 elem->next = NULL;
101                 queue->freenodes->last->next = elem;
102                 queue->freenodes->last = elem;
103         }
104         queue->freenodes->count = slots;
105         return queue;
106 }
107
108 void queue_raz(DagNodeQueue *queue)
109 {
110         DagNodeQueueElem * elem;
111         
112         elem = queue->first;
113         if (queue->freenodes->last)
114                 queue->freenodes->last->next = elem;
115         else
116                 queue->freenodes->first = queue->freenodes->last = elem;
117         
118         elem->node = NULL;
119         queue->freenodes->count++;
120         while (elem->next) {
121                 elem = elem->next;
122                 elem->node = NULL;
123                 queue->freenodes->count++;
124         }
125         queue->freenodes->last = elem;
126         queue->count = 0;
127 }
128
129 void queue_delete(DagNodeQueue *queue)
130 {
131         DagNodeQueueElem * elem;
132         DagNodeQueueElem * temp;
133         
134         elem = queue->first;
135         while (elem) {
136                 temp = elem;
137                 elem = elem->next;
138                 MEM_freeN(temp);
139         }
140         
141         elem = queue->freenodes->first;
142         while (elem) {
143                 temp = elem;
144                 elem = elem->next;
145                 MEM_freeN(temp);
146         }
147         
148         MEM_freeN(queue->freenodes);                    
149         MEM_freeN(queue);                       
150 }
151
152 /* insert in queue, remove in front */
153 void push_queue(DagNodeQueue *queue, DagNode *node)
154 {
155         DagNodeQueueElem * elem;
156         int i;
157
158         if (node == NULL) {
159                 fprintf(stderr,"pushing null node \n");
160                 return;
161         }
162         /*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->count);*/
163
164         elem = queue->freenodes->first;
165         if (elem != NULL) {
166                 queue->freenodes->first = elem->next;
167                 if ( queue->freenodes->last == elem) {
168                         queue->freenodes->last = NULL;
169                         queue->freenodes->first = NULL;
170                 }
171                 queue->freenodes->count--;
172         } else { /* alllocating more */         
173                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
174                 elem->node = NULL;
175                 elem->next = NULL;
176                 queue->freenodes->first = queue->freenodes->last = elem;
177
178                 for (i = 1; i <DAGQUEUEALLOC;i++) {
179                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
180                         elem->node = NULL;
181                         elem->next = NULL;
182                         queue->freenodes->last->next = elem;
183                         queue->freenodes->last = elem;
184                 }
185                 queue->freenodes->count = DAGQUEUEALLOC;
186                         
187                 elem = queue->freenodes->first; 
188                 queue->freenodes->first = elem->next;   
189         }
190         elem->next = NULL;
191         elem->node = node;
192         if (queue->last != NULL)
193                 queue->last->next = elem;
194         queue->last = elem;
195         if (queue->first == NULL) {
196                 queue->first = elem;
197         }
198         queue->count++;
199 }
200
201
202 /* insert in front, remove in front */
203 void push_stack(DagNodeQueue *queue, DagNode *node)
204 {
205         DagNodeQueueElem * elem;
206         int i;
207
208         elem = queue->freenodes->first; 
209         if (elem != NULL) {
210                 queue->freenodes->first = elem->next;
211                 if ( queue->freenodes->last == elem) {
212                         queue->freenodes->last = NULL;
213                         queue->freenodes->first = NULL;
214                 }
215                 queue->freenodes->count--;
216         } else { /* alllocating more */
217                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
218                 elem->node = NULL;
219                 elem->next = NULL;
220                 queue->freenodes->first = queue->freenodes->last = elem;
221
222                 for (i = 1; i <DAGQUEUEALLOC;i++) {
223                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
224                         elem->node = NULL;
225                         elem->next = NULL;
226                         queue->freenodes->last->next = elem;
227                         queue->freenodes->last = elem;
228                 }
229                 queue->freenodes->count = DAGQUEUEALLOC;
230                         
231                 elem = queue->freenodes->first; 
232                 queue->freenodes->first = elem->next;   
233         }
234         elem->next = queue->first;
235         elem->node = node;
236         queue->first = elem;
237         if (queue->last == NULL)
238                 queue->last = elem;
239         queue->count++;
240 }
241
242
243 DagNode * pop_queue(DagNodeQueue *queue)
244 {
245         DagNodeQueueElem * elem;
246         DagNode *node;
247
248         elem = queue->first;
249         if (elem) {
250                 queue->first = elem->next;
251                 if (queue->last == elem) {
252                         queue->last=NULL;
253                         queue->first=NULL;
254                 }
255                 queue->count--;
256                 if (queue->freenodes->last)
257                         queue->freenodes->last->next=elem;
258                 queue->freenodes->last=elem;
259                 if (queue->freenodes->first == NULL)
260                         queue->freenodes->first=elem;
261                 node = elem->node;
262                 elem->node = NULL;
263                 elem->next = NULL;
264                 queue->freenodes->count++;
265                 return node;
266         } else {
267                 fprintf(stderr,"return null \n");
268                 return NULL;
269         }
270 }
271
272 void    *pop_ob_queue(struct DagNodeQueue *queue) {
273         return(pop_queue(queue)->ob);
274 }
275
276 DagNode * get_top_node_queue(DagNodeQueue *queue) 
277 {
278         return queue->first->node;
279 }
280
281 int             queue_count(struct DagNodeQueue *queue){
282         return queue->count;
283 }
284
285
286 DagForest *dag_init(void)
287 {
288         DagForest *forest;
289         /* use callocN to init all zero */
290         forest = MEM_callocN(sizeof(DagForest),"DAG root");
291         return forest;
292 }
293
294 /* isdata = object data... */
295 // XXX this needs to be extended to be more flexible (so that not only objects are evaluated via depsgraph)...
296 static void dag_add_driver_relation(AnimData *adt, DagForest *dag, DagNode *node, int isdata)
297 {
298         FCurve *fcu;
299         DagNode *node1;
300         
301         for (fcu= adt->drivers.first; fcu; fcu= fcu->next) {
302                 ChannelDriver *driver= fcu->driver;
303                 DriverVar *dvar;
304                 
305                 /* loop over variables to get the target relationships */
306                 for (dvar= driver->variables.first; dvar; dvar= dvar->next) {
307                         /* only used targets */
308                         DRIVER_TARGETS_USED_LOOPER(dvar) 
309                         {
310                                 if (dtar->id) {
311                                         // FIXME: other data types need to be added here so that they can work!
312                                         if (GS(dtar->id->name)==ID_OB) {
313                                                 Object *ob= (Object *)dtar->id;
314                                                 
315                                                 /* normal channel-drives-channel */
316                                                 node1 = dag_get_node(dag, dtar->id);
317                                                 
318                                                 /* check if bone... */
319                                                 if ((ob->type==OB_ARMATURE) && 
320                                                         ( ((dtar->rna_path) && strstr(dtar->rna_path, "pose.bones[")) || 
321                                                           ((dtar->flag & DTAR_FLAG_STRUCT_REF) && (dtar->pchan_name[0])) )) 
322                                                 {
323                                                         dag_add_relation(dag, node1, node, isdata?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver");
324                                                 }
325                                                 /* check if ob data */
326                                                 else if (dtar->rna_path && strstr(dtar->rna_path, "data."))
327                                                         dag_add_relation(dag, node1, node, isdata?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver");
328                                                 /* normal */
329                                                 else
330                                                         dag_add_relation(dag, node1, node, isdata?DAG_RL_OB_DATA:DAG_RL_OB_OB, "Driver");
331                                         }
332                                 }
333                         }
334                         DRIVER_TARGETS_LOOPER_END
335                 }
336         }
337 }
338
339 static void dag_add_collision_field_relation(DagForest *dag, Scene *scene, Object *ob, DagNode *node)
340 {
341         Base *base;
342         DagNode *node2;
343
344         // would be nice to have a list of colliders here
345         // so for now walk all objects in scene check 'same layer rule'
346         for(base = scene->base.first; base; base= base->next) {
347                 if((base->lay & ob->lay) && base->object->pd) {
348                         Object *ob1= base->object;
349                         if((ob1->pd->deflect || ob1->pd->forcefield) && (ob1 != ob))  {
350                                 node2 = dag_get_node(dag, ob1);                                 
351                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Field Collision");
352                         }
353                 }
354         }
355 }
356
357 static void build_dag_object(DagForest *dag, DagNode *scenenode, Scene *scene, Object *ob, int mask)
358 {
359         bConstraint *con;
360         DagNode * node;
361         DagNode * node2;
362         DagNode * node3;
363         Key *key;
364         ParticleSystem *psys;
365         int addtoroot= 1;
366         
367         node = dag_get_node(dag, ob);
368         
369         if ((ob->data) && (mask&DAG_RL_DATA)) {
370                 node2 = dag_get_node(dag,ob->data);
371                 dag_add_relation(dag,node,node2,DAG_RL_DATA, "Object-Data Relation");
372                 node2->first_ancestor = ob;
373                 node2->ancestor_count += 1;
374         }
375         
376         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;
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;
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         if(sce->camera) {
1910                 node= dag_get_node(sce->theDag, sce->camera);
1911                 node->scelay |= lay;
1912         }
1913
1914 #ifdef DURIAN_CAMERA_SWITCH
1915         {
1916                 TimeMarker *m;
1917
1918                 for(m= sce->markers.first; m; m= m->next) {
1919                         if(m->camera) {
1920                                 node= dag_get_node(sce->theDag, m->camera);
1921                                 node->scelay |= lay;
1922                         }
1923                 }
1924         }
1925 #endif
1926
1927         /* flush layer nodes to dependencies */
1928         for(itA = firstnode->child; itA; itA= itA->next)
1929                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
1930                         flush_layer_node(sce, itA->node, lasttime);
1931 }
1932
1933 static void dag_tag_renderlayers(Scene *sce, unsigned int lay)
1934 {
1935         if(sce->nodetree) {
1936                 bNode *node;
1937                 Base *base;
1938                 unsigned int lay_changed= 0;
1939                 
1940                 for(base= sce->base.first; base; base= base->next)
1941                         if(base->lay & lay)
1942                                 if(base->object->recalc)
1943                                         lay_changed |= base->lay;
1944                         
1945                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
1946                         if(node->id==(ID *)sce) {
1947                                 SceneRenderLayer *srl= BLI_findlink(&sce->r.layers, node->custom1);
1948                                 if(srl && (srl->lay & lay_changed))
1949                                         NodeTagChanged(sce->nodetree, node);
1950                         }
1951                 }
1952         }
1953 }
1954
1955 /* flushes all recalc flags in objects down the dependency tree */
1956 void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const short time)
1957 {
1958         DagNode *firstnode;
1959         DagAdjList *itA;
1960         Object *ob;
1961         int lasttime;
1962         
1963         if(sce->theDag==NULL) {
1964                 printf("DAG zero... not allowed to happen!\n");
1965                 DAG_scene_sort(bmain, sce);
1966         }
1967         
1968         firstnode= sce->theDag->DagNode.first;  // always scene node
1969
1970         /* first we flush the layer flags */
1971         dag_scene_flush_layers(sce, lay);
1972
1973         /* then we use the relationships + layer info to flush update events */
1974         sce->theDag->time++;    // so we know which nodes were accessed
1975         lasttime= sce->theDag->time;
1976         for(itA = firstnode->child; itA; itA= itA->next)
1977                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)
1978                         flush_update_node(itA->node, lay, lasttime);
1979
1980         /* if update is not due to time change, do pointcache clears */
1981         if(!time) {
1982                 sce->theDag->time++;    // so we know which nodes were accessed
1983                 lasttime= sce->theDag->time;
1984                 for(itA = firstnode->child; itA; itA= itA->next) {
1985                         if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)  {
1986                                 ob= (Object*)(itA->node->ob);
1987
1988                                 if(ob->recalc & OB_RECALC_ALL) {
1989                                         if(BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH))
1990                                                 ob->recalc |= OB_RECALC_DATA;
1991
1992                                         flush_pointcache_reset(sce, itA->node, lasttime, 1);
1993                                 }
1994                                 else
1995                                         flush_pointcache_reset(sce, itA->node, lasttime, 0);
1996                         }
1997                 }
1998         }
1999         
2000         dag_tag_renderlayers(sce, lay);
2001 }
2002
2003 static int object_modifiers_use_time(Object *ob)
2004 {
2005         ModifierData *md;
2006         
2007         /* check if a modifier in modifier stack needs time input */
2008         for (md=ob->modifiers.first; md; md=md->next)
2009                 if (modifier_dependsOnTime(md))
2010                         return 1;
2011         
2012         /* check whether any modifiers are animated */
2013         if (ob->adt) {
2014                 AnimData *adt = ob->adt;
2015                 
2016                 /* action - check for F-Curves with paths containing 'modifiers[' */
2017                 if (adt->action) {
2018                         FCurve *fcu;
2019                         
2020                         for (fcu = adt->action->curves.first; fcu; fcu = fcu->next) {
2021                                 if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
2022                                         return 1;
2023                         }
2024                 }
2025                 
2026                 // XXX: also, should check NLA strips, though for now assume that nobody uses
2027                 // that and we can omit that for performance reasons...
2028         }
2029         
2030         return 0;
2031 }
2032
2033 static short animdata_use_time(AnimData *adt)
2034 {
2035         NlaTrack *nlt;
2036         
2037         if(adt==NULL) return 0;
2038         
2039         /* check action - only if assigned, and it has anim curves */
2040         if (adt->action && adt->action->curves.first)
2041                 return 1;
2042         
2043         /* check NLA tracks + strips */
2044         for (nlt= adt->nla_tracks.first; nlt; nlt= nlt->next) {
2045                 if (nlt->strips.first)
2046                         return 1;
2047         }
2048         
2049         return 0;
2050 }
2051
2052 static void dag_object_time_update_flags(Object *ob)
2053 {
2054         if(ob->constraints.first) {
2055                 bConstraint *con;
2056                 for (con = ob->constraints.first; con; con=con->next) {
2057                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2058                         ListBase targets = {NULL, NULL};
2059                         bConstraintTarget *ct;
2060                         
2061                         if (cti && cti->get_constraint_targets) {
2062                                 cti->get_constraint_targets(con, &targets);
2063                                 
2064                                 for (ct= targets.first; ct; ct= ct->next) {
2065                                         if (ct->tar) {
2066                                                 ob->recalc |= OB_RECALC_OB;
2067                                                 break;
2068                                         }
2069                                 }
2070                                 
2071                                 if (cti->flush_constraint_targets)
2072                                         cti->flush_constraint_targets(con, &targets, 1);
2073                         }
2074                 }
2075         }
2076         
2077         if(ob->parent) {
2078                 /* motion path or bone child */
2079                 if(ob->parent->type==OB_CURVE || ob->parent->type==OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
2080         }
2081         
2082 #if 0 // XXX old animation system
2083         if(ob->nlastrips.first) {
2084                 if(ob->dup_group) {
2085                         bActionStrip *strip;
2086                         /* this case is for groups with nla, whilst nla target has no action or nla */
2087                         for(strip= ob->nlastrips.first; strip; strip= strip->next) {
2088                                 if(strip->object)
2089                                         strip->object->recalc |= OB_RECALC_ALL;
2090                         }
2091                 }
2092         }
2093 #endif // XXX old animation system
2094         
2095         if(animdata_use_time(ob->adt)) {
2096                 ob->recalc |= OB_RECALC_OB;
2097                 ob->adt->recalc |= ADT_RECALC_ANIM;
2098         }
2099         
2100         if((ob->adt) && (ob->type==OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA;
2101         
2102         if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
2103         if((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->recalc |= OB_RECALC_DATA;
2104         
2105         {
2106                 AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
2107                 Mesh *me;
2108                 Curve *cu;
2109                 Lattice *lt;
2110                 
2111                 switch(ob->type) {
2112                         case OB_MESH:
2113                                 me= ob->data;
2114                                 if(me->key) {
2115                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2116                                                 ob->recalc |= OB_RECALC_DATA;
2117                                         }
2118                                 }
2119                                 if(ob->particlesystem.first)
2120                                         ob->recalc |= OB_RECALC_DATA;
2121                                 break;
2122                         case OB_CURVE:
2123                         case OB_SURF:
2124                                 cu= ob->data;
2125                                 if(cu->key) {
2126                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2127                                                 ob->recalc |= OB_RECALC_DATA;
2128                                         }
2129                                 }
2130                                 break;
2131                         case OB_FONT:
2132                                 cu= ob->data;
2133                                 if(cu->nurb.first==NULL && cu->str && cu->vfont)
2134                                         ob->recalc |= OB_RECALC_DATA;
2135                                 break;
2136                         case OB_LATTICE:
2137                                 lt= ob->data;
2138                                 if(lt->key) {
2139                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2140                                                 ob->recalc |= OB_RECALC_DATA;
2141                                         }
2142                                 }
2143                                         break;
2144                         case OB_MBALL:
2145                                 if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
2146                                 break;
2147                 }
2148                 
2149                 if(animdata_use_time(adt)) {
2150                         ob->recalc |= OB_RECALC_DATA;
2151                         adt->recalc |= ADT_RECALC_ANIM;
2152                 }
2153
2154                 if(ob->particlesystem.first) {
2155                         ParticleSystem *psys= ob->particlesystem.first;
2156
2157                         for(; psys; psys=psys->next) {
2158                                 if(psys_check_enabled(ob, psys)) {
2159                                         ob->recalc |= OB_RECALC_DATA;
2160                                         break;
2161                                 }
2162                         }
2163                 }
2164         }               
2165 }
2166 /* flag all objects that need recalc, for changes in time for example */
2167 /* do_time: make this optional because undo resets objects to their animated locations without this */
2168 void DAG_scene_update_flags(Main *bmain, Scene *scene, unsigned int lay, const short do_time)
2169 {
2170         Base *base;
2171         Object *ob;
2172         Group *group;
2173         GroupObject *go;
2174         Scene *sce_iter;
2175
2176         /* set ob flags where animated systems are */
2177         for(SETLOOPER(scene, sce_iter, base)) {
2178                 ob= base->object;
2179
2180                 if(do_time) {
2181                         /* now if DagNode were part of base, the node->lay could be checked... */
2182                         /* we do all now, since the scene_flush checks layers and clears recalc flags even */
2183                         dag_object_time_update_flags(ob);
2184                 }
2185
2186                 /* handled in next loop */
2187                 if(ob->dup_group)
2188                         ob->dup_group->id.flag |= LIB_DOIT;
2189         }
2190
2191         if(do_time) {
2192                 /* we do groups each once */
2193                 for(group= bmain->group.first; group; group= group->id.next) {
2194                         if(group->id.flag & LIB_DOIT) {
2195                                 for(go= group->gobject.first; go; go= go->next) {
2196                                         dag_object_time_update_flags(go->ob);
2197                                 }
2198                         }
2199                 }
2200         }
2201
2202         for(sce_iter= scene; sce_iter; sce_iter= sce_iter->set)
2203                 DAG_scene_flush_update(bmain, sce_iter, lay, 1);
2204         
2205         if(do_time) {
2206                 /* test: set time flag, to disable baked systems to update */
2207                 for(SETLOOPER(scene, sce_iter, base)) {
2208                         ob= base->object;
2209                         if(ob->recalc)
2210                                 ob->recalc |= OB_RECALC_TIME;
2211                 }
2212
2213                 /* hrmf... an exception to look at once, for invisible camera object we do it over */
2214                 if(scene->camera)
2215                         dag_object_time_update_flags(scene->camera);
2216         }
2217
2218         /* and store the info in groupobject */
2219         for(group= bmain->group.first; group; group= group->id.next) {
2220                 if(group->id.flag & LIB_DOIT) {
2221                         for(go= group->gobject.first; go; go= go->next) {
2222                                 go->recalc= go->ob->recalc;
2223                                 // printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
2224                         }
2225                         group->id.flag &= ~LIB_DOIT;
2226                 }
2227         }
2228         
2229 }
2230
2231 static void dag_current_scene_layers(Main *bmain, Scene **sce, unsigned int *lay)
2232 {
2233         wmWindowManager *wm;
2234         wmWindow *win;
2235
2236         /* only one scene supported currently, making more scenes work
2237            correctly requires changes beyond just the dependency graph */
2238
2239         *sce= NULL;
2240         *lay= 0;
2241
2242         if((wm= bmain->wm.first)) {
2243                 /* if we have a windowmanager, look into windows */
2244                 for(win=wm->windows.first; win; win=win->next) {
2245                         if(win->screen) {
2246                                 if(!*sce) *sce= win->screen->scene;
2247                                 *lay |= BKE_screen_visible_layers(win->screen, win->screen->scene);
2248                         }
2249                 }
2250         }
2251         else {
2252                 /* if not, use the first sce */
2253                 *sce= bmain->scene.first;
2254                 if(*sce) *lay= (*sce)->lay;
2255
2256                 /* XXX for background mode, we should get the scene
2257                    from somewhere, for the -S option, but it's in
2258                    the context, how to get it here? */
2259         }
2260 }
2261
2262 void DAG_ids_flush_update(Main *bmain, int time)
2263 {
2264         Scene *sce;
2265         unsigned int lay;
2266
2267         dag_current_scene_layers(bmain, &sce, &lay);
2268
2269         if(sce)
2270                 DAG_scene_flush_update(bmain, sce, lay, time);
2271 }
2272
2273 void DAG_on_visible_update(Main *bmain, const short do_time)
2274 {
2275         Scene *scene;
2276         Base *base;
2277         Object *ob;
2278         Group *group;
2279         GroupObject *go;
2280         DagNode *node;
2281         unsigned int lay, oblay;
2282
2283         dag_current_scene_layers(bmain, &scene, &lay);
2284
2285         if(scene && scene->theDag) {
2286                 Scene *sce_iter;
2287                 /* derivedmeshes and displists are not saved to file so need to be
2288                    remade, tag them so they get remade in the scene update loop,
2289                    note armature poses or object matrices are preserved and do not
2290                    require updates, so we skip those */
2291                 dag_scene_flush_layers(scene, lay);
2292
2293                 for(SETLOOPER(scene, sce_iter, base)) {
2294                         ob= base->object;
2295                         node= (sce_iter->theDag)? dag_get_node(sce_iter->theDag, ob): NULL;
2296                         oblay= (node)? node->lay: ob->lay;
2297
2298                         if((oblay & lay) & ~scene->lay_updated) {
2299                                 if(ELEM6(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2300                                         ob->recalc |= OB_RECALC_DATA;
2301                                 if(ob->dup_group) 
2302                                         ob->dup_group->id.flag |= LIB_DOIT;
2303                         }
2304                 }
2305
2306                 for(group= bmain->group.first; group; group= group->id.next) {
2307                         if(group->id.flag & LIB_DOIT) {
2308                                 for(go= group->gobject.first; go; go= go->next) {
2309                                         if(ELEM6(go->ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2310                                                 go->ob->recalc |= OB_RECALC_DATA;
2311                                         if(go->ob->proxy_from)
2312                                                 go->ob->recalc |= OB_RECALC_OB;
2313                                 }
2314                                 
2315                                 group->id.flag &= ~LIB_DOIT;
2316                         }
2317                 }
2318
2319                 /* now tag update flags, to ensure deformers get calculated on redraw */
2320                 DAG_scene_update_flags(bmain, scene, lay, do_time);
2321                 scene->lay_updated |= lay;
2322         }
2323 }
2324
2325 static void dag_id_flush_update__isDependentTexture(void *userData, Object *UNUSED(ob), ID **idpoin)
2326 {
2327         struct { ID *id; int is_dependent; } *data = userData;
2328         
2329         if(*idpoin && GS((*idpoin)->name)==ID_TE) {
2330                 if (data->id == (*idpoin))
2331                         data->is_dependent = 1;
2332         }
2333 }
2334
2335 static void dag_id_flush_update(Scene *sce, ID *id)
2336 {
2337         Main *bmain= G.main;
2338         Object *obt, *ob= NULL;
2339         short idtype;
2340
2341         /* here we flush a few things before actual scene wide flush, mostly
2342            due to only objects and not other datablocks being in the depsgraph */
2343
2344         /* set flags & pointcache for object */
2345         if(GS(id->name) == ID_OB) {
2346                 ob= (Object*)id;
2347                 BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH);
2348
2349                 if(ob->recalc & OB_RECALC_DATA) {
2350                         /* all users of this ob->data should be checked */
2351                         id= ob->data;
2352
2353                         /* no point in trying in this cases */
2354                         if(id && id->us <= 1) {
2355                                 dag_editors_update(bmain, id);
2356                                 id= NULL;
2357                         }
2358                 }
2359         }
2360
2361         /* set flags & pointcache for object data */
2362         if(id) {
2363                 idtype= GS(id->name);
2364
2365                 if(ELEM7(idtype, ID_ME, ID_CU, ID_MB, ID_LA, ID_LT, ID_CA, ID_AR)) {
2366                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2367                                 if(!(ob && obt == ob) && obt->data == id) {
2368                                         obt->recalc |= OB_RECALC_DATA;
2369                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2370                                 }
2371                         }
2372                 }
2373                 
2374                 /* set flags based on textures - can influence depgraph via modifiers */
2375                 if(idtype == ID_TE) {
2376                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2377                                 struct { ID *id; int is_dependent; } data;
2378                                 data.id= id;
2379                                 data.is_dependent= 0;
2380
2381                                 modifiers_foreachIDLink(obt, dag_id_flush_update__isDependentTexture, &data);
2382                                 if (data.is_dependent)
2383                                         obt->recalc |= OB_RECALC_DATA;
2384
2385                                 /* particle settings can use the texture as well */
2386                                 if(obt->particlesystem.first) {
2387                                         ParticleSystem *psys = obt->particlesystem.first;
2388                                         MTex **mtexp, *mtex;
2389                                         int a;
2390                                         for(; psys; psys=psys->next) {
2391                                                 mtexp = psys->part->mtex;
2392                                                 for(a=0; a<MAX_MTEX; a++, mtexp++) {
2393                                                         mtex = *mtexp;
2394                                                         if(mtex && mtex->tex == (Tex*)id) {
2395                                                                 obt->recalc |= OB_RECALC_DATA;
2396                                                                 
2397                                                                 if(mtex->mapto & PAMAP_INIT)
2398                                                                         psys->recalc |= PSYS_RECALC_RESET;
2399                                                                 if(mtex->mapto & PAMAP_CHILD)
2400                                                                         psys->recalc |= PSYS_RECALC_CHILD;
2401
2402                                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2403                                                         }
2404                                                 }
2405                                         }
2406                                 }
2407                         }
2408                 }
2409                 
2410                 /* set flags based on ShapeKey */
2411                 if(idtype == ID_KE) {
2412                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2413                                 Key *key= ob_get_key(obt);
2414                                 if(!(ob && obt == ob) && ((ID *)key == id)) {
2415                                         obt->flag |= (OB_RECALC_OB|OB_RECALC_DATA);
2416                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2417                                 }
2418                         }
2419                 }
2420                 
2421                 /* set flags based on particle settings */
2422                 if(idtype == ID_PA) {
2423                         ParticleSystem *psys;
2424                         for(obt=bmain->object.first; obt; obt= obt->id.next)
2425                                 for(psys=obt->particlesystem.first; psys; psys=psys->next)
2426                                         if(&psys->part->id == id)
2427                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2428                 }
2429
2430                 /* update editors */
2431                 dag_editors_update(bmain, id);
2432         }
2433 }
2434
2435 void DAG_ids_flush_tagged(Main *bmain)
2436 {
2437         ListBase *lbarray[MAX_LIBARRAY];
2438         Scene *sce;
2439         unsigned int lay;
2440         int a, have_tag = 0;
2441
2442         dag_current_scene_layers(bmain, &sce, &lay);
2443
2444         if(!sce || !sce->theDag)
2445                 return;
2446
2447         /* loop over all ID types */
2448         a  = set_listbasepointers(bmain, lbarray);
2449
2450         while(a--) {
2451                 ListBase *lb = lbarray[a];
2452                 ID *id = lb->first;
2453
2454                 /* we tag based on first ID type character to avoid 
2455                    looping over all ID's in case there are no tags */
2456                 if(id && bmain->id_tag_update[id->name[0]]) {
2457                         for(; id; id=id->next) {
2458                                 if(id->flag & LIB_ID_RECALC) {
2459                                         dag_id_flush_update(sce, id);
2460                                         id->flag &= ~LIB_ID_RECALC;
2461                                 }
2462                         }
2463
2464                         have_tag = 1;
2465                 }
2466         }
2467
2468         if(have_tag) {
2469                 /* clear tags */
2470                 memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update));
2471
2472                 /* flush changes to other objects */
2473                 DAG_scene_flush_update(bmain, sce, lay, 0);
2474         }
2475 }
2476
2477 void DAG_id_tag_update(ID *id, short flag)
2478 {
2479         Main *bmain= G.main;
2480
2481         if(id==NULL) return;
2482         
2483         /* tag ID for update */
2484         id->flag |= LIB_ID_RECALC;
2485         bmain->id_tag_update[id->name[0]] = 1;
2486
2487         /* flag is for objects and particle systems */
2488         if(flag) {
2489                 Object *ob;
2490                 ParticleSystem *psys;
2491                 short idtype = GS(id->name);
2492
2493                 if(idtype == ID_OB) {
2494                         /* only quick tag */
2495                         ob = (Object*)id;
2496                         ob->recalc |= (flag & OB_RECALC_ALL);
2497                 }
2498                 else if(idtype == ID_PA) {
2499                         /* this is weak still, should be done delayed as well */
2500                         for(ob=bmain->object.first; ob; ob=ob->id.next) {
2501                                 for(psys=ob->particlesystem.first; psys; psys=psys->next) {
2502                                         if(&psys->part->id == id) {
2503                                                 ob->recalc |= (flag & OB_RECALC_ALL);
2504                                                 psys->recalc |= (flag & PSYS_RECALC);
2505                                         }
2506                                 }
2507                         }
2508                 }
2509                 else {
2510                         /* disable because this is called on various ID types automatically.
2511                          * where printing warning is not useful. for now just ignore */
2512                         /* BLI_assert(!"invalid flag for this 'idtype'"); */
2513                 }
2514         }
2515 }
2516
2517 #if 0 // UNUSED
2518 /* recursively descends tree, each node only checked once */
2519 /* node is checked to be of type object */
2520 static int parent_check_node(DagNode *node, int curtime)
2521 {
2522         DagAdjList *itA;
2523         
2524         node->lasttime= curtime;
2525         
2526         if(node->color==DAG_GRAY)
2527                 return DAG_GRAY;
2528         
2529         for(itA = node->child; itA; itA= itA->next) {
2530                 if(itA->node->type==ID_OB) {
2531                         
2532                         if(itA->node->color==DAG_GRAY)
2533                                 return DAG_GRAY;
2534
2535                         /* descend if not done */
2536                         if(itA->node->lasttime!=curtime) {
2537                                 itA->node->color= parent_check_node(itA->node, curtime);
2538                         
2539                                 if(itA->node->color==DAG_GRAY)
2540                                         return DAG_GRAY;
2541                         }
2542                 }
2543         }
2544         
2545         return DAG_WHITE;
2546 }
2547 #endif
2548
2549 /* ******************* DAG FOR ARMATURE POSE ***************** */
2550
2551 /* we assume its an armature with pose */
2552 void DAG_pose_sort(Object *ob)
2553 {
2554         bPose *pose= ob->pose;
2555         bPoseChannel *pchan;
2556         bConstraint *con;
2557         DagNode *node;
2558         DagNode *node2, *node3;
2559         DagNode *rootnode;
2560         DagForest *dag;
2561         DagNodeQueue *nqueue;
2562         DagAdjList *itA;
2563         ListBase tempbase;
2564         int skip = 0;
2565         
2566         dag = dag_init();
2567         ugly_hack_sorry= 0;     // no ID structs
2568
2569         rootnode = dag_add_node(dag, NULL);     // node->ob becomes NULL
2570         
2571         /* we add the hierarchy and the constraints */
2572         for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2573                 int addtoroot = 1;
2574                 
2575                 node = dag_get_node(dag, pchan);
2576                 
2577                 if(pchan->parent) {
2578                         node2 = dag_get_node(dag, pchan->parent);
2579                         dag_add_relation(dag, node2, node, 0, "Parent Relation");
2580                         addtoroot = 0;
2581                 }
2582                 for (con = pchan->constraints.first; con; con=con->next) {
2583                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2584                         ListBase targets = {NULL, NULL};
2585                         bConstraintTarget *ct;
2586                         
2587                         if (cti && cti->get_constraint_targets) {
2588                                 cti->get_constraint_targets(con, &targets);
2589                                 
2590                                 for (ct= targets.first; ct; ct= ct->next) {
2591                                         if (ct->tar==ob && ct->subtarget[0]) {
2592                                                 bPoseChannel *target= get_pose_channel(ob->pose, ct->subtarget);
2593                                                 if (target) {
2594                                                         node2= dag_get_node(dag, target);
2595                                                         dag_add_relation(dag, node2, node, 0, "Pose Constraint");
2596                                                         
2597                                                         if (con->type==CONSTRAINT_TYPE_KINEMATIC) {
2598                                                                 bKinematicConstraint *data = (bKinematicConstraint *)con->data;
2599                                                                 bPoseChannel *parchan;
2600                                                                 int segcount= 0;
2601                                                                 
2602                                                                 /* exclude tip from chain? */
2603                                                                 if(!(data->flag & CONSTRAINT_IK_TIP))
2604                                                                         parchan= pchan->parent;
2605                                                                 else
2606                                                                         parchan= pchan;
2607                                                                 
2608                                                                 /* Walk to the chain's root */
2609                                                                 while (parchan) {
2610                                                                         node3= dag_get_node(dag, parchan);
2611                                                                         dag_add_relation(dag, node2, node3, 0, "IK Constraint");
2612                                                                         
2613                                                                         segcount++;
2614                                                                         if (segcount==data->rootbone || segcount>255) break; // 255 is weak
2615                                                                         parchan= parchan->parent;
2616                                                                 }
2617                                                         }
2618                                                 }
2619                                         }
2620                                 }
2621                                 
2622                                 if (cti->flush_constraint_targets)
2623                                         cti->flush_constraint_targets(con, &targets, 1);
2624                         }
2625                 }
2626                 if (addtoroot == 1 ) {
2627                         dag_add_relation(dag, rootnode, node, 0, "Root Bone Relation");
2628                 }
2629         }
2630
2631         dag_check_cycle(dag);
2632         
2633         /* now we try to sort... */
2634         tempbase.first= tempbase.last= NULL;
2635
2636         nqueue = queue_create(DAGQUEUEALLOC);
2637         
2638         /* tag nodes unchecked */
2639         for(node = dag->DagNode.first; node; node= node->next) 
2640                 node->color = DAG_WHITE;
2641         
2642         node = dag->DagNode.first;
2643         
2644         node->color = DAG_GRAY;
2645         push_stack(nqueue, node);  
2646         
2647         while(nqueue->count) {
2648                 
2649                 skip = 0;
2650                 node = get_top_node_queue(nqueue);
2651                 
2652                 itA = node->child;
2653                 while(itA != NULL) {
2654                         if(itA->node->color == DAG_WHITE) {
2655                                 itA->node->color = DAG_GRAY;
2656                                 push_stack(nqueue,itA->node);
2657                                 skip = 1;
2658                                 break;
2659                         } 
2660                         itA = itA->next;
2661                 }                       
2662                 
2663                 if (!skip) {
2664                         if (node) {
2665                                 node = pop_queue(nqueue);
2666                                 if (node->ob == NULL)   // we are done
2667                                         break ;
2668                                 node->color = DAG_BLACK;
2669                                 
2670                                 /* put node in new list */
2671                                 BLI_remlink(&pose->chanbase, node->ob);
2672                                 BLI_addhead(&tempbase, node->ob);
2673                         }       
2674                 }
2675         }
2676         
2677         // temporal correction for circular dependancies
2678         while(pose->chanbase.first) {
2679                 pchan= pose->chanbase.first;
2680                 BLI_remlink(&pose->chanbase, pchan);
2681                 BLI_addhead(&tempbase, pchan);
2682
2683                 printf("cyclic %s\n", pchan->name);
2684         }
2685         
2686         pose->chanbase = tempbase;
2687         queue_delete(nqueue);
2688         
2689 //      printf("\nordered\n");
2690 //      for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2691 //              printf(" %s\n", pchan->name);
2692 //      }
2693         
2694         free_forest( dag );
2695         MEM_freeN( dag );
2696         
2697         ugly_hack_sorry= 1;
2698 }
2699
2700
2701