23f1d229d6adeee449102744a9479e0c139d2d93
[blender.git] / source / blender / depsgraph / intern / builder / deg_builder_relations.cc
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) 2013 Blender Foundation.
19  * All rights reserved.
20  *
21  * Original Author: Joshua Leung
22  * Contributor(s): Based on original depsgraph.c code - Blender Foundation (2005-2013)
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/depsgraph/intern/builder/deg_builder_relations.cc
28  *  \ingroup depsgraph
29  *
30  * Methods for constructing depsgraph
31  */
32
33 #include "intern/builder/deg_builder_relations.h"
34
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <cstring>  /* required for STREQ later on. */
38
39 #include "MEM_guardedalloc.h"
40
41 #include "BLI_utildefines.h"
42 #include "BLI_blenlib.h"
43
44 extern "C" {
45 #include "DNA_action_types.h"
46 #include "DNA_anim_types.h"
47 #include "DNA_armature_types.h"
48 #include "DNA_camera_types.h"
49 #include "DNA_cachefile_types.h"
50 #include "DNA_collection_types.h"
51 #include "DNA_constraint_types.h"
52 #include "DNA_curve_types.h"
53 #include "DNA_effect_types.h"
54 #include "DNA_gpencil_types.h"
55 #include "DNA_key_types.h"
56 #include "DNA_lamp_types.h"
57 #include "DNA_material_types.h"
58 #include "DNA_mask_types.h"
59 #include "DNA_mesh_types.h"
60 #include "DNA_meta_types.h"
61 #include "DNA_movieclip_types.h"
62 #include "DNA_node_types.h"
63 #include "DNA_particle_types.h"
64 #include "DNA_lightprobe_types.h"
65 #include "DNA_object_types.h"
66 #include "DNA_rigidbody_types.h"
67 #include "DNA_scene_types.h"
68 #include "DNA_speaker_types.h"
69 #include "DNA_texture_types.h"
70 #include "DNA_world_types.h"
71 #include "DNA_object_force_types.h"
72
73 #include "BKE_action.h"
74 #include "BKE_armature.h"
75 #include "BKE_animsys.h"
76 #include "BKE_collection.h"
77 #include "BKE_constraint.h"
78 #include "BKE_curve.h"
79 #include "BKE_effect.h"
80 #include "BKE_collision.h"
81 #include "BKE_fcurve.h"
82 #include "BKE_key.h"
83 #include "BKE_material.h"
84 #include "BKE_mball.h"
85 #include "BKE_modifier.h"
86 #include "BKE_gpencil_modifier.h"
87 #include "BKE_node.h"
88 #include "BKE_object.h"
89 #include "BKE_particle.h"
90 #include "BKE_pointcache.h"
91 #include "BKE_rigidbody.h"
92 #include "BKE_shader_fx.h"
93 #include "BKE_shrinkwrap.h"
94 #include "BKE_sound.h"
95 #include "BKE_tracking.h"
96 #include "BKE_world.h"
97
98 #include "RNA_access.h"
99 #include "RNA_types.h"
100 } /* extern "C" */
101
102 #include "DEG_depsgraph.h"
103 #include "DEG_depsgraph_build.h"
104
105 #include "intern/builder/deg_builder.h"
106 #include "intern/builder/deg_builder_pchanmap.h"
107 #include "intern/eval/deg_eval_copy_on_write.h"
108
109 #include "intern/nodes/deg_node.h"
110 #include "intern/nodes/deg_node_component.h"
111 #include "intern/nodes/deg_node_id.h"
112 #include "intern/nodes/deg_node_operation.h"
113 #include "intern/nodes/deg_node_time.h"
114
115 #include "intern/depsgraph_intern.h"
116 #include "intern/depsgraph_types.h"
117
118 #include "util/deg_util_foreach.h"
119
120 namespace DEG {
121
122 /* ***************** */
123 /* Relations Builder */
124
125 /* TODO(sergey): This is somewhat weak, but we don't want neither false-positive
126  * time dependencies nor special exceptions in the depsgraph evaluation.
127  */
128 static bool python_driver_depends_on_time(ChannelDriver *driver)
129 {
130         if (driver->expression[0] == '\0') {
131                 /* Empty expression depends on nothing. */
132                 return false;
133         }
134         if (strchr(driver->expression, '(') != NULL) {
135                 /* Function calls are considered dependent on a time. */
136                 return true;
137         }
138         if (strstr(driver->expression, "frame") != NULL) {
139                 /* Variable `frame` depends on time. */
140                 /* TODO(sergey): This is a bit weak, but not sure about better way of
141                  * handling this.
142                  */
143                 return true;
144         }
145         /* Possible indirect time relation s should be handled via variable
146          * targets.
147          */
148         return false;
149 }
150
151 static bool particle_system_depends_on_time(ParticleSystem *psys)
152 {
153         ParticleSettings *part = psys->part;
154         /* Non-hair particles we always consider dependent on time. */
155         if (part->type != PART_HAIR) {
156                 return true;
157         }
158         /* Dynamics always depends on time. */
159         if (psys->flag & PSYS_HAIR_DYNAMICS) {
160                 return true;
161         }
162         /* TODO(sergey): Check what else makes hair dependent on time. */
163         return false;
164 }
165
166 static bool object_particles_depends_on_time(Object *object)
167 {
168         if (object->type != OB_MESH) {
169                 return false;
170         }
171         LISTBASE_FOREACH (ParticleSystem *, psys, &object->particlesystem) {
172                 if (particle_system_depends_on_time(psys)) {
173                         return true;
174                 }
175         }
176         return false;
177 }
178
179 static bool check_id_has_anim_component(ID *id)
180 {
181         AnimData *adt = BKE_animdata_from_id(id);
182         if (adt == NULL) {
183                 return false;
184         }
185         return (adt->action != NULL) ||
186                (!BLI_listbase_is_empty(&adt->nla_tracks));
187 }
188
189 static eDepsOperation_Code bone_target_opcode(ID *target,
190                                               const char *subtarget,
191                                               ID *id,
192                                               const char *component_subdata,
193                                               RootPChanMap *root_map)
194 {
195         /* Same armature.  */
196         if (target == id) {
197                 /* Using "done" here breaks in-chain deps, while using
198                  * "ready" here breaks most production rigs instead.
199                  * So, we do a compromise here, and only do this when an
200                  * IK chain conflict may occur.
201                  */
202                 if (root_map->has_common_root(component_subdata, subtarget)) {
203                         return DEG_OPCODE_BONE_READY;
204                 }
205         }
206         return DEG_OPCODE_BONE_DONE;
207 }
208
209 static bool bone_has_segments(Object *object, const char *bone_name)
210 {
211         /* Proxies don't have BONE_SEGMENTS */
212         if (ID_IS_LINKED(object) && object->proxy_from != NULL) {
213                 return false;
214         }
215         /* Only B-Bones have segments. */
216         bPoseChannel *pchan = BKE_pose_channel_find_name(object->pose, bone_name);
217         return pchan && pchan->bone && pchan->bone->segments > 1;
218 }
219
220 /* **** General purpose functions ****  */
221
222 DepsgraphRelationBuilder::DepsgraphRelationBuilder(Main *bmain,
223                                                    Depsgraph *graph)
224     : bmain_(bmain),
225       graph_(graph),
226       scene_(NULL)
227 {
228 }
229
230 TimeSourceDepsNode *DepsgraphRelationBuilder::get_node(
231         const TimeSourceKey &key) const
232 {
233         if (key.id) {
234                 /* XXX TODO */
235                 return NULL;
236         }
237         else {
238                 return graph_->time_source;
239         }
240 }
241
242 ComponentDepsNode *DepsgraphRelationBuilder::get_node(
243         const ComponentKey &key) const
244 {
245         IDDepsNode *id_node = graph_->find_id_node(key.id);
246         if (!id_node) {
247                 fprintf(stderr, "find_node component: Could not find ID %s\n",
248                         (key.id != NULL) ? key.id->name : "<null>");
249                 return NULL;
250         }
251
252         ComponentDepsNode *node = id_node->find_component(key.type, key.name);
253         return node;
254 }
255
256 OperationDepsNode *DepsgraphRelationBuilder::get_node(
257         const OperationKey &key) const
258 {
259         OperationDepsNode *op_node = find_node(key);
260         if (op_node == NULL) {
261                 fprintf(stderr, "find_node_operation: Failed for (%s, '%s')\n",
262                         operationCodeAsString(key.opcode), key.name);
263         }
264         return op_node;
265 }
266
267 DepsNode *DepsgraphRelationBuilder::get_node(const RNAPathKey &key) const
268 {
269         return graph_->find_node_from_pointer(&key.ptr, key.prop);
270 }
271
272 OperationDepsNode *DepsgraphRelationBuilder::find_node(
273         const OperationKey &key) const
274 {
275         IDDepsNode *id_node = graph_->find_id_node(key.id);
276         if (!id_node) {
277                 return NULL;
278         }
279         ComponentDepsNode *comp_node = id_node->find_component(key.component_type,
280                                                                key.component_name);
281         if (!comp_node) {
282                 return NULL;
283         }
284         return comp_node->find_operation(key.opcode, key.name, key.name_tag);
285 }
286
287 bool DepsgraphRelationBuilder::has_node(const OperationKey &key) const
288 {
289         return find_node(key) != NULL;
290 }
291
292 void DepsgraphRelationBuilder::add_customdata_mask(Object *object, uint64_t mask)
293 {
294         if (mask != 0 && object != NULL && object->type == OB_MESH) {
295                 DEG::IDDepsNode *id_node = graph_->find_id_node(&object->id);
296
297                 if (id_node == NULL) {
298                         BLI_assert(!"ID should always be valid");
299                 }
300                 else {
301                         id_node->customdata_mask |= mask;
302                 }
303         }
304 }
305
306 void DepsgraphRelationBuilder::add_special_eval_flag(ID *id, uint32_t flag)
307 {
308         DEG::IDDepsNode *id_node = graph_->find_id_node(id);
309         if (id_node == NULL) {
310                 BLI_assert(!"ID should always be valid");
311         }
312         else {
313                 id_node->eval_flags |= flag;
314         }
315 }
316
317 DepsRelation *DepsgraphRelationBuilder::add_time_relation(
318         TimeSourceDepsNode *timesrc,
319         DepsNode *node_to,
320         const char *description,
321         bool check_unique,
322         int flags)
323 {
324         if (timesrc && node_to) {
325                 return graph_->add_new_relation(
326                         timesrc, node_to, description, check_unique, flags);
327         }
328         else {
329                 DEG_DEBUG_PRINTF((::Depsgraph *)graph_,
330                                  BUILD, "add_time_relation(%p = %s, %p = %s, %s) Failed\n",
331                                  timesrc,   (timesrc) ? timesrc->identifier().c_str() : "<None>",
332                                  node_to,   (node_to) ? node_to->identifier().c_str() : "<None>",
333                                  description);
334         }
335         return NULL;
336 }
337
338 DepsRelation *DepsgraphRelationBuilder::add_operation_relation(
339         OperationDepsNode *node_from,
340         OperationDepsNode *node_to,
341         const char *description,
342         bool check_unique,
343         int flags)
344 {
345         if (node_from && node_to) {
346                 return graph_->add_new_relation(node_from,
347                                                 node_to,
348                                                 description,
349                                                 check_unique,
350                                                 flags);
351         }
352         else {
353                 DEG_DEBUG_PRINTF((::Depsgraph *)graph_,
354                                  BUILD, "add_operation_relation(%p = %s, %p = %s, %s) Failed\n",
355                                  node_from, (node_from) ? node_from->identifier().c_str() : "<None>",
356                                  node_to,   (node_to)   ? node_to->identifier().c_str() : "<None>",
357                                  description);
358         }
359         return NULL;
360 }
361
362 void DepsgraphRelationBuilder::add_collision_relations(
363         const OperationKey &key,
364         Object *object,
365         Collection *collection,
366         const char *name)
367 {
368         ListBase *relations = deg_build_collision_relations(graph_, collection, eModifierType_Collision);
369
370         LISTBASE_FOREACH (CollisionRelation *, relation, relations) {
371                 if (relation->ob != object) {
372                         ComponentKey trf_key(&relation->ob->id, DEG_NODE_TYPE_TRANSFORM);
373                         add_relation(trf_key, key, name);
374
375                         ComponentKey coll_key(&relation->ob->id, DEG_NODE_TYPE_GEOMETRY);
376                         add_relation(coll_key, key, name);
377                 }
378         }
379 }
380
381 void DepsgraphRelationBuilder::add_forcefield_relations(
382         const OperationKey &key,
383         Object *object,
384         ParticleSystem *psys,
385         EffectorWeights *eff,
386         bool add_absorption,
387         const char *name)
388 {
389         ListBase *relations = deg_build_effector_relations(graph_, eff->group);
390
391         LISTBASE_FOREACH (EffectorRelation *, relation, relations) {
392                 if (relation->ob != object) {
393                         ComponentKey eff_key(&relation->ob->id, DEG_NODE_TYPE_TRANSFORM);
394                         add_relation(eff_key, key, name);
395
396                         if (relation->pd->forcefield == PFIELD_SMOKEFLOW && relation->pd->f_source) {
397                                 ComponentKey trf_key(&relation->pd->f_source->id,
398                                                      DEG_NODE_TYPE_TRANSFORM);
399                                 add_relation(trf_key, key, "Smoke Force Domain");
400                                 ComponentKey eff_key(&relation->pd->f_source->id,
401                                                      DEG_NODE_TYPE_GEOMETRY);
402                                 add_relation(eff_key, key, "Smoke Force Domain");
403                         }
404                         if (add_absorption && (relation->pd->flag & PFIELD_VISIBILITY)) {
405                                 add_collision_relations(key,
406                                                         object,
407                                                         NULL,
408                                                         "Force Absorption");
409                         }
410                 }
411                 if (relation->psys) {
412                         if (relation->ob != object) {
413                                 ComponentKey eff_key(&relation->ob->id, DEG_NODE_TYPE_EVAL_PARTICLES);
414                                 add_relation(eff_key, key, name);
415                                 /* TODO: remove this when/if EVAL_PARTICLES is sufficient
416                                  * for up to date particles.
417                                  */
418                                 ComponentKey mod_key(&relation->ob->id, DEG_NODE_TYPE_GEOMETRY);
419                                 add_relation(mod_key, key, name);
420                         }
421                         else if (relation->psys != psys) {
422                                 OperationKey eff_key(&relation->ob->id,
423                                                      DEG_NODE_TYPE_EVAL_PARTICLES,
424                                                      DEG_OPCODE_PARTICLE_SYSTEM_EVAL,
425                                                      relation->psys->name);
426                                 add_relation(eff_key, key, name);
427                         }
428                 }
429         }
430 }
431
432 Depsgraph *DepsgraphRelationBuilder::getGraph()
433 {
434         return graph_;
435 }
436
437 /* **** Functions to build relations between entities  **** */
438
439 void DepsgraphRelationBuilder::begin_build()
440 {
441 }
442
443 void DepsgraphRelationBuilder::build_id(ID *id)
444 {
445         if (id == NULL) {
446                 return;
447         }
448         switch (GS(id->name)) {
449                 case ID_AC:
450                         build_action((bAction *)id);
451                         break;
452                 case ID_AR:
453                         build_armature((bArmature *)id);
454                         break;
455                 case ID_CA:
456                         build_camera((Camera *)id);
457                         break;
458                 case ID_GR:
459                         build_collection(NULL, NULL, (Collection *)id);
460                         break;
461                 case ID_OB:
462                         build_object(NULL, (Object *)id);
463                         break;
464                 case ID_KE:
465                         build_shapekeys((Key *)id);
466                         break;
467                 case ID_LA:
468                         build_lamp((Lamp *)id);
469                         break;
470                 case ID_LP:
471                         build_lightprobe((LightProbe *)id);
472                         break;
473                 case ID_NT:
474                         build_nodetree((bNodeTree *)id);
475                         break;
476                 case ID_MA:
477                         build_material((Material *)id);
478                         break;
479                 case ID_TE:
480                         build_texture((Tex *)id);
481                         break;
482                 case ID_WO:
483                         build_world((World *)id);
484                         break;
485                 case ID_MSK:
486                         build_mask((Mask *)id);
487                         break;
488                 case ID_MC:
489                         build_movieclip((MovieClip *)id);
490                         break;
491                 case ID_ME:
492                 case ID_CU:
493                 case ID_MB:
494                 case ID_LT:
495                         build_object_data_geometry_datablock(id);
496                         break;
497                 case ID_SPK:
498                         build_speaker((Speaker *)id);
499                         break;
500                 case ID_TXT:
501                         /* Not a part of dependency graph. */
502                         break;
503                 case ID_CF:
504                         build_cachefile((CacheFile *)id);
505                         break;
506                 default:
507                         fprintf(stderr, "Unhandled ID %s\n", id->name);
508                         BLI_assert(!"Should never happen");
509                         break;
510         }
511 }
512
513 void DepsgraphRelationBuilder::build_collection(
514         LayerCollection *from_layer_collection,
515         Object *object,
516         Collection *collection)
517 {
518         if (from_layer_collection != NULL) {
519                 /* If we came from layer collection we don't go deeper, view layer
520                  * builder takes care of going deeper.
521                  *
522                  * NOTE: Do early output before tagging build as done, so possbile
523                  * subsequent builds from outside of the layer collection properly
524                  * recurses into all the nested objects and collections. */
525                 return;
526         }
527         const bool group_done = built_map_.checkIsBuiltAndTag(collection);
528         OperationKey object_transform_final_key(object != NULL ? &object->id : NULL,
529                                                 DEG_NODE_TYPE_TRANSFORM,
530                                                 DEG_OPCODE_TRANSFORM_FINAL);
531         ComponentKey duplicator_key(object != NULL ? &object->id : NULL,
532                                     DEG_NODE_TYPE_DUPLI);
533         if (!group_done) {
534                 LISTBASE_FOREACH (CollectionObject *, cob, &collection->gobject) {
535                         build_object(NULL, cob->ob);
536                 }
537                 LISTBASE_FOREACH (CollectionChild *, child, &collection->children) {
538                         build_collection(NULL, NULL, child->collection);
539                 }
540         }
541         if (object != NULL) {
542                 FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_BEGIN(collection, ob, graph_->mode)
543                 {
544                         ComponentKey dupli_transform_key(&ob->id, DEG_NODE_TYPE_TRANSFORM);
545                         add_relation(dupli_transform_key,
546                                      object_transform_final_key,
547                                      "Dupligroup");
548                         /* Hook to special component, to ensure proper visibility/evaluation
549                          * optimizations.
550                          */
551                         add_relation(dupli_transform_key, duplicator_key, "Dupligroup");
552                         const eDepsNode_Type dupli_geometry_component_type =
553                                 deg_geometry_tag_to_component(&ob->id);
554                         if (dupli_geometry_component_type != DEG_NODE_TYPE_UNDEFINED) {
555                                 ComponentKey dupli_geometry_component_key(
556                                         &ob->id, dupli_geometry_component_type);
557                                 add_relation(dupli_geometry_component_key,
558                                              duplicator_key,
559                                              "Dupligroup");
560                         }
561                 }
562                 FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_END;
563         }
564 }
565
566 void DepsgraphRelationBuilder::build_object(Base *base, Object *object)
567 {
568         if (built_map_.checkIsBuiltAndTag(object)) {
569                 if (base != NULL) {
570                         build_object_flags(base, object);
571                 }
572                 return;
573         }
574         /* Object Transforms */
575         eDepsOperation_Code base_op = (object->parent) ? DEG_OPCODE_TRANSFORM_PARENT
576                                                        : DEG_OPCODE_TRANSFORM_LOCAL;
577         OperationKey base_op_key(&object->id, DEG_NODE_TYPE_TRANSFORM, base_op);
578         OperationKey local_transform_key(&object->id,
579                                          DEG_NODE_TYPE_TRANSFORM,
580                                          DEG_OPCODE_TRANSFORM_LOCAL);
581         OperationKey parent_transform_key(&object->id,
582                                           DEG_NODE_TYPE_TRANSFORM,
583                                           DEG_OPCODE_TRANSFORM_PARENT);
584         OperationKey final_transform_key(&object->id,
585                                          DEG_NODE_TYPE_TRANSFORM,
586                                          DEG_OPCODE_TRANSFORM_FINAL);
587         OperationKey ob_ubereval_key(&object->id,
588                                      DEG_NODE_TYPE_TRANSFORM,
589                                      DEG_OPCODE_TRANSFORM_OBJECT_UBEREVAL);
590         /* Various flags, flushing from bases/collections. */
591         build_object_flags(base, object);
592         /* Parenting. */
593         if (object->parent != NULL) {
594                 /* Make sure parent object's relations are built. */
595                 build_object(NULL, object->parent);
596                 /* Parent relationship. */
597                 build_object_parent(object);
598                 /* Local -> parent. */
599                 add_relation(local_transform_key,
600                              parent_transform_key,
601                              "ObLocal -> ObParent");
602         }
603         /* Modifiers. */
604         if (object->modifiers.first != NULL) {
605                 BuilderWalkUserData data;
606                 data.builder = this;
607                 modifiers_foreachIDLink(object, modifier_walk, &data);
608         }
609         /* Grease Pencil Modifiers. */
610         if (object->greasepencil_modifiers.first != NULL) {
611                 BuilderWalkUserData data;
612                 data.builder = this;
613                 BKE_gpencil_modifiers_foreachIDLink(object, modifier_walk, &data);
614         }
615         /* Shader FX. */
616         if (object->shader_fx.first != NULL) {
617                 BuilderWalkUserData data;
618                 data.builder = this;
619                 BKE_shaderfx_foreachIDLink(object, modifier_walk, &data);
620         }
621         /* Constraints. */
622         if (object->constraints.first != NULL) {
623                 BuilderWalkUserData data;
624                 data.builder = this;
625                 BKE_constraints_id_loop(&object->constraints, constraint_walk, &data);
626         }
627         /* Object constraints. */
628         if (object->constraints.first != NULL) {
629                 OperationKey constraint_key(&object->id,
630                                             DEG_NODE_TYPE_TRANSFORM,
631                                             DEG_OPCODE_TRANSFORM_CONSTRAINTS);
632                 /* Constraint relations. */
633                 build_constraints(&object->id,
634                                   DEG_NODE_TYPE_TRANSFORM,
635                                   "",
636                                   &object->constraints,
637                                   NULL);
638                 /* operation order */
639                 add_relation(base_op_key, constraint_key, "ObBase-> Constraint Stack");
640                 add_relation(constraint_key, final_transform_key, "ObConstraints -> Done");
641                 // XXX
642                 add_relation(constraint_key, ob_ubereval_key, "Temp Ubereval");
643                 add_relation(ob_ubereval_key, final_transform_key, "Temp Ubereval");
644         }
645         else {
646                 /* NOTE: Keep an eye here, we skip some relations here to "streamline"
647                  * dependencies and avoid transitive relations which causes overhead.
648                  * But once we get rid of uber eval node this will need reconsideration.
649                  */
650                 if (object->rigidbody_object == NULL) {
651                         /* Rigid body will hook up another node inbetween, so skip
652                          * relation here to avoid transitive relation.
653                          */
654                         add_relation(base_op_key, ob_ubereval_key, "Temp Ubereval");
655                 }
656                 add_relation(ob_ubereval_key, final_transform_key, "Temp Ubereval");
657         }
658         /* Animation data */
659         build_animdata(&object->id);
660         /* Object data. */
661         build_object_data(object);
662         /* Particle systems. */
663         if (object->particlesystem.first != NULL) {
664                 build_particles(object);
665         }
666         /* Proxy object to copy from. */
667         if (object->proxy_from != NULL) {
668                 build_object(NULL, object->proxy_from);
669                 ComponentKey ob_transform_key(&object->proxy_from->id, DEG_NODE_TYPE_TRANSFORM);
670                 ComponentKey proxy_transform_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
671                 add_relation(ob_transform_key, proxy_transform_key, "Proxy Transform");
672         }
673         if (object->proxy_group != NULL) {
674                 build_object(NULL, object->proxy_group);
675                 OperationKey proxy_group_ubereval_key(&object->proxy_group->id,
676                                                       DEG_NODE_TYPE_TRANSFORM,
677                                                       DEG_OPCODE_TRANSFORM_OBJECT_UBEREVAL);
678                 add_relation(proxy_group_ubereval_key, final_transform_key, "Proxy Group Transform");
679         }
680         /* Object dupligroup. */
681         if (object->dup_group != NULL) {
682                 build_collection(NULL, object, object->dup_group);
683         }
684         /* Point caches. */
685         build_object_pointcache(object);
686         /* Syncronization back to original object. */
687         OperationKey synchronize_key(&object->id,
688                                      DEG_NODE_TYPE_SYNCHRONIZE,
689                                      DEG_OPCODE_SYNCHRONIZE_TO_ORIGINAL);
690         add_relation(
691                 final_transform_key, synchronize_key, "Synchronize to Original");
692 }
693
694 void DepsgraphRelationBuilder::build_object_flags(Base *base, Object *object)
695 {
696         if (base == NULL) {
697                 return;
698         }
699         OperationKey view_layer_done_key(&scene_->id,
700                                          DEG_NODE_TYPE_LAYER_COLLECTIONS,
701                                          DEG_OPCODE_VIEW_LAYER_EVAL);
702         OperationKey object_flags_key(&object->id,
703                                       DEG_NODE_TYPE_OBJECT_FROM_LAYER,
704                                       DEG_OPCODE_OBJECT_BASE_FLAGS);
705         add_relation(view_layer_done_key, object_flags_key, "Base flags flush");
706         /* Syncronization back to original object. */
707         OperationKey synchronize_key(&object->id,
708                                      DEG_NODE_TYPE_SYNCHRONIZE,
709                                      DEG_OPCODE_SYNCHRONIZE_TO_ORIGINAL);
710         add_relation(
711                 object_flags_key, synchronize_key, "Synchronize to Original");
712 }
713
714 void DepsgraphRelationBuilder::build_object_data(Object *object)
715 {
716         if (object->data == NULL) {
717                 return;
718         }
719         ID *obdata_id = (ID *)object->data;
720         /* Object data animation. */
721         if (!built_map_.checkIsBuilt(obdata_id)) {
722                 build_animdata(obdata_id);
723         }
724         /* type-specific data. */
725         switch (object->type) {
726                 case OB_MESH:
727                 case OB_CURVE:
728                 case OB_FONT:
729                 case OB_SURF:
730                 case OB_MBALL:
731                 case OB_LATTICE:
732                 case OB_GPENCIL:
733                 {
734                         build_object_data_geometry(object);
735                         /* TODO(sergey): Only for until we support granular
736                          * update of curves.
737                          */
738                         if (object->type == OB_FONT) {
739                                 Curve *curve = (Curve *)object->data;
740                                 if (curve->textoncurve) {
741                                         add_special_eval_flag(&curve->textoncurve->id, DAG_EVAL_NEED_CURVE_PATH);
742                                 }
743                         }
744                         break;
745                 }
746                 case OB_ARMATURE:
747                         if (ID_IS_LINKED(object) && object->proxy_from != NULL) {
748                                 build_proxy_rig(object);
749                         }
750                         else {
751                                  build_rig(object);
752                         }
753                         break;
754                 case OB_LAMP:
755                         build_object_data_lamp(object);
756                         break;
757                 case OB_CAMERA:
758                         build_object_data_camera(object);
759                         break;
760                 case OB_LIGHTPROBE:
761                         build_object_data_lightprobe(object);
762                         break;
763                 case OB_SPEAKER:
764                         build_object_data_speaker(object);
765                         break;
766         }
767         Key *key = BKE_key_from_object(object);
768         if (key != NULL) {
769                 ComponentKey geometry_key((ID *)object->data, DEG_NODE_TYPE_GEOMETRY);
770                 ComponentKey key_key(&key->id, DEG_NODE_TYPE_GEOMETRY);
771                 add_relation(key_key, geometry_key, "Shapekeys");
772                 build_nested_shapekey(&object->id, key);
773         }
774 }
775
776 void DepsgraphRelationBuilder::build_object_data_camera(Object *object)
777 {
778         Camera *camera = (Camera *)object->data;
779         build_camera(camera);
780         ComponentKey object_parameters_key(&object->id, DEG_NODE_TYPE_PARAMETERS);
781         ComponentKey camera_parameters_key(&camera->id, DEG_NODE_TYPE_PARAMETERS);
782         add_relation(camera_parameters_key, object_parameters_key, "Camera -> Object");
783 }
784
785 void DepsgraphRelationBuilder::build_object_data_lamp(Object *object)
786 {
787         Lamp *lamp = (Lamp *)object->data;
788         build_lamp(lamp);
789         ComponentKey object_parameters_key(&object->id, DEG_NODE_TYPE_PARAMETERS);
790         ComponentKey lamp_parameters_key(&lamp->id, DEG_NODE_TYPE_PARAMETERS);
791         add_relation(lamp_parameters_key, object_parameters_key, "Light -> Object");
792 }
793
794 void DepsgraphRelationBuilder::build_object_data_lightprobe(Object *object)
795 {
796         LightProbe *probe = (LightProbe *)object->data;
797         build_lightprobe(probe);
798         OperationKey probe_key(&probe->id,
799                                DEG_NODE_TYPE_PARAMETERS,
800                                DEG_OPCODE_LIGHT_PROBE_EVAL);
801         OperationKey object_key(&object->id,
802                                 DEG_NODE_TYPE_PARAMETERS,
803                                 DEG_OPCODE_LIGHT_PROBE_EVAL);
804         add_relation(probe_key, object_key, "LightProbe Update");
805 }
806
807 void DepsgraphRelationBuilder::build_object_data_speaker(Object *object)
808 {
809         Speaker *speaker = (Speaker *)object->data;
810         build_speaker(speaker);
811         OperationKey probe_key(&speaker->id,
812                                DEG_NODE_TYPE_PARAMETERS,
813                                DEG_OPCODE_SPEAKER_EVAL);
814         OperationKey object_key(&object->id,
815                                 DEG_NODE_TYPE_PARAMETERS,
816                                 DEG_OPCODE_SPEAKER_EVAL);
817         add_relation(probe_key, object_key, "Speaker Update");
818 }
819
820 void DepsgraphRelationBuilder::build_object_parent(Object *object)
821 {
822         /* XXX: for now, need to use the component key (not just direct to the parent op),
823          * or else the matrix doesn't get reset/
824          */
825         // XXX: @sergey - it would be good if we got that backwards flushing working
826         // when tagging for updates.
827         //OperationKey ob_key(&object->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_PARENT);
828         ComponentKey ob_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
829
830         /* type-specific links */
831         switch (object->partype) {
832                 case PARSKEL:  /* Armature Deform (Virtual Modifier) */
833                 {
834                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
835                         add_relation(parent_key, ob_key, "Armature Deform Parent");
836                         break;
837                 }
838
839                 case PARVERT1: /* Vertex Parent */
840                 case PARVERT3:
841                 {
842                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_GEOMETRY);
843                         add_relation(parent_key, ob_key, "Vertex Parent");
844
845                         /* XXX not sure what this is for or how you could be done properly - lukas */
846                         add_customdata_mask(object->parent, CD_MASK_ORIGINDEX);
847
848                         ComponentKey transform_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
849                         add_relation(transform_key, ob_key, "Vertex Parent TFM");
850                         break;
851                 }
852
853                 case PARBONE: /* Bone Parent */
854                 {
855                         ComponentKey parent_bone_key(&object->parent->id,
856                                                      DEG_NODE_TYPE_BONE,
857                                                      object->parsubstr);
858                         OperationKey parent_transform_key(&object->parent->id,
859                                                           DEG_NODE_TYPE_TRANSFORM,
860                                                           DEG_OPCODE_TRANSFORM_FINAL);
861                         add_relation(parent_bone_key, ob_key, "Bone Parent");
862                         add_relation(parent_transform_key, ob_key, "Armature Parent");
863                         break;
864                 }
865
866                 default:
867                 {
868                         if (object->parent->type == OB_LATTICE) {
869                                 /* Lattice Deform Parent - Virtual Modifier */
870                                 // XXX: no virtual modifiers should be left!
871                                 ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
872                                 ComponentKey geom_key(&object->parent->id, DEG_NODE_TYPE_GEOMETRY);
873
874                                 add_relation(parent_key, ob_key, "Lattice Deform Parent");
875                                 add_relation(geom_key, ob_key, "Lattice Deform Parent Geom");
876                         }
877                         else if (object->parent->type == OB_CURVE) {
878                                 Curve *cu = (Curve *)object->parent->data;
879
880                                 if (cu->flag & CU_PATH) {
881                                         /* Follow Path */
882                                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_GEOMETRY);
883                                         add_relation(parent_key, ob_key, "Curve Follow Parent");
884
885                                         ComponentKey transform_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
886                                         add_relation(transform_key, ob_key, "Curve Follow TFM");
887                                 }
888                                 else {
889                                         /* Standard Parent */
890                                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
891                                         add_relation(parent_key, ob_key, "Curve Parent");
892                                 }
893                         }
894                         else {
895                                 /* Standard Parent */
896                                 ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
897                                 add_relation(parent_key, ob_key, "Parent");
898                         }
899                         break;
900                 }
901         }
902 }
903
904 void DepsgraphRelationBuilder::build_object_pointcache(Object *object)
905 {
906         ComponentKey point_cache_key(&object->id, DEG_NODE_TYPE_POINT_CACHE);
907         /* Different point caches are affecting different aspects of life of the
908          * object. We keep track of those aspects and avoid duplicate relations. */
909         enum {
910                 FLAG_TRANSFORM = (1 << 0),
911                 FLAG_GEOMETRY = (1 << 1),
912                 FLAG_ALL = (FLAG_TRANSFORM | FLAG_GEOMETRY),
913         };
914         ListBase ptcache_id_list;
915         BKE_ptcache_ids_from_object(&ptcache_id_list, object, scene_, 0);
916         int handled_components = 0;
917         LISTBASE_FOREACH (PTCacheID *, ptcache_id, &ptcache_id_list) {
918                 /* Check which components needs the point cache. */
919                 int flag;
920                 if (ptcache_id->type == PTCACHE_TYPE_RIGIDBODY) {
921                         flag = FLAG_TRANSFORM;
922                         ComponentKey transform_key(&object->id,
923                                                    DEG_NODE_TYPE_TRANSFORM);
924                         add_relation(point_cache_key,
925                                      transform_key,
926                                      "Point Cache -> Rigid Body");
927                 }
928                 else {
929                         flag = FLAG_GEOMETRY;
930                         ComponentKey geometry_key(&object->id,
931                                                    DEG_NODE_TYPE_GEOMETRY);
932                         add_relation(point_cache_key,
933                                      geometry_key,
934                                      "Point Cache -> Geometry");
935                 }
936                 /* Tag that we did handle that component. */
937                 handled_components |= flag;
938                 if (handled_components == FLAG_ALL) {
939                         break;
940                 }
941         }
942         BLI_freelistN(&ptcache_id_list);
943 }
944
945 void DepsgraphRelationBuilder::build_constraints(ID *id,
946                                                  eDepsNode_Type component_type,
947                                                  const char *component_subdata,
948                                                  ListBase *constraints,
949                                                  RootPChanMap *root_map)
950 {
951         OperationKey constraint_op_key(
952                 id,
953                 component_type,
954                 component_subdata,
955                 (component_type == DEG_NODE_TYPE_BONE)
956                         ? DEG_OPCODE_BONE_CONSTRAINTS
957                         : DEG_OPCODE_TRANSFORM_CONSTRAINTS);
958         /* Add dependencies for each constraint in turn. */
959         for (bConstraint *con = (bConstraint *)constraints->first; con; con = con->next) {
960                 const bConstraintTypeInfo *cti = BKE_constraint_typeinfo_get(con);
961                 /* Invalid constraint type. */
962                 if (cti == NULL) {
963                         continue;
964                 }
965                 /* Special case for camera tracking -- it doesn't use targets to
966                  * define relations.
967                  */
968                 /* TODO: we can now represent dependencies in a much richer manner,
969                  * so review how this is done.
970                  */
971                 if (ELEM(cti->type,
972                          CONSTRAINT_TYPE_FOLLOWTRACK,
973                          CONSTRAINT_TYPE_CAMERASOLVER,
974                          CONSTRAINT_TYPE_OBJECTSOLVER))
975                 {
976                         bool depends_on_camera = false;
977                         if (cti->type == CONSTRAINT_TYPE_FOLLOWTRACK) {
978                                 bFollowTrackConstraint *data = (bFollowTrackConstraint *)con->data;
979                                 if (((data->clip) ||
980                                      (data->flag & FOLLOWTRACK_ACTIVECLIP)) && data->track[0])
981                                 {
982                                         depends_on_camera = true;
983                                 }
984                                 if (data->depth_ob) {
985                                         ComponentKey depth_transform_key(&data->depth_ob->id,
986                                                                          DEG_NODE_TYPE_TRANSFORM);
987                                         ComponentKey depth_geometry_key(&data->depth_ob->id,
988                                                                         DEG_NODE_TYPE_GEOMETRY);
989                                         add_relation(depth_transform_key, constraint_op_key, cti->name);
990                                         add_relation(depth_geometry_key, constraint_op_key, cti->name);
991                                 }
992                         }
993                         else if (cti->type == CONSTRAINT_TYPE_OBJECTSOLVER) {
994                                 depends_on_camera = true;
995                         }
996                         if (depends_on_camera && scene_->camera != NULL) {
997                                 ComponentKey camera_key(&scene_->camera->id, DEG_NODE_TYPE_TRANSFORM);
998                                 add_relation(camera_key, constraint_op_key, cti->name);
999                         }
1000                         /* TODO(sergey): This is more a TimeSource -> MovieClip ->
1001                          * Constraint dependency chain.
1002                          */
1003                         TimeSourceKey time_src_key;
1004                         add_relation(time_src_key, constraint_op_key, "TimeSrc -> Animation");
1005                 }
1006                 else if (cti->type == CONSTRAINT_TYPE_TRANSFORM_CACHE) {
1007                         /* TODO(kevin): This is more a TimeSource -> CacheFile -> Constraint
1008                          * dependency chain.
1009                          */
1010                         TimeSourceKey time_src_key;
1011                         add_relation(time_src_key, constraint_op_key, "TimeSrc -> Animation");
1012                         bTransformCacheConstraint *data = (bTransformCacheConstraint *)con->data;
1013                         if (data->cache_file) {
1014                                 ComponentKey cache_key(&data->cache_file->id, DEG_NODE_TYPE_CACHE);
1015                                 add_relation(cache_key, constraint_op_key, cti->name);
1016                         }
1017                 }
1018                 else if (cti->get_constraint_targets) {
1019                         ListBase targets = {NULL, NULL};
1020                         cti->get_constraint_targets(con, &targets);
1021                         LISTBASE_FOREACH (bConstraintTarget *, ct, &targets) {
1022                                 if (ct->tar == NULL) {
1023                                         continue;
1024                                 }
1025                                 if (ELEM(con->type,
1026                                          CONSTRAINT_TYPE_KINEMATIC,
1027                                          CONSTRAINT_TYPE_SPLINEIK))
1028                                 {
1029                                         /* Ignore IK constraints - these are handled separately
1030                                          * (on pose level).
1031                                          */
1032                                 }
1033                                 else if (ELEM(con->type,
1034                                               CONSTRAINT_TYPE_FOLLOWPATH,
1035                                               CONSTRAINT_TYPE_CLAMPTO))
1036                                 {
1037                                         /* These constraints require path geometry data. */
1038                                         ComponentKey target_key(&ct->tar->id, DEG_NODE_TYPE_GEOMETRY);
1039                                         add_relation(target_key, constraint_op_key, cti->name);
1040                                         ComponentKey target_transform_key(&ct->tar->id,
1041                                                                           DEG_NODE_TYPE_TRANSFORM);
1042                                         add_relation(target_transform_key, constraint_op_key, cti->name);
1043                                 }
1044                                 else if ((ct->tar->type == OB_ARMATURE) && (ct->subtarget[0])) {
1045                                         eDepsOperation_Code opcode;
1046                                         /* relation to bone */
1047                                         opcode = bone_target_opcode(&ct->tar->id, ct->subtarget,
1048                                                                     id, component_subdata, root_map);
1049                                         /* Armature constraint always wants the final position and chan_mat. */
1050                                         if (ELEM(con->type, CONSTRAINT_TYPE_ARMATURE)) {
1051                                                 opcode = DEG_OPCODE_BONE_DONE;
1052                                         }
1053                                         /* if needs bbone shape, reference the segment computation */
1054                                         if (BKE_constraint_target_uses_bbone(con, ct) &&
1055                                             bone_has_segments(ct->tar, ct->subtarget))
1056                                         {
1057                                                 opcode = DEG_OPCODE_BONE_SEGMENTS;
1058                                         }
1059                                         OperationKey target_key(&ct->tar->id,
1060                                                                 DEG_NODE_TYPE_BONE,
1061                                                                 ct->subtarget,
1062                                                                 opcode);
1063                                         add_relation(target_key, constraint_op_key, cti->name);
1064                                 }
1065                                 else if (ELEM(ct->tar->type, OB_MESH, OB_LATTICE) &&
1066                                          (ct->subtarget[0]))
1067                                 {
1068                                         /* Vertex group. */
1069                                         /* NOTE: for now, we don't need to represent vertex groups
1070                                          * separately.
1071                                          */
1072                                         ComponentKey target_key(&ct->tar->id, DEG_NODE_TYPE_GEOMETRY);
1073                                         add_relation(target_key, constraint_op_key, cti->name);
1074                                         add_customdata_mask(ct->tar, CD_MASK_MDEFORMVERT);
1075                                 }
1076                                 else if (con->type == CONSTRAINT_TYPE_SHRINKWRAP) {
1077                                         bShrinkwrapConstraint *scon = (bShrinkwrapConstraint *) con->data;
1078
1079                                         /* Constraints which requires the target object surface. */
1080                                         ComponentKey target_key(&ct->tar->id, DEG_NODE_TYPE_GEOMETRY);
1081                                         add_relation(target_key, constraint_op_key, cti->name);
1082
1083                                         /* Add dependency on normal layers if necessary. */
1084                                         if (ct->tar->type == OB_MESH && scon->shrinkType != MOD_SHRINKWRAP_NEAREST_VERTEX) {
1085                                                 bool track = (scon->flag & CON_SHRINKWRAP_TRACK_NORMAL) != 0;
1086                                                 if (track || BKE_shrinkwrap_needs_normals(scon->shrinkType, scon->shrinkMode)) {
1087                                                         add_customdata_mask(ct->tar, CD_MASK_NORMAL | CD_MASK_CUSTOMLOOPNORMAL);
1088                                                 }
1089                                                 if (scon->shrinkType == MOD_SHRINKWRAP_TARGET_PROJECT) {
1090                                                         add_special_eval_flag(&ct->tar->id, DAG_EVAL_NEED_SHRINKWRAP_BOUNDARY);
1091                                                 }
1092                                         }
1093
1094                                         /* NOTE: obdata eval now doesn't necessarily depend on the
1095                                          * object's transform.
1096                                          */
1097                                         ComponentKey target_transform_key(&ct->tar->id,
1098                                                                           DEG_NODE_TYPE_TRANSFORM);
1099                                         add_relation(target_transform_key, constraint_op_key, cti->name);
1100                                 }
1101                                 else {
1102                                         /* Standard object relation. */
1103                                         // TODO: loc vs rot vs scale?
1104                                         if (&ct->tar->id == id) {
1105                                                 /* Constraint targeting own object:
1106                                                  * - This case is fine IFF we're dealing with a bone
1107                                                  *   constraint pointing to its own armature. In that
1108                                                  *   case, it's just transform -> bone.
1109                                                  * - If however it is a real self targeting case, just
1110                                                  *   make it depend on the previous constraint (or the
1111                                                  *   pre-constraint state).
1112                                                  */
1113                                                 if ((ct->tar->type == OB_ARMATURE) &&
1114                                                     (component_type == DEG_NODE_TYPE_BONE))
1115                                                 {
1116                                                         OperationKey target_key(&ct->tar->id,
1117                                                                                 DEG_NODE_TYPE_TRANSFORM,
1118                                                                                 DEG_OPCODE_TRANSFORM_FINAL);
1119                                                         add_relation(target_key, constraint_op_key, cti->name);
1120                                                 }
1121                                                 else {
1122                                                         OperationKey target_key(&ct->tar->id,
1123                                                                                 DEG_NODE_TYPE_TRANSFORM,
1124                                                                                 DEG_OPCODE_TRANSFORM_LOCAL);
1125                                                         add_relation(target_key, constraint_op_key, cti->name);
1126                                                 }
1127                                         }
1128                                         else {
1129                                                 /* Normal object dependency. */
1130                                                 OperationKey target_key(&ct->tar->id,
1131                                                                         DEG_NODE_TYPE_TRANSFORM,
1132                                                                         DEG_OPCODE_TRANSFORM_FINAL);
1133                                                 add_relation(target_key, constraint_op_key, cti->name);
1134                                         }
1135                                 }
1136                                 /* Constraints which needs world's matrix for transform.
1137                                  * TODO(sergey): More constraints here?
1138                                  */
1139                                 if (ELEM(con->type,
1140                                          CONSTRAINT_TYPE_ROTLIKE,
1141                                          CONSTRAINT_TYPE_SIZELIKE,
1142                                          CONSTRAINT_TYPE_LOCLIKE,
1143                                          CONSTRAINT_TYPE_TRANSLIKE))
1144                                 {
1145                                         /* TODO(sergey): Add used space check. */
1146                                         ComponentKey target_transform_key(&ct->tar->id,
1147                                                                           DEG_NODE_TYPE_TRANSFORM);
1148                                         add_relation(target_transform_key, constraint_op_key, cti->name);
1149                                 }
1150                         }
1151                         if (cti->flush_constraint_targets) {
1152                                 cti->flush_constraint_targets(con, &targets, 1);
1153                         }
1154                 }
1155         }
1156 }
1157
1158 void DepsgraphRelationBuilder::build_animdata(ID *id)
1159 {
1160         /* Animation curves and NLA. */
1161         build_animdata_curves(id);
1162         /* Drivers. */
1163         build_animdata_drivers(id);
1164 }
1165
1166 void DepsgraphRelationBuilder::build_animdata_curves(ID *id)
1167 {
1168         AnimData *adt = BKE_animdata_from_id(id);
1169         if (adt == NULL) {
1170                 return;
1171         }
1172         if (adt->action != NULL) {
1173                 build_action(adt->action);
1174         }
1175         if (adt->action == NULL && adt->nla_tracks.first == NULL) {
1176                 return;
1177         }
1178         /* Wire up dependency to time source. */
1179         ComponentKey adt_key(id, DEG_NODE_TYPE_ANIMATION);
1180         /* Relation from action itself. */
1181         if (adt->action != NULL) {
1182                 ComponentKey action_key(&adt->action->id, DEG_NODE_TYPE_ANIMATION);
1183                 add_relation(action_key, adt_key, "Action -> Animation");
1184         }
1185         /* Get source operations. */
1186         DepsNode *node_from = get_node(adt_key);
1187         BLI_assert(node_from != NULL);
1188         if (node_from == NULL) {
1189                 return;
1190         }
1191         OperationDepsNode *operation_from = node_from->get_exit_operation();
1192         BLI_assert(operation_from != NULL);
1193         /* Build relations from animation operation to properties it changes. */
1194         if (adt->action != NULL) {
1195                 build_animdata_curves_targets(id, adt_key,
1196                                       operation_from,
1197                                       &adt->action->curves);
1198         }
1199         LISTBASE_FOREACH(NlaTrack *, nlt, &adt->nla_tracks) {
1200                 build_animdata_nlastrip_targets(id, adt_key,
1201                                                 operation_from,
1202                                                 &nlt->strips);
1203         }
1204 }
1205
1206 void DepsgraphRelationBuilder::build_animdata_curves_targets(
1207         ID *id, ComponentKey &adt_key,
1208         OperationDepsNode *operation_from,
1209         ListBase *curves)
1210 {
1211         /* Iterate over all curves and build relations. */
1212         PointerRNA id_ptr;
1213         RNA_id_pointer_create(id, &id_ptr);
1214         LISTBASE_FOREACH(FCurve *, fcu, curves) {
1215                 PointerRNA ptr;
1216                 PropertyRNA *prop;
1217                 int index;
1218                 if (!RNA_path_resolve_full(&id_ptr, fcu->rna_path,
1219                                            &ptr, &prop, &index))
1220                 {
1221                         continue;
1222                 }
1223                 DepsNode *node_to = graph_->find_node_from_pointer(&ptr, prop);
1224                 if (node_to == NULL) {
1225                         continue;
1226                 }
1227                 OperationDepsNode *operation_to = node_to->get_entry_operation();
1228                 /* NOTE: Special case for bones, avoid relation from animation to
1229                  * each of the bones. Bone evaluation could only start from pose
1230                  * init anyway.
1231                  */
1232                 if (operation_to->opcode == DEG_OPCODE_BONE_LOCAL) {
1233                         OperationKey pose_init_key(id,
1234                                                    DEG_NODE_TYPE_EVAL_POSE,
1235                                                    DEG_OPCODE_POSE_INIT);
1236                         add_relation(adt_key, pose_init_key, "Animation -> Prop", true);
1237                         continue;
1238                 }
1239                 graph_->add_new_relation(operation_from, operation_to,
1240                                          "Animation -> Prop",
1241                                          true);
1242                 /* It is possible that animation is writing to a nested ID datablock,
1243                  * need to make sure animation is evaluated after target ID is copied.
1244                  */
1245                 const IDDepsNode *id_node_from = operation_from->owner->owner;
1246                 const IDDepsNode *id_node_to = operation_to->owner->owner;
1247                 if (id_node_from != id_node_to) {
1248                         ComponentKey cow_key(id_node_to->id_orig,
1249                                              DEG_NODE_TYPE_COPY_ON_WRITE);
1250                         add_relation(cow_key, adt_key, "Target CoW -> Animation", true);
1251                 }
1252         }
1253 }
1254
1255 void DepsgraphRelationBuilder::build_animdata_nlastrip_targets(
1256         ID *id, ComponentKey &adt_key,
1257         OperationDepsNode *operation_from,
1258         ListBase *strips)
1259 {
1260         LISTBASE_FOREACH(NlaStrip *, strip, strips) {
1261                 if (strip->act != NULL) {
1262                         build_action(strip->act);
1263
1264                         ComponentKey action_key(&strip->act->id, DEG_NODE_TYPE_ANIMATION);
1265                         add_relation(action_key, adt_key, "Action -> Animation");
1266
1267                         build_animdata_curves_targets(id, adt_key,
1268                                                       operation_from,
1269                                                       &strip->act->curves);
1270                 }
1271                 else if (strip->strips.first != NULL) {
1272                         build_animdata_nlastrip_targets(id, adt_key,
1273                                                         operation_from,
1274                                                         &strip->strips);
1275                 }
1276         }
1277 }
1278
1279 void DepsgraphRelationBuilder::build_animdata_drivers(ID *id)
1280 {
1281         AnimData *adt = BKE_animdata_from_id(id);
1282         if (adt == NULL) {
1283                 return;
1284         }
1285         ComponentKey adt_key(id, DEG_NODE_TYPE_ANIMATION);
1286         LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) {
1287                 OperationKey driver_key(id,
1288                                         DEG_NODE_TYPE_PARAMETERS,
1289                                         DEG_OPCODE_DRIVER,
1290                                         fcu->rna_path ? fcu->rna_path : "",
1291                                         fcu->array_index);
1292
1293                 /* create the driver's relations to targets */
1294                 build_driver(id, fcu);
1295                 /* Special case for array drivers: we can not multithread them because
1296                  * of the way how they work internally: animation system will write the
1297                  * whole array back to RNA even when changing individual array value.
1298                  *
1299                  * Some tricky things here:
1300                  * - array_index is -1 for single channel drivers, meaning we only have
1301                  *   to do some magic when array_index is not -1.
1302                  * - We do relation from next array index to a previous one, so we don't
1303                  *   have to deal with array index 0.
1304                  *
1305                  * TODO(sergey): Avoid liner lookup somehow.
1306                  */
1307                 if (fcu->array_index > 0) {
1308                         FCurve *fcu_prev = NULL;
1309                         LISTBASE_FOREACH (FCurve *, fcu_candidate, &adt->drivers) {
1310                                 /* Writing to different RNA paths is  */
1311                                 const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1312                                 if (!STREQ(fcu_candidate->rna_path, rna_path)) {
1313                                         continue;
1314                                 }
1315                                 /* We only do relation from previous fcurve to previous one. */
1316                                 if (fcu_candidate->array_index >= fcu->array_index) {
1317                                         continue;
1318                                 }
1319                                 /* Choose fcurve with highest possible array index. */
1320                                 if (fcu_prev == NULL ||
1321                                     fcu_candidate->array_index > fcu_prev->array_index)
1322                                 {
1323                                         fcu_prev = fcu_candidate;
1324                                 }
1325                         }
1326                         if (fcu_prev != NULL) {
1327                                 OperationKey prev_driver_key(id,
1328                                                              DEG_NODE_TYPE_PARAMETERS,
1329                                                              DEG_OPCODE_DRIVER,
1330                                                              fcu_prev->rna_path ? fcu_prev->rna_path : "",
1331                                                              fcu_prev->array_index);
1332                                 OperationKey driver_key(id,
1333                                                         DEG_NODE_TYPE_PARAMETERS,
1334                                                         DEG_OPCODE_DRIVER,
1335                                                         fcu->rna_path ? fcu->rna_path : "",
1336                                                         fcu->array_index);
1337                                 add_relation(prev_driver_key, driver_key, "Driver Order");
1338                         }
1339                 }
1340
1341                 /* prevent driver from occurring before own animation... */
1342                 if (adt->action || adt->nla_tracks.first) {
1343                         add_relation(adt_key, driver_key, "AnimData Before Drivers");
1344                 }
1345         }
1346 }
1347
1348 void DepsgraphRelationBuilder::build_action(bAction *action)
1349 {
1350         if (built_map_.checkIsBuiltAndTag(action)) {
1351                 return;
1352         }
1353         TimeSourceKey time_src_key;
1354         ComponentKey animation_key(&action->id, DEG_NODE_TYPE_ANIMATION);
1355         add_relation(time_src_key, animation_key, "TimeSrc -> Animation");
1356 }
1357
1358 void DepsgraphRelationBuilder::build_driver(ID *id, FCurve *fcu)
1359 {
1360         ChannelDriver *driver = fcu->driver;
1361         OperationKey driver_key(id,
1362                                 DEG_NODE_TYPE_PARAMETERS,
1363                                 DEG_OPCODE_DRIVER,
1364                                 fcu->rna_path ? fcu->rna_path : "",
1365                                 fcu->array_index);
1366         /* Driver -> data components (for interleaved evaluation
1367          * bones/constraints/modifiers).
1368          */
1369         build_driver_data(id, fcu);
1370         /* Loop over variables to get the target relationships. */
1371         build_driver_variables(id, fcu);
1372         /* It's quite tricky to detect if the driver actually depends on time or
1373          * not, so for now we'll be quite conservative here about optimization and
1374          * consider all python drivers to be depending on time.
1375          */
1376         if ((driver->type == DRIVER_TYPE_PYTHON) &&
1377             python_driver_depends_on_time(driver))
1378         {
1379                 TimeSourceKey time_src_key;
1380                 add_relation(time_src_key, driver_key, "TimeSrc -> Driver");
1381         }
1382 }
1383
1384 void DepsgraphRelationBuilder::build_driver_data(ID *id, FCurve *fcu)
1385 {
1386         OperationKey driver_key(id,
1387                                 DEG_NODE_TYPE_PARAMETERS,
1388                                 DEG_OPCODE_DRIVER,
1389                                 fcu->rna_path ? fcu->rna_path : "",
1390                                 fcu->array_index);
1391         const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1392         const RNAPathKey self_key(id, rna_path);
1393         if (GS(id->name) == ID_AR && strstr(rna_path, "bones[")) {
1394                 /* Drivers on armature-level bone settings (i.e. bbone stuff),
1395                  * which will affect the evaluation of corresponding pose bones.
1396                  */
1397                 IDDepsNode *arm_node = graph_->find_id_node(id);
1398                 char *bone_name = BLI_str_quoted_substrN(rna_path, "bones[");
1399                 if (arm_node != NULL && bone_name != NULL) {
1400                         /* Find objects which use this, and make their eval callbacks
1401                          * depend on this.
1402                          */
1403                         foreach (DepsRelation *rel, arm_node->outlinks) {
1404                                 IDDepsNode *to_node = (IDDepsNode *)rel->to;
1405                                 /* We only care about objects with pose data which use this. */
1406                                 if (GS(to_node->id_orig->name) == ID_OB) {
1407                                         Object *object = (Object *)to_node->id_orig;
1408                                         // NOTE: object->pose may be NULL
1409                                         bPoseChannel *pchan = BKE_pose_channel_find_name(object->pose,
1410                                                                                          bone_name);
1411                                         if (pchan != NULL) {
1412                                                 OperationKey bone_key(&object->id,
1413                                                                       DEG_NODE_TYPE_BONE,
1414                                                                       pchan->name,
1415                                                                       DEG_OPCODE_BONE_LOCAL);
1416                                                 add_relation(driver_key,
1417                                                              bone_key,
1418                                                              "Arm Bone -> Driver -> Bone");
1419                                         }
1420                                 }
1421                         }
1422                         /* Free temp data. */
1423                         MEM_freeN(bone_name);
1424                         bone_name = NULL;
1425                 }
1426                 else {
1427                         fprintf(stderr,
1428                                 "Couldn't find armature bone name for driver path - '%s'\n",
1429                                 rna_path);
1430                 }
1431         }
1432         else if (rna_path != NULL && rna_path[0] != '\0') {
1433                 RNAPathKey target_key(id, rna_path);
1434                 if (RNA_pointer_is_null(&target_key.ptr)) {
1435                         /* TODO(sergey): This would only mean that driver is broken.
1436                          * so we can't create relation anyway. However, we need to avoid
1437                          * adding drivers which are known to be buggy to a dependency
1438                          * graph, in order to save computational power.
1439                          */
1440                         return;
1441                 }
1442                 add_relation(driver_key, target_key, "Driver -> Target");
1443                 /* Similar to the case with f-curves, driver might drive a nested
1444                  * datablock, which means driver execution should wait for that
1445                  * datablock to be copied.
1446                  */
1447                 {
1448                         PointerRNA id_ptr;
1449                         PointerRNA ptr;
1450                         RNA_id_pointer_create(id, &id_ptr);
1451                         if (RNA_path_resolve_full(&id_ptr, fcu->rna_path, &ptr, NULL, NULL)) {
1452                                 if (id_ptr.id.data != ptr.id.data) {
1453                                         ComponentKey cow_key((ID *)ptr.id.data,
1454                                                              DEG_NODE_TYPE_COPY_ON_WRITE);
1455                                         add_relation(cow_key,
1456                                                      driver_key,
1457                                                      "Target CoW -> Driver",
1458                                                      true);
1459                                 }
1460                         }
1461                 }
1462                 if (target_key.prop != NULL &&
1463                     RNA_property_is_idprop(target_key.prop))
1464                 {
1465                         OperationKey parameters_key(id,
1466                                                     DEG_NODE_TYPE_PARAMETERS,
1467                                                     DEG_OPCODE_PARAMETERS_EVAL);
1468                         add_relation(target_key,
1469                                      parameters_key,
1470                                      "Driver Target -> Properties");
1471                 }
1472         }
1473 }
1474
1475 void DepsgraphRelationBuilder::build_driver_variables(ID *id, FCurve *fcu)
1476 {
1477         ChannelDriver *driver = fcu->driver;
1478         OperationKey driver_key(id,
1479                                 DEG_NODE_TYPE_PARAMETERS,
1480                                 DEG_OPCODE_DRIVER,
1481                                 fcu->rna_path ? fcu->rna_path : "",
1482                                 fcu->array_index);
1483         const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1484         const RNAPathKey self_key(id, rna_path);
1485
1486         LISTBASE_FOREACH (DriverVar *, dvar, &driver->variables) {
1487                 /* Only used targets. */
1488                 DRIVER_TARGETS_USED_LOOPER_BEGIN(dvar)
1489                 {
1490                         if (dtar->id == NULL) {
1491                                 continue;
1492                         }
1493                         build_id(dtar->id);
1494                         /* Initialize relations coming to proxy_from. */
1495                         Object *proxy_from = NULL;
1496                         if ((GS(dtar->id->name) == ID_OB) &&
1497                             (((Object *)dtar->id)->proxy_from != NULL))
1498                         {
1499                                 proxy_from = ((Object *)dtar->id)->proxy_from;
1500                                 build_id(&proxy_from->id);
1501                         }
1502                         /* Special handling for directly-named bones. */
1503                         if ((dtar->flag & DTAR_FLAG_STRUCT_REF) &&
1504                             (((Object *)dtar->id)->type == OB_ARMATURE) &&
1505                             (dtar->pchan_name[0]))
1506                         {
1507                                 Object *object = (Object *)dtar->id;
1508                                 bPoseChannel *target_pchan =
1509                                         BKE_pose_channel_find_name(object->pose,
1510                                                                    dtar->pchan_name);
1511                                 if (target_pchan == NULL) {
1512                                         continue;
1513                                 }
1514                                 OperationKey variable_key(dtar->id,
1515                                                           DEG_NODE_TYPE_BONE,
1516                                                           target_pchan->name,
1517                                                           DEG_OPCODE_BONE_DONE);
1518                                 if (is_same_bone_dependency(variable_key, self_key)) {
1519                                         continue;
1520                                 }
1521                                 add_relation(variable_key, driver_key, "Bone Target -> Driver");
1522                         }
1523                         else if (dtar->flag & DTAR_FLAG_STRUCT_REF) {
1524                                 /* Get node associated with the object's transforms. */
1525                                 if (dtar->id == id) {
1526                                         /* Ignore input dependency if we're driving properties of
1527                                          * the same ID, otherwise we'll be ending up in a cyclic
1528                                          * dependency here.
1529                                          */
1530                                         continue;
1531                                 }
1532                                 OperationKey target_key(dtar->id,
1533                                                         DEG_NODE_TYPE_TRANSFORM,
1534                                                         DEG_OPCODE_TRANSFORM_FINAL);
1535                                 add_relation(target_key, driver_key, "Target -> Driver");
1536                         }
1537                         else if (dtar->rna_path != NULL && dtar->rna_path[0] != '\0') {
1538                                 RNAPathKey variable_key(dtar->id, dtar->rna_path);
1539                                 if (RNA_pointer_is_null(&variable_key.ptr)) {
1540                                         continue;
1541                                 }
1542                                 if (is_same_bone_dependency(variable_key, self_key) ||
1543                                     is_same_nodetree_node_dependency(variable_key, self_key) ||
1544                                     is_same_shapekey_dependency(variable_key, self_key))
1545                                 {
1546                                         continue;
1547                                 }
1548                                 add_relation(variable_key, driver_key, "RNA Target -> Driver");
1549                                 if (proxy_from != NULL) {
1550                                         RNAPathKey proxy_from_variable_key(&proxy_from->id,
1551                                                                            dtar->rna_path);
1552                                         add_relation(proxy_from_variable_key,
1553                                                      variable_key,
1554                                                      "Proxy From -> Variable");
1555                                 }
1556                         }
1557                         else {
1558                                 /* If rna_path is NULL, and DTAR_FLAG_STRUCT_REF isn't set, this
1559                                  * is an incomplete target reference, so nothing to do here. */
1560                         }
1561                 }
1562                 DRIVER_TARGETS_LOOPER_END;
1563         }
1564 }
1565
1566 void DepsgraphRelationBuilder::build_world(World *world)
1567 {
1568         if (built_map_.checkIsBuiltAndTag(world)) {
1569                 return;
1570         }
1571         /* animation */
1572         build_animdata(&world->id);
1573         /* world's nodetree */
1574         if (world->nodetree != NULL) {
1575                 build_nodetree(world->nodetree);
1576                 OperationKey ntree_key(&world->nodetree->id,
1577                                        DEG_NODE_TYPE_SHADING,
1578                                        DEG_OPCODE_MATERIAL_UPDATE);
1579                 OperationKey world_key(&world->id,
1580                                           DEG_NODE_TYPE_SHADING,
1581                                           DEG_OPCODE_WORLD_UPDATE);
1582                 add_relation(ntree_key, world_key, "World's NTree");
1583                 build_nested_nodetree(&world->id, world->nodetree);
1584         }
1585 }
1586
1587 void DepsgraphRelationBuilder::build_rigidbody(Scene *scene)
1588 {
1589         RigidBodyWorld *rbw = scene->rigidbody_world;
1590
1591         OperationKey init_key(&scene->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_REBUILD);
1592         OperationKey sim_key(&scene->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_SIM);
1593
1594         /* rel between the two sim-nodes */
1595         add_relation(init_key, sim_key, "Rigidbody [Init -> SimStep]");
1596
1597         /* set up dependencies between these operations and other builtin nodes --------------- */
1598
1599         /* time dependency */
1600         TimeSourceKey time_src_key;
1601         add_relation(time_src_key, init_key, "TimeSrc -> Rigidbody Reset/Rebuild (Optional)");
1602
1603         /* objects - simulation participants */
1604         if (rbw->group) {
1605                 build_collection(NULL, NULL, rbw->group);
1606
1607                 FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN(rbw->group, object)
1608                 {
1609                         if (object->type != OB_MESH) {
1610                                 continue;
1611                         }
1612
1613                         /* hook up evaluation order...
1614                          * 1) flushing rigidbody results follows base transforms being applied
1615                          * 2) rigidbody flushing can only be performed after simulation has been run
1616                          *
1617                          * 3) simulation needs to know base transforms to figure out what to do
1618                          *    XXX: there's probably a difference between passive and active
1619                          *         - passive don't change, so may need to know full transform...
1620                          */
1621                         OperationKey rbo_key(&object->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_TRANSFORM_COPY);
1622
1623                         eDepsOperation_Code trans_opcode = object->parent ? DEG_OPCODE_TRANSFORM_PARENT : DEG_OPCODE_TRANSFORM_LOCAL;
1624                         OperationKey trans_op(&object->id, DEG_NODE_TYPE_TRANSFORM, trans_opcode);
1625
1626                         add_relation(sim_key, rbo_key, "Rigidbody Sim Eval -> RBO Sync");
1627
1628                         /* Geometry must be known to create the rigid body. RBO_MESH_BASE uses the non-evaluated
1629                          * mesh, so then the evaluation is unnecessary. */
1630                         if (object->rigidbody_object->mesh_source != RBO_MESH_BASE) {
1631                                 ComponentKey geom_key(&object->id, DEG_NODE_TYPE_GEOMETRY);
1632                                 add_relation(geom_key, init_key, "Object Geom Eval -> Rigidbody Rebuild");
1633                         }
1634
1635                         /* if constraints exist, those depend on the result of the rigidbody sim
1636                          * - This allows constraints to modify the result of the sim (i.e. clamping)
1637                          *   while still allowing the sim to depend on some changes to the objects.
1638                          *   Also, since constraints are hooked up to the final nodes, this link
1639                          *   means that we can also fit in there too...
1640                          * - Later, it might be good to include a constraint in the stack allowing us
1641                          *   to control whether rigidbody eval gets interleaved into the constraint stack
1642                          */
1643                         if (object->constraints.first) {
1644                                 OperationKey constraint_key(&object->id,
1645                                                             DEG_NODE_TYPE_TRANSFORM,
1646                                                             DEG_OPCODE_TRANSFORM_CONSTRAINTS);
1647                                 add_relation(rbo_key, constraint_key, "RBO Sync -> Ob Constraints");
1648                         }
1649                         else {
1650                                 /* Final object transform depends on rigidbody.
1651                                  *
1652                                  * NOTE: Currently we consider final here an ubereval node.
1653                                  * If it is gone we'll need to reconsider relation here.
1654                                  */
1655                                 OperationKey uber_key(&object->id,
1656                                                       DEG_NODE_TYPE_TRANSFORM,
1657                                                       DEG_OPCODE_TRANSFORM_OBJECT_UBEREVAL);
1658                                 add_relation(rbo_key, uber_key, "RBO Sync -> Uber (Temp)");
1659                         }
1660
1661                         /* Needed to get correct base values. */
1662                         add_relation(trans_op, sim_key, "Base Ob Transform -> Rigidbody Sim Eval");
1663                 }
1664                 FOREACH_COLLECTION_OBJECT_RECURSIVE_END;
1665         }
1666
1667         /* constraints */
1668         if (rbw->constraints) {
1669                 FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN(rbw->constraints, object)
1670                 {
1671                         RigidBodyCon *rbc = object->rigidbody_constraint;
1672                         if (rbc == NULL || rbc->ob1 == NULL || rbc->ob2 == NULL) {
1673                                 /* When either ob1 or ob2 is NULL, the constraint doesn't work. */
1674                                 continue;
1675                         }
1676
1677                         /* final result of the constraint object's transform controls how the
1678                          * constraint affects the physics sim for these objects
1679                          */
1680                         ComponentKey trans_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
1681                         OperationKey ob1_key(&rbc->ob1->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_TRANSFORM_COPY);
1682                         OperationKey ob2_key(&rbc->ob2->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_TRANSFORM_COPY);
1683
1684                         /* - constrained-objects sync depends on the constraint-holder */
1685                         add_relation(trans_key, ob1_key, "RigidBodyConstraint -> RBC.Object_1");
1686                         add_relation(trans_key, ob2_key, "RigidBodyConstraint -> RBC.Object_2");
1687
1688                         /* - ensure that sim depends on this constraint's transform */
1689                         add_relation(trans_key, sim_key, "RigidBodyConstraint Transform -> RB Simulation");
1690                 }
1691                 FOREACH_COLLECTION_OBJECT_RECURSIVE_END;
1692         }
1693 }
1694
1695 void DepsgraphRelationBuilder::build_particles(Object *object)
1696 {
1697         TimeSourceKey time_src_key;
1698         OperationKey obdata_ubereval_key(&object->id,
1699                                          DEG_NODE_TYPE_GEOMETRY,
1700                                          DEG_OPCODE_GEOMETRY_UBEREVAL);
1701         OperationKey eval_init_key(&object->id,
1702                                    DEG_NODE_TYPE_EVAL_PARTICLES,
1703                                    DEG_OPCODE_PARTICLE_SYSTEM_EVAL_INIT);
1704
1705         /* Particle systems. */
1706         LISTBASE_FOREACH (ParticleSystem *, psys, &object->particlesystem) {
1707                 ParticleSettings *part = psys->part;
1708
1709                 /* Build particle settings relations.
1710                  *
1711                  * NOTE: The call itself ensures settings are only build once.
1712                  */
1713                 build_particle_settings(part);
1714
1715                 /* This particle system. */
1716                 OperationKey psys_key(&object->id,
1717                                       DEG_NODE_TYPE_EVAL_PARTICLES,
1718                                       DEG_OPCODE_PARTICLE_SYSTEM_EVAL,
1719                                       psys->name);
1720
1721                 /* Update particle system when settings changes. */
1722                 OperationKey particle_settings_key(&part->id,
1723                                                    DEG_NODE_TYPE_PARAMETERS,
1724                                                    DEG_OPCODE_PARTICLE_SETTINGS_EVAL);
1725                 add_relation(particle_settings_key, eval_init_key, "Particle Settings Change");
1726                 add_relation(eval_init_key, psys_key, "Init -> PSys");
1727                 /* TODO(sergey): Currently particle update is just a placeholder,
1728                  * hook it to the ubereval node so particle system is getting updated
1729                  * on playback.
1730                  */
1731                 add_relation(psys_key, obdata_ubereval_key, "PSys -> UberEval");
1732                 /* Collisions */
1733                 if (part->type != PART_HAIR) {
1734                         add_collision_relations(psys_key,
1735                                                 object,
1736                                                 part->collision_group,
1737                                                 "Particle Collision");
1738                 }
1739                 else if ((psys->flag & PSYS_HAIR_DYNAMICS) &&
1740                          psys->clmd != NULL &&
1741                          psys->clmd->coll_parms != NULL)
1742                 {
1743                         add_collision_relations(psys_key,
1744                                                 object,
1745                                                 psys->clmd->coll_parms->group,
1746                                                 "Hair Collision");
1747                 }
1748                 /* Effectors. */
1749                 add_forcefield_relations(psys_key,
1750                                          object,
1751                                          psys,
1752                                          part->effector_weights,
1753                                          part->type == PART_HAIR,
1754                                          "Particle Field");
1755                 /* Boids .*/
1756                 if (part->boids) {
1757                         LISTBASE_FOREACH (BoidState *, state, &part->boids->states) {
1758                                 LISTBASE_FOREACH (BoidRule *, rule, &state->rules) {
1759                                         Object *ruleob = NULL;
1760                                         if (rule->type == eBoidRuleType_Avoid) {
1761                                                 ruleob = ((BoidRuleGoalAvoid *)rule)->ob;
1762                                         }
1763                                         else if (rule->type == eBoidRuleType_FollowLeader) {
1764                                                 ruleob = ((BoidRuleFollowLeader *)rule)->ob;
1765                                         }
1766                                         if (ruleob) {
1767                                                 ComponentKey ruleob_key(&ruleob->id,
1768                                                                         DEG_NODE_TYPE_TRANSFORM);
1769                                                 add_relation(ruleob_key, psys_key, "Boid Rule");
1770                                         }
1771                                 }
1772                         }
1773                 }
1774                 switch (part->ren_as) {
1775                         case PART_DRAW_OB:
1776                                 if (part->dup_ob != NULL) {
1777                                         /* Make sure object's relations are all built.  */
1778                                         build_object(NULL, part->dup_ob);
1779                                         /* Build relation for the particle visualization. */
1780                                         build_particles_visualization_object(object,
1781                                                                              psys,
1782                                                                              part->dup_ob);
1783                                 }
1784                                 break;
1785                         case PART_DRAW_GR:
1786                                 if (part->dup_group != NULL) {
1787                                         build_collection(NULL, NULL, part->dup_group);
1788                                         LISTBASE_FOREACH (CollectionObject *, go, &part->dup_group->gobject) {
1789                                                 build_particles_visualization_object(object,
1790                                                                                      psys,
1791                                                                                      go->ob);
1792                                         }
1793                                 }
1794                                 break;
1795                 }
1796         }
1797
1798         /* Particle depends on the object transform, so that channel is to be ready
1799          * first.
1800          *
1801          * TODO(sergey): This relation should be altered once real granular update
1802          * is implemented.
1803          */
1804         ComponentKey transform_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
1805         add_relation(transform_key, obdata_ubereval_key, "Partcile Eval");
1806 }
1807
1808 void DepsgraphRelationBuilder::build_particle_settings(ParticleSettings *part)
1809 {
1810         if (built_map_.checkIsBuiltAndTag(part)) {
1811                 return;
1812         }
1813         /* Animation data relations. */
1814         build_animdata(&part->id);
1815 }
1816
1817 void DepsgraphRelationBuilder::build_particles_visualization_object(
1818         Object *object,
1819         ParticleSystem *psys,
1820         Object *draw_object)
1821 {
1822         OperationKey psys_key(&object->id,
1823                               DEG_NODE_TYPE_EVAL_PARTICLES,
1824                               DEG_OPCODE_PARTICLE_SYSTEM_EVAL,
1825                               psys->name);
1826         OperationKey obdata_ubereval_key(&object->id,
1827                                          DEG_NODE_TYPE_GEOMETRY,
1828                                          DEG_OPCODE_GEOMETRY_UBEREVAL);
1829         ComponentKey dup_ob_key(&draw_object->id, DEG_NODE_TYPE_TRANSFORM);
1830         add_relation(dup_ob_key, psys_key, "Particle Object Visualization");
1831         if (draw_object->type == OB_MBALL) {
1832                 ComponentKey dup_geometry_key(&draw_object->id, DEG_NODE_TYPE_GEOMETRY);
1833                 add_relation(obdata_ubereval_key,
1834                              dup_geometry_key,
1835                              "Particle MBall Visualization");
1836         }
1837 }
1838
1839 /* Shapekeys */
1840 void DepsgraphRelationBuilder::build_shapekeys(Key *key)
1841 {
1842         if (built_map_.checkIsBuiltAndTag(key)) {
1843                 return;
1844         }
1845         /* attach animdata to geometry */
1846         build_animdata(&key->id);
1847 }
1848
1849 /**
1850  * ObData Geometry Evaluation
1851  * ==========================
1852  *
1853  * The evaluation of geometry on objects is as follows:
1854  * - The actual evaluated of the derived geometry (e.g. Mesh, DispList)
1855  *   occurs in the Geometry component of the object which references this.
1856  *   This includes modifiers, and the temporary "ubereval" for geometry.
1857  *   Therefore, each user of a piece of shared geometry data ends up evaluating
1858  *   its own version of the stuff, complete with whatever modifiers it may use.
1859  *
1860  * - The datablocks for the geometry data - "obdata" (e.g. ID_ME, ID_CU, ID_LT.)
1861  *   are used for
1862  *     1) calculating the bounding boxes of the geometry data,
1863  *     2) aggregating inward links from other objects (e.g. for text on curve)
1864  *        and also for the links coming from the shapekey datablocks
1865  * - Animation/Drivers affecting the parameters of the geometry are made to
1866  *   trigger updates on the obdata geometry component, which then trigger
1867  *   downstream re-evaluation of the individual instances of this geometry.
1868  */
1869 void DepsgraphRelationBuilder::build_object_data_geometry(Object *object)
1870 {
1871         ID *obdata = (ID *)object->data;
1872         /* Init operation of object-level geometry evaluation. */
1873         OperationKey geom_init_key(&object->id,
1874                                    DEG_NODE_TYPE_GEOMETRY,
1875                                    DEG_OPCODE_PLACEHOLDER,
1876                                    "Eval Init");
1877         /* Get nodes for result of obdata's evaluation, and geometry evaluation
1878          * on object.
1879          */
1880         ComponentKey obdata_geom_key(obdata, DEG_NODE_TYPE_GEOMETRY);
1881         ComponentKey geom_key(&object->id, DEG_NODE_TYPE_GEOMETRY);
1882         /* Link components to each other. */
1883         add_relation(obdata_geom_key, geom_key, "Object Geometry Base Data");
1884         OperationKey obdata_ubereval_key(&object->id,
1885                                          DEG_NODE_TYPE_GEOMETRY,
1886                                          DEG_OPCODE_GEOMETRY_UBEREVAL);
1887         /* Special case: modifiers evaluation queries scene for various things like
1888          * data mask to be used. We add relation here to ensure object is never
1889          * evaluated prior to Scene's CoW is ready.
1890          */
1891         OperationKey scene_key(&scene_->id,
1892                                DEG_NODE_TYPE_LAYER_COLLECTIONS,
1893                                DEG_OPCODE_VIEW_LAYER_EVAL);
1894         DepsRelation *rel = add_relation(scene_key, obdata_ubereval_key, "CoW Relation");
1895         rel->flag |= DEPSREL_FLAG_NO_FLUSH;
1896         /* Modifiers */
1897         if (object->modifiers.first != NULL) {
1898                 ModifierUpdateDepsgraphContext ctx = {};
1899                 ctx.scene = scene_;
1900                 ctx.object = object;
1901                 LISTBASE_FOREACH (ModifierData *, md, &object->modifiers) {
1902                         const ModifierTypeInfo *mti = modifierType_getInfo((ModifierType)md->type);
1903                         if (mti->updateDepsgraph) {
1904                                 DepsNodeHandle handle = create_node_handle(obdata_ubereval_key);
1905                                 ctx.node = reinterpret_cast< ::DepsNodeHandle* >(&handle);
1906                                 mti->updateDepsgraph(md, &ctx);
1907                         }
1908                         if (BKE_object_modifier_use_time(object, md)) {
1909                                 TimeSourceKey time_src_key;
1910                                 add_relation(time_src_key, obdata_ubereval_key, "Time Source");
1911                         }
1912                 }
1913         }
1914         /* Grease Pencil Modifiers */
1915         if (object->greasepencil_modifiers.first != NULL) {
1916                 ModifierUpdateDepsgraphContext ctx = {};
1917                 ctx.scene = scene_;
1918                 ctx.object = object;
1919                 LISTBASE_FOREACH(GpencilModifierData *, md, &object->greasepencil_modifiers) {
1920                         const GpencilModifierTypeInfo *mti = BKE_gpencil_modifierType_getInfo((GpencilModifierType)md->type);
1921                         if (mti->updateDepsgraph) {
1922                                 DepsNodeHandle handle = create_node_handle(obdata_ubereval_key);
1923                                 ctx.node = reinterpret_cast< ::DepsNodeHandle* >(&handle);
1924                                 mti->updateDepsgraph(md, &ctx);
1925                         }
1926                         if (BKE_object_modifier_gpencil_use_time(object, md)) {
1927                                 TimeSourceKey time_src_key;
1928                                 add_relation(time_src_key, obdata_ubereval_key, "Time Source");
1929                         }
1930                 }
1931         }
1932         /* Shader FX */
1933         if (object->shader_fx.first != NULL) {
1934                 ModifierUpdateDepsgraphContext ctx = {};
1935                 ctx.scene = scene_;
1936                 ctx.object = object;
1937                 LISTBASE_FOREACH(ShaderFxData *, fx, &object->shader_fx) {
1938                         const ShaderFxTypeInfo *fxi = BKE_shaderfxType_getInfo((ShaderFxType)fx->type);
1939                         if (fxi->updateDepsgraph) {
1940                                 DepsNodeHandle handle = create_node_handle(obdata_ubereval_key);
1941                                 ctx.node = reinterpret_cast< ::DepsNodeHandle* >(&handle);
1942                                 fxi->updateDepsgraph(fx, &ctx);
1943                         }
1944                         if (BKE_object_shaderfx_use_time(object, fx)) {
1945                                 TimeSourceKey time_src_key;
1946                                 add_relation(time_src_key, obdata_ubereval_key, "Time Source");
1947                         }
1948                 }
1949         }
1950         /* Materials. */
1951         if (object->totcol) {
1952                 for (int a = 1; a <= object->totcol; a++) {
1953                         Material *ma = give_current_material(object, a);
1954                         if (ma != NULL) {
1955                                 build_material(ma);
1956
1957                                 if (object->type == OB_MESH) {
1958                                         OperationKey material_key(&ma->id,
1959                                                                   DEG_NODE_TYPE_SHADING,
1960                                                                   DEG_OPCODE_MATERIAL_UPDATE);
1961                                         OperationKey shading_key(&object->id,
1962                                                                  DEG_NODE_TYPE_SHADING,
1963                                                                  DEG_OPCODE_SHADING);
1964                                         add_relation(material_key, shading_key, "Material Update");
1965                                 }
1966                         }
1967                 }
1968         }
1969         /* Geometry collision. */
1970         if (ELEM(object->type, OB_MESH, OB_CURVE, OB_LATTICE)) {
1971                 // add geometry collider relations
1972         }
1973         /* Make sure uber update is the last in the dependencies.
1974          *
1975          * TODO(sergey): Get rid of this node.
1976          */
1977         if (object->type != OB_ARMATURE) {
1978                 /* Armatures does no longer require uber node. */
1979                 OperationKey obdata_ubereval_key(&object->id,
1980                                                  DEG_NODE_TYPE_GEOMETRY,
1981                                                  DEG_OPCODE_GEOMETRY_UBEREVAL);
1982                 add_relation(geom_init_key,
1983                              obdata_ubereval_key,
1984                              "Object Geometry UberEval");
1985                 if (object->totcol != 0 && object->type == OB_MESH) {
1986                         ComponentKey object_shading_key(&object->id, DEG_NODE_TYPE_SHADING);
1987                         DepsRelation *rel = add_relation(obdata_ubereval_key,
1988                                                          object_shading_key,
1989                                                          "Object Geometry batch Update");
1990                         rel->flag |= DEPSREL_FLAG_NO_FLUSH;
1991                 }
1992         }
1993         if (object->type == OB_MBALL) {
1994                 Object *mom = BKE_mball_basis_find(scene_, object);
1995                 ComponentKey mom_geom_key(&mom->id, DEG_NODE_TYPE_GEOMETRY);
1996                 /* motherball - mom depends on children! */
1997                 if (mom == object) {
1998                         ComponentKey mom_transform_key(&mom->id,
1999                                                        DEG_NODE_TYPE_TRANSFORM);
2000                         add_relation(mom_transform_key,
2001                                      mom_geom_key,
2002                                      "Metaball Motherball Transform -> Geometry");
2003                 }
2004                 else {
2005                         ComponentKey transform_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
2006                         add_relation(geom_key, mom_geom_key, "Metaball Motherball");
2007                         add_relation(transform_key, mom_geom_key, "Metaball Motherball");
2008                 }
2009         }
2010         /* NOTE: This is compatibility code to support particle systems
2011          *
2012          * for viewport being properly rendered in final render mode.
2013          * This relation is similar to what dag_object_time_update_flags()
2014          * was doing for mesh objects with particle system.
2015          *
2016          * Ideally we need to get rid of this relation.
2017          */
2018         if (object_particles_depends_on_time(object)) {
2019                 TimeSourceKey time_key;
2020                 OperationKey obdata_ubereval_key(&object->id,
2021                                                  DEG_NODE_TYPE_GEOMETRY,
2022                                                  DEG_OPCODE_GEOMETRY_UBEREVAL);
2023                 add_relation(time_key, obdata_ubereval_key, "Legacy particle time");
2024         }
2025         /* Object data datablock. */
2026         build_object_data_geometry_datablock((ID *)object->data);
2027         Key *key = BKE_key_from_object(object);
2028         if (key != NULL) {
2029                 if (key->adt != NULL) {
2030                         if (key->adt->action || key->adt->nla_tracks.first) {
2031                                 ComponentKey obdata_key((ID *)object->data,
2032                                                         DEG_NODE_TYPE_GEOMETRY);
2033                                 ComponentKey adt_key(&key->id, DEG_NODE_TYPE_ANIMATION);
2034                                 add_relation(adt_key, obdata_key, "Animation");
2035                         }
2036                 }
2037         }
2038         /* Syncronization back to original object. */
2039         ComponentKey final_geometry_jey(&object->id, DEG_NODE_TYPE_GEOMETRY);
2040         OperationKey synchronize_key(&object->id,
2041                                      DEG_NODE_TYPE_SYNCHRONIZE,
2042                                      DEG_OPCODE_SYNCHRONIZE_TO_ORIGINAL);
2043         add_relation(
2044                 final_geometry_jey, synchronize_key, "Synchronize to Original");
2045 }
2046
2047 void DepsgraphRelationBuilder::build_object_data_geometry_datablock(ID *obdata)
2048 {
2049         if (built_map_.checkIsBuiltAndTag(obdata)) {
2050                 return;
2051         }
2052         /* Animation. */
2053         build_animdata(obdata);
2054         /* ShapeKeys. */
2055         Key *key = BKE_key_from_id(obdata);
2056         if (key != NULL) {
2057                 build_shapekeys(key);
2058         }
2059         /* Link object data evaluation node to exit operation. */
2060         OperationKey obdata_geom_eval_key(obdata,
2061                 DEG_NODE_TYPE_GEOMETRY,
2062                 DEG_OPCODE_PLACEHOLDER,
2063                 "Geometry Eval");
2064         OperationKey obdata_geom_done_key(obdata,
2065                 DEG_NODE_TYPE_GEOMETRY,
2066                 DEG_OPCODE_PLACEHOLDER,
2067                 "Eval Done");
2068         add_relation(obdata_geom_eval_key,
2069                      obdata_geom_done_key,
2070                      "ObData Geom Eval Done");
2071         /* Type-specific links. */
2072         const ID_Type id_type = GS(obdata->name);
2073         switch (id_type) {
2074                 case ID_ME:
2075                         break;
2076                 case ID_MB:
2077                         break;
2078                 case ID_CU:
2079                 {
2080                         Curve *cu = (Curve *)obdata;
2081                         if (cu->bevobj != NULL) {
2082                                 ComponentKey bevob_geom_key(&cu->bevobj->id,
2083                                         DEG_NODE_TYPE_GEOMETRY);
2084                                 add_relation(bevob_geom_key,
2085                                         obdata_geom_eval_key,
2086                                         "Curve Bevel Geometry");
2087                                 ComponentKey bevob_key(&cu->bevobj->id,
2088                                         DEG_NODE_TYPE_TRANSFORM);
2089                                 add_relation(bevob_key,
2090                                         obdata_geom_eval_key,
2091                                         "Curve Bevel Transform");
2092                                 build_object(NULL, cu->bevobj);
2093                         }
2094                         if (cu->taperobj != NULL) {
2095                                 ComponentKey taperob_key(&cu->taperobj->id,
2096                                         DEG_NODE_TYPE_GEOMETRY);
2097                                 add_relation(taperob_key, obdata_geom_eval_key, "Curve Taper");
2098                                 build_object(NULL, cu->taperobj);
2099                         }
2100                         if (cu->textoncurve != NULL) {
2101                                 ComponentKey textoncurve_key(&cu->textoncurve->id,
2102                                         DEG_NODE_TYPE_GEOMETRY);
2103                                 add_relation(textoncurve_key,
2104                                         obdata_geom_eval_key,
2105                                         "Text on Curve");
2106                                 build_object(NULL, cu->textoncurve);
2107                         }
2108                         break;
2109                 }
2110                 case ID_LT:
2111                         break;
2112                 case ID_GD: /* Grease Pencil */
2113                 {
2114                         bGPdata *gpd = (bGPdata *)obdata;
2115
2116                         /* Geometry cache needs to be recalculated on frame change
2117                          * (e.g. to fix crashes after scrubbing the timeline when
2118                          * onion skinning is enabled, since the ghosts need to be
2119                          * re-added to the cache once scrubbing ends)
2120                          */
2121                         TimeSourceKey time_key;
2122                         ComponentKey geometry_key(obdata, DEG_NODE_TYPE_GEOMETRY);
2123                         add_relation(time_key,
2124                                      geometry_key,
2125                                      "GP Frame Change");
2126
2127                         /* Geometry cache also needs to be recalculated when Material
2128                          * settings change (e.g. when fill.opacity changes on/off,
2129                          * we need to rebuild the bGPDstroke->triangles caches)
2130                          */
2131                         for (int i = 0; i < gpd->totcol; i++) {
2132                                 Material *ma = gpd->mat[i];
2133                                 if ((ma != NULL) && (ma->gp_style != NULL)) {
2134                                         OperationKey material_key(&ma->id,
2135                                                                   DEG_NODE_TYPE_SHADING,
2136                                                                   DEG_OPCODE_MATERIAL_UPDATE);
2137                                         add_relation(material_key,
2138                                                      geometry_key,
2139                                                      "Material -> GP Data");
2140                                 }
2141                         }
2142                         break;
2143                 }
2144                 default:
2145                         BLI_assert(!"Should not happen");
2146                         break;
2147         }
2148 }
2149
2150 void DepsgraphRelationBuilder::build_armature(bArmature *armature)
2151 {
2152         if (built_map_.checkIsBuiltAndTag(armature)) {
2153                 return;
2154         }
2155         build_animdata(&armature->id);
2156 }
2157
2158 void DepsgraphRelationBuilder::build_camera(Camera *camera)
2159 {
2160         if (built_map_.checkIsBuiltAndTag(camera)) {
2161                 return;
2162         }
2163         if (camera->dof_ob != NULL) {
2164                 ComponentKey camera_parameters_key(&camera->id, DEG_NODE_TYPE_PARAMETERS);
2165                 ComponentKey dof_ob_key(&camera->dof_ob->id, DEG_NODE_TYPE_TRANSFORM);
2166                 add_relation(dof_ob_key, camera_parameters_key, "Camera DOF");
2167         }
2168 }
2169
2170 /* Lamps */
2171 void DepsgraphRelationBuilder::build_lamp(Lamp *lamp)
2172 {
2173         if (built_map_.checkIsBuiltAndTag(lamp)) {
2174                 return;
2175         }
2176         /* lamp's nodetree */
2177         if (lamp->nodetree != NULL) {
2178                 build_nodetree(lamp->nodetree);
2179                 ComponentKey lamp_parameters_key(&lamp->id, DEG_NODE_TYPE_PARAMETERS);
2180                 ComponentKey nodetree_key(&lamp->nodetree->id, DEG_NODE_TYPE_SHADING);
2181                 add_relation(nodetree_key, lamp_parameters_key, "NTree->Light Parameters");
2182                 build_nested_nodetree(&lamp->id, lamp->nodetree);
2183         }
2184 }
2185
2186 void DepsgraphRelationBuilder::build_nodetree(bNodeTree *ntree)
2187 {
2188         if (ntree == NULL) {
2189                 return;
2190         }
2191         if (built_map_.checkIsBuiltAndTag(ntree)) {
2192                 return;
2193         }
2194         build_animdata(&ntree->id);
2195         ComponentKey shading_key(&ntree->id, DEG_NODE_TYPE_SHADING);
2196         /* nodetree's nodes... */
2197         LISTBASE_FOREACH (bNode *, bnode, &ntree->nodes) {
2198                 ID *id = bnode->id;
2199                 if (id == NULL) {
2200                         continue;
2201                 }
2202                 ID_Type id_type = GS(id->name);
2203                 if (id_type == ID_MA) {
2204                         build_material((Material *)bnode->id);
2205                 }
2206                 else if (id_type == ID_TE) {
2207                         build_texture((Tex *)bnode->id);
2208                 }
2209                 else if (id_type == ID_IM) {
2210                         /* nothing for now. */
2211                 }
2212                 else if (id_type == ID_OB) {
2213                         build_object(NULL, (Object *)id);
2214                 }
2215                 else if (id_type == ID_SCE) {
2216                         /* Scenes are used by compositor trees, and handled by render
2217                          * pipeline. No need to build dependencies for them here.
2218                          */
2219                 }
2220                 else if (id_type == ID_TXT) {
2221                         /* Ignore script nodes. */
2222                 }
2223                 else if (id_type == ID_MSK) {
2224                         build_mask((Mask *)id);
2225                 }
2226                 else if (id_type == ID_MC) {
2227                         build_movieclip((MovieClip *)id);
2228                 }
2229                 else if (bnode->type == NODE_GROUP) {
2230                         bNodeTree *group_ntree = (bNodeTree *)id;
2231                         build_nodetree(group_ntree);
2232                         ComponentKey group_shading_key(&group_ntree->id,
2233                                                        DEG_NODE_TYPE_SHADING);
2234                         add_relation(group_shading_key, shading_key, "Group Node");
2235                 }
2236                 else {
2237                         BLI_assert(!"Unknown ID type used for node");
2238                 }
2239         }
2240
2241         OperationKey shading_update_key(&ntree->id,
2242                                         DEG_NODE_TYPE_SHADING,
2243                                         DEG_OPCODE_MATERIAL_UPDATE);
2244         OperationKey shading_parameters_key(&ntree->id,
2245                                             DEG_NODE_TYPE_SHADING_PARAMETERS,
2246                                             DEG_OPCODE_MATERIAL_UPDATE);
2247         add_relation(shading_parameters_key, shading_update_key, "NTree Shading Parameters");
2248
2249         if (check_id_has_anim_component(&ntree->id)) {
2250                 ComponentKey animation_key(&ntree->id, DEG_NODE_TYPE_ANIMATION);
2251                 add_relation(animation_key, shading_parameters_key, "NTree Shading Parameters");
2252         }
2253 }
2254
2255 /* Recursively build graph for material */
2256 void DepsgraphRelationBuilder::build_material(Material *material)
2257 {
2258         if (built_map_.checkIsBuiltAndTag(material)) {
2259                 return;
2260         }
2261         /* animation */
2262         build_animdata(&material->id);
2263         /* material's nodetree */
2264         if (material->nodetree != NULL) {
2265                 build_nodetree(material->nodetree);
2266                 OperationKey ntree_key(&material->nodetree->id,
2267                                        DEG_NODE_TYPE_SHADING,
2268                                        DEG_OPCODE_MATERIAL_UPDATE);
2269                 OperationKey material_key(&material->id,
2270                                           DEG_NODE_TYPE_SHADING,
2271                                           DEG_OPCODE_MATERIAL_UPDATE);
2272                 add_relation(ntree_key, material_key, "Material's NTree");
2273                 build_nested_nodetree(&material->id, material->nodetree);
2274         }
2275 }
2276
2277 /* Recursively build graph for texture */
2278 void DepsgraphRelationBuilder::build_texture(Tex *texture)
2279 {
2280         if (built_map_.checkIsBuiltAndTag(texture)) {
2281                 return;
2282         }
2283         /* texture itself */
2284         build_animdata(&texture->id);
2285         /* texture's nodetree */
2286         build_nodetree(texture->nodetree);
2287         build_nested_nodetree(&texture->id, texture->nodetree);
2288 }
2289
2290 void DepsgraphRelationBuilder::build_compositor(Scene *scene)
2291 {
2292         /* For now, just a plain wrapper? */
2293         build_nodetree(scene->nodetree);
2294 }
2295
2296 void DepsgraphRelationBuilder::build_gpencil(bGPdata *gpd)
2297 {
2298         if (built_map_.checkIsBuiltAndTag(gpd)) {
2299                 return;
2300         }
2301         /* animation */
2302         build_animdata(&gpd->id);
2303
2304         // TODO: parent object (when that feature is implemented)
2305 }
2306
2307 void DepsgraphRelationBuilder::build_cachefile(CacheFile *cache_file)
2308 {
2309         if (built_map_.checkIsBuiltAndTag(cache_file)) {
2310                 return;
2311         }
2312         /* Animation. */
2313         build_animdata(&cache_file->id);
2314 }
2315
2316 void DepsgraphRelationBuilder::build_mask(Mask *mask)
2317 {
2318         if (built_map_.checkIsBuiltAndTag(mask)) {
2319                 return;
2320         }
2321         ID *mask_id = &mask->id;
2322         /* F-Curve animation. */
2323         build_animdata(mask_id);
2324         /* Own mask animation. */
2325         OperationKey mask_animation_key(mask_id,
2326                                         DEG_NODE_TYPE_ANIMATION,
2327                                         DEG_OPCODE_MASK_ANIMATION);
2328         TimeSourceKey time_src_key;
2329         add_relation(time_src_key, mask_animation_key, "TimeSrc -> Mask Animation");
2330         /* Final mask evaluation. */
2331         ComponentKey parameters_key(mask_id, DEG_NODE_TYPE_PARAMETERS);
2332         add_relation(mask_animation_key, parameters_key, "Mask Animation -> Mask Eval");
2333 }
2334
2335 void DepsgraphRelationBuilder::build_movieclip(MovieClip *clip)
2336 {
2337         if (built_map_.checkIsBuiltAndTag(clip)) {
2338                 return;
2339         }
2340         /* Animation. */
2341         build_animdata(&clip->id);
2342 }
2343
2344 void DepsgraphRelationBuilder::build_lightprobe(LightProbe *probe)
2345 {
2346         if (built_map_.checkIsBuiltAndTag(probe)) {
2347                 return;
2348         }
2349         build_animdata(&probe->id);
2350 }
2351
2352 void DepsgraphRelationBuilder::build_speaker(Speaker *speaker)
2353 {
2354         if (built_map_.checkIsBuiltAndTag(speaker)) {
2355                 return;
2356         }
2357         build_animdata(&speaker->id);
2358 }
2359
2360 void DepsgraphRelationBuilder::build_copy_on_write_relations()
2361 {
2362         foreach (IDDepsNode *id_node, graph_->id_nodes) {
2363                 build_copy_on_write_relations(id_node);
2364         }
2365 }
2366
2367 /* Nested datablocks (node trees, shape keys) requires special relation to
2368  * ensure owner's datablock remapping happens after node tree itself is ready.
2369  *
2370  * This is similar to what happens in ntree_hack_remap_pointers().
2371  */
2372 void DepsgraphRelationBuilder::build_nested_datablock(ID *owner, ID *id)
2373 {
2374         OperationKey owner_copy_on_write_key(owner,
2375                                              DEG_NODE_TYPE_COPY_ON_WRITE,
2376                                              DEG_OPCODE_COPY_ON_WRITE);
2377         OperationKey id_copy_on_write_key(id,
2378                                           DEG_NODE_TYPE_COPY_ON_WRITE,
2379                                           DEG_OPCODE_COPY_ON_WRITE);
2380         add_relation(id_copy_on_write_key,
2381                      owner_copy_on_write_key,
2382                      "Eval Order");
2383 }
2384
2385 void DepsgraphRelationBuilder::build_nested_nodetree(ID *owner,
2386                                                      bNodeTree *ntree)
2387 {
2388         if (ntree == NULL) {
2389                 return;
2390         }
2391         build_nested_datablock(owner, &ntree->id);
2392 }
2393
2394 void DepsgraphRelationBuilder::build_nested_shapekey(ID *owner, Key *key)
2395 {
2396         if (key == NULL) {
2397                 return;
2398         }
2399         build_nested_datablock(owner, &key->id);
2400 }
2401
2402 void DepsgraphRelationBuilder::build_copy_on_write_relations(IDDepsNode *id_node)
2403 {
2404         ID *id_orig = id_node->id_orig;
2405         const ID_Type id_type = GS(id_orig->name);
2406         TimeSourceKey time_source_key;
2407         OperationKey copy_on_write_key(id_orig,
2408                                        DEG_NODE_TYPE_COPY_ON_WRITE,
2409                                        DEG_OPCODE_COPY_ON_WRITE);
2410         /* XXX: This is a quick hack to make Alt-A to work. */
2411         // add_relation(time_source_key, copy_on_write_key, "Fluxgate capacitor hack");
2412         /* Resat of code is using rather low level trickery, so need to get some
2413          * explicit pointers. */
2414         DepsNode *node_cow = find_node(copy_on_write_key);
2415         OperationDepsNode *op_cow = node_cow->get_exit_operation();
2416         /* Plug any other components to this one. */
2417         GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, id_node->components)
2418         {
2419                 if (comp_node->type == DEG_NODE_TYPE_COPY_ON_WRITE) {
2420                         /* Copy-on-write component never depends on itself. */
2421                         continue;
2422                 }
2423                 if (!comp_node->depends_on_cow()) {
2424                         /* Component explicitly requests to not add relation. */
2425                         continue;
2426                 }
2427                 int rel_flag = (DEPSREL_FLAG_NO_FLUSH | DEPSREL_FLAG_GODMODE);
2428                 if (id_type == ID_ME && comp_node->type == DEG_NODE_TYPE_GEOMETRY) {
2429                         rel_flag &= ~DEPSREL_FLAG_NO_FLUSH;
2430                 }
2431                 /* materials need update grease pencil objects */
2432                 if (id_type == ID_MA) {
2433                         rel_flag &= ~DEPSREL_FLAG_NO_FLUSH;
2434                 }
2435                 /* Notes on exceptions:
2436                  * - Parameters component is where drivers are living. Changing any
2437                  *   of the (custom) properties in the original datablock (even the
2438                  *   ones which do not imply other component update) need to make
2439                  *   sure drivers are properly updated.
2440                  *   This way, for example, changing ID property will properly poke
2441                  *   all drivers to be updated.
2442                  *
2443                  * - View layers have cached array of bases in them, which is not
2444                  *   copied by copy-on-write, and not preserved. PROBABLY it is better
2445                  *   to preserve that cache in copy-on-write, but for the time being
2446                  *   we allow flush to layer collections component which will ensure
2447                  *   that cached array fo bases exists and is up-to-date.
2448                  *
2449                  * - Action is allowed to flush as well, this way it's possible to
2450                  *   keep current tagging in animation editors (which tags action for
2451                  *   CoW update when it's changed) but yet guarantee evaluation order
2452                  *   with objects which are using that action.
2453                  */
2454                 if (comp_node->type == DEG_NODE_TYPE_PARAMETERS ||
2455                     comp_node->type == DEG_NODE_TYPE_LAYER_COLLECTIONS ||
2456                     (comp_node->type == DEG_NODE_TYPE_ANIMATION && id_type == ID_AC))
2457                 {
2458                         rel_flag &= ~DEPSREL_FLAG_NO_FLUSH;
2459                 }
2460                 /* All entry operations of each component should wait for a proper
2461                  * copy of ID.
2462                  */
2463                 OperationDepsNode *op_entry = comp_node->get_entry_operation();
2464                 if (op_entry != NULL) {
2465                         DepsRelation *rel = graph_->add_new_relation(
2466                                 op_cow, op_entry, "CoW Dependency");
2467                         rel->flag |= rel_flag;
2468                 }
2469                 /* All dangling operations should also be executed after copy-on-write. */
2470                 GHASH_FOREACH_BEGIN(OperationDepsNode *, op_node, comp_node->operations_map)
2471                 {
2472                         if (op_node == op_entry) {
2473                                 continue;
2474                         }
2475                         if (op_node->inlinks.size() == 0) {
2476                                 DepsRelation *rel = graph_->add_new_relation(
2477                                         op_cow, op_node, "CoW Dependency");
2478                                 rel->flag |= rel_flag;
2479                         }
2480                         else {
2481                                 bool has_same_comp_dependency = false;
2482                                 foreach (DepsRelation *rel_current, op_node->inlinks) {
2483                                         if (rel_current->from->type != DEG_NODE_TYPE_OPERATION) {
2484                                                 continue;
2485                                         }
2486                                         OperationDepsNode *op_node_from =
2487                                                 (OperationDepsNode *)rel_current->from;
2488                                         if (op_node_from->owner == op_node->owner) {
2489                                                 has_same_comp_dependency = true;
2490                                                 break;
2491                                         }
2492                                 }
2493                                 if (!has_same_comp_dependency) {
2494                                         DepsRelation *rel = graph_->add_new_relation(
2495                                                 op_cow, op_node, "CoW Dependency");
2496                                         rel->flag |= rel_flag;
2497                                 }
2498                         }
2499                 }
2500                 GHASH_FOREACH_END();
2501                 /* NOTE: We currently ignore implicit relations to an external
2502                  * datablocks for copy-on-write operations. This means, for example,
2503                  * copy-on-write component of Object will not wait for copy-on-write
2504                  * component of it's Mesh. This is because pointers are all known
2505                  * already so remapping will happen all correct. And then If some object
2506                  * evaluation step needs geometry, it will have transitive dependency
2507                  * to Mesh copy-on-write already.
2508                  */
2509         }
2510         GHASH_FOREACH_END();
2511         /* TODO(sergey): This solves crash for now, but causes too many
2512          * updates potentially.
2513          */
2514         if (GS(id_orig->name) == ID_OB) {
2515                 Object *object = (Object *)id_orig;
2516                 ID *object_data_id = (ID *)object->data;
2517                 if (object_data_id != NULL) {
2518                         if (deg_copy_on_write_is_needed(object_data_id)) {
2519                                 OperationKey data_copy_on_write_key(object_data_id,
2520                                                                     DEG_NODE_TYPE_COPY_ON_WRITE,
2521                                                                     DEG_OPCODE_COPY_ON_WRITE);
2522                                 add_relation(data_copy_on_write_key,
2523                                              copy_on_write_key,
2524                                              "Eval Order",
2525                                              DEPSREL_FLAG_GODMODE);
2526                         }
2527                 }
2528                 else {
2529                         BLI_assert(object->type == OB_EMPTY);
2530                 }
2531         }
2532 }
2533
2534 /* **** ID traversal callbacks functions **** */
2535
2536 void DepsgraphRelationBuilder::modifier_walk(void *user_data,
2537                                              struct Object * /*object*/,
2538                                              struct ID **idpoin,
2539                                              int /*cb_flag*/)
2540 {
2541         BuilderWalkUserData *data = (BuilderWalkUserData *)user_data;
2542         ID *id = *idpoin;
2543         if (id == NULL) {
2544                 return;
2545         }
2546         data->builder->build_id(id);
2547 }
2548
2549 void DepsgraphRelationBuilder::constraint_walk(bConstraint * /*con*/,
2550                                                ID **idpoin,
2551                                                bool /*is_reference*/,
2552                                                void *user_data)
2553 {
2554         BuilderWalkUserData *data = (BuilderWalkUserData *)user_data;
2555         ID *id = *idpoin;
2556         if (id == NULL) {
2557                 return;
2558         }
2559         data->builder->build_id(id);
2560 }
2561
2562 }  // namespace DEG