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