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