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