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