Merge branch 'blender-v2.81-release'
[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 possible
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   build_object_proxy_from(object);
661   build_object_proxy_group(object);
662   /* Object dupligroup. */
663   if (object->instance_collection != NULL) {
664     build_collection(NULL, object, object->instance_collection);
665   }
666   /* Point caches. */
667   build_object_pointcache(object);
668   /* Synchronization back to original object. */
669   OperationKey synchronize_key(
670       &object->id, NodeType::SYNCHRONIZATION, OperationCode::SYNCHRONIZE_TO_ORIGINAL);
671   add_relation(final_transform_key, synchronize_key, "Synchronize to Original");
672   /* Parameters. */
673   build_parameters(&object->id);
674 }
675
676 void DepsgraphRelationBuilder::build_object_proxy_from(Object *object)
677 {
678   if (object->proxy_from == NULL) {
679     return;
680   }
681   /* Object is linked here (comes from the library). */
682   build_object(NULL, object->proxy_from);
683   ComponentKey ob_transform_key(&object->proxy_from->id, NodeType::TRANSFORM);
684   ComponentKey proxy_transform_key(&object->id, NodeType::TRANSFORM);
685   add_relation(ob_transform_key, proxy_transform_key, "Proxy Transform");
686 }
687
688 void DepsgraphRelationBuilder::build_object_proxy_group(Object *object)
689 {
690   if (object->proxy_group == NULL || object->proxy_group == object->proxy) {
691     return;
692   }
693   /* Object is local here (local in .blend file, users interacts with it). */
694   build_object(NULL, object->proxy_group);
695   OperationKey proxy_group_eval_key(
696       &object->proxy_group->id, NodeType::TRANSFORM, OperationCode::TRANSFORM_EVAL);
697   OperationKey transform_eval_key(&object->id, NodeType::TRANSFORM, OperationCode::TRANSFORM_EVAL);
698   add_relation(proxy_group_eval_key, transform_eval_key, "Proxy Group Transform");
699 }
700
701 void DepsgraphRelationBuilder::build_object_flags(Base *base, Object *object)
702 {
703   if (base == NULL) {
704     return;
705   }
706   OperationKey view_layer_done_key(
707       &scene_->id, NodeType::LAYER_COLLECTIONS, OperationCode::VIEW_LAYER_EVAL);
708   OperationKey object_flags_key(
709       &object->id, NodeType::OBJECT_FROM_LAYER, OperationCode::OBJECT_BASE_FLAGS);
710   add_relation(view_layer_done_key, object_flags_key, "Base flags flush");
711   /* Synchronization back to original object. */
712   OperationKey synchronize_key(
713       &object->id, NodeType::SYNCHRONIZATION, OperationCode::SYNCHRONIZE_TO_ORIGINAL);
714   add_relation(object_flags_key, synchronize_key, "Synchronize to Original");
715 }
716
717 void DepsgraphRelationBuilder::build_object_data(Object *object)
718 {
719   if (object->data == NULL) {
720     return;
721   }
722   ID *obdata_id = (ID *)object->data;
723   /* Object data animation. */
724   if (!built_map_.checkIsBuilt(obdata_id)) {
725     build_animdata(obdata_id);
726   }
727   /* type-specific data. */
728   switch (object->type) {
729     case OB_MESH:
730     case OB_CURVE:
731     case OB_FONT:
732     case OB_SURF:
733     case OB_MBALL:
734     case OB_LATTICE:
735     case OB_GPENCIL: {
736       build_object_data_geometry(object);
737       /* TODO(sergey): Only for until we support granular
738        * update of curves. */
739       if (object->type == OB_FONT) {
740         Curve *curve = (Curve *)object->data;
741         if (curve->textoncurve) {
742           add_special_eval_flag(&curve->textoncurve->id, DAG_EVAL_NEED_CURVE_PATH);
743         }
744       }
745       break;
746     }
747     case OB_ARMATURE:
748       if (ID_IS_LINKED(object) && object->proxy_from != NULL) {
749         build_proxy_rig(object);
750       }
751       else {
752         build_rig(object);
753       }
754       break;
755     case OB_LAMP:
756       build_object_data_light(object);
757       break;
758     case OB_CAMERA:
759       build_object_data_camera(object);
760       break;
761     case OB_LIGHTPROBE:
762       build_object_data_lightprobe(object);
763       break;
764     case OB_SPEAKER:
765       build_object_data_speaker(object);
766       break;
767   }
768   Key *key = BKE_key_from_object(object);
769   if (key != NULL) {
770     ComponentKey geometry_key((ID *)object->data, NodeType::GEOMETRY);
771     ComponentKey key_key(&key->id, NodeType::GEOMETRY);
772     add_relation(key_key, geometry_key, "Shapekeys");
773     build_nested_shapekey(&object->id, key);
774   }
775   /* Materials. */
776   Material ***materials_ptr = give_matarar(object);
777   if (materials_ptr != NULL) {
778     short *num_materials_ptr = give_totcolp(object);
779     build_materials(*materials_ptr, *num_materials_ptr);
780   }
781 }
782
783 void DepsgraphRelationBuilder::build_object_data_camera(Object *object)
784 {
785   Camera *camera = (Camera *)object->data;
786   build_camera(camera);
787   ComponentKey object_parameters_key(&object->id, NodeType::PARAMETERS);
788   ComponentKey camera_parameters_key(&camera->id, NodeType::PARAMETERS);
789   add_relation(camera_parameters_key, object_parameters_key, "Camera -> Object");
790 }
791
792 void DepsgraphRelationBuilder::build_object_data_light(Object *object)
793 {
794   Light *lamp = (Light *)object->data;
795   build_light(lamp);
796   ComponentKey lamp_parameters_key(&lamp->id, NodeType::PARAMETERS);
797   ComponentKey object_parameters_key(&object->id, NodeType::PARAMETERS);
798   add_relation(lamp_parameters_key, object_parameters_key, "Light -> Object");
799 }
800
801 void DepsgraphRelationBuilder::build_object_data_lightprobe(Object *object)
802 {
803   LightProbe *probe = (LightProbe *)object->data;
804   build_lightprobe(probe);
805   OperationKey probe_key(&probe->id, NodeType::PARAMETERS, OperationCode::LIGHT_PROBE_EVAL);
806   OperationKey object_key(&object->id, NodeType::PARAMETERS, OperationCode::LIGHT_PROBE_EVAL);
807   add_relation(probe_key, object_key, "LightProbe Update");
808 }
809
810 void DepsgraphRelationBuilder::build_object_data_speaker(Object *object)
811 {
812   Speaker *speaker = (Speaker *)object->data;
813   build_speaker(speaker);
814   ComponentKey speaker_key(&speaker->id, NodeType::AUDIO);
815   ComponentKey object_key(&object->id, NodeType::AUDIO);
816   add_relation(speaker_key, object_key, "Speaker Update");
817 }
818
819 void DepsgraphRelationBuilder::build_object_parent(Object *object)
820 {
821   Object *parent = object->parent;
822   ID *parent_id = &object->parent->id;
823   ComponentKey object_transform_key(&object->id, NodeType::TRANSFORM);
824   /* Type-specific links. */
825   switch (object->partype) {
826     /* Armature Deform (Virtual Modifier) */
827     case PARSKEL: {
828       ComponentKey parent_transform_key(parent_id, NodeType::TRANSFORM);
829       add_relation(parent_transform_key, object_transform_key, "Parent Armature Transform");
830
831       if (parent->type == OB_ARMATURE) {
832         ComponentKey object_geometry_key(&object->id, NodeType::GEOMETRY);
833         ComponentKey parent_pose_key(parent_id, NodeType::EVAL_POSE);
834         add_relation(
835             parent_transform_key, object_geometry_key, "Parent Armature Transform -> Geometry");
836         add_relation(parent_pose_key, object_geometry_key, "Parent Armature Pose -> Geometry");
837
838         add_depends_on_transform_relation(
839             &object->id, object_geometry_key, "Virtual Armature Modifier");
840       }
841
842       break;
843     }
844
845     /* Vertex Parent */
846     case PARVERT1:
847     case PARVERT3: {
848       ComponentKey parent_key(parent_id, NodeType::GEOMETRY);
849       add_relation(parent_key, object_transform_key, "Vertex Parent");
850       /* Original index is used for optimizations of lookups for subdiv
851        * only meshes.
852        * TODO(sergey): This optimization got lost at 2.8, so either verify
853        * we can get rid of this mask here, or bring the optimization
854        * back. */
855       add_customdata_mask(object->parent,
856                           DEGCustomDataMeshMasks::MaskVert(CD_MASK_ORIGINDEX) |
857                               DEGCustomDataMeshMasks::MaskEdge(CD_MASK_ORIGINDEX) |
858                               DEGCustomDataMeshMasks::MaskFace(CD_MASK_ORIGINDEX) |
859                               DEGCustomDataMeshMasks::MaskPoly(CD_MASK_ORIGINDEX));
860       ComponentKey transform_key(parent_id, NodeType::TRANSFORM);
861       add_relation(transform_key, object_transform_key, "Vertex Parent TFM");
862       break;
863     }
864
865     /* Bone Parent */
866     case PARBONE: {
867       ComponentKey parent_bone_key(parent_id, NodeType::BONE, object->parsubstr);
868       OperationKey parent_transform_key(
869           parent_id, NodeType::TRANSFORM, OperationCode::TRANSFORM_FINAL);
870       add_relation(parent_bone_key, object_transform_key, "Bone Parent");
871       add_relation(parent_transform_key, object_transform_key, "Armature Parent");
872       break;
873     }
874
875     default: {
876       if (object->parent->type == OB_LATTICE) {
877         /* Lattice Deform Parent - Virtual Modifier. */
878         ComponentKey parent_key(parent_id, NodeType::TRANSFORM);
879         ComponentKey geom_key(parent_id, NodeType::GEOMETRY);
880         add_relation(parent_key, object_transform_key, "Lattice Deform Parent");
881         add_relation(geom_key, object_transform_key, "Lattice Deform Parent Geom");
882       }
883       else if (object->parent->type == OB_CURVE) {
884         Curve *cu = (Curve *)object->parent->data;
885
886         if (cu->flag & CU_PATH) {
887           /* Follow Path. */
888           ComponentKey parent_key(parent_id, NodeType::GEOMETRY);
889           add_relation(parent_key, object_transform_key, "Curve Follow Parent");
890           ComponentKey transform_key(parent_id, NodeType::TRANSFORM);
891           add_relation(transform_key, object_transform_key, "Curve Follow TFM");
892         }
893         else {
894           /* Standard Parent. */
895           ComponentKey parent_key(parent_id, NodeType::TRANSFORM);
896           add_relation(parent_key, object_transform_key, "Curve Parent");
897         }
898       }
899       else {
900         /* Standard Parent. */
901         ComponentKey parent_key(parent_id, NodeType::TRANSFORM);
902         add_relation(parent_key, object_transform_key, "Parent");
903       }
904       break;
905     }
906   }
907   /* Metaballs are the odd balls here (no pun intended): they will request
908    * instance-list (formerly known as dupli-list) during evaluation. This is
909    * their way of interacting with all instanced surfaces, making a nice
910    * effect when is used form particle system. */
911   if (object->type == OB_MBALL && parent->transflag & OB_DUPLI) {
912     ComponentKey parent_geometry_key(parent_id, NodeType::GEOMETRY);
913     /* NOTE: Metaballs are evaluating geometry only after their transform,
914      * so we only hook up to transform channel here. */
915     add_relation(parent_geometry_key, object_transform_key, "Parent");
916   }
917
918   /* Dupliverts uses original vertex index. */
919   if (parent->transflag & OB_DUPLIVERTS) {
920     add_customdata_mask(parent, DEGCustomDataMeshMasks::MaskVert(CD_MASK_ORIGINDEX));
921   }
922 }
923
924 void DepsgraphRelationBuilder::build_object_pointcache(Object *object)
925 {
926   ComponentKey point_cache_key(&object->id, NodeType::POINT_CACHE);
927   /* Different point caches are affecting different aspects of life of the
928    * object. We keep track of those aspects and avoid duplicate relations. */
929   enum {
930     FLAG_TRANSFORM = (1 << 0),
931     FLAG_GEOMETRY = (1 << 1),
932     FLAG_ALL = (FLAG_TRANSFORM | FLAG_GEOMETRY),
933   };
934   ListBase ptcache_id_list;
935   BKE_ptcache_ids_from_object(&ptcache_id_list, object, scene_, 0);
936   int handled_components = 0;
937   LISTBASE_FOREACH (PTCacheID *, ptcache_id, &ptcache_id_list) {
938     /* Check which components needs the point cache. */
939     int flag = -1;
940     if (ptcache_id->type == PTCACHE_TYPE_RIGIDBODY) {
941       flag = FLAG_TRANSFORM;
942       OperationKey transform_key(
943           &object->id, NodeType::TRANSFORM, OperationCode::TRANSFORM_SIMULATION_INIT);
944       add_relation(point_cache_key, transform_key, "Point Cache -> Rigid Body");
945       /* Manual changes to effectors need to invalidate simulation. */
946       OperationKey rigidbody_rebuild_key(
947           &scene_->id, NodeType::TRANSFORM, OperationCode::RIGIDBODY_REBUILD);
948       add_relation(rigidbody_rebuild_key,
949                    point_cache_key,
950                    "Rigid Body Rebuild -> Point Cache Reset",
951                    RELATION_FLAG_FLUSH_USER_EDIT_ONLY);
952     }
953     else {
954       flag = FLAG_GEOMETRY;
955       OperationKey geometry_key(&object->id, NodeType::GEOMETRY, OperationCode::GEOMETRY_EVAL);
956       add_relation(point_cache_key, geometry_key, "Point Cache -> Geometry");
957     }
958     BLI_assert(flag != -1);
959     /* Tag that we did handle that component. */
960     handled_components |= flag;
961     if (handled_components == FLAG_ALL) {
962       break;
963     }
964   }
965   /* Manual edits to any dependency (or self) should reset the point cache. */
966   if (!BLI_listbase_is_empty(&ptcache_id_list)) {
967     OperationKey transform_eval_key(
968         &object->id, NodeType::TRANSFORM, OperationCode::TRANSFORM_EVAL);
969     OperationKey geometry_init_key(
970         &object->id, NodeType::GEOMETRY, OperationCode::GEOMETRY_EVAL_INIT);
971     add_relation(transform_eval_key,
972                  point_cache_key,
973                  "Transform Simulation -> Point Cache",
974                  RELATION_FLAG_FLUSH_USER_EDIT_ONLY);
975     add_relation(geometry_init_key,
976                  point_cache_key,
977                  "Geometry Init -> Point Cache",
978                  RELATION_FLAG_FLUSH_USER_EDIT_ONLY);
979   }
980   BLI_freelistN(&ptcache_id_list);
981 }
982
983 void DepsgraphRelationBuilder::build_constraints(ID *id,
984                                                  NodeType component_type,
985                                                  const char *component_subdata,
986                                                  ListBase *constraints,
987                                                  RootPChanMap *root_map)
988 {
989   OperationKey constraint_op_key(id,
990                                  component_type,
991                                  component_subdata,
992                                  (component_type == NodeType::BONE) ?
993                                      OperationCode::BONE_CONSTRAINTS :
994                                      OperationCode::TRANSFORM_CONSTRAINTS);
995   /* Add dependencies for each constraint in turn. */
996   for (bConstraint *con = (bConstraint *)constraints->first; con; con = con->next) {
997     const bConstraintTypeInfo *cti = BKE_constraint_typeinfo_get(con);
998     /* Invalid constraint type. */
999     if (cti == NULL) {
1000       continue;
1001     }
1002     /* Special case for camera tracking -- it doesn't use targets to
1003      * define relations. */
1004     /* TODO: we can now represent dependencies in a much richer manner,
1005      * so review how this is done.  */
1006     if (ELEM(cti->type,
1007              CONSTRAINT_TYPE_FOLLOWTRACK,
1008              CONSTRAINT_TYPE_CAMERASOLVER,
1009              CONSTRAINT_TYPE_OBJECTSOLVER)) {
1010       bool depends_on_camera = false;
1011       if (cti->type == CONSTRAINT_TYPE_FOLLOWTRACK) {
1012         bFollowTrackConstraint *data = (bFollowTrackConstraint *)con->data;
1013         if (((data->clip) || (data->flag & FOLLOWTRACK_ACTIVECLIP)) && data->track[0]) {
1014           depends_on_camera = true;
1015         }
1016         if (data->depth_ob) {
1017           ComponentKey depth_transform_key(&data->depth_ob->id, NodeType::TRANSFORM);
1018           ComponentKey depth_geometry_key(&data->depth_ob->id, NodeType::GEOMETRY);
1019           add_relation(depth_transform_key, constraint_op_key, cti->name);
1020           add_relation(depth_geometry_key, constraint_op_key, cti->name);
1021         }
1022       }
1023       else if (cti->type == CONSTRAINT_TYPE_OBJECTSOLVER) {
1024         depends_on_camera = true;
1025       }
1026       if (depends_on_camera && scene_->camera != NULL) {
1027         ComponentKey camera_key(&scene_->camera->id, NodeType::TRANSFORM);
1028         add_relation(camera_key, constraint_op_key, cti->name);
1029       }
1030       /* TODO(sergey): This is more a TimeSource -> MovieClip ->
1031        * Constraint dependency chain. */
1032       TimeSourceKey time_src_key;
1033       add_relation(time_src_key, constraint_op_key, "TimeSrc -> Animation");
1034     }
1035     else if (cti->type == CONSTRAINT_TYPE_TRANSFORM_CACHE) {
1036       /* TODO(kevin): This is more a TimeSource -> CacheFile -> Constraint
1037        * dependency chain. */
1038       TimeSourceKey time_src_key;
1039       add_relation(time_src_key, constraint_op_key, "TimeSrc -> Animation");
1040       bTransformCacheConstraint *data = (bTransformCacheConstraint *)con->data;
1041       if (data->cache_file) {
1042         ComponentKey cache_key(&data->cache_file->id, NodeType::CACHE);
1043         add_relation(cache_key, constraint_op_key, cti->name);
1044       }
1045     }
1046     else if (cti->get_constraint_targets) {
1047       ListBase targets = {NULL, NULL};
1048       cti->get_constraint_targets(con, &targets);
1049       LISTBASE_FOREACH (bConstraintTarget *, ct, &targets) {
1050         if (ct->tar == NULL) {
1051           continue;
1052         }
1053         if (ELEM(con->type, CONSTRAINT_TYPE_KINEMATIC, CONSTRAINT_TYPE_SPLINEIK)) {
1054           /* Ignore IK constraints - these are handled separately
1055            * (on pose level). */
1056         }
1057         else if (ELEM(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO)) {
1058           /* These constraints require path geometry data. */
1059           ComponentKey target_key(&ct->tar->id, NodeType::GEOMETRY);
1060           add_relation(target_key, constraint_op_key, cti->name);
1061           ComponentKey target_transform_key(&ct->tar->id, NodeType::TRANSFORM);
1062           add_relation(target_transform_key, constraint_op_key, cti->name);
1063         }
1064         else if ((ct->tar->type == OB_ARMATURE) && (ct->subtarget[0])) {
1065           OperationCode opcode;
1066           /* relation to bone */
1067           opcode = bone_target_opcode(
1068               &ct->tar->id, ct->subtarget, id, component_subdata, root_map);
1069           /* Armature constraint always wants the final position and chan_mat. */
1070           if (ELEM(con->type, CONSTRAINT_TYPE_ARMATURE)) {
1071             opcode = OperationCode::BONE_DONE;
1072           }
1073           /* if needs bbone shape, reference the segment computation */
1074           if (BKE_constraint_target_uses_bbone(con, ct) &&
1075               check_pchan_has_bbone_segments(ct->tar, ct->subtarget)) {
1076             opcode = OperationCode::BONE_SEGMENTS;
1077           }
1078           OperationKey target_key(&ct->tar->id, NodeType::BONE, ct->subtarget, opcode);
1079           add_relation(target_key, constraint_op_key, cti->name);
1080         }
1081         else if (ELEM(ct->tar->type, OB_MESH, OB_LATTICE) && (ct->subtarget[0])) {
1082           /* Vertex group. */
1083           /* NOTE: Vertex group is likely to be used to get vertices
1084            * in a world space. This requires to know both geometry
1085            * and transformation of the target object. */
1086           ComponentKey target_transform_key(&ct->tar->id, NodeType::TRANSFORM);
1087           ComponentKey target_geometry_key(&ct->tar->id, NodeType::GEOMETRY);
1088           add_relation(target_transform_key, constraint_op_key, cti->name);
1089           add_relation(target_geometry_key, constraint_op_key, cti->name);
1090           add_customdata_mask(ct->tar, DEGCustomDataMeshMasks::MaskVert(CD_MASK_MDEFORMVERT));
1091         }
1092         else if (con->type == CONSTRAINT_TYPE_SHRINKWRAP) {
1093           bShrinkwrapConstraint *scon = (bShrinkwrapConstraint *)con->data;
1094
1095           /* Constraints which requires the target object surface. */
1096           ComponentKey target_key(&ct->tar->id, NodeType::GEOMETRY);
1097           add_relation(target_key, constraint_op_key, cti->name);
1098
1099           /* Add dependency on normal layers if necessary. */
1100           if (ct->tar->type == OB_MESH && scon->shrinkType != MOD_SHRINKWRAP_NEAREST_VERTEX) {
1101             bool track = (scon->flag & CON_SHRINKWRAP_TRACK_NORMAL) != 0;
1102             if (track || BKE_shrinkwrap_needs_normals(scon->shrinkType, scon->shrinkMode)) {
1103               add_customdata_mask(ct->tar,
1104                                   DEGCustomDataMeshMasks::MaskVert(CD_MASK_NORMAL) |
1105                                       DEGCustomDataMeshMasks::MaskLoop(CD_MASK_CUSTOMLOOPNORMAL));
1106             }
1107             if (scon->shrinkType == MOD_SHRINKWRAP_TARGET_PROJECT) {
1108               add_special_eval_flag(&ct->tar->id, DAG_EVAL_NEED_SHRINKWRAP_BOUNDARY);
1109             }
1110           }
1111
1112           /* NOTE: obdata eval now doesn't necessarily depend on the
1113            * object's transform. */
1114           ComponentKey target_transform_key(&ct->tar->id, NodeType::TRANSFORM);
1115           add_relation(target_transform_key, constraint_op_key, cti->name);
1116         }
1117         else {
1118           /* Standard object relation. */
1119           // TODO: loc vs rot vs scale?
1120           if (&ct->tar->id == id) {
1121             /* Constraint targeting own object:
1122              * - This case is fine IFF we're dealing with a bone
1123              *   constraint pointing to its own armature. In that
1124              *   case, it's just transform -> bone.
1125              * - If however it is a real self targeting case, just
1126              *   make it depend on the previous constraint (or the
1127              *   pre-constraint state). */
1128             if ((ct->tar->type == OB_ARMATURE) && (component_type == NodeType::BONE)) {
1129               OperationKey target_key(
1130                   &ct->tar->id, NodeType::TRANSFORM, OperationCode::TRANSFORM_FINAL);
1131               add_relation(target_key, constraint_op_key, cti->name);
1132             }
1133             else {
1134               OperationKey target_key(
1135                   &ct->tar->id, NodeType::TRANSFORM, OperationCode::TRANSFORM_LOCAL);
1136               add_relation(target_key, constraint_op_key, cti->name);
1137             }
1138           }
1139           else {
1140             /* Normal object dependency. */
1141             OperationKey target_key(
1142                 &ct->tar->id, NodeType::TRANSFORM, OperationCode::TRANSFORM_FINAL);
1143             add_relation(target_key, constraint_op_key, cti->name);
1144           }
1145         }
1146         /* Constraints which needs world's matrix for transform.
1147          * TODO(sergey): More constraints here? */
1148         if (ELEM(con->type,
1149                  CONSTRAINT_TYPE_ROTLIKE,
1150                  CONSTRAINT_TYPE_SIZELIKE,
1151                  CONSTRAINT_TYPE_LOCLIKE,
1152                  CONSTRAINT_TYPE_TRANSLIKE)) {
1153           /* TODO(sergey): Add used space check. */
1154           ComponentKey target_transform_key(&ct->tar->id, NodeType::TRANSFORM);
1155           add_relation(target_transform_key, constraint_op_key, cti->name);
1156         }
1157       }
1158       if (cti->flush_constraint_targets) {
1159         cti->flush_constraint_targets(con, &targets, 1);
1160       }
1161     }
1162   }
1163 }
1164
1165 void DepsgraphRelationBuilder::build_animdata(ID *id)
1166 {
1167   /* Images. */
1168   build_animation_images(id);
1169   /* Animation curves and NLA. */
1170   build_animdata_curves(id);
1171   /* Drivers. */
1172   build_animdata_drivers(id);
1173 }
1174
1175 void DepsgraphRelationBuilder::build_animdata_curves(ID *id)
1176 {
1177   AnimData *adt = BKE_animdata_from_id(id);
1178   if (adt == NULL) {
1179     return;
1180   }
1181   if (adt->action != NULL) {
1182     build_action(adt->action);
1183   }
1184   if (adt->action == NULL && BLI_listbase_is_empty(&adt->nla_tracks)) {
1185     return;
1186   }
1187   /* Ensure evaluation order from entry to exit. */
1188   OperationKey animation_entry_key(id, NodeType::ANIMATION, OperationCode::ANIMATION_ENTRY);
1189   OperationKey animation_eval_key(id, NodeType::ANIMATION, OperationCode::ANIMATION_EVAL);
1190   OperationKey animation_exit_key(id, NodeType::ANIMATION, OperationCode::ANIMATION_EXIT);
1191   add_relation(animation_entry_key, animation_eval_key, "Init -> Eval");
1192   add_relation(animation_eval_key, animation_exit_key, "Eval -> Exit");
1193   /* Wire up dependency from action. */
1194   ComponentKey adt_key(id, NodeType::ANIMATION);
1195   /* Relation from action itself. */
1196   if (adt->action != NULL) {
1197     ComponentKey action_key(&adt->action->id, NodeType::ANIMATION);
1198     add_relation(action_key, adt_key, "Action -> Animation");
1199   }
1200   /* Get source operations. */
1201   Node *node_from = get_node(adt_key);
1202   BLI_assert(node_from != NULL);
1203   if (node_from == NULL) {
1204     return;
1205   }
1206   OperationNode *operation_from = node_from->get_exit_operation();
1207   BLI_assert(operation_from != NULL);
1208   /* Build relations from animation operation to properties it changes. */
1209   if (adt->action != NULL) {
1210     build_animdata_curves_targets(id, adt_key, operation_from, &adt->action->curves);
1211   }
1212   LISTBASE_FOREACH (NlaTrack *, nlt, &adt->nla_tracks) {
1213     build_animdata_nlastrip_targets(id, adt_key, operation_from, &nlt->strips);
1214   }
1215 }
1216
1217 void DepsgraphRelationBuilder::build_animdata_curves_targets(ID *id,
1218                                                              ComponentKey &adt_key,
1219                                                              OperationNode *operation_from,
1220                                                              ListBase *curves)
1221 {
1222   /* Iterate over all curves and build relations. */
1223   PointerRNA id_ptr;
1224   RNA_id_pointer_create(id, &id_ptr);
1225   LISTBASE_FOREACH (FCurve *, fcu, curves) {
1226     PointerRNA ptr;
1227     PropertyRNA *prop;
1228     int index;
1229     if (!RNA_path_resolve_full(&id_ptr, fcu->rna_path, &ptr, &prop, &index)) {
1230       continue;
1231     }
1232     Node *node_to = rna_node_query_.find_node(&ptr, prop, RNAPointerSource::ENTRY);
1233     if (node_to == NULL) {
1234       continue;
1235     }
1236     OperationNode *operation_to = node_to->get_entry_operation();
1237     /* NOTE: Special case for bones, avoid relation from animation to
1238      * each of the bones. Bone evaluation could only start from pose
1239      * init anyway. */
1240     if (operation_to->opcode == OperationCode::BONE_LOCAL) {
1241       OperationKey pose_init_key(id, NodeType::EVAL_POSE, OperationCode::POSE_INIT);
1242       add_relation(adt_key, pose_init_key, "Animation -> Prop", RELATION_CHECK_BEFORE_ADD);
1243       continue;
1244     }
1245     graph_->add_new_relation(
1246         operation_from, operation_to, "Animation -> Prop", RELATION_CHECK_BEFORE_ADD);
1247     /* It is possible that animation is writing to a nested ID data-block,
1248      * need to make sure animation is evaluated after target ID is copied. */
1249     const IDNode *id_node_from = operation_from->owner->owner;
1250     const IDNode *id_node_to = operation_to->owner->owner;
1251     if (id_node_from != id_node_to) {
1252       ComponentKey cow_key(id_node_to->id_orig, NodeType::COPY_ON_WRITE);
1253       add_relation(cow_key,
1254                    adt_key,
1255                    "Animated CoW -> Animation",
1256                    RELATION_CHECK_BEFORE_ADD | RELATION_FLAG_NO_FLUSH);
1257     }
1258   }
1259 }
1260
1261 void DepsgraphRelationBuilder::build_animdata_nlastrip_targets(ID *id,
1262                                                                ComponentKey &adt_key,
1263                                                                OperationNode *operation_from,
1264                                                                ListBase *strips)
1265 {
1266   LISTBASE_FOREACH (NlaStrip *, strip, strips) {
1267     if (strip->act != NULL) {
1268       build_action(strip->act);
1269
1270       ComponentKey action_key(&strip->act->id, NodeType::ANIMATION);
1271       add_relation(action_key, adt_key, "Action -> Animation");
1272
1273       build_animdata_curves_targets(id, adt_key, operation_from, &strip->act->curves);
1274     }
1275     else if (strip->strips.first != NULL) {
1276       build_animdata_nlastrip_targets(id, adt_key, operation_from, &strip->strips);
1277     }
1278   }
1279 }
1280
1281 void DepsgraphRelationBuilder::build_animdata_drivers(ID *id)
1282 {
1283   AnimData *adt = BKE_animdata_from_id(id);
1284   if (adt == NULL) {
1285     return;
1286   }
1287   ComponentKey adt_key(id, NodeType::ANIMATION);
1288   LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) {
1289     OperationKey driver_key(id,
1290                             NodeType::PARAMETERS,
1291                             OperationCode::DRIVER,
1292                             fcu->rna_path ? fcu->rna_path : "",
1293                             fcu->array_index);
1294
1295     /* create the driver's relations to targets */
1296     build_driver(id, fcu);
1297     /* Special case for array drivers: we can not multithread them because
1298      * of the way how they work internally: animation system will write the
1299      * whole array back to RNA even when changing individual array value.
1300      *
1301      * Some tricky things here:
1302      * - array_index is -1 for single channel drivers, meaning we only have
1303      *   to do some magic when array_index is not -1.
1304      * - We do relation from next array index to a previous one, so we don't
1305      *   have to deal with array index 0.
1306      *
1307      * TODO(sergey): Avoid liner lookup somehow. */
1308     if (fcu->array_index > 0) {
1309       FCurve *fcu_prev = NULL;
1310       LISTBASE_FOREACH (FCurve *, fcu_candidate, &adt->drivers) {
1311         /* Writing to different RNA paths is  */
1312         const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1313         if (!STREQ(fcu_candidate->rna_path, rna_path)) {
1314           continue;
1315         }
1316         /* We only do relation from previous fcurve to previous one. */
1317         if (fcu_candidate->array_index >= fcu->array_index) {
1318           continue;
1319         }
1320         /* Choose fcurve with highest possible array index. */
1321         if (fcu_prev == NULL || fcu_candidate->array_index > fcu_prev->array_index) {
1322           fcu_prev = fcu_candidate;
1323         }
1324       }
1325       if (fcu_prev != NULL) {
1326         OperationKey prev_driver_key(id,
1327                                      NodeType::PARAMETERS,
1328                                      OperationCode::DRIVER,
1329                                      fcu_prev->rna_path ? fcu_prev->rna_path : "",
1330                                      fcu_prev->array_index);
1331         OperationKey driver_key(id,
1332                                 NodeType::PARAMETERS,
1333                                 OperationCode::DRIVER,
1334                                 fcu->rna_path ? fcu->rna_path : "",
1335                                 fcu->array_index);
1336         add_relation(prev_driver_key, driver_key, "Driver Order");
1337       }
1338     }
1339
1340     /* prevent driver from occurring before own animation... */
1341     if (adt->action || adt->nla_tracks.first) {
1342       add_relation(adt_key, driver_key, "AnimData Before Drivers");
1343     }
1344   }
1345 }
1346
1347 void DepsgraphRelationBuilder::build_animation_images(ID *id)
1348 {
1349   /* TODO: can we check for existence of node for performance? */
1350   if (BKE_image_user_id_has_animation(id)) {
1351     OperationKey image_animation_key(id, NodeType::ANIMATION, OperationCode::IMAGE_ANIMATION);
1352     TimeSourceKey time_src_key;
1353     add_relation(time_src_key, image_animation_key, "TimeSrc -> Image Animation");
1354   }
1355 }
1356
1357 void DepsgraphRelationBuilder::build_action(bAction *action)
1358 {
1359   if (built_map_.checkIsBuiltAndTag(action)) {
1360     return;
1361   }
1362   TimeSourceKey time_src_key;
1363   ComponentKey animation_key(&action->id, NodeType::ANIMATION);
1364   add_relation(time_src_key, animation_key, "TimeSrc -> Animation");
1365 }
1366
1367 void DepsgraphRelationBuilder::build_driver(ID *id, FCurve *fcu)
1368 {
1369   ChannelDriver *driver = fcu->driver;
1370   OperationKey driver_key(id,
1371                           NodeType::PARAMETERS,
1372                           OperationCode::DRIVER,
1373                           fcu->rna_path ? fcu->rna_path : "",
1374                           fcu->array_index);
1375   /* Driver -> data components (for interleaved evaluation
1376    * bones/constraints/modifiers). */
1377   build_driver_data(id, fcu);
1378   /* Loop over variables to get the target relationships. */
1379   build_driver_variables(id, fcu);
1380   /* It's quite tricky to detect if the driver actually depends on time or
1381    * not, so for now we'll be quite conservative here about optimization and
1382    * consider all python drivers to be depending on time. */
1383   if ((driver->type == DRIVER_TYPE_PYTHON) && python_driver_depends_on_time(driver)) {
1384     TimeSourceKey time_src_key;
1385     add_relation(time_src_key, driver_key, "TimeSrc -> Driver");
1386   }
1387 }
1388
1389 void DepsgraphRelationBuilder::build_driver_data(ID *id, FCurve *fcu)
1390 {
1391   /* Validate the RNA path pointer just in case. */
1392   const char *rna_path = fcu->rna_path;
1393   if (rna_path == NULL || rna_path[0] == '\0') {
1394     return;
1395   }
1396   /* Parse the RNA path to find the target property pointer. */
1397   RNAPathKey property_entry_key(id, rna_path, RNAPointerSource::ENTRY);
1398   if (RNA_pointer_is_null(&property_entry_key.ptr)) {
1399     /* TODO(sergey): This would only mean that driver is broken.
1400      * so we can't create relation anyway. However, we need to avoid
1401      * adding drivers which are known to be buggy to a dependency
1402      * graph, in order to save computational power. */
1403     return;
1404   }
1405   OperationKey driver_key(
1406       id, NodeType::PARAMETERS, OperationCode::DRIVER, rna_path, fcu->array_index);
1407   /* If the target of the driver is a Bone property, find the Armature data,
1408    * and then link the driver to all pose bone evaluation components that use
1409    * it. This is necessary to provide more granular dependencies specifically for
1410    * Bone objects, because the armature data doesn't have per-bone components,
1411    * and generic add_relation can only add one link. */
1412   ID *id_ptr = property_entry_key.ptr.owner_id;
1413   bool is_bone = id_ptr && property_entry_key.ptr.type == &RNA_Bone;
1414   /* If the Bone property is referenced via obj.pose.bones[].bone,
1415    * the RNA pointer refers to the Object ID, so skip to data. */
1416   if (is_bone && GS(id_ptr->name) == ID_OB) {
1417     id_ptr = (ID *)((Object *)id_ptr)->data;
1418   }
1419   if (is_bone && GS(id_ptr->name) == ID_AR) {
1420     /* Drivers on armature-level bone settings (i.e. bbone stuff),
1421      * which will affect the evaluation of corresponding pose bones. */
1422     Bone *bone = (Bone *)property_entry_key.ptr.data;
1423     if (bone != NULL) {
1424       /* Find objects which use this, and make their eval callbacks
1425        * depend on this. */
1426       for (IDNode *to_node : graph_->id_nodes) {
1427         if (GS(to_node->id_orig->name) == ID_OB) {
1428           Object *object = (Object *)to_node->id_orig;
1429           /* We only care about objects with pose data which use this. */
1430           if (object->data == id_ptr && object->pose != NULL) {
1431             bPoseChannel *pchan = BKE_pose_channel_find_name(object->pose, bone->name);
1432             if (pchan != NULL) {
1433               OperationKey bone_key(
1434                   &object->id, NodeType::BONE, pchan->name, OperationCode::BONE_LOCAL);
1435               add_relation(driver_key, bone_key, "Arm Bone -> Driver -> Bone");
1436             }
1437           }
1438         }
1439       }
1440       /* Make the driver depend on COW, similar to the generic case below. */
1441       if (id_ptr != id) {
1442         ComponentKey cow_key(id_ptr, NodeType::COPY_ON_WRITE);
1443         add_relation(cow_key, driver_key, "Driven CoW -> Driver", RELATION_CHECK_BEFORE_ADD);
1444       }
1445     }
1446     else {
1447       fprintf(stderr, "Couldn't find armature bone name for driver path - '%s'\n", rna_path);
1448     }
1449   }
1450   else {
1451     /* If it's not a Bone, handle the generic single dependency case. */
1452     add_relation(driver_key, property_entry_key, "Driver -> Driven Property");
1453     /* Similar to the case with f-curves, driver might drive a nested
1454      * data-block, which means driver execution should wait for that
1455      * data-block to be copied. */
1456     {
1457       PointerRNA id_ptr;
1458       PointerRNA ptr;
1459       RNA_id_pointer_create(id, &id_ptr);
1460       if (RNA_path_resolve_full(&id_ptr, fcu->rna_path, &ptr, NULL, NULL)) {
1461         if (id_ptr.owner_id != ptr.owner_id) {
1462           ComponentKey cow_key(ptr.owner_id, NodeType::COPY_ON_WRITE);
1463           add_relation(cow_key, driver_key, "Driven CoW -> Driver", RELATION_CHECK_BEFORE_ADD);
1464         }
1465       }
1466     }
1467     if (property_entry_key.prop != NULL && RNA_property_is_idprop(property_entry_key.prop)) {
1468       RNAPathKey property_exit_key(id, rna_path, RNAPointerSource::EXIT);
1469       OperationKey parameters_key(id, NodeType::PARAMETERS, OperationCode::PARAMETERS_EVAL);
1470       add_relation(property_exit_key, parameters_key, "Driven Property -> Properties");
1471     }
1472   }
1473 }
1474
1475 void DepsgraphRelationBuilder::build_driver_variables(ID *id, FCurve *fcu)
1476 {
1477   ChannelDriver *driver = fcu->driver;
1478   OperationKey driver_key(id,
1479                           NodeType::PARAMETERS,
1480                           OperationCode::DRIVER,
1481                           fcu->rna_path ? fcu->rna_path : "",
1482                           fcu->array_index);
1483   const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1484   const RNAPathKey self_key(id, rna_path, RNAPointerSource::ENTRY);
1485   LISTBASE_FOREACH (DriverVar *, dvar, &driver->variables) {
1486     /* Only used targets. */
1487     DRIVER_TARGETS_USED_LOOPER_BEGIN (dvar) {
1488       ID *target_id = dtar->id;
1489       if (target_id == NULL) {
1490         continue;
1491       }
1492       build_id(target_id);
1493       build_driver_id_property(target_id, dtar->rna_path);
1494       /* Look up the proxy - matches dtar_id_ensure_proxy_from during evaluation. */
1495       Object *object = NULL;
1496       if (GS(target_id->name) == ID_OB) {
1497         object = (Object *)target_id;
1498         if (object->proxy_from != NULL) {
1499           /* Redirect the target to the proxy, like in evaluation. */
1500           object = object->proxy_from;
1501           target_id = &object->id;
1502           /* Prepare the redirected target. */
1503           build_id(target_id);
1504           build_driver_id_property(target_id, dtar->rna_path);
1505         }
1506       }
1507       /* Special handling for directly-named bones. */
1508       if ((dtar->flag & DTAR_FLAG_STRUCT_REF) && (object && object->type == OB_ARMATURE) &&
1509           (dtar->pchan_name[0])) {
1510         bPoseChannel *target_pchan = BKE_pose_channel_find_name(object->pose, dtar->pchan_name);
1511         if (target_pchan == NULL) {
1512           continue;
1513         }
1514         OperationKey variable_key(
1515             target_id, NodeType::BONE, target_pchan->name, OperationCode::BONE_DONE);
1516         if (is_same_bone_dependency(variable_key, self_key)) {
1517           continue;
1518         }
1519         add_relation(variable_key, driver_key, "Bone Target -> Driver");
1520       }
1521       else if (dtar->flag & DTAR_FLAG_STRUCT_REF) {
1522         /* Get node associated with the object's transforms. */
1523         if (target_id == id) {
1524           /* Ignore input dependency if we're driving properties of
1525            * the same ID, otherwise we'll be ending up in a cyclic
1526            * dependency here. */
1527           continue;
1528         }
1529         OperationKey target_key(target_id, NodeType::TRANSFORM, OperationCode::TRANSFORM_FINAL);
1530         add_relation(target_key, driver_key, "Target -> Driver");
1531       }
1532       else if (dtar->rna_path != NULL && dtar->rna_path[0] != '\0') {
1533         RNAPathKey variable_exit_key(target_id, dtar->rna_path, RNAPointerSource::EXIT);
1534         if (RNA_pointer_is_null(&variable_exit_key.ptr)) {
1535           continue;
1536         }
1537         if (is_same_bone_dependency(variable_exit_key, self_key) ||
1538             is_same_nodetree_node_dependency(variable_exit_key, self_key)) {
1539           continue;
1540         }
1541         add_relation(variable_exit_key, driver_key, "RNA Target -> Driver");
1542       }
1543       else {
1544         /* If rna_path is NULL, and DTAR_FLAG_STRUCT_REF isn't set, this
1545          * is an incomplete target reference, so nothing to do here. */
1546       }
1547     }
1548     DRIVER_TARGETS_LOOPER_END;
1549   }
1550 }
1551
1552 void DepsgraphRelationBuilder::build_driver_id_property(ID *id, const char *rna_path)
1553 {
1554   if (id == NULL || rna_path == NULL) {
1555     return;
1556   }
1557   PointerRNA id_ptr, ptr;
1558   PropertyRNA *prop;
1559   int index;
1560   RNA_id_pointer_create(id, &id_ptr);
1561   if (!RNA_path_resolve_full(&id_ptr, rna_path, &ptr, &prop, &index)) {
1562     return;
1563   }
1564   if (prop == NULL) {
1565     return;
1566   }
1567   if (!RNA_property_is_idprop(prop)) {
1568     return;
1569   }
1570   const char *prop_identifier = RNA_property_identifier((PropertyRNA *)prop);
1571   OperationKey id_property_key(
1572       id, NodeType::PARAMETERS, OperationCode::ID_PROPERTY, prop_identifier);
1573   OperationKey parameters_exit_key(id, NodeType::PARAMETERS, OperationCode::PARAMETERS_EXIT);
1574   add_relation(
1575       id_property_key, parameters_exit_key, "ID Property -> Done", RELATION_CHECK_BEFORE_ADD);
1576 }
1577
1578 void DepsgraphRelationBuilder::build_parameters(ID *id)
1579 {
1580   OperationKey parameters_entry_key(id, NodeType::PARAMETERS, OperationCode::PARAMETERS_ENTRY);
1581   OperationKey parameters_eval_key(id, NodeType::PARAMETERS, OperationCode::PARAMETERS_EVAL);
1582   OperationKey parameters_exit_key(id, NodeType::PARAMETERS, OperationCode::PARAMETERS_EXIT);
1583   add_relation(parameters_entry_key, parameters_eval_key, "Entry -> Eval");
1584   add_relation(parameters_eval_key, parameters_exit_key, "Entry -> Exit");
1585 }
1586
1587 void DepsgraphRelationBuilder::build_world(World *world)
1588 {
1589   if (built_map_.checkIsBuiltAndTag(world)) {
1590     return;
1591   }
1592   /* animation */
1593   build_animdata(&world->id);
1594   build_parameters(&world->id);
1595   /* world's nodetree */
1596   if (world->nodetree != NULL) {
1597     build_nodetree(world->nodetree);
1598     OperationKey ntree_key(
1599         &world->nodetree->id, NodeType::SHADING, OperationCode::MATERIAL_UPDATE);
1600     OperationKey world_key(&world->id, NodeType::SHADING, OperationCode::WORLD_UPDATE);
1601     add_relation(ntree_key, world_key, "World's NTree");
1602     build_nested_nodetree(&world->id, world->nodetree);
1603   }
1604 }
1605
1606 void DepsgraphRelationBuilder::build_rigidbody(Scene *scene)
1607 {
1608   RigidBodyWorld *rbw = scene->rigidbody_world;
1609   OperationKey rb_init_key(&scene->id, NodeType::TRANSFORM, OperationCode::RIGIDBODY_REBUILD);
1610   OperationKey rb_simulate_key(&scene->id, NodeType::TRANSFORM, OperationCode::RIGIDBODY_SIM);
1611   /* Simulation depends on time. */
1612   TimeSourceKey time_src_key;
1613   add_relation(time_src_key, rb_init_key, "TimeSrc -> Rigidbody Init");
1614   /* Simulation should always be run after initialization. */
1615   /* NOTE: It is possible in theory to have dependency cycle which involves
1616    * this relation. We never want it to be killed. */
1617   add_relation(rb_init_key, rb_simulate_key, "Rigidbody [Init -> SimStep]", RELATION_FLAG_GODMODE);
1618   /* Effectors should be evaluated at the time simulation is being
1619    * initialized.
1620    * TODO(sergey): Verify that it indeed goes to initialization and not to a
1621    * simulation. */
1622   ListBase *effector_relations = build_effector_relations(graph_, rbw->effector_weights->group);
1623   LISTBASE_FOREACH (EffectorRelation *, effector_relation, effector_relations) {
1624     ComponentKey effector_transform_key(&effector_relation->ob->id, NodeType::TRANSFORM);
1625     add_relation(effector_transform_key, rb_init_key, "RigidBody Field");
1626     if (effector_relation->pd != NULL) {
1627       const short shape = effector_relation->pd->shape;
1628       if (ELEM(shape, PFIELD_SHAPE_SURFACE, PFIELD_SHAPE_POINTS)) {
1629         ComponentKey effector_geometry_key(&effector_relation->ob->id, NodeType::GEOMETRY);
1630         add_relation(effector_geometry_key, rb_init_key, "RigidBody Field");
1631       }
1632     }
1633   }
1634   /* Objects. */
1635   if (rbw->group != NULL) {
1636     build_collection(NULL, NULL, rbw->group);
1637     FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN (rbw->group, object) {
1638       if (object->type != OB_MESH) {
1639         continue;
1640       }
1641       OperationKey rb_transform_copy_key(
1642           &object->id, NodeType::TRANSFORM, OperationCode::RIGIDBODY_TRANSFORM_COPY);
1643       /* Rigid body synchronization depends on the actual simulation. */
1644       add_relation(rb_simulate_key, rb_transform_copy_key, "Rigidbody Sim Eval -> RBO Sync");
1645       /* Simulation uses object transformation after parenting and solving constraints. */
1646       OperationKey object_transform_simulation_init_key(
1647           &object->id, NodeType::TRANSFORM, OperationCode::TRANSFORM_SIMULATION_INIT);
1648       OperationKey object_transform_eval_key(
1649           &object->id, NodeType::TRANSFORM, OperationCode::TRANSFORM_EVAL);
1650       add_relation(object_transform_simulation_init_key,
1651                    rb_simulate_key,
1652                    "Object Transform -> Rigidbody Sim Eval");
1653       /* Geometry must be known to create the rigid body. RBO_MESH_BASE
1654        * uses the non-evaluated mesh, so then the evaluation is
1655        * unnecessary. */
1656       if (object->rigidbody_object != NULL &&
1657           object->rigidbody_object->mesh_source != RBO_MESH_BASE) {
1658         /* NOTE: We prefer this relation to be never killed, to avoid
1659          * access partially evaluated mesh from solver. */
1660         ComponentKey object_geometry_key(&object->id, NodeType::GEOMETRY);
1661         add_relation(object_geometry_key,
1662                      rb_simulate_key,
1663                      "Object Geom Eval -> Rigidbody Rebuild",
1664                      RELATION_FLAG_GODMODE);
1665       }
1666       /* Final transform is whetever solver gave to us. */
1667       OperationKey object_transform_final_key(
1668           &object->id, NodeType::TRANSFORM, OperationCode::TRANSFORM_FINAL);
1669       add_relation(
1670           rb_transform_copy_key, object_transform_final_key, "Rigidbody Sync -> Transform Final");
1671     }
1672     FOREACH_COLLECTION_OBJECT_RECURSIVE_END;
1673   }
1674   /* Constraints. */
1675   if (rbw->constraints != NULL) {
1676     FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN (rbw->constraints, object) {
1677       RigidBodyCon *rbc = object->rigidbody_constraint;
1678       if (rbc == NULL || rbc->ob1 == NULL || rbc->ob2 == NULL) {
1679         /* When either ob1 or ob2 is NULL, the constraint doesn't
1680          * work. */
1681         continue;
1682       }
1683       /* Make sure indirectly linked objects are fully built. */
1684       build_object(NULL, object);
1685       build_object(NULL, rbc->ob1);
1686       build_object(NULL, rbc->ob2);
1687       /* final result of the constraint object's transform controls how
1688        * the constraint affects the physics sim for these objects. */
1689       ComponentKey trans_key(&object->id, NodeType::TRANSFORM);
1690       OperationKey ob1_key(
1691           &rbc->ob1->id, NodeType::TRANSFORM, OperationCode::RIGIDBODY_TRANSFORM_COPY);
1692       OperationKey ob2_key(
1693           &rbc->ob2->id, NodeType::TRANSFORM, OperationCode::RIGIDBODY_TRANSFORM_COPY);
1694       /* Constrained-objects sync depends on the constraint-holder. */
1695       add_relation(trans_key, ob1_key, "RigidBodyConstraint -> RBC.Object_1");
1696       add_relation(trans_key, ob2_key, "RigidBodyConstraint -> RBC.Object_2");
1697       /* Ensure that sim depends on this constraint's transform. */
1698       add_relation(trans_key, rb_simulate_key, "RigidBodyConstraint Transform -> RB Simulation");
1699     }
1700     FOREACH_COLLECTION_OBJECT_RECURSIVE_END;
1701   }
1702 }
1703
1704 void DepsgraphRelationBuilder::build_particle_systems(Object *object)
1705 {
1706   TimeSourceKey time_src_key;
1707   OperationKey obdata_ubereval_key(&object->id, NodeType::GEOMETRY, OperationCode::GEOMETRY_EVAL);
1708   OperationKey eval_init_key(
1709       &object->id, NodeType::PARTICLE_SYSTEM, OperationCode::PARTICLE_SYSTEM_INIT);
1710   OperationKey eval_done_key(
1711       &object->id, NodeType::PARTICLE_SYSTEM, OperationCode::PARTICLE_SYSTEM_DONE);
1712   ComponentKey eval_key(&object->id, NodeType::PARTICLE_SYSTEM);
1713   if (BKE_ptcache_object_has(scene_, object, 0)) {
1714     ComponentKey point_cache_key(&object->id, NodeType::POINT_CACHE);
1715     add_relation(
1716         eval_key, point_cache_key, "Particle Point Cache", RELATION_FLAG_FLUSH_USER_EDIT_ONLY);
1717   }
1718   /* Particle systems. */
1719   LISTBASE_FOREACH (ParticleSystem *, psys, &object->particlesystem) {
1720     ParticleSettings *part = psys->part;
1721     /* Build particle settings relations.
1722      * NOTE: The call itself ensures settings are only build once. */
1723     build_particle_settings(part);
1724     /* This particle system. */
1725     OperationKey psys_key(
1726         &object->id, NodeType::PARTICLE_SYSTEM, OperationCode::PARTICLE_SYSTEM_EVAL, psys->name);
1727     /* Update particle system when settings changes. */
1728     OperationKey particle_settings_key(
1729         &part->id, NodeType::PARTICLE_SETTINGS, OperationCode::PARTICLE_SETTINGS_EVAL);
1730     add_relation(particle_settings_key, eval_init_key, "Particle Settings Change");
1731     add_relation(eval_init_key, psys_key, "Init -> PSys");
1732     add_relation(psys_key, eval_done_key, "PSys -> Done");
1733     /* TODO(sergey): Currently particle update is just a placeholder,
1734      * hook it to the ubereval node so particle system is getting updated
1735      * on playback. */
1736     add_relation(psys_key, obdata_ubereval_key, "PSys -> UberEval");
1737     /* Collisions. */
1738     if (part->type != PART_HAIR) {
1739       add_particle_collision_relations(
1740           psys_key, object, part->collision_group, "Particle Collision");
1741     }
1742     else if ((psys->flag & PSYS_HAIR_DYNAMICS) && psys->clmd != NULL &&
1743              psys->clmd->coll_parms != NULL) {
1744       add_particle_collision_relations(
1745           psys_key, object, psys->clmd->coll_parms->group, "Hair Collision");
1746     }
1747     /* Effectors. */
1748     add_particle_forcefield_relations(
1749         psys_key, object, psys, part->effector_weights, part->type == PART_HAIR, "Particle Field");
1750     /* Boids .*/
1751     if (part->boids != NULL) {
1752       LISTBASE_FOREACH (BoidState *, state, &part->boids->states) {
1753         LISTBASE_FOREACH (BoidRule *, rule, &state->rules) {
1754           Object *ruleob = NULL;
1755           if (rule->type == eBoidRuleType_Avoid) {
1756             ruleob = ((BoidRuleGoalAvoid *)rule)->ob;
1757           }
1758           else if (rule->type == eBoidRuleType_FollowLeader) {
1759             ruleob = ((BoidRuleFollowLeader *)rule)->ob;
1760           }
1761           if (ruleob != NULL) {
1762             ComponentKey ruleob_key(&ruleob->id, NodeType::TRANSFORM);
1763             add_relation(ruleob_key, psys_key, "Boid Rule");
1764           }
1765         }
1766       }
1767     }
1768     /* Keyed particle targets. */
1769     if (part->phystype == PART_PHYS_KEYED) {
1770       LISTBASE_FOREACH (ParticleTarget *, particle_target, &psys->targets) {
1771         if (particle_target->ob == NULL || particle_target->ob == object) {
1772           continue;
1773         }
1774         /* Make sure target object is pulled into the graph. */
1775         build_object(NULL, particle_target->ob);
1776         /* Use geometry component, since that's where particles are
1777          * actually evaluated. */
1778         ComponentKey target_key(&particle_target->ob->id, NodeType::GEOMETRY);
1779         add_relation(target_key, psys_key, "Keyed Target");
1780       }
1781     }
1782     /* Visualization. */
1783     switch (part->ren_as) {
1784       case PART_DRAW_OB:
1785         if (part->instance_object != NULL) {
1786           /* Make sure object's relations are all built.  */
1787           build_object(NULL, part->instance_object);
1788           /* Build relation for the particle visualization. */
1789           build_particle_system_visualization_object(object, psys, part->instance_object);
1790         }
1791         break;
1792       case PART_DRAW_GR:
1793         if (part->instance_collection != NULL) {
1794           build_collection(NULL, NULL, part->instance_collection);
1795           LISTBASE_FOREACH (CollectionObject *, go, &part->instance_collection->gobject) {
1796             build_particle_system_visualization_object(object, psys, go->ob);
1797           }
1798         }
1799         break;
1800     }
1801   }
1802   /* Particle depends on the object transform, so that channel is to be ready
1803    * first. */
1804   add_depends_on_transform_relation(&object->id, obdata_ubereval_key, "Particle Eval");
1805 }
1806
1807 void DepsgraphRelationBuilder::build_particle_settings(ParticleSettings *part)
1808 {
1809   if (built_map_.checkIsBuiltAndTag(part)) {
1810     return;
1811   }
1812   /* Animation data relations. */
1813   build_animdata(&part->id);
1814   build_parameters(&part->id);
1815   OperationKey particle_settings_init_key(
1816       &part->id, NodeType::PARTICLE_SETTINGS, OperationCode::PARTICLE_SETTINGS_INIT);
1817   OperationKey particle_settings_eval_key(
1818       &part->id, NodeType::PARTICLE_SETTINGS, OperationCode::PARTICLE_SETTINGS_EVAL);
1819   OperationKey particle_settings_reset_key(
1820       &part->id, NodeType::PARTICLE_SETTINGS, OperationCode::PARTICLE_SETTINGS_RESET);
1821   add_relation(
1822       particle_settings_init_key, particle_settings_eval_key, "Particle Settings Init Order");
1823   add_relation(particle_settings_reset_key, particle_settings_eval_key, "Particle Settings Reset");
1824   /* Texture slots. */
1825   for (int mtex_index = 0; mtex_index < MAX_MTEX; mtex_index++) {
1826     MTex *mtex = part->mtex[mtex_index];
1827     if (mtex == NULL || mtex->tex == NULL) {
1828       continue;
1829     }
1830     build_texture(mtex->tex);
1831     ComponentKey texture_key(&mtex->tex->id, NodeType::GENERIC_DATABLOCK);
1832     add_relation(texture_key,
1833                  particle_settings_reset_key,
1834                  "Particle Texture",
1835                  RELATION_FLAG_FLUSH_USER_EDIT_ONLY);
1836     /* TODO(sergey): Consider moving texture space handling to an own
1837      * function. */
1838     if (mtex->texco == TEXCO_OBJECT && mtex->object != NULL) {
1839       ComponentKey object_key(&mtex->object->id, NodeType::TRANSFORM);
1840       add_relation(object_key, particle_settings_eval_key, "Particle Texture Space");
1841     }
1842   }
1843   if (check_id_has_anim_component(&part->id)) {
1844     ComponentKey animation_key(&part->id, NodeType::ANIMATION);
1845     add_relation(animation_key, particle_settings_eval_key, "Particle Settings Animation");
1846   }
1847 }
1848
1849 void DepsgraphRelationBuilder::build_particle_system_visualization_object(Object *object,
1850                                                                           ParticleSystem *psys,
1851                                                                           Object *draw_object)
1852 {
1853   OperationKey psys_key(
1854       &object->id, NodeType::PARTICLE_SYSTEM, OperationCode::PARTICLE_SYSTEM_EVAL, psys->name);
1855   OperationKey obdata_ubereval_key(&object->id, NodeType::GEOMETRY, OperationCode::GEOMETRY_EVAL);
1856   ComponentKey dup_ob_key(&draw_object->id, NodeType::TRANSFORM);
1857   add_relation(dup_ob_key, psys_key, "Particle Object Visualization");
1858   if (draw_object->type == OB_MBALL) {
1859     ComponentKey dup_geometry_key(&draw_object->id, NodeType::GEOMETRY);
1860     add_relation(obdata_ubereval_key, dup_geometry_key, "Particle MBall Visualization");
1861   }
1862 }
1863
1864 /* Shapekeys */
1865 void DepsgraphRelationBuilder::build_shapekeys(Key *key)
1866 {
1867   if (built_map_.checkIsBuiltAndTag(key)) {
1868     return;
1869   }
1870   /* Attach animdata to geometry. */
1871   build_animdata(&key->id);
1872   build_parameters(&key->id);
1873   /* Connect all blocks properties to the final result evaluation. */
1874   ComponentKey geometry_key(&key->id, NodeType::GEOMETRY);
1875   OperationKey parameters_eval_key(&key->id, NodeType::PARAMETERS, OperationCode::PARAMETERS_EVAL);
1876   LISTBASE_FOREACH (KeyBlock *, key_block, &key->block) {
1877     OperationKey key_block_key(
1878         &key->id, NodeType::PARAMETERS, OperationCode::PARAMETERS_EVAL, key_block->name);
1879     add_relation(key_block_key, geometry_key, "Key Block Properties");
1880     add_relation(key_block_key, parameters_eval_key, "Key Block Properties");
1881   }
1882 }
1883
1884 /**
1885  * ObData Geometry Evaluation
1886  * ==========================
1887  *
1888  * The evaluation of geometry on objects is as follows:
1889  * - The actual evaluated of the derived geometry (e.g. Mesh, DispList)
1890  *   occurs in the Geometry component of the object which references this.
1891  *   This includes modifiers, and the temporary "ubereval" for geometry.
1892  *   Therefore, each user of a piece of shared geometry data ends up evaluating
1893  *   its own version of the stuff, complete with whatever modifiers it may use.
1894  *
1895  * - The data-blocks for the geometry data - "obdata" (e.g. ID_ME, ID_CU, ID_LT.)
1896  *   are used for
1897  *     1) calculating the bounding boxes of the geometry data,
1898  *     2) aggregating inward links from other objects (e.g. for text on curve)
1899  *        and also for the links coming from the shapekey data-blocks
1900  * - Animation/Drivers affecting the parameters of the geometry are made to
1901  *   trigger updates on the obdata geometry component, which then trigger
1902  *   downstream re-evaluation of the individual instances of this geometry. */
1903 void DepsgraphRelationBuilder::build_object_data_geometry(Object *object)
1904 {
1905   ID *obdata = (ID *)object->data;
1906   /* Init operation of object-level geometry evaluation. */
1907   OperationKey geom_init_key(&object->id, NodeType::GEOMETRY, OperationCode::GEOMETRY_EVAL_INIT);
1908   /* Get nodes for result of obdata's evaluation, and geometry evaluation
1909    * on object. */
1910   ComponentKey obdata_geom_key(obdata, NodeType::GEOMETRY);
1911   ComponentKey geom_key(&object->id, NodeType::GEOMETRY);
1912   /* Link components to each other. */
1913   add_relation(obdata_geom_key, geom_key, "Object Geometry Base Data");
1914   OperationKey obdata_ubereval_key(&object->id, NodeType::GEOMETRY, OperationCode::GEOMETRY_EVAL);
1915   /* Special case: modifiers evaluation queries scene for various things like
1916    * data mask to be used. We add relation here to ensure object is never
1917    * evaluated prior to Scene's CoW is ready. */
1918   OperationKey scene_key(&scene_->id, NodeType::PARAMETERS, OperationCode::SCENE_EVAL);
1919   Relation *rel = add_relation(scene_key, obdata_ubereval_key, "CoW Relation");
1920   rel->flag |= RELATION_FLAG_NO_FLUSH;
1921   /* Modifiers */
1922   if (object->modifiers.first != NULL) {
1923     ModifierUpdateDepsgraphContext ctx = {};
1924     ctx.scene = scene_;
1925     ctx.object = object;
1926     LISTBASE_FOREACH (ModifierData *, md, &object->modifiers) {
1927       const ModifierTypeInfo *mti = modifierType_getInfo((ModifierType)md->type);
1928       if (mti->updateDepsgraph) {
1929         DepsNodeHandle handle = create_node_handle(obdata_ubereval_key);
1930         ctx.node = reinterpret_cast<::DepsNodeHandle *>(&handle);
1931         mti->updateDepsgraph(md, &ctx);
1932       }
1933       if (BKE_object_modifier_use_time(object, md)) {
1934         TimeSourceKey time_src_key;
1935         add_relation(time_src_key, obdata_ubereval_key, "Time Source");
1936       }
1937     }
1938   }
1939   /* Grease Pencil Modifiers. */
1940   if (object->greasepencil_modifiers.first != NULL) {
1941     ModifierUpdateDepsgraphContext ctx = {};
1942     ctx.scene = scene_;
1943     ctx.object = object;
1944     LISTBASE_FOREACH (GpencilModifierData *, md, &object->greasepencil_modifiers) {
1945       const GpencilModifierTypeInfo *mti = BKE_gpencil_modifierType_getInfo(
1946           (GpencilModifierType)md->type);
1947       if (mti->updateDepsgraph) {
1948         DepsNodeHandle handle = create_node_handle(obdata_ubereval_key);
1949         ctx.node = reinterpret_cast<::DepsNodeHandle *>(&handle);
1950         mti->updateDepsgraph(md, &ctx);
1951       }
1952       if (BKE_object_modifier_gpencil_use_time(object, md)) {
1953         TimeSourceKey time_src_key;
1954         add_relation(time_src_key, obdata_ubereval_key, "Time Source");
1955       }
1956     }
1957   }
1958   /* Shader FX. */
1959   if (object->shader_fx.first != NULL) {
1960     ModifierUpdateDepsgraphContext ctx = {};
1961     ctx.scene = scene_;
1962     ctx.object = object;
1963     LISTBASE_FOREACH (ShaderFxData *, fx, &object->shader_fx) {
1964       const ShaderFxTypeInfo *fxi = BKE_shaderfxType_getInfo((ShaderFxType)fx->type);
1965       if (fxi->updateDepsgraph) {
1966         DepsNodeHandle handle = create_node_handle(obdata_ubereval_key);
1967         ctx.node = reinterpret_cast<::DepsNodeHandle *>(&handle);
1968         fxi->updateDepsgraph(fx, &ctx);
1969       }
1970       if (BKE_object_shaderfx_use_time(object, fx)) {
1971         TimeSourceKey time_src_key;
1972         add_relation(time_src_key, obdata_ubereval_key, "Time Source");
1973       }
1974     }
1975   }
1976   /* Materials. */
1977   build_materials(object->mat, object->totcol);
1978   /* Geometry collision. */
1979   if (ELEM(object->type, OB_MESH, OB_CURVE, OB_LATTICE)) {
1980     // add geometry collider relations
1981   }
1982   /* Make sure uber update is the last in the dependencies. */
1983   if (object->type != OB_ARMATURE) {
1984     /* Armatures does no longer require uber node. */
1985     OperationKey obdata_ubereval_key(
1986         &object->id, NodeType::GEOMETRY, OperationCode::GEOMETRY_EVAL);
1987     add_relation(geom_init_key, obdata_ubereval_key, "Object Geometry UberEval");
1988   }
1989   if (object->type == OB_MBALL) {
1990     Object *mom = BKE_mball_basis_find(scene_, object);
1991     ComponentKey mom_geom_key(&mom->id, NodeType::GEOMETRY);
1992     /* motherball - mom depends on children! */
1993     if (mom == object) {
1994       ComponentKey mom_transform_key(&mom->id, NodeType::TRANSFORM);
1995       add_relation(mom_transform_key, mom_geom_key, "Metaball Motherball Transform -> Geometry");
1996     }
1997     else {
1998       ComponentKey transform_key(&object->id, NodeType::TRANSFORM);
1999       add_relation(geom_key, mom_geom_key, "Metaball Motherball");
2000       add_relation(transform_key, mom_geom_key, "Metaball Motherball");
2001     }
2002   }
2003   /* NOTE: This is compatibility code to support particle systems
2004    *
2005    * for viewport being properly rendered in final render mode.
2006    * This relation is similar to what dag_object_time_update_flags()
2007    * was doing for mesh objects with particle system.
2008    *
2009    * Ideally we need to get rid of this relation. */
2010   if (object_particles_depends_on_time(object)) {
2011     TimeSourceKey time_key;
2012     OperationKey obdata_ubereval_key(
2013         &object->id, NodeType::GEOMETRY, OperationCode::GEOMETRY_EVAL);
2014     add_relation(time_key, obdata_ubereval_key, "Legacy particle time");
2015   }
2016   /* Object data data-block. */
2017   build_object_data_geometry_datablock((ID *)object->data);
2018   Key *key = BKE_key_from_object(object);
2019   if (key != NULL) {
2020     if (key->adt != NULL) {
2021       if (key->adt->action || key->adt->nla_tracks.first) {
2022         ComponentKey obdata_key((ID *)object->data, NodeType::GEOMETRY);
2023         ComponentKey adt_key(&key->id, NodeType::ANIMATION);
2024         add_relation(adt_key, obdata_key, "Animation");
2025       }
2026     }
2027   }
2028   /* Synchronization back to original object. */
2029   ComponentKey final_geometry_key(&object->id, NodeType::GEOMETRY);
2030   OperationKey synchronize_key(
2031       &object->id, NodeType::SYNCHRONIZATION, OperationCode::SYNCHRONIZE_TO_ORIGINAL);
2032   add_relation(final_geometry_key, synchronize_key, "Synchronize to Original");
2033   /* Batch cache. */
2034   OperationKey object_data_select_key(
2035       obdata, NodeType::BATCH_CACHE, OperationCode::GEOMETRY_SELECT_UPDATE);
2036   OperationKey object_select_key(
2037       &object->id, NodeType::BATCH_CACHE, OperationCode::GEOMETRY_SELECT_UPDATE);
2038   add_relation(object_data_select_key, object_select_key, "Data Selection -> Object Selection");
2039   add_relation(
2040       geom_key, object_select_key, "Object Geometry -> Select Update", RELATION_FLAG_NO_FLUSH);
2041 }
2042
2043 void DepsgraphRelationBuilder::build_object_data_geometry_datablock(ID *obdata)
2044 {
2045   if (built_map_.checkIsBuiltAndTag(obdata)) {
2046     return;
2047   }
2048   /* Animation. */
2049   build_animdata(obdata);
2050   build_parameters(obdata);
2051   /* ShapeKeys. */
2052   Key *key = BKE_key_from_id(obdata);
2053   if (key != NULL) {
2054     build_shapekeys(key);
2055   }
2056   /* Link object data evaluation node to exit operation. */
2057   OperationKey obdata_geom_eval_key(obdata, NodeType::GEOMETRY, OperationCode::GEOMETRY_EVAL);
2058   OperationKey obdata_geom_done_key(obdata, NodeType::GEOMETRY, OperationCode::GEOMETRY_EVAL_DONE);
2059   add_relation(obdata_geom_eval_key, obdata_geom_done_key, "ObData Geom Eval Done");
2060   /* Type-specific links. */
2061   const ID_Type id_type = GS(obdata->name);
2062   switch (id_type) {
2063     case ID_ME:
2064       break;
2065     case ID_MB:
2066       break;
2067     case ID_CU: {
2068       Curve *cu = (Curve *)obdata;
2069       if (cu->bevobj != NULL) {
2070         ComponentKey bevob_geom_key(&cu->bevobj->id, NodeType::GEOMETRY);
2071         add_relation(bevob_geom_key, obdata_geom_eval_key, "Curve Bevel Geometry");
2072         ComponentKey bevob_key(&cu->bevobj->id, NodeType::TRANSFORM);
2073         add_relation(bevob_key, obdata_geom_eval_key, "Curve Bevel Transform");
2074         build_object(NULL, cu->bevobj);
2075       }
2076       if (cu->taperobj != NULL) {
2077         ComponentKey taperob_key(&cu->taperobj->id, NodeType::GEOMETRY);
2078         add_relation(taperob_key, obdata_geom_eval_key, "Curve Taper");
2079         build_object(NULL, cu->taperobj);
2080       }
2081       if (cu->textoncurve != NULL) {
2082         ComponentKey textoncurve_key(&cu->textoncurve->id, NodeType::GEOMETRY);
2083         add_relation(textoncurve_key, obdata_geom_eval_key, "Text on Curve");
2084         build_object(NULL, cu->textoncurve);
2085       }
2086       break;
2087     }
2088     case ID_LT:
2089       break;
2090     case ID_GD: /* Grease Pencil */
2091     {
2092       bGPdata *gpd = (bGPdata *)obdata;
2093
2094       /* Geometry cache needs to be recalculated on frame change
2095        * (e.g. to fix crashes after scrubbing the timeline when
2096        * onion skinning is enabled, since the ghosts need to be
2097        * re-added to the cache once scrubbing ends). */
2098       TimeSourceKey time_key;
2099       ComponentKey geometry_key(obdata, NodeType::GEOMETRY);
2100       add_relation(time_key, geometry_key, "GP Frame Change");
2101
2102       /* Geometry cache also needs to be recalculated when Material
2103        * settings change (e.g. when fill.opacity changes on/off,
2104        * we need to rebuild the bGPDstroke->triangles caches). */
2105       for (int i = 0; i < gpd->totcol; i++) {
2106         Material *ma = gpd->mat[i];
2107         if ((ma != NULL) && (ma->gp_style != NULL)) {
2108           OperationKey material_key(&ma->id, NodeType::SHADING, OperationCode::MATERIAL_UPDATE);
2109           add_relation(material_key, geometry_key, "Material -> GP Data");
2110         }
2111       }
2112       break;
2113     }
2114     default:
2115       BLI_assert(!"Should not happen");
2116       break;
2117   }
2118 }
2119
2120 void DepsgraphRelationBuilder::build_armature(bArmature *armature)
2121 {
2122   if (built_map_.checkIsBuiltAndTag(armature)) {
2123     return;
2124   }
2125   build_animdata(&armature->id);
2126   build_parameters(&armature->id);
2127 }
2128
2129 void DepsgraphRelationBuilder::build_camera(Camera *camera)
2130 {
2131   if (built_map_.checkIsBuiltAndTag(camera)) {
2132     return;
2133   }
2134   build_animdata(&camera->id);
2135   build_parameters(&camera->id);
2136   if (camera->dof.focus_object != NULL) {
2137     build_object(NULL, camera->dof.focus_object);
2138     ComponentKey camera_parameters_key(&camera->id, NodeType::PARAMETERS);
2139     ComponentKey dof_ob_key(&camera->dof.focus_object->id, NodeType::TRANSFORM);
2140     add_relation(dof_ob_key, camera_parameters_key, "Camera DOF");
2141   }
2142 }
2143
2144 /* Lights */
2145 void DepsgraphRelationBuilder::build_light(Light *lamp)
2146 {
2147   if (built_map_.checkIsBuiltAndTag(lamp)) {
2148     return;
2149   }
2150   build_animdata(&lamp->id);
2151   build_parameters(&lamp->id);
2152   /* light's nodetree */
2153   if (lamp->nodetree != NULL) {
2154     build_nodetree(lamp->nodetree);
2155     ComponentKey lamp_parameters_key(&lamp->id, NodeType::PARAMETERS);
2156     ComponentKey nodetree_key(&lamp->nodetree->id, NodeType::SHADING);
2157     add_relation(nodetree_key, lamp_parameters_key, "NTree->Light Parameters");
2158     build_nested_nodetree(&lamp->id, lamp->nodetree);
2159   }
2160 }
2161
2162 void DepsgraphRelationBuilder::build_nodetree(bNodeTree *ntree)
2163 {
2164   if (ntree == NULL) {
2165     return;
2166   }
2167   if (built_map_.checkIsBuiltAndTag(ntree)) {
2168     return;
2169   }
2170   build_animdata(&ntree->id);
2171   build_parameters(&ntree->id);
2172   ComponentKey shading_key(&ntree->id, NodeType::SHADING);
2173   /* nodetree's nodes... */
2174   LISTBASE_FOREACH (bNode *, bnode, &ntree->nodes) {
2175     ID *id = bnode->id;
2176     if (id == NULL) {
2177       continue;
2178     }
2179     ID_Type id_type = GS(id->name);
2180     if (id_type == ID_MA) {
2181       build_material((Material *)bnode->id);
2182       ComponentKey material_key(id, NodeType::SHADING);
2183       add_relation(material_key, shading_key, "Material -> Node");
2184     }
2185     else if (id_type == ID_TE) {
2186       build_texture((Tex *)bnode->id);
2187       ComponentKey texture_key(id, NodeType::GENERIC_DATABLOCK);
2188       add_relation(texture_key, shading_key, "Texture -> Node");
2189     }
2190     else if (id_type == ID_IM) {
2191       build_image((Image *)bnode->id);
2192       ComponentKey image_key(id, NodeType::GENERIC_DATABLOCK);
2193       add_relation(image_key, shading_key, "Image -> Node");
2194     }
2195     else if (id_type == ID_OB) {
2196       build_object(NULL, (Object *)id);
2197       ComponentKey object_transform_key(id, NodeType::TRANSFORM);
2198       add_relation(object_transform_key, shading_key, "Object Transform -> Node");
2199       if (object_have_geometry_component(reinterpret_cast<Object *>(id))) {
2200         ComponentKey object_geometry_key(id, NodeType::GEOMETRY);
2201         add_relation(object_geometry_key, shading_key, "Object Geometry -> Node");
2202       }
2203     }
2204     else if (id_type == ID_SCE) {
2205       Scene *node_scene = (Scene *)id;
2206       build_scene_parameters(node_scene);
2207       /* Camera is used by defocus node.
2208        *
2209        * On the one hand it's annoying to always pull it in, but on another hand it's also annoying
2210        * to have hardcoded node-type exception here. */
2211       if (node_scene->camera != NULL) {
2212         build_object(NULL, node_scene->camera);
2213       }
2214     }
2215     else if (id_type == ID_TXT) {
2216       /* Ignore script nodes. */
2217     }
2218     else if (id_type == ID_MSK) {
2219       build_mask((Mask *)id);
2220       OperationKey mask_key(id, NodeType::PARAMETERS, OperationCode::MASK_EVAL);
2221       add_relation(mask_key, shading_key, "Mask -> Node");
2222     }
2223     else if (id_type == ID_MC) {
2224       build_movieclip((MovieClip *)id);
2225       OperationKey clip_key(id, NodeType::PARAMETERS, OperationCode::MOVIECLIP_EVAL);
2226       add_relation(clip_key, shading_key, "Clip -> Node");
2227     }
2228     else if (ELEM(bnode->type, NODE_GROUP, NODE_CUSTOM_GROUP)) {
2229       bNodeTree *group_ntree = (bNodeTree *)id;
2230       build_nodetree(group_ntree);
2231       ComponentKey group_shading_key(&group_ntree->id, NodeType::SHADING);
2232       add_relation(group_shading_key, shading_key, "Group Node");
2233     }
2234     else {
2235       BLI_assert(!"Unknown ID type used for node");
2236     }
2237   }
2238
2239   OperationKey shading_update_key(&ntree->id, NodeType::SHADING, OperationCode::MATERIAL_UPDATE);
2240   OperationKey shading_parameters_key(
2241       &ntree->id, NodeType::SHADING_PARAMETERS, OperationCode::MATERIAL_UPDATE);
2242   add_relation(shading_parameters_key, shading_update_key, "NTree Shading Parameters");
2243
2244   if (check_id_has_anim_component(&ntree->id)) {
2245     ComponentKey animation_key(&ntree->id, NodeType::ANIMATION);
2246     add_relation(animation_key, shading_parameters_key, "NTree Shading Parameters");
2247   }
2248   ComponentKey parameters_key(&ntree->id, NodeType::PARAMETERS);
2249   add_relation(parameters_key, shading_parameters_key, "NTree Shading Parameters");
2250 }
2251
2252 /* Recursively build graph for material */
2253 void DepsgraphRelationBuilder::build_material(Material *material)
2254 {
2255   if (built_map_.checkIsBuiltAndTag(material)) {
2256     return;
2257   }
2258   /* animation */
2259   build_animdata(&material->id);
2260   build_parameters(&material->id);
2261   /* material's nodetree */
2262   if (material->nodetree != NULL) {
2263     build_nodetree(material->nodetree);
2264     OperationKey ntree_key(
2265         &material->nodetree->id, NodeType::SHADING, OperationCode::MATERIAL_UPDATE);
2266     OperationKey material_key(&material->id, NodeType::SHADING, OperationCode::MATERIAL_UPDATE);
2267     add_relation(ntree_key, material_key, "Material's NTree");
2268     build_nested_nodetree(&material->id, material->nodetree);
2269   }
2270 }
2271
2272 void DepsgraphRelationBuilder::build_materials(Material **materials, int num_materials)
2273 {
2274   for (int i = 0; i < num_materials; i++) {
2275     if (materials[i] == NULL) {
2276       continue;
2277     }
2278     build_material(materials[i]);
2279   }
2280 }
2281
2282 /* Recursively build graph for texture */
2283 void DepsgraphRelationBuilder::build_texture(Tex *texture)
2284 {
2285   if (built_map_.checkIsBuiltAndTag(texture)) {
2286     return;
2287   }
2288   /* texture itself */
2289   build_animdata(&texture->id);
2290   build_parameters(&texture->id);
2291   /* texture's nodetree */
2292   build_nodetree(texture->nodetree);
2293   /* Special cases for different IDs which texture uses. */
2294   if (texture->type == TEX_IMAGE) {
2295     if (texture->ima != NULL) {
2296       build_image(texture->ima);
2297     }
2298   }
2299   build_nested_nodetree(&texture->id, texture->nodetree);
2300   if (check_id_has_anim_component(&texture->id)) {
2301     ComponentKey animation_key(&texture->id, NodeType::ANIMATION);
2302     ComponentKey datablock_key(&texture->id, NodeType::GENERIC_DATABLOCK);
2303     add_relation(animation_key, datablock_key, "Datablock Animation");
2304   }
2305 }
2306
2307 void DepsgraphRelationBuilder::build_image(Image *image)
2308 {
2309   if (built_map_.checkIsBuiltAndTag(image)) {
2310     return;
2311   }
2312   build_parameters(&image->id);
2313 }
2314
2315 void DepsgraphRelationBuilder::build_gpencil(bGPdata *gpd)
2316 {
2317   if (built_map_.checkIsBuiltAndTag(gpd)) {
2318     return;
2319   }
2320   /* animation */
2321   build_animdata(&gpd->id);
2322   build_parameters(&gpd->id);
2323
2324   // TODO: parent object (when that feature is implemented)
2325 }
2326
2327 void DepsgraphRelationBuilder::build_cachefile(CacheFile *cache_file)
2328 {
2329   if (built_map_.checkIsBuiltAndTag(cache_file)) {
2330     return;
2331   }
2332   /* Animation. */
2333   build_animdata(&cache_file->id);
2334   build_parameters(&cache_file->id);
2335   if (check_id_has_anim_component(&cache_file->id)) {
2336     ComponentKey animation_key(&cache_file->id, NodeType::ANIMATION);
2337     ComponentKey datablock_key(&cache_file->id, NodeType::CACHE);
2338     add_relation(animation_key, datablock_key, "Datablock Animation");
2339   }
2340
2341   /* Cache file updates */
2342   if (cache_file->is_sequence) {
2343     OperationKey cache_update_key(
2344         &cache_file->id, NodeType::CACHE, OperationCode::FILE_CACHE_UPDATE);
2345     TimeSourceKey time_src_key;
2346     add_relation(time_src_key, cache_update_key, "TimeSrc -> Cache File Eval");
2347   }
2348 }
2349
2350 void DepsgraphRelationBuilder::build_mask(Mask *mask)
2351 {
2352   if (built_map_.checkIsBuiltAndTag(mask)) {
2353     return;
2354   }
2355   ID *mask_id = &mask->id;
2356   /* F-Curve animation. */
2357   build_animdata(mask_id);
2358   build_parameters(mask_id);
2359   /* Own mask animation. */
2360   OperationKey mask_animation_key(mask_id, NodeType::ANIMATION, OperationCode::MASK_ANIMATION);
2361   TimeSourceKey time_src_key;
2362   add_relation(time_src_key, mask_animation_key, "TimeSrc -> Mask Animation");
2363   /* Final mask evaluation. */
2364   OperationKey mask_eval_key(mask_id, NodeType::PARAMETERS, OperationCode::MASK_EVAL);
2365   add_relation(mask_animation_key, mask_eval_key, "Mask Animation -> Mask Eval");
2366   /* Build parents. */
2367   LISTBASE_FOREACH (MaskLayer *, mask_layer, &mask->masklayers) {
2368     LISTBASE_FOREACH (MaskSpline *, spline, &mask_layer->splines) {
2369       for (int i = 0; i < spline->tot_point; i++) {
2370         MaskSplinePoint *point = &spline->points[i];
2371         MaskParent *parent = &point->parent;
2372         if (parent == NULL || parent->id == NULL) {
2373           continue;
2374         }
2375         build_id(parent->id);
2376         if (parent->id_type == ID_MC) {
2377           OperationKey movieclip_eval_key(
2378               parent->id, NodeType::PARAMETERS, OperationCode::MOVIECLIP_EVAL);
2379           add_relation(movieclip_eval_key, mask_eval_key, "Movie Clip -> Mask Eval");
2380         }
2381       }
2382     }
2383   }
2384 }
2385
2386 void DepsgraphRelationBuilder::build_movieclip(MovieClip *clip)
2387 {
2388   if (built_map_.checkIsBuiltAndTag(clip)) {
2389     return;
2390   }
2391   /* Animation. */
2392   build_animdata(&clip->id);
2393   build_parameters(&clip->id);
2394 }
2395
2396 void DepsgraphRelationBuilder::build_lightprobe(LightProbe *probe)
2397 {
2398   if (built_map_.checkIsBuiltAndTag(probe)) {
2399     return;
2400   }
2401   build_animdata(&probe->id);
2402   build_parameters(&probe->id);
2403 }
2404
2405 void DepsgraphRelationBuilder::build_speaker(Speaker *speaker)
2406 {
2407   if (built_map_.checkIsBuiltAndTag(speaker)) {
2408     return;
2409   }
2410   build_animdata(&speaker->id);
2411   build_parameters(&speaker->id);
2412   if (speaker->sound != NULL) {
2413     build_sound(speaker->sound);
2414     ComponentKey speaker_key(&speaker->id, NodeType::AUDIO);
2415     ComponentKey sound_key(&speaker->sound->id, NodeType::AUDIO);
2416     add_relation(sound_key, speaker_key, "Sound -> Speaker");
2417   }
2418 }
2419
2420 void DepsgraphRelationBuilder::build_sound(bSound *sound)
2421 {
2422   if (built_map_.checkIsBuiltAndTag(sound)) {
2423     return;
2424   }
2425   build_animdata(&sound->id);
2426   build_parameters(&sound->id);
2427 }
2428
2429 void DepsgraphRelationBuilder::build_scene_sequencer(Scene *scene)
2430 {
2431   if (scene->ed == NULL) {
2432     return;
2433   }
2434   build_scene_audio(scene);
2435   ComponentKey scene_audio_key(&scene->id, NodeType::AUDIO);
2436   /* Make sure dependencies from sequences data goes to the sequencer evaluation. */
2437   ComponentKey sequencer_key(&scene->id, NodeType::SEQUENCER);
2438   Sequence *seq;
2439   bool has_audio_strips = false;
2440   SEQ_BEGIN (scene->ed, seq) {
2441     if (seq->sound != NULL) {
2442       build_sound(seq->sound);
2443       ComponentKey sound_key(&seq->sound->id, NodeType::AUDIO);
2444       add_relation(sound_key, sequencer_key, "Sound -> Sequencer");
2445       has_audio_strips = true;
2446     }
2447     if (seq->scene != NULL) {
2448       build_scene_parameters(seq->scene);
2449       /* This is to support 3D audio. */
2450       has_audio_strips = true;
2451     }
2452     if (seq->type == SEQ_TYPE_SCENE && seq->scene != NULL) {
2453       if (seq->flag & SEQ_SCENE_STRIPS) {
2454         build_scene_sequencer(seq->scene);
2455         ComponentKey sequence_scene_audio_key(&seq->scene->id, NodeType::AUDIO);
2456         add_relation(sequence_scene_audio_key, sequencer_key, "Sequence Scene Audio -> Sequencer");
2457         ComponentKey sequence_scene_key(&seq->scene->id, NodeType::SEQUENCER);
2458         add_relation(sequence_scene_key, sequencer_key, "Sequence Scene -> Sequencer");
2459       }
2460       ViewLayer *sequence_view_layer = BKE_view_layer_default_render(seq->scene);
2461       build_scene_speakers(seq->scene, sequence_view_layer);
2462     }
2463     /* TODO(sergey): Movie clip, camera, mask. */
2464   }
2465   SEQ_END;
2466   if (has_audio_strips) {
2467     add_relation(sequencer_key, scene_audio_key, "Sequencer -> Audio");
2468   }
2469 }
2470
2471 void DepsgraphRelationBuilder::build_scene_audio(Scene * /*scene*/)
2472 {
2473 }
2474
2475 void DepsgraphRelationBuilder::build_scene_speakers(Scene * /*scene*/, ViewLayer *view_layer)
2476 {
2477   LISTBASE_FOREACH (Base *, base, &view_layer->object_bases) {
2478     Object *object = base->object;
2479     if (object->type != OB_SPEAKER || !need_pull_base_into_graph(base)) {
2480       continue;
2481     }
2482     build_object(NULL, base->object);
2483   }
2484 }
2485
2486 void DepsgraphRelationBuilder::build_copy_on_write_relations()
2487 {
2488   for (IDNode *id_node : graph_->id_nodes) {
2489     build_copy_on_write_relations(id_node);
2490   }
2491 }
2492
2493 /* Nested datablocks (node trees, shape keys) requires special relation to
2494  * ensure owner's datablock remapping happens after node tree itself is ready.
2495  *
2496  * This is similar to what happens in ntree_hack_remap_pointers().
2497  */
2498 void DepsgraphRelationBuilder::build_nested_datablock(ID *owner, ID *id)
2499 {
2500   OperationKey owner_copy_on_write_key(
2501       owner, NodeType::COPY_ON_WRITE, OperationCode::COPY_ON_WRITE);
2502   OperationKey id_copy_on_write_key(id, NodeType::COPY_ON_WRITE, OperationCode::COPY_ON_WRITE);
2503   add_relation(id_copy_on_write_key, owner_copy_on_write_key, "Eval Order");
2504 }
2505
2506 void DepsgraphRelationBuilder::build_nested_nodetree(ID *owner, bNodeTree *ntree)
2507 {
2508   if (ntree == NULL) {
2509     return;
2510   }
2511   build_nested_datablock(owner, &ntree->id);
2512 }
2513
2514 void DepsgraphRelationBuilder::build_nested_shapekey(ID *owner, Key *key)
2515 {
2516   if (key == NULL) {
2517     return;
2518   }
2519   build_nested_datablock(owner, &key->id);
2520 }
2521
2522 void DepsgraphRelationBuilder::build_copy_on_write_relations(IDNode *id_node)
2523 {
2524   ID *id_orig = id_node->id_orig;
2525   const ID_Type id_type = GS(id_orig->name);
2526   TimeSourceKey time_source_key;
2527   OperationKey copy_on_write_key(id_orig, NodeType::COPY_ON_WRITE, OperationCode::COPY_ON_WRITE);
2528   /* XXX: This is a quick hack to make Alt-A to work. */
2529   // add_relation(time_source_key, copy_on_write_key, "Fluxgate capacitor hack");
2530   /* Resat of code is using rather low level trickery, so need to get some
2531    * explicit pointers. */
2532   Node *node_cow = find_node(copy_on_write_key);
2533   OperationNode *op_cow = node_cow->get_exit_operation();
2534   /* Plug any other components to this one. */
2535   GHASH_FOREACH_BEGIN (ComponentNode *, comp_node, id_node->components) {
2536     if (comp_node->type == NodeType::COPY_ON_WRITE) {
2537       /* Copy-on-write component never depends on itself. */
2538       continue;
2539     }
2540     if (!comp_node->depends_on_cow()) {
2541       /* Component explicitly requests to not add relation. */
2542       continue;
2543     }
2544     int rel_flag = (RELATION_FLAG_NO_FLUSH | RELATION_FLAG_GODMODE);
2545     if ((id_type == ID_ME && comp_node->type == NodeType::GEOMETRY) ||
2546         (id_type == ID_CF && comp_node->type == NodeType::CACHE)) {
2547       rel_flag &= ~RELATION_FLAG_NO_FLUSH;
2548     }
2549     /* TODO(sergey): Needs better solution for this. */
2550     if (id_type == ID_SO) {
2551       rel_flag &= ~RELATION_FLAG_NO_FLUSH;
2552     }
2553     /* Notes on exceptions:
2554      * - Parameters component is where drivers are living. Changing any
2555      *   of the (custom) properties in the original datablock (even the
2556      *   ones which do not imply other component update) need to make
2557      *   sure drivers are properly updated.
2558      *   This way, for example, changing ID property will properly poke
2559      *   all drivers to be updated.
2560      *
2561      * - View layers have cached array of bases in them, which is not
2562      *   copied by copy-on-write, and not preserved. PROBABLY it is better
2563      *   to preserve that cache in copy-on-write, but for the time being
2564      *   we allow flush to layer collections component which will ensure
2565      *   that cached array of bases exists and is up-to-date. */
2566     if (comp_node->type == NodeType::PARAMETERS ||
2567         comp_node->type == NodeType::LAYER_COLLECTIONS) {
2568       rel_flag &= ~RELATION_FLAG_NO_FLUSH;
2569     }
2570     /* All entry operations of each component should wait for a proper
2571      * copy of ID. */
2572     OperationNode *op_entry = comp_node->get_entry_operation();
2573     if (op_entry != NULL) {
2574       Relation *rel = graph_->add_new_relation(op_cow, op_entry, "CoW Dependency");
2575       rel->flag |= rel_flag;
2576     }
2577     /* All dangling operations should also be executed after copy-on-write. */
2578     GHASH_FOREACH_BEGIN (OperationNode *, op_node, comp_node->operations_map) {
2579       if (op_node == op_entry) {
2580         continue;
2581       }
2582       if (op_node->inlinks.size() == 0) {
2583         Relation *rel = graph_->add_new_relation(op_cow, op_node, "CoW Dependency");
2584         rel->flag |= rel_flag;
2585       }
2586       else {
2587         bool has_same_comp_dependency = false;
2588         for (Relation *rel_current : op_node->inlinks) {
2589           if (rel_current->from->type != NodeType::OPERATION) {
2590             continue;
2591           }
2592           OperationNode *op_node_from = (OperationNode *)rel_current->from;
2593           if (op_node_from->owner == op_node->owner) {
2594             has_same_comp_dependency = true;
2595             break;
2596           }
2597         }
2598         if (!has_same_comp_dependency) {
2599           Relation *rel = graph_->add_new_relation(op_cow, op_node, "CoW Dependency");
2600           rel->flag |= rel_flag;
2601         }
2602       }
2603     }
2604     GHASH_FOREACH_END();
2605     /* NOTE: We currently ignore implicit relations to an external
2606      * data-blocks for copy-on-write operations. This means, for example,
2607      * copy-on-write component of Object will not wait for copy-on-write
2608      * component of it's Mesh. This is because pointers are all known
2609      * already so remapping will happen all correct. And then If some object
2610      * evaluation step needs geometry, it will have transitive dependency
2611      * to Mesh copy-on-write already. */
2612   }
2613   GHASH_FOREACH_END();
2614   /* TODO(sergey): This solves crash for now, but causes too many
2615    * updates potentially. */
2616   if (GS(id_orig->name) == ID_OB) {
2617     Object *object = (Object *)id_orig;
2618     ID *object_data_id = (ID *)object->data;
2619     if (object_data_id != NULL) {
2620       if (deg_copy_on_write_is_needed(object_data_id)) {
2621         OperationKey data_copy_on_write_key(
2622             object_data_id, NodeType::COPY_ON_WRITE, OperationCode::COPY_ON_WRITE);
2623         add_relation(
2624             data_copy_on_write_key, copy_on_write_key, "Eval Order", RELATION_FLAG_GODMODE);
2625       }
2626     }
2627     else {
2628       BLI_assert(object->type == OB_EMPTY);
2629     }
2630   }
2631 }
2632
2633 /* **** ID traversal callbacks functions **** */
2634
2635 void DepsgraphRelationBuilder::modifier_walk(void *user_data,
2636                                              struct Object * /*object*/,
2637                                              struct ID **idpoin,
2638                                              int /*cb_flag*/)
2639 {
2640   BuilderWalkUserData *data = (BuilderWalkUserData *)user_data;
2641   ID *id = *idpoin;
2642   if (id == NULL) {
2643     return;
2644   }
2645   data->builder->build_id(id);
2646 }
2647
2648 void DepsgraphRelationBuilder::constraint_walk(bConstraint * /*con*/,
2649                                                ID **idpoin,
2650                                                bool /*is_reference*/,
2651                                                void *user_data)
2652 {
2653   BuilderWalkUserData *data = (BuilderWalkUserData *)user_data;
2654   ID *id = *idpoin;
2655   if (id == NULL) {
2656     return;
2657   }
2658   data->builder->build_id(id);
2659 }
2660
2661 }  // namespace DEG