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