Camera tracking integration
[blender.git] / source / blender / blenkernel / intern / depsgraph.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2004 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): none yet.
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/depsgraph.c
27  *  \ingroup bke
28  */
29
30  
31 #include <stdio.h>
32 #include <string.h>
33 #include <math.h>
34
35 #include "MEM_guardedalloc.h"
36
37 #include "BLI_winstuff.h"
38 #include "BLI_utildefines.h"
39 #include "BLI_listbase.h"
40 #include "BLI_ghash.h"
41
42 #include "DNA_anim_types.h"
43 #include "DNA_camera_types.h"
44 #include "DNA_group_types.h"
45 #include "DNA_lattice_types.h"
46 #include "DNA_key_types.h"
47 #include "DNA_material_types.h"
48 #include "DNA_mesh_types.h"
49 #include "DNA_node_types.h"
50 #include "DNA_scene_types.h"
51 #include "DNA_screen_types.h"
52 #include "DNA_windowmanager_types.h"
53 #include "DNA_movieclip_types.h"
54
55 #include "BKE_animsys.h"
56 #include "BKE_action.h"
57 #include "BKE_effect.h"
58 #include "BKE_fcurve.h"
59 #include "BKE_global.h"
60 #include "BKE_group.h"
61 #include "BKE_key.h"
62 #include "BKE_library.h"
63 #include "BKE_main.h"
64 #include "BKE_node.h"
65 #include "BKE_mball.h"
66 #include "BKE_modifier.h"
67 #include "BKE_object.h"
68 #include "BKE_particle.h"
69 #include "BKE_pointcache.h"
70 #include "BKE_scene.h"
71 #include "BKE_screen.h"
72 #include "BKE_utildefines.h"
73
74 #include "depsgraph_private.h"
75  
76 /* Queue and stack operations for dag traversal 
77  *
78  * the queue store a list of freenodes to avoid successives alloc/dealloc
79  */
80
81 DagNodeQueue * queue_create (int slots) 
82 {
83         DagNodeQueue * queue;
84         DagNodeQueueElem * elem;
85         int i;
86         
87         queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
88         queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
89         queue->count = 0;
90         queue->maxlevel = 0;
91         queue->first = queue->last = NULL;
92         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3");
93         elem->node = NULL;
94         elem->next = NULL;
95         queue->freenodes->first = queue->freenodes->last = elem;
96         
97         for (i = 1; i <slots;i++) {
98                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4");
99                 elem->node = NULL;
100                 elem->next = NULL;
101                 queue->freenodes->last->next = elem;
102                 queue->freenodes->last = elem;
103         }
104         queue->freenodes->count = slots;
105         return queue;
106 }
107
108 void queue_raz(DagNodeQueue *queue)
109 {
110         DagNodeQueueElem * elem;
111         
112         elem = queue->first;
113         if (queue->freenodes->last)
114                 queue->freenodes->last->next = elem;
115         else
116                 queue->freenodes->first = queue->freenodes->last = elem;
117         
118         elem->node = NULL;
119         queue->freenodes->count++;
120         while (elem->next) {
121                 elem = elem->next;
122                 elem->node = NULL;
123                 queue->freenodes->count++;
124         }
125         queue->freenodes->last = elem;
126         queue->count = 0;
127 }
128
129 void queue_delete(DagNodeQueue *queue)
130 {
131         DagNodeQueueElem * elem;
132         DagNodeQueueElem * temp;
133         
134         elem = queue->first;
135         while (elem) {
136                 temp = elem;
137                 elem = elem->next;
138                 MEM_freeN(temp);
139         }
140         
141         elem = queue->freenodes->first;
142         while (elem) {
143                 temp = elem;
144                 elem = elem->next;
145                 MEM_freeN(temp);
146         }
147         
148         MEM_freeN(queue->freenodes);                    
149         MEM_freeN(queue);                       
150 }
151
152 /* insert in queue, remove in front */
153 void push_queue(DagNodeQueue *queue, DagNode *node)
154 {
155         DagNodeQueueElem * elem;
156         int i;
157
158         if (node == NULL) {
159                 fprintf(stderr,"pushing null node \n");
160                 return;
161         }
162         /*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->count);*/
163
164         elem = queue->freenodes->first;
165         if (elem != NULL) {
166                 queue->freenodes->first = elem->next;
167                 if ( queue->freenodes->last == elem) {
168                         queue->freenodes->last = NULL;
169                         queue->freenodes->first = NULL;
170                 }
171                 queue->freenodes->count--;
172         } else { /* alllocating more */         
173                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
174                 elem->node = NULL;
175                 elem->next = NULL;
176                 queue->freenodes->first = queue->freenodes->last = elem;
177
178                 for (i = 1; i <DAGQUEUEALLOC;i++) {
179                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
180                         elem->node = NULL;
181                         elem->next = NULL;
182                         queue->freenodes->last->next = elem;
183                         queue->freenodes->last = elem;
184                 }
185                 queue->freenodes->count = DAGQUEUEALLOC;
186                         
187                 elem = queue->freenodes->first; 
188                 queue->freenodes->first = elem->next;   
189         }
190         elem->next = NULL;
191         elem->node = node;
192         if (queue->last != NULL)
193                 queue->last->next = elem;
194         queue->last = elem;
195         if (queue->first == NULL) {
196                 queue->first = elem;
197         }
198         queue->count++;
199 }
200
201
202 /* insert in front, remove in front */
203 void push_stack(DagNodeQueue *queue, DagNode *node)
204 {
205         DagNodeQueueElem * elem;
206         int i;
207
208         elem = queue->freenodes->first; 
209         if (elem != NULL) {
210                 queue->freenodes->first = elem->next;
211                 if ( queue->freenodes->last == elem) {
212                         queue->freenodes->last = NULL;
213                         queue->freenodes->first = NULL;
214                 }
215                 queue->freenodes->count--;
216         } else { /* alllocating more */
217                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
218                 elem->node = NULL;
219                 elem->next = NULL;
220                 queue->freenodes->first = queue->freenodes->last = elem;
221
222                 for (i = 1; i <DAGQUEUEALLOC;i++) {
223                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
224                         elem->node = NULL;
225                         elem->next = NULL;
226                         queue->freenodes->last->next = elem;
227                         queue->freenodes->last = elem;
228                 }
229                 queue->freenodes->count = DAGQUEUEALLOC;
230                         
231                 elem = queue->freenodes->first; 
232                 queue->freenodes->first = elem->next;   
233         }
234         elem->next = queue->first;
235         elem->node = node;
236         queue->first = elem;
237         if (queue->last == NULL)
238                 queue->last = elem;
239         queue->count++;
240 }
241
242
243 DagNode * pop_queue(DagNodeQueue *queue)
244 {
245         DagNodeQueueElem * elem;
246         DagNode *node;
247
248         elem = queue->first;
249         if (elem) {
250                 queue->first = elem->next;
251                 if (queue->last == elem) {
252                         queue->last=NULL;
253                         queue->first=NULL;
254                 }
255                 queue->count--;
256                 if (queue->freenodes->last)
257                         queue->freenodes->last->next=elem;
258                 queue->freenodes->last=elem;
259                 if (queue->freenodes->first == NULL)
260                         queue->freenodes->first=elem;
261                 node = elem->node;
262                 elem->node = NULL;
263                 elem->next = NULL;
264                 queue->freenodes->count++;
265                 return node;
266         } else {
267                 fprintf(stderr,"return null \n");
268                 return NULL;
269         }
270 }
271
272 void    *pop_ob_queue(struct DagNodeQueue *queue) {
273         return(pop_queue(queue)->ob);
274 }
275
276 DagNode * get_top_node_queue(DagNodeQueue *queue) 
277 {
278         return queue->first->node;
279 }
280
281 int             queue_count(struct DagNodeQueue *queue){
282         return queue->count;
283 }
284
285
286 DagForest *dag_init(void)
287 {
288         DagForest *forest;
289         /* use callocN to init all zero */
290         forest = MEM_callocN(sizeof(DagForest),"DAG root");
291         return forest;
292 }
293
294 /* isdata = object data... */
295 // XXX this needs to be extended to be more flexible (so that not only objects are evaluated via depsgraph)...
296 static void dag_add_driver_relation(AnimData *adt, DagForest *dag, DagNode *node, int isdata)
297 {
298         FCurve *fcu;
299         DagNode *node1;
300         
301         for (fcu= adt->drivers.first; fcu; fcu= fcu->next) {
302                 ChannelDriver *driver= fcu->driver;
303                 DriverVar *dvar;
304                 int isdata_fcu = isdata || (fcu->rna_path && strstr(fcu->rna_path, "modifiers["));
305                 
306                 /* loop over variables to get the target relationships */
307                 for (dvar= driver->variables.first; dvar; dvar= dvar->next) {
308                         /* only used targets */
309                         DRIVER_TARGETS_USED_LOOPER(dvar) 
310                         {
311                                 if (dtar->id) {
312                                         // FIXME: other data types need to be added here so that they can work!
313                                         if (GS(dtar->id->name)==ID_OB) {
314                                                 Object *ob= (Object *)dtar->id;
315                                                 
316                                                 /* normal channel-drives-channel */
317                                                 node1 = dag_get_node(dag, dtar->id);
318                                                 
319                                                 /* check if bone... */
320                                                 if ((ob->type==OB_ARMATURE) && 
321                                                         ( ((dtar->rna_path) && strstr(dtar->rna_path, "pose.bones[")) || 
322                                                           ((dtar->flag & DTAR_FLAG_STRUCT_REF) && (dtar->pchan_name[0])) )) 
323                                                 {
324                                                         dag_add_relation(dag, node1, node, isdata_fcu?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver");
325                                                 }
326                                                 /* check if ob data */
327                                                 else if (dtar->rna_path && strstr(dtar->rna_path, "data."))
328                                                         dag_add_relation(dag, node1, node, isdata_fcu?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver");
329                                                 /* normal */
330                                                 else
331                                                         dag_add_relation(dag, node1, node, isdata_fcu?DAG_RL_OB_DATA:DAG_RL_OB_OB, "Driver");
332                                         }
333                                 }
334                         }
335                         DRIVER_TARGETS_LOOPER_END
336                 }
337         }
338 }
339
340 static void dag_add_collision_field_relation(DagForest *dag, Scene *scene, Object *ob, DagNode *node)
341 {
342         Base *base;
343         DagNode *node2;
344
345         // would be nice to have a list of colliders here
346         // so for now walk all objects in scene check 'same layer rule'
347         for(base = scene->base.first; base; base= base->next) {
348                 if((base->lay & ob->lay) && base->object->pd) {
349                         Object *ob1= base->object;
350                         if((ob1->pd->deflect || ob1->pd->forcefield) && (ob1 != ob))  {
351                                 node2 = dag_get_node(dag, ob1);                                 
352                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Field Collision");
353                         }
354                 }
355         }
356 }
357
358 static void build_dag_object(DagForest *dag, DagNode *scenenode, Scene *scene, Object *ob, int mask)
359 {
360         bConstraint *con;
361         DagNode * node;
362         DagNode * node2;
363         DagNode * node3;
364         Key *key;
365         ParticleSystem *psys;
366         int addtoroot= 1;
367         
368         node = dag_get_node(dag, ob);
369         
370         if ((ob->data) && (mask&DAG_RL_DATA)) {
371                 node2 = dag_get_node(dag,ob->data);
372                 dag_add_relation(dag,node,node2,DAG_RL_DATA, "Object-Data Relation");
373                 node2->first_ancestor = ob;
374                 node2->ancestor_count += 1;
375         }
376
377         /* also build a custom data mask for dependencies that need certain layers */
378         node->customdata_mask= 0;
379         
380         if (ob->type == OB_ARMATURE) {
381                 if (ob->pose){
382                         bPoseChannel *pchan;
383                         bConstraint *con;
384                         
385                         for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next) {
386                                 for (con = pchan->constraints.first; con; con=con->next) {
387                                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
388                                         ListBase targets = {NULL, NULL};
389                                         bConstraintTarget *ct;
390                                         
391                                         if (cti && cti->get_constraint_targets) {
392                                                 cti->get_constraint_targets(con, &targets);
393                                                 
394                                                 for (ct= targets.first; ct; ct= ct->next) {
395                                                         if (ct->tar && ct->tar != ob) {
396                                                                 // fprintf(stderr,"armature %s target :%s \n", ob->id.name, target->id.name);
397                                                                 node3 = dag_get_node(dag, ct->tar);
398                                                                 
399                                                                 if (ct->subtarget[0])
400                                                                         dag_add_relation(dag,node3,node, DAG_RL_OB_DATA|DAG_RL_DATA_DATA, cti->name);
401                                                                 else if(ELEM3(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO, CONSTRAINT_TYPE_SPLINEIK))        
402                                                                         dag_add_relation(dag,node3,node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, cti->name);
403                                                                 else
404                                                                         dag_add_relation(dag,node3,node, DAG_RL_OB_DATA, cti->name);
405                                                         }
406                                                 }
407                                                 
408                                                 if (cti->flush_constraint_targets)
409                                                         cti->flush_constraint_targets(con, &targets, 1);
410                                         }
411                                         
412                                 }
413                         }
414                 }
415         }
416         
417         /* driver dependencies, nla modifiers */
418 #if 0 // XXX old animation system
419         if(ob->nlastrips.first) {
420                 bActionStrip *strip;
421                 bActionChannel *chan;
422                 for(strip= ob->nlastrips.first; strip; strip= strip->next) {
423                         if(strip->modifiers.first) {
424                                 bActionModifier *amod;
425                                 for(amod= strip->modifiers.first; amod; amod= amod->next) {
426                                         if(amod->ob) {
427                                                 node2 = dag_get_node(dag, amod->ob);
428                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "NLA Strip Modifier");
429                                         }
430                                 }
431                         }
432                 }
433         }
434 #endif // XXX old animation system
435         if (ob->adt)
436                 dag_add_driver_relation(ob->adt, dag, node, (ob->type == OB_ARMATURE)); // XXX isdata arg here doesn't give an accurate picture of situation
437                 
438         key= ob_get_key(ob);
439         if (key && key->adt)
440                 dag_add_driver_relation(key->adt, dag, node, 1);
441
442         if (ob->modifiers.first) {
443                 ModifierData *md;
444                 
445                 for(md=ob->modifiers.first; md; md=md->next) {
446                         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
447                         
448                         if (mti->updateDepgraph) mti->updateDepgraph(md, dag, scene, ob, node);
449                 }
450         }
451         if (ob->parent) {
452                 node2 = dag_get_node(dag,ob->parent);
453                 
454                 switch(ob->partype) {
455                         case PARSKEL:
456                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Parent");
457                                 break;
458                         case PARVERT1: case PARVERT3:
459                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Vertex Parent");
460                                 node2->customdata_mask |= CD_MASK_ORIGINDEX;
461                                 break;
462                         case PARBONE:
463                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Bone Parent");
464                                 break;
465                         default:
466                                 if(ob->parent->type==OB_LATTICE) 
467                                         dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Lattice Parent");
468                                 else if(ob->parent->type==OB_CURVE) {
469                                         Curve *cu= ob->parent->data;
470                                         if(cu->flag & CU_PATH) 
471                                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Curve Parent");
472                                         else
473                                                 dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Curve Parent");
474                                 }
475                                 else
476                                         dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Parent");
477                 }
478                 /* exception case: parent is duplivert */
479                 if(ob->type==OB_MBALL && (ob->parent->transflag & OB_DUPLIVERTS)) {
480                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Duplivert");
481                 }
482                 
483                 addtoroot = 0;
484         }
485         if (ob->proxy) {
486                 node2 = dag_get_node(dag, ob->proxy);
487                 dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Proxy");
488                 /* inverted relation, so addtoroot shouldn't be set to zero */
489         }
490         
491         if (ob->transflag & OB_DUPLI) {
492                 if((ob->transflag & OB_DUPLIGROUP) && ob->dup_group) {
493                         GroupObject *go;
494                         for(go= ob->dup_group->gobject.first; go; go= go->next) {
495                                 if(go->ob) {
496                                         node2 = dag_get_node(dag, go->ob);
497                                         /* node2 changes node1, this keeps animations updated in groups?? not logical? */
498                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Dupligroup");
499                                 }
500                         }
501                 }
502         }
503
504         /* softbody collision  */
505         if ((ob->type==OB_MESH) || (ob->type==OB_CURVE) || (ob->type==OB_LATTICE)) {
506                 if(modifiers_isSoftbodyEnabled(ob) || modifiers_isClothEnabled(ob) || ob->particlesystem.first)
507                         dag_add_collision_field_relation(dag, scene, ob, node); /* TODO: use effectorweight->group */
508         }
509         
510         /* object data drivers */
511         if (ob->data) {
512                 AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
513                 if (adt)
514                         dag_add_driver_relation(adt, dag, node, 1);
515         }
516         
517         /* object type/data relationships */
518         switch (ob->type) {
519                 case OB_CAMERA:
520                 {
521                         Camera *cam = (Camera *)ob->data;
522                         
523                         if (cam->dof_ob) {
524                                 node2 = dag_get_node(dag, cam->dof_ob);
525                                 dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Camera DoF");
526                         }
527                 }
528                         break;
529                 case OB_MBALL: 
530                 {
531                         Object *mom= find_basis_mball(scene, ob);
532                         
533                         if(mom!=ob) {
534                                 node2 = dag_get_node(dag, mom);
535                                 dag_add_relation(dag,node,node2,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Metaball");  // mom depends on children!
536                         }
537                 }
538                         break;
539                 case OB_CURVE:
540                 {
541                         Curve *cu= ob->data;
542                         
543                         if(cu->bevobj) {
544                                 node2 = dag_get_node(dag, cu->bevobj);
545                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Curve Bevel");
546                         }
547                         if(cu->taperobj) {
548                                 node2 = dag_get_node(dag, cu->taperobj);
549                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Curve Taper");
550                         }
551                 }
552                         break;
553                 case OB_FONT: 
554                 {
555                         Curve *cu= ob->data;
556                         
557                         if(cu->textoncurve) {
558                                 node2 = dag_get_node(dag, cu->textoncurve);
559                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Texture On Curve");
560                         }
561                 }
562                         break;
563         }
564         
565         /* particles */
566         psys= ob->particlesystem.first;
567         if(psys) {
568                 GroupObject *go;
569
570                 for(; psys; psys=psys->next) {
571                         BoidRule *rule = NULL;
572                         BoidState *state = NULL;
573                         ParticleSettings *part= psys->part;
574                         ListBase *effectors = NULL;
575                         EffectorCache *eff;
576
577                         dag_add_relation(dag, node, node, DAG_RL_OB_DATA, "Particle-Object Relation");
578
579                         if(!psys_check_enabled(ob, psys))
580                                 continue;
581
582                         if(ELEM(part->phystype,PART_PHYS_KEYED,PART_PHYS_BOIDS)) {
583                                 ParticleTarget *pt = psys->targets.first;
584
585                                 for(; pt; pt=pt->next) {
586                                         if(pt->ob && BLI_findlink(&pt->ob->particlesystem, pt->psys-1)) {
587                                                 node2 = dag_get_node(dag, pt->ob);
588                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Particle Targets");
589                                         }
590                            }
591                         }
592
593                         if(part->ren_as == PART_DRAW_OB && part->dup_ob) {
594                                 node2 = dag_get_node(dag, part->dup_ob);
595                                 dag_add_relation(dag, node, node2, DAG_RL_OB_OB, "Particle Object Visualisation");
596                                 if(part->dup_ob->type == OB_MBALL)
597                                         dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA, "Particle Object Visualisation");
598                         }
599
600                         if(part->ren_as == PART_DRAW_GR && part->dup_group) {
601                                 for(go=part->dup_group->gobject.first; go; go=go->next) {
602                                         node2 = dag_get_node(dag, go->ob);
603                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Particle Group Visualisation");
604                                 }
605                         }
606
607                         effectors = pdInitEffectors(scene, ob, psys, part->effector_weights);
608
609                         if(effectors) for(eff = effectors->first; eff; eff=eff->next) {
610                                 if(eff->psys) {
611                                         node2 = dag_get_node(dag, eff->ob);
612                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Particle Field");
613                                 }
614                         }
615
616                         pdEndEffectors(&effectors);
617
618                         if(part->boids) {
619                                 for(state = part->boids->states.first; state; state=state->next) {
620                                         for(rule = state->rules.first; rule; rule=rule->next) {
621                                                 Object *ruleob = NULL;
622                                                 if(rule->type==eBoidRuleType_Avoid)
623                                                         ruleob = ((BoidRuleGoalAvoid*)rule)->ob;
624                                                 else if(rule->type==eBoidRuleType_FollowLeader)
625                                                         ruleob = ((BoidRuleFollowLeader*)rule)->ob;
626
627                                                 if(ruleob) {
628                                                         node2 = dag_get_node(dag, ruleob);
629                                                         dag_add_relation(dag, node2, node, DAG_RL_OB_DATA, "Boid Rule");
630                                                 }
631                                         }
632                                 }
633                         }
634                 }
635         }
636         
637         /* object constraints */
638         for (con = ob->constraints.first; con; con=con->next) {
639                 bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
640                 ListBase targets = {NULL, NULL};
641                 bConstraintTarget *ct;
642                 
643                 if(!cti)
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_ACTIVECLIP) && 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                                         nodeUpdate(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         
2035         dag_tag_renderlayers(sce, lay);
2036 }
2037
2038 static int object_modifiers_use_time(Object *ob)
2039 {
2040         ModifierData *md;
2041         
2042         /* check if a modifier in modifier stack needs time input */
2043         for (md=ob->modifiers.first; md; md=md->next)
2044                 if (modifier_dependsOnTime(md))
2045                         return 1;
2046         
2047         /* check whether any modifiers are animated */
2048         if (ob->adt) {
2049                 AnimData *adt = ob->adt;
2050                 FCurve *fcu;
2051                 
2052                 /* action - check for F-Curves with paths containing 'modifiers[' */
2053                 if (adt->action) {
2054                         for (fcu = adt->action->curves.first; fcu; fcu = fcu->next) {
2055                                 if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
2056                                         return 1;
2057                         }
2058                 }
2059                 
2060                 /* This here allows modifier properties to get driven and still update properly
2061                  *
2062                  * Workaround to get [#26764] (e.g. subsurf levels not updating when animated/driven)
2063                  * working, without the updating problems ([#28525] [#28690] [#28774] [#28777]) caused
2064                  * by the RNA updates cache introduced in r.38649
2065                  */
2066                 for (fcu = adt->drivers.first; fcu; fcu = fcu->next) {
2067                         if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
2068                                 return 1;
2069                 }
2070                 
2071                 // XXX: also, should check NLA strips, though for now assume that nobody uses
2072                 // that and we can omit that for performance reasons...
2073         }
2074         
2075         return 0;
2076 }
2077
2078 static short animdata_use_time(AnimData *adt)
2079 {
2080         NlaTrack *nlt;
2081         
2082         if(adt==NULL) return 0;
2083         
2084         /* check action - only if assigned, and it has anim curves */
2085         if (adt->action && adt->action->curves.first)
2086                 return 1;
2087         
2088         /* check NLA tracks + strips */
2089         for (nlt= adt->nla_tracks.first; nlt; nlt= nlt->next) {
2090                 if (nlt->strips.first)
2091                         return 1;
2092         }
2093         
2094         /* If we have drivers, more likely than not, on a frame change
2095          * they'll need updating because their owner changed
2096          * 
2097          * This is kindof a hack to get around a whole host of problems
2098          * involving drivers using non-object datablock data (which the 
2099          * depsgraph currently has no way of representing let alone correctly
2100          * dependency sort+tagging). By doing this, at least we ensure that 
2101          * some commonly attempted drivers (such as scene -> current frame;
2102          * see "Driver updates fail" thread on Bf-committers dated July 2)
2103          * will work correctly, and that other non-object datablocks will have
2104          * their drivers update at least on frame change.
2105          *
2106          * -- Aligorith, July 4 2011
2107          */
2108         if (adt->drivers.first)
2109                 return 1;
2110         
2111         return 0;
2112 }
2113
2114 static void dag_object_time_update_flags(Object *ob)
2115 {
2116         if(ob->constraints.first) {
2117                 bConstraint *con;
2118                 for (con = ob->constraints.first; con; con=con->next) {
2119                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2120                         ListBase targets = {NULL, NULL};
2121                         bConstraintTarget *ct;
2122                         
2123                         if (cti) {
2124                                 /* special case for FollowTrack -- it doesn't use targets to define relations */
2125                                 if(ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER)) {
2126                                         ob->recalc |= OB_RECALC_OB;
2127                                 }
2128                                 else if (cti->get_constraint_targets) {
2129                                         cti->get_constraint_targets(con, &targets);
2130                                         
2131                                         for (ct= targets.first; ct; ct= ct->next) {
2132                                                 if (ct->tar) {
2133                                                         ob->recalc |= OB_RECALC_OB;
2134                                                         break;
2135                                                 }
2136                                         }
2137                                         
2138                                         if (cti->flush_constraint_targets)
2139                                                 cti->flush_constraint_targets(con, &targets, 1);
2140                                 }
2141                                 
2142                         }
2143                 }
2144         }
2145         
2146         if(ob->parent) {
2147                 /* motion path or bone child */
2148                 if(ob->parent->type==OB_CURVE || ob->parent->type==OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
2149         }
2150         
2151 #if 0 // XXX old animation system
2152         if(ob->nlastrips.first) {
2153                 if(ob->dup_group) {
2154                         bActionStrip *strip;
2155                         /* this case is for groups with nla, whilst nla target has no action or nla */
2156                         for(strip= ob->nlastrips.first; strip; strip= strip->next) {
2157                                 if(strip->object)
2158                                         strip->object->recalc |= OB_RECALC_ALL;
2159                         }
2160                 }
2161         }
2162 #endif // XXX old animation system
2163         
2164         if(animdata_use_time(ob->adt)) {
2165                 ob->recalc |= OB_RECALC_OB;
2166                 ob->adt->recalc |= ADT_RECALC_ANIM;
2167         }
2168         
2169         if((ob->adt) && (ob->type==OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA;
2170         
2171         if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
2172         if((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->recalc |= OB_RECALC_DATA;
2173         
2174         {
2175                 AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
2176                 Mesh *me;
2177                 Curve *cu;
2178                 Lattice *lt;
2179                 
2180                 switch(ob->type) {
2181                         case OB_MESH:
2182                                 me= ob->data;
2183                                 if(me->key) {
2184                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2185                                                 ob->recalc |= OB_RECALC_DATA;
2186                                         }
2187                                 }
2188                                 if(ob->particlesystem.first)
2189                                         ob->recalc |= OB_RECALC_DATA;
2190                                 break;
2191                         case OB_CURVE:
2192                         case OB_SURF:
2193                                 cu= ob->data;
2194                                 if(cu->key) {
2195                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2196                                                 ob->recalc |= OB_RECALC_DATA;
2197                                         }
2198                                 }
2199                                 break;
2200                         case OB_FONT:
2201                                 cu= ob->data;
2202                                 if(cu->nurb.first==NULL && cu->str && cu->vfont)
2203                                         ob->recalc |= OB_RECALC_DATA;
2204                                 break;
2205                         case OB_LATTICE:
2206                                 lt= ob->data;
2207                                 if(lt->key) {
2208                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2209                                                 ob->recalc |= OB_RECALC_DATA;
2210                                         }
2211                                 }
2212                                         break;
2213                         case OB_MBALL:
2214                                 if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
2215                                 break;
2216                 }
2217                 
2218                 if(animdata_use_time(adt)) {
2219                         ob->recalc |= OB_RECALC_DATA;
2220                         adt->recalc |= ADT_RECALC_ANIM;
2221                 }
2222
2223                 if(ob->particlesystem.first) {
2224                         ParticleSystem *psys= ob->particlesystem.first;
2225
2226                         for(; psys; psys=psys->next) {
2227                                 if(psys_check_enabled(ob, psys)) {
2228                                         ob->recalc |= OB_RECALC_DATA;
2229                                         break;
2230                                 }
2231                         }
2232                 }
2233         }               
2234 }
2235 /* flag all objects that need recalc, for changes in time for example */
2236 /* do_time: make this optional because undo resets objects to their animated locations without this */
2237 void DAG_scene_update_flags(Main *bmain, Scene *scene, unsigned int lay, const short do_time)
2238 {
2239         Base *base;
2240         Object *ob;
2241         Group *group;
2242         GroupObject *go;
2243         Scene *sce_iter;
2244
2245         /* set ob flags where animated systems are */
2246         for(SETLOOPER(scene, sce_iter, base)) {
2247                 ob= base->object;
2248
2249                 if(do_time) {
2250                         /* now if DagNode were part of base, the node->lay could be checked... */
2251                         /* we do all now, since the scene_flush checks layers and clears recalc flags even */
2252                         dag_object_time_update_flags(ob);
2253                 }
2254
2255                 /* handled in next loop */
2256                 if(ob->dup_group)
2257                         ob->dup_group->id.flag |= LIB_DOIT;
2258         }
2259
2260         if(do_time) {
2261                 /* we do groups each once */
2262                 for(group= bmain->group.first; group; group= group->id.next) {
2263                         if(group->id.flag & LIB_DOIT) {
2264                                 for(go= group->gobject.first; go; go= go->next) {
2265                                         dag_object_time_update_flags(go->ob);
2266                                 }
2267                         }
2268                 }
2269         }
2270
2271         for(sce_iter= scene; sce_iter; sce_iter= sce_iter->set)
2272                 DAG_scene_flush_update(bmain, sce_iter, lay, 1);
2273         
2274         if(do_time) {
2275                 /* test: set time flag, to disable baked systems to update */
2276                 for(SETLOOPER(scene, sce_iter, base)) {
2277                         ob= base->object;
2278                         if(ob->recalc)
2279                                 ob->recalc |= OB_RECALC_TIME;
2280                 }
2281
2282                 /* hrmf... an exception to look at once, for invisible camera object we do it over */
2283                 if(scene->camera)
2284                         dag_object_time_update_flags(scene->camera);
2285         }
2286
2287         /* and store the info in groupobject */
2288         for(group= bmain->group.first; group; group= group->id.next) {
2289                 if(group->id.flag & LIB_DOIT) {
2290                         for(go= group->gobject.first; go; go= go->next) {
2291                                 go->recalc= go->ob->recalc;
2292                                 // printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
2293                         }
2294                         group->id.flag &= ~LIB_DOIT;
2295                 }
2296         }
2297         
2298 }
2299
2300 static void dag_current_scene_layers(Main *bmain, Scene **sce, unsigned int *lay)
2301 {
2302         wmWindowManager *wm;
2303         wmWindow *win;
2304
2305         /* only one scene supported currently, making more scenes work
2306            correctly requires changes beyond just the dependency graph */
2307
2308         *sce= NULL;
2309         *lay= 0;
2310
2311         if((wm= bmain->wm.first)) {
2312                 /* if we have a windowmanager, look into windows */
2313                 for(win=wm->windows.first; win; win=win->next) {
2314                         if(win->screen) {
2315                                 if(!*sce) *sce= win->screen->scene;
2316                                 *lay |= BKE_screen_visible_layers(win->screen, win->screen->scene);
2317                         }
2318                 }
2319         }
2320         else {
2321                 /* if not, use the first sce */
2322                 *sce= bmain->scene.first;
2323                 if(*sce) *lay= (*sce)->lay;
2324
2325                 /* XXX for background mode, we should get the scene
2326                    from somewhere, for the -S option, but it's in
2327                    the context, how to get it here? */
2328         }
2329 }
2330
2331 void DAG_ids_flush_update(Main *bmain, int time)
2332 {
2333         Scene *sce;
2334         unsigned int lay;
2335
2336         dag_current_scene_layers(bmain, &sce, &lay);
2337
2338         if(sce)
2339                 DAG_scene_flush_update(bmain, sce, lay, time);
2340 }
2341
2342 void DAG_on_visible_update(Main *bmain, const short do_time)
2343 {
2344         Scene *scene;
2345         Base *base;
2346         Object *ob;
2347         Group *group;
2348         GroupObject *go;
2349         DagNode *node;
2350         unsigned int lay, oblay;
2351
2352         dag_current_scene_layers(bmain, &scene, &lay);
2353
2354         if(scene && scene->theDag) {
2355                 Scene *sce_iter;
2356                 /* derivedmeshes and displists are not saved to file so need to be
2357                    remade, tag them so they get remade in the scene update loop,
2358                    note armature poses or object matrices are preserved and do not
2359                    require updates, so we skip those */
2360                 dag_scene_flush_layers(scene, lay);
2361
2362                 for(SETLOOPER(scene, sce_iter, base)) {
2363                         ob= base->object;
2364                         node= (sce_iter->theDag)? dag_get_node(sce_iter->theDag, ob): NULL;
2365                         oblay= (node)? node->lay: ob->lay;
2366
2367                         if((oblay & lay) & ~scene->lay_updated) {
2368                                 if(ELEM6(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2369                                         ob->recalc |= OB_RECALC_DATA;
2370                                 if(ob->dup_group) 
2371                                         ob->dup_group->id.flag |= LIB_DOIT;
2372                         }
2373                 }
2374
2375                 for(group= bmain->group.first; group; group= group->id.next) {
2376                         if(group->id.flag & LIB_DOIT) {
2377                                 for(go= group->gobject.first; go; go= go->next) {
2378                                         if(ELEM6(go->ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2379                                                 go->ob->recalc |= OB_RECALC_DATA;
2380                                         if(go->ob->proxy_from)
2381                                                 go->ob->recalc |= OB_RECALC_OB;
2382                                 }
2383                                 
2384                                 group->id.flag &= ~LIB_DOIT;
2385                         }
2386                 }
2387
2388                 /* now tag update flags, to ensure deformers get calculated on redraw */
2389                 DAG_scene_update_flags(bmain, scene, lay, do_time);
2390                 scene->lay_updated |= lay;
2391         }
2392 }
2393
2394 static void dag_id_flush_update__isDependentTexture(void *userData, Object *UNUSED(ob), ID **idpoin)
2395 {
2396         struct { ID *id; int is_dependent; } *data = userData;
2397         
2398         if(*idpoin && GS((*idpoin)->name)==ID_TE) {
2399                 if (data->id == (*idpoin))
2400                         data->is_dependent = 1;
2401         }
2402 }
2403
2404 static void dag_id_flush_update(Scene *sce, ID *id)
2405 {
2406         Main *bmain= G.main;
2407         Object *obt, *ob= NULL;
2408         short idtype;
2409
2410         /* here we flush a few things before actual scene wide flush, mostly
2411            due to only objects and not other datablocks being in the depsgraph */
2412
2413         /* set flags & pointcache for object */
2414         if(GS(id->name) == ID_OB) {
2415                 ob= (Object*)id;
2416                 BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH);
2417
2418                 if(ob->recalc & OB_RECALC_DATA) {
2419                         /* all users of this ob->data should be checked */
2420                         id= ob->data;
2421
2422                         /* no point in trying in this cases */
2423                         if(id && id->us <= 1) {
2424                                 dag_editors_update(bmain, id);
2425                                 id= NULL;
2426                         }
2427                 }
2428         }
2429
2430         /* set flags & pointcache for object data */
2431         if(id) {
2432                 idtype= GS(id->name);
2433
2434                 if(ELEM8(idtype, ID_ME, ID_CU, ID_MB, ID_LA, ID_LT, ID_CA, ID_AR, ID_SPK)) {
2435                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2436                                 if(!(ob && obt == ob) && obt->data == id) {
2437                                         obt->recalc |= OB_RECALC_DATA;
2438                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2439                                 }
2440                         }
2441                 }
2442                 
2443                 /* set flags based on textures - can influence depgraph via modifiers */
2444                 if(idtype == ID_TE) {
2445                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2446                                 struct { ID *id; int is_dependent; } data;
2447                                 data.id= id;
2448                                 data.is_dependent= 0;
2449
2450                                 modifiers_foreachIDLink(obt, dag_id_flush_update__isDependentTexture, &data);
2451                                 if (data.is_dependent)
2452                                         obt->recalc |= OB_RECALC_DATA;
2453
2454                                 /* particle settings can use the texture as well */
2455                                 if(obt->particlesystem.first) {
2456                                         ParticleSystem *psys = obt->particlesystem.first;
2457                                         MTex **mtexp, *mtex;
2458                                         int a;
2459                                         for(; psys; psys=psys->next) {
2460                                                 mtexp = psys->part->mtex;
2461                                                 for(a=0; a<MAX_MTEX; a++, mtexp++) {
2462                                                         mtex = *mtexp;
2463                                                         if(mtex && mtex->tex == (Tex*)id) {
2464                                                                 obt->recalc |= OB_RECALC_DATA;
2465                                                                 
2466                                                                 if(mtex->mapto & PAMAP_INIT)
2467                                                                         psys->recalc |= PSYS_RECALC_RESET;
2468                                                                 if(mtex->mapto & PAMAP_CHILD)
2469                                                                         psys->recalc |= PSYS_RECALC_CHILD;
2470
2471                                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2472                                                         }
2473                                                 }
2474                                         }
2475                                 }
2476                         }
2477                 }
2478                 
2479                 /* set flags based on ShapeKey */
2480                 if(idtype == ID_KE) {
2481                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2482                                 Key *key= ob_get_key(obt);
2483                                 if(!(ob && obt == ob) && ((ID *)key == id)) {
2484                                         obt->flag |= (OB_RECALC_OB|OB_RECALC_DATA);
2485                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2486                                 }
2487                         }
2488                 }
2489                 
2490                 /* set flags based on particle settings */
2491                 if(idtype == ID_PA) {
2492                         ParticleSystem *psys;
2493                         for(obt=bmain->object.first; obt; obt= obt->id.next)
2494                                 for(psys=obt->particlesystem.first; psys; psys=psys->next)
2495                                         if(&psys->part->id == id)
2496                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2497                 }
2498
2499                 if(idtype == ID_MC) {
2500                         for(obt=bmain->object.first; obt; obt= obt->id.next){
2501                                 bConstraint *con;
2502                                 for (con = obt->constraints.first; con; con=con->next) {
2503                                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2504                                         if(ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER)) {
2505                                                 obt->recalc |= OB_RECALC_OB;
2506                                                 break;
2507                                         }
2508                                 }
2509                         }
2510
2511                         if(sce->nodetree) {
2512                                 bNode *node;
2513
2514                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
2515                                         if(node->id==id) {
2516                                                 nodeUpdate(sce->nodetree, node);
2517                                         }
2518                                 }
2519                         }
2520                 }
2521
2522                 /* camera's matrix is used to orient reconstructed stuff,
2523                    so it should happen tracking-related constraints recalculation
2524                    when camera is changing */
2525                 if(sce->camera && &sce->camera->id == id && sce->clip) {
2526                         dag_id_flush_update(sce, &sce->clip->id);
2527                 }
2528
2529                 /* update editors */
2530                 dag_editors_update(bmain, id);
2531         }
2532 }
2533
2534 void DAG_ids_flush_tagged(Main *bmain)
2535 {
2536         ListBase *lbarray[MAX_LIBARRAY];
2537         Scene *sce;
2538         unsigned int lay;
2539         int a, have_tag = 0;
2540
2541         dag_current_scene_layers(bmain, &sce, &lay);
2542
2543         if(!sce || !sce->theDag)
2544                 return;
2545
2546         /* loop over all ID types */
2547         a  = set_listbasepointers(bmain, lbarray);
2548
2549         while(a--) {
2550                 ListBase *lb = lbarray[a];
2551                 ID *id = lb->first;
2552
2553                 /* we tag based on first ID type character to avoid 
2554                    looping over all ID's in case there are no tags */
2555                 if(id && bmain->id_tag_update[id->name[0]]) {
2556                         for(; id; id=id->next) {
2557                                 if(id->flag & LIB_ID_RECALC) {
2558                                         dag_id_flush_update(sce, id);
2559                                         id->flag &= ~LIB_ID_RECALC;
2560                                 }
2561                         }
2562
2563                         have_tag = 1;
2564                 }
2565         }
2566
2567         if(have_tag) {
2568                 /* clear tags */
2569                 memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update));
2570
2571                 /* flush changes to other objects */
2572                 DAG_scene_flush_update(bmain, sce, lay, 0);
2573         }
2574 }
2575
2576 void DAG_id_tag_update(ID *id, short flag)
2577 {
2578         Main *bmain= G.main;
2579
2580         if(id==NULL) return;
2581         
2582         /* tag ID for update */
2583         id->flag |= LIB_ID_RECALC;
2584         bmain->id_tag_update[id->name[0]] = 1;
2585
2586         /* flag is for objects and particle systems */
2587         if(flag) {
2588                 Object *ob;
2589                 ParticleSystem *psys;
2590                 short idtype = GS(id->name);
2591
2592                 if(idtype == ID_OB) {
2593                         /* only quick tag */
2594                         ob = (Object*)id;
2595                         ob->recalc |= (flag & OB_RECALC_ALL);
2596                 }
2597                 else if(idtype == ID_PA) {
2598                         /* this is weak still, should be done delayed as well */
2599                         for(ob=bmain->object.first; ob; ob=ob->id.next) {
2600                                 for(psys=ob->particlesystem.first; psys; psys=psys->next) {
2601                                         if(&psys->part->id == id) {
2602                                                 ob->recalc |= (flag & OB_RECALC_ALL);
2603                                                 psys->recalc |= (flag & PSYS_RECALC);
2604                                         }
2605                                 }
2606                         }
2607                 }
2608                 else {
2609                         /* disable because this is called on various ID types automatically.
2610                          * where printing warning is not useful. for now just ignore */
2611                         /* BLI_assert(!"invalid flag for this 'idtype'"); */
2612                 }
2613         }
2614 }
2615
2616 #if 0 // UNUSED
2617 /* recursively descends tree, each node only checked once */
2618 /* node is checked to be of type object */
2619 static int parent_check_node(DagNode *node, int curtime)
2620 {
2621         DagAdjList *itA;
2622         
2623         node->lasttime= curtime;
2624         
2625         if(node->color==DAG_GRAY)
2626                 return DAG_GRAY;
2627         
2628         for(itA = node->child; itA; itA= itA->next) {
2629                 if(itA->node->type==ID_OB) {
2630                         
2631                         if(itA->node->color==DAG_GRAY)
2632                                 return DAG_GRAY;
2633
2634                         /* descend if not done */
2635                         if(itA->node->lasttime!=curtime) {
2636                                 itA->node->color= parent_check_node(itA->node, curtime);
2637                         
2638                                 if(itA->node->color==DAG_GRAY)
2639                                         return DAG_GRAY;
2640                         }
2641                 }
2642         }
2643         
2644         return DAG_WHITE;
2645 }
2646 #endif
2647
2648 /* ******************* DAG FOR ARMATURE POSE ***************** */
2649
2650 /* we assume its an armature with pose */
2651 void DAG_pose_sort(Object *ob)
2652 {
2653         bPose *pose= ob->pose;
2654         bPoseChannel *pchan;
2655         bConstraint *con;
2656         DagNode *node;
2657         DagNode *node2, *node3;
2658         DagNode *rootnode;
2659         DagForest *dag;
2660         DagNodeQueue *nqueue;
2661         DagAdjList *itA;
2662         ListBase tempbase;
2663         int skip = 0;
2664         
2665         dag = dag_init();
2666         ugly_hack_sorry= 0;     // no ID structs
2667
2668         rootnode = dag_add_node(dag, NULL);     // node->ob becomes NULL
2669         
2670         /* we add the hierarchy and the constraints */
2671         for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2672                 int addtoroot = 1;
2673                 
2674                 node = dag_get_node(dag, pchan);
2675                 
2676                 if(pchan->parent) {
2677                         node2 = dag_get_node(dag, pchan->parent);
2678                         dag_add_relation(dag, node2, node, 0, "Parent Relation");
2679                         addtoroot = 0;
2680                 }
2681                 for (con = pchan->constraints.first; con; con=con->next) {
2682                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2683                         ListBase targets = {NULL, NULL};
2684                         bConstraintTarget *ct;
2685                         
2686                         if (cti && cti->get_constraint_targets) {
2687                                 cti->get_constraint_targets(con, &targets);
2688                                 
2689                                 for (ct= targets.first; ct; ct= ct->next) {
2690                                         if (ct->tar==ob && ct->subtarget[0]) {
2691                                                 bPoseChannel *target= get_pose_channel(ob->pose, ct->subtarget);
2692                                                 if (target) {
2693                                                         node2= dag_get_node(dag, target);
2694                                                         dag_add_relation(dag, node2, node, 0, "Pose Constraint");
2695                                                         
2696                                                         if (con->type==CONSTRAINT_TYPE_KINEMATIC) {
2697                                                                 bKinematicConstraint *data = (bKinematicConstraint *)con->data;
2698                                                                 bPoseChannel *parchan;
2699                                                                 int segcount= 0;
2700                                                                 
2701                                                                 /* exclude tip from chain? */
2702                                                                 if(!(data->flag & CONSTRAINT_IK_TIP))
2703                                                                         parchan= pchan->parent;
2704                                                                 else
2705                                                                         parchan= pchan;
2706                                                                 
2707                                                                 /* Walk to the chain's root */
2708                                                                 while (parchan) {
2709                                                                         node3= dag_get_node(dag, parchan);
2710                                                                         dag_add_relation(dag, node2, node3, 0, "IK Constraint");
2711                                                                         
2712                                                                         segcount++;
2713                                                                         if (segcount==data->rootbone || segcount>255) break; // 255 is weak
2714                                                                         parchan= parchan->parent;
2715                                                                 }
2716                                                         }
2717                                                 }
2718                                         }
2719                                 }
2720                                 
2721                                 if (cti->flush_constraint_targets)
2722                                         cti->flush_constraint_targets(con, &targets, 1);
2723                         }
2724                 }
2725                 if (addtoroot == 1 ) {
2726                         dag_add_relation(dag, rootnode, node, 0, "Root Bone Relation");
2727                 }
2728         }
2729
2730         dag_check_cycle(dag);
2731         
2732         /* now we try to sort... */
2733         tempbase.first= tempbase.last= NULL;
2734
2735         nqueue = queue_create(DAGQUEUEALLOC);
2736         
2737         /* tag nodes unchecked */
2738         for(node = dag->DagNode.first; node; node= node->next) 
2739                 node->color = DAG_WHITE;
2740         
2741         node = dag->DagNode.first;
2742         
2743         node->color = DAG_GRAY;
2744         push_stack(nqueue, node);  
2745         
2746         while(nqueue->count) {
2747                 
2748                 skip = 0;
2749                 node = get_top_node_queue(nqueue);
2750                 
2751                 itA = node->child;
2752                 while(itA != NULL) {
2753                         if(itA->node->color == DAG_WHITE) {
2754                                 itA->node->color = DAG_GRAY;
2755                                 push_stack(nqueue,itA->node);
2756                                 skip = 1;
2757                                 break;
2758                         } 
2759                         itA = itA->next;
2760                 }                       
2761                 
2762                 if (!skip) {
2763                         if (node) {
2764                                 node = pop_queue(nqueue);
2765                                 if (node->ob == NULL)   // we are done
2766                                         break ;
2767                                 node->color = DAG_BLACK;
2768                                 
2769                                 /* put node in new list */
2770                                 BLI_remlink(&pose->chanbase, node->ob);
2771                                 BLI_addhead(&tempbase, node->ob);
2772                         }       
2773                 }
2774         }
2775         
2776         // temporal correction for circular dependancies
2777         while(pose->chanbase.first) {
2778                 pchan= pose->chanbase.first;
2779                 BLI_remlink(&pose->chanbase, pchan);
2780                 BLI_addhead(&tempbase, pchan);
2781
2782                 printf("cyclic %s\n", pchan->name);
2783         }
2784         
2785         pose->chanbase = tempbase;
2786         queue_delete(nqueue);
2787         
2788 //      printf("\nordered\n");
2789 //      for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2790 //              printf(" %s\n", pchan->name);
2791 //      }
2792         
2793         free_forest( dag );
2794         MEM_freeN( dag );
2795         
2796         ugly_hack_sorry= 1;
2797 }
2798
2799
2800