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