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