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