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