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