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