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