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