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