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