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