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