Merge branch 'master' into blender2.8
[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_constraint_types.h"
51 #include "DNA_curve_types.h"
52 #include "DNA_effect_types.h"
53 #include "DNA_gpencil_types.h"
54 #include "DNA_group_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_texture_types.h"
69 #include "DNA_world_types.h"
70 #include "DNA_object_force_types.h"
71
72 #include "BKE_action.h"
73 #include "BKE_armature.h"
74 #include "BKE_animsys.h"
75 #include "BKE_constraint.h"
76 #include "BKE_curve.h"
77 #include "BKE_effect.h"
78 #include "BKE_collision.h"
79 #include "BKE_fcurve.h"
80 #include "BKE_group.h"
81 #include "BKE_key.h"
82 #include "BKE_library.h"
83 #include "BKE_main.h"
84 #include "BKE_material.h"
85 #include "BKE_mball.h"
86 #include "BKE_modifier.h"
87 #include "BKE_node.h"
88 #include "BKE_object.h"
89 #include "BKE_particle.h"
90 #include "BKE_rigidbody.h"
91 #include "BKE_sound.h"
92 #include "BKE_tracking.h"
93 #include "BKE_world.h"
94
95 #include "RNA_access.h"
96 #include "RNA_types.h"
97 } /* extern "C" */
98
99 #include "DEG_depsgraph.h"
100 #include "DEG_depsgraph_build.h"
101
102 #include "intern/builder/deg_builder.h"
103 #include "intern/builder/deg_builder_pchanmap.h"
104
105 #include "intern/nodes/deg_node.h"
106 #include "intern/nodes/deg_node_component.h"
107 #include "intern/nodes/deg_node_id.h"
108 #include "intern/nodes/deg_node_operation.h"
109 #include "intern/nodes/deg_node_time.h"
110
111 #include "intern/depsgraph_intern.h"
112 #include "intern/depsgraph_types.h"
113
114 #include "util/deg_util_foreach.h"
115
116 namespace DEG {
117
118 namespace {
119
120 struct BuilderWalkUserData {
121         DepsgraphRelationBuilder *builder;
122 };
123
124 void modifier_walk(void *user_data,
125                    struct Object * /*object*/,
126                    struct ID **idpoin,
127                    int /*cb_flag*/)
128 {
129         BuilderWalkUserData *data = (BuilderWalkUserData *)user_data;
130         ID *id = *idpoin;
131         if (id == NULL) {
132                 return;
133         }
134         switch (GS(id->name)) {
135                 case ID_OB:
136                         data->builder->build_object(NULL, (Object *)id);
137                         break;
138                 case ID_TE:
139                         data->builder->build_texture((Tex *)id);
140                         break;
141                 default:
142                         /* pass */
143                         break;
144         }
145 }
146
147 void constraint_walk(bConstraint * /*con*/,
148                      ID **idpoin,
149                      bool /*is_reference*/,
150                      void *user_data)
151 {
152         BuilderWalkUserData *data = (BuilderWalkUserData *)user_data;
153         if (*idpoin) {
154                 ID *id = *idpoin;
155                 if (GS(id->name) == ID_OB) {
156                         data->builder->build_object(NULL, (Object *)id);
157                 }
158         }
159 }
160
161 }  /* namespace */
162
163 /* ***************** */
164 /* Relations Builder */
165
166 /* TODO(sergey): This is somewhat weak, but we don't want neither false-positive
167  * time dependencies nor special exceptions in the depsgraph evaluation.
168  */
169 static bool python_driver_depends_on_time(ChannelDriver *driver)
170 {
171         if (driver->expression[0] == '\0') {
172                 /* Empty expression depends on nothing. */
173                 return false;
174         }
175         if (strchr(driver->expression, '(') != NULL) {
176                 /* Function calls are considered dependent on a time. */
177                 return true;
178         }
179         if (strstr(driver->expression, "frame") != NULL) {
180                 /* Variable `frame` depends on time. */
181                 /* TODO(sergey): This is a bit weak, but not sure about better way of
182                  * handling this.
183                  */
184                 return true;
185         }
186         /* Possible indirect time relation s should be handled via variable
187          * targets.
188          */
189         return false;
190 }
191
192 static bool particle_system_depends_on_time(ParticleSystem *psys)
193 {
194         ParticleSettings *part = psys->part;
195         /* Non-hair particles we always consider dependent on time. */
196         if (part->type != PART_HAIR) {
197                 return true;
198         }
199         /* Dynamics always depends on time. */
200         if (psys->flag & PSYS_HAIR_DYNAMICS) {
201                 return true;
202         }
203         /* TODO(sergey): Check what else makes hair dependent on time. */
204         return false;
205 }
206
207 static bool object_particles_depends_on_time(Object *object)
208 {
209         LISTBASE_FOREACH (ParticleSystem *, psys, &object->particlesystem) {
210                 if (particle_system_depends_on_time(psys)) {
211                         return true;
212                 }
213         }
214         return false;
215 }
216
217 /* **** General purpose functions ****  */
218
219 DepsgraphRelationBuilder::DepsgraphRelationBuilder(Main *bmain,
220                                                    Depsgraph *graph)
221     : bmain_(bmain),
222       graph_(graph),
223       scene_(NULL)
224 {
225 }
226
227 TimeSourceDepsNode *DepsgraphRelationBuilder::get_node(
228         const TimeSourceKey &key) const
229 {
230         if (key.id) {
231                 /* XXX TODO */
232                 return NULL;
233         }
234         else {
235                 return graph_->time_source;
236         }
237 }
238
239 ComponentDepsNode *DepsgraphRelationBuilder::get_node(
240         const ComponentKey &key) const
241 {
242         IDDepsNode *id_node = graph_->find_id_node(key.id);
243         if (!id_node) {
244                 fprintf(stderr, "find_node component: Could not find ID %s\n",
245                         (key.id != NULL) ? key.id->name : "<null>");
246                 return NULL;
247         }
248
249         ComponentDepsNode *node = id_node->find_component(key.type, key.name);
250         return node;
251 }
252
253 OperationDepsNode *DepsgraphRelationBuilder::get_node(
254         const OperationKey &key) const
255 {
256         OperationDepsNode *op_node = find_node(key);
257         if (op_node == NULL) {
258                 fprintf(stderr, "find_node_operation: Failed for (%s, '%s')\n",
259                         DEG_OPNAMES[key.opcode], key.name);
260         }
261         return op_node;
262 }
263
264 DepsNode *DepsgraphRelationBuilder::get_node(const RNAPathKey &key) const
265 {
266         return graph_->find_node_from_pointer(&key.ptr, key.prop);
267 }
268
269 OperationDepsNode *DepsgraphRelationBuilder::find_node(
270         const OperationKey &key) const
271 {
272         IDDepsNode *id_node = graph_->find_id_node(key.id);
273         if (!id_node) {
274                 return NULL;
275         }
276         ComponentDepsNode *comp_node = id_node->find_component(key.component_type,
277                                                                key.component_name);
278         if (!comp_node) {
279                 return NULL;
280         }
281         return comp_node->find_operation(key.opcode, key.name, key.name_tag);
282 }
283
284 bool DepsgraphRelationBuilder::has_node(const OperationKey &key) const
285 {
286         return find_node(key) != NULL;
287 }
288
289 void DepsgraphRelationBuilder::add_time_relation(TimeSourceDepsNode *timesrc,
290                                                  DepsNode *node_to,
291                                                  const char *description,
292                                                  bool check_unique)
293 {
294         if (timesrc && node_to) {
295                 graph_->add_new_relation(timesrc, node_to, description, check_unique);
296         }
297         else {
298                 DEG_DEBUG_PRINTF(BUILD, "add_time_relation(%p = %s, %p = %s, %s) Failed\n",
299                                  timesrc,   (timesrc) ? timesrc->identifier().c_str() : "<None>",
300                                  node_to,   (node_to) ? node_to->identifier().c_str() : "<None>",
301                                  description);
302         }
303 }
304
305 void DepsgraphRelationBuilder::add_operation_relation(
306         OperationDepsNode *node_from,
307         OperationDepsNode *node_to,
308         const char *description,
309         bool check_unique)
310 {
311         if (node_from && node_to) {
312                 graph_->add_new_relation(node_from, node_to, description, check_unique);
313         }
314         else {
315                 DEG_DEBUG_PRINTF(BUILD, "add_operation_relation(%p = %s, %p = %s, %s) Failed\n",
316                                  node_from, (node_from) ? node_from->identifier().c_str() : "<None>",
317                                  node_to,   (node_to)   ? node_to->identifier().c_str() : "<None>",
318                                  description);
319         }
320 }
321
322 void DepsgraphRelationBuilder::add_collision_relations(
323         const OperationKey &key,
324         Scene *scene,
325         Object *object,
326         Group *group,
327         bool dupli,
328         const char *name)
329 {
330         unsigned int numcollobj;
331         Object **collobjs = get_collisionobjects_ext(scene,
332                                                      object,
333                                                      group,
334                                                      &numcollobj,
335                                                      eModifierType_Collision,
336                                                      dupli);
337         for (unsigned int i = 0; i < numcollobj; i++) {
338                 Object *ob1 = collobjs[i];
339
340                 ComponentKey trf_key(&ob1->id, DEG_NODE_TYPE_TRANSFORM);
341                 add_relation(trf_key, key, name);
342
343                 ComponentKey coll_key(&ob1->id, DEG_NODE_TYPE_GEOMETRY);
344                 add_relation(coll_key, key, name);
345         }
346         if (collobjs != NULL) {
347                 MEM_freeN(collobjs);
348         }
349 }
350
351 void DepsgraphRelationBuilder::add_forcefield_relations(
352         const OperationKey &key,
353         Scene *scene,
354         Object *object,
355         ParticleSystem *psys,
356         EffectorWeights *eff,
357         bool add_absorption,
358         const char *name)
359 {
360         ListBase *effectors = pdInitEffectors(NULL, scene, object, psys, eff, false);
361         if (effectors != NULL) {
362                 LISTBASE_FOREACH (EffectorCache *, eff, effectors) {
363                         if (eff->ob != object) {
364                                 ComponentKey eff_key(&eff->ob->id, DEG_NODE_TYPE_TRANSFORM);
365                                 add_relation(eff_key, key, name);
366                         }
367                         if (eff->psys != NULL) {
368                                 if (eff->ob != object) {
369                                         ComponentKey eff_key(&eff->ob->id, DEG_NODE_TYPE_EVAL_PARTICLES);
370                                         add_relation(eff_key, key, name);
371
372                                         /* TODO: remove this when/if EVAL_PARTICLES is sufficient
373                                          * for up to date particles.
374                                          */
375                                         ComponentKey mod_key(&eff->ob->id, DEG_NODE_TYPE_GEOMETRY);
376                                         add_relation(mod_key, key, name);
377                                 }
378                                 else if (eff->psys != psys) {
379                                         OperationKey eff_key(&eff->ob->id,
380                                                              DEG_NODE_TYPE_EVAL_PARTICLES,
381                                                              DEG_OPCODE_PARTICLE_SYSTEM_EVAL,
382                                                              eff->psys->name);
383                                         add_relation(eff_key, key, name);
384                                 }
385                         }
386                         if (eff->pd->forcefield == PFIELD_SMOKEFLOW && eff->pd->f_source) {
387                                 ComponentKey trf_key(&eff->pd->f_source->id,
388                                                      DEG_NODE_TYPE_TRANSFORM);
389                                 add_relation(trf_key, key, "Smoke Force Domain");
390
391                                 ComponentKey eff_key(&eff->pd->f_source->id,
392                                                      DEG_NODE_TYPE_GEOMETRY);
393                                 add_relation(eff_key, key, "Smoke Force Domain");
394                         }
395                         if (add_absorption && (eff->pd->flag & PFIELD_VISIBILITY)) {
396                                 add_collision_relations(key,
397                                                         scene,
398                                                         object,
399                                                         NULL,
400                                                         true,
401                                                         "Force Absorption");
402                         }
403                 }
404         }
405
406         pdEndEffectors(&effectors);
407 }
408
409 Depsgraph *DepsgraphRelationBuilder::getGraph()
410 {
411         return graph_;
412 }
413
414 /* **** Functions to build relations between entities  **** */
415
416 void DepsgraphRelationBuilder::begin_build()
417 {
418 }
419
420 void DepsgraphRelationBuilder::build_group(Object *object, Group *group)
421 {
422         const bool group_done = built_map_.checkIsBuiltAndTag(group);
423         OperationKey object_local_transform_key(object != NULL ? &object->id : NULL,
424                                                 DEG_NODE_TYPE_TRANSFORM,
425                                                 DEG_OPCODE_TRANSFORM_LOCAL);
426         if (!group_done) {
427                 LISTBASE_FOREACH (Base *, base, &group->view_layer->object_bases) {
428                         build_object(NULL, base->object);
429                 }
430         }
431         if (object != NULL) {
432                 LISTBASE_FOREACH (Base *, base, &group->view_layer->object_bases) {
433                         ComponentKey dupli_transform_key(&base->object->id, DEG_NODE_TYPE_TRANSFORM);
434                         add_relation(dupli_transform_key, object_local_transform_key, "Dupligroup");
435                 }
436         }
437 }
438
439 void DepsgraphRelationBuilder::build_object(Base *base, Object *object)
440 {
441         if (built_map_.checkIsBuiltAndTag(object)) {
442                 if (base != NULL) {
443                         build_object_flags(base, object);
444                 }
445                 return;
446         }
447         /* Object Transforms */
448         eDepsOperation_Code base_op = (object->parent) ? DEG_OPCODE_TRANSFORM_PARENT
449                                                        : DEG_OPCODE_TRANSFORM_LOCAL;
450         OperationKey base_op_key(&object->id, DEG_NODE_TYPE_TRANSFORM, base_op);
451         OperationKey local_transform_key(&object->id,
452                                          DEG_NODE_TYPE_TRANSFORM,
453                                          DEG_OPCODE_TRANSFORM_LOCAL);
454         OperationKey parent_transform_key(&object->id,
455                                           DEG_NODE_TYPE_TRANSFORM,
456                                           DEG_OPCODE_TRANSFORM_PARENT);
457         OperationKey final_transform_key(&object->id,
458                                          DEG_NODE_TYPE_TRANSFORM,
459                                          DEG_OPCODE_TRANSFORM_FINAL);
460         OperationKey ob_ubereval_key(&object->id,
461                                      DEG_NODE_TYPE_TRANSFORM,
462                                      DEG_OPCODE_TRANSFORM_OBJECT_UBEREVAL);
463         /* Various flags, flushing from bases/collections. */
464         build_object_flags(base, object);
465         /* Parenting. */
466         if (object->parent != NULL) {
467                 /* Parent relationship. */
468                 build_object_parent(object);
469                 /* Local -> parent. */
470                 add_relation(local_transform_key,
471                              parent_transform_key,
472                              "ObLocal -> ObParent");
473         }
474         /* Modifiers. */
475         if (object->modifiers.first != NULL) {
476                 BuilderWalkUserData data;
477                 data.builder = this;
478                 modifiers_foreachIDLink(object, modifier_walk, &data);
479         }
480         /* Constraints. */
481         if (object->constraints.first != NULL) {
482                 BuilderWalkUserData data;
483                 data.builder = this;
484                 BKE_constraints_id_loop(&object->constraints, constraint_walk, &data);
485         }
486         /* Object constraints. */
487         if (object->constraints.first != NULL) {
488                 OperationKey constraint_key(&object->id,
489                                             DEG_NODE_TYPE_TRANSFORM,
490                                             DEG_OPCODE_TRANSFORM_CONSTRAINTS);
491                 /* Constraint relations. */
492                 build_constraints(&object->id,
493                                   DEG_NODE_TYPE_TRANSFORM,
494                                   "",
495                                   &object->constraints,
496                                   NULL);
497                 /* operation order */
498                 add_relation(base_op_key, constraint_key, "ObBase-> Constraint Stack");
499                 add_relation(constraint_key, final_transform_key, "ObConstraints -> Done");
500                 // XXX
501                 add_relation(constraint_key, ob_ubereval_key, "Temp Ubereval");
502                 add_relation(ob_ubereval_key, final_transform_key, "Temp Ubereval");
503         }
504         else {
505                 /* NOTE: Keep an eye here, we skip some relations here to "streamline"
506                  * dependencies and avoid transitive relations which causes overhead.
507                  * But once we get rid of uber eval node this will need reconsideration.
508                  */
509                 if (object->rigidbody_object == NULL) {
510                         /* Rigid body will hook up another node inbetween, so skip
511                          * relation here to avoid transitive relation.
512                          */
513                         add_relation(base_op_key, ob_ubereval_key, "Temp Ubereval");
514                 }
515                 add_relation(ob_ubereval_key, final_transform_key, "Temp Ubereval");
516         }
517         /* Animation data */
518         build_animdata(&object->id);
519         /* Object data. */
520         build_object_data(object);
521         /* Particle systems. */
522         if (object->particlesystem.first != NULL) {
523                 build_particles(object);
524         }
525         /* Grease pencil. */
526         if (object->gpd != NULL) {
527                 build_gpencil(object->gpd);
528         }
529         /* Object that this is a proxy for. */
530         if (object->proxy != NULL) {
531                 object->proxy->proxy_from = object;
532                 build_object(NULL, object->proxy);
533                 /* TODO(sergey): This is an inverted relation, matches old depsgraph
534                  * behavior and need to be investigated if it still need to be inverted.
535                  */
536                 ComponentKey ob_pose_key(&object->id, DEG_NODE_TYPE_EVAL_POSE);
537                 ComponentKey proxy_pose_key(&object->proxy->id, DEG_NODE_TYPE_EVAL_POSE);
538                 add_relation(ob_pose_key, proxy_pose_key, "Proxy");
539         }
540         /* Object dupligroup. */
541         if (object->dup_group != NULL) {
542                 build_group(object, object->dup_group);
543         }
544 }
545
546 void DepsgraphRelationBuilder::build_object_flags(Base *base, Object *object)
547 {
548         if (base == NULL) {
549                 return;
550         }
551         OperationKey view_layer_done_key(&scene_->id,
552                                          DEG_NODE_TYPE_LAYER_COLLECTIONS,
553                                          DEG_OPCODE_VIEW_LAYER_DONE);
554         OperationKey object_flags_key(&object->id,
555                                       DEG_NODE_TYPE_LAYER_COLLECTIONS,
556                                       DEG_OPCODE_OBJECT_BASE_FLAGS);
557         add_relation(view_layer_done_key, object_flags_key, "Base flags flush");
558 }
559
560 void DepsgraphRelationBuilder::build_object_data(Object *object)
561 {
562         if (object->data == NULL) {
563                 return;
564         }
565         ID *obdata_id = (ID *)object->data;
566         /* Object data animation. */
567         build_animdata(obdata_id);
568         /* type-specific data. */
569         switch (object->type) {
570                 case OB_MESH:
571                 case OB_CURVE:
572                 case OB_FONT:
573                 case OB_SURF:
574                 case OB_MBALL:
575                 case OB_LATTICE:
576                 {
577                         build_obdata_geom(object);
578                         break;
579                 }
580                 case OB_ARMATURE:
581                         if (ID_IS_LINKED(object) && object->proxy_from != NULL) {
582                                 build_proxy_rig(object);
583                         }
584                         else {
585                                 build_rig(object);
586                         }
587                         break;
588                 case OB_LAMP:
589                         build_lamp(object);
590                         break;
591                 case OB_CAMERA:
592                         build_camera(object);
593                         break;
594                 case OB_LIGHTPROBE:
595                         build_lightprobe(object);
596                         break;
597         }
598         Key *key = BKE_key_from_object(object);
599         if (key != NULL) {
600                 ComponentKey geometry_key((ID *)object->data, DEG_NODE_TYPE_GEOMETRY);
601                 ComponentKey key_key(&key->id, DEG_NODE_TYPE_GEOMETRY);
602                 add_relation(key_key, geometry_key, "Shapekeys");
603         }
604 }
605
606 void DepsgraphRelationBuilder::build_object_parent(Object *object)
607 {
608         /* XXX: for now, need to use the component key (not just direct to the parent op),
609          * or else the matrix doesn't get reset/
610          */
611         // XXX: @sergey - it would be good if we got that backwards flushing working
612         // when tagging for updates.
613         //OperationKey ob_key(&object->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_PARENT);
614         ComponentKey ob_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
615
616         /* type-specific links */
617         switch (object->partype) {
618                 case PARSKEL:  /* Armature Deform (Virtual Modifier) */
619                 {
620                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
621                         add_relation(parent_key, ob_key, "Armature Deform Parent");
622                         break;
623                 }
624
625                 case PARVERT1: /* Vertex Parent */
626                 case PARVERT3:
627                 {
628                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_GEOMETRY);
629                         add_relation(parent_key, ob_key, "Vertex Parent");
630
631                         /* XXX not sure what this is for or how you could be done properly - lukas */
632                         OperationDepsNode *parent_node = find_operation_node(parent_key);
633                         if (parent_node != NULL) {
634                                 parent_node->customdata_mask |= CD_MASK_ORIGINDEX;
635                         }
636
637                         ComponentKey transform_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
638                         add_relation(transform_key, ob_key, "Vertex Parent TFM");
639                         break;
640                 }
641
642                 case PARBONE: /* Bone Parent */
643                 {
644                         ComponentKey parent_bone_key(&object->parent->id,
645                                                      DEG_NODE_TYPE_BONE,
646                                                      object->parsubstr);
647                         OperationKey parent_transform_key(&object->parent->id,
648                                                           DEG_NODE_TYPE_TRANSFORM,
649                                                           DEG_OPCODE_TRANSFORM_FINAL);
650                         add_relation(parent_bone_key, ob_key, "Bone Parent");
651                         add_relation(parent_transform_key, ob_key, "Armature Parent");
652                         break;
653                 }
654
655                 default:
656                 {
657                         if (object->parent->type == OB_LATTICE) {
658                                 /* Lattice Deform Parent - Virtual Modifier */
659                                 // XXX: no virtual modifiers should be left!
660                                 ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
661                                 ComponentKey geom_key(&object->parent->id, DEG_NODE_TYPE_GEOMETRY);
662
663                                 add_relation(parent_key, ob_key, "Lattice Deform Parent");
664                                 add_relation(geom_key, ob_key, "Lattice Deform Parent Geom");
665                         }
666                         else if (object->parent->type == OB_CURVE) {
667                                 Curve *cu = (Curve *)object->parent->data;
668
669                                 if (cu->flag & CU_PATH) {
670                                         /* Follow Path */
671                                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_GEOMETRY);
672                                         add_relation(parent_key, ob_key, "Curve Follow Parent");
673
674                                         ComponentKey transform_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
675                                         add_relation(transform_key, ob_key, "Curve Follow TFM");
676                                 }
677                                 else {
678                                         /* Standard Parent */
679                                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
680                                         add_relation(parent_key, ob_key, "Curve Parent");
681                                 }
682                         }
683                         else {
684                                 /* Standard Parent */
685                                 ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
686                                 add_relation(parent_key, ob_key, "Parent");
687                         }
688                         break;
689                 }
690         }
691
692         /* exception case: parent is duplivert */
693         if ((object->type == OB_MBALL) && (object->parent->transflag & OB_DUPLIVERTS)) {
694                 //dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_OB, "Duplivert");
695         }
696 }
697
698 void DepsgraphRelationBuilder::build_constraints(ID *id,
699                                                  eDepsNode_Type component_type,
700                                                  const char *component_subdata,
701                                                  ListBase *constraints,
702                                                  RootPChanMap *root_map)
703 {
704         OperationKey constraint_op_key(
705                 id,
706                 component_type,
707                 component_subdata,
708                 (component_type == DEG_NODE_TYPE_BONE)
709                         ? DEG_OPCODE_BONE_CONSTRAINTS
710                         : DEG_OPCODE_TRANSFORM_CONSTRAINTS);
711         /* Add dependencies for each constraint in turn. */
712         for (bConstraint *con = (bConstraint *)constraints->first; con; con = con->next) {
713                 const bConstraintTypeInfo *cti = BKE_constraint_typeinfo_get(con);
714                 /* Invalid constraint type. */
715                 if (cti == NULL) {
716                         continue;
717                 }
718                 /* Special case for camera tracking -- it doesn't use targets to
719                  * define relations.
720                  */
721                 /* TODO: we can now represent dependencies in a much richer manner,
722                  * so review how this is done.
723                  */
724                 if (ELEM(cti->type,
725                          CONSTRAINT_TYPE_FOLLOWTRACK,
726                          CONSTRAINT_TYPE_CAMERASOLVER,
727                          CONSTRAINT_TYPE_OBJECTSOLVER))
728                 {
729                         bool depends_on_camera = false;
730                         if (cti->type == CONSTRAINT_TYPE_FOLLOWTRACK) {
731                                 bFollowTrackConstraint *data = (bFollowTrackConstraint *)con->data;
732                                 if (((data->clip) ||
733                                      (data->flag & FOLLOWTRACK_ACTIVECLIP)) && data->track[0])
734                                 {
735                                         depends_on_camera = true;
736                                 }
737                                 if (data->depth_ob) {
738                                         ComponentKey depth_transform_key(&data->depth_ob->id,
739                                                                          DEG_NODE_TYPE_TRANSFORM);
740                                         ComponentKey depth_geometry_key(&data->depth_ob->id,
741                                                                         DEG_NODE_TYPE_GEOMETRY);
742                                         add_relation(depth_transform_key, constraint_op_key, cti->name);
743                                         add_relation(depth_geometry_key, constraint_op_key, cti->name);
744                                 }
745                         }
746                         else if (cti->type == CONSTRAINT_TYPE_OBJECTSOLVER) {
747                                 depends_on_camera = true;
748                         }
749                         if (depends_on_camera && scene_->camera != NULL) {
750                                 ComponentKey camera_key(&scene_->camera->id, DEG_NODE_TYPE_TRANSFORM);
751                                 add_relation(camera_key, constraint_op_key, cti->name);
752                         }
753                         /* TODO(sergey): This is more a TimeSource -> MovieClip ->
754                          * Constraint dependency chain.
755                          */
756                         TimeSourceKey time_src_key;
757                         add_relation(time_src_key, constraint_op_key, "TimeSrc -> Animation");
758                 }
759                 else if (cti->type == CONSTRAINT_TYPE_TRANSFORM_CACHE) {
760                         /* TODO(kevin): This is more a TimeSource -> CacheFile -> Constraint
761                          * dependency chain.
762                          */
763                         TimeSourceKey time_src_key;
764                         add_relation(time_src_key, constraint_op_key, "TimeSrc -> Animation");
765                         bTransformCacheConstraint *data = (bTransformCacheConstraint *)con->data;
766                         if (data->cache_file) {
767                                 ComponentKey cache_key(&data->cache_file->id, DEG_NODE_TYPE_CACHE);
768                                 add_relation(cache_key, constraint_op_key, cti->name);
769                         }
770                 }
771                 else if (cti->get_constraint_targets) {
772                         ListBase targets = {NULL, NULL};
773                         cti->get_constraint_targets(con, &targets);
774                         LISTBASE_FOREACH (bConstraintTarget *, ct, &targets) {
775                                 if (ct->tar == NULL) {
776                                         continue;
777                                 }
778                                 if (ELEM(con->type,
779                                          CONSTRAINT_TYPE_KINEMATIC,
780                                          CONSTRAINT_TYPE_SPLINEIK))
781                                 {
782                                         /* Ignore IK constraints - these are handled separately
783                                          * (on pose level).
784                                          */
785                                 }
786                                 else if (ELEM(con->type,
787                                               CONSTRAINT_TYPE_FOLLOWPATH,
788                                               CONSTRAINT_TYPE_CLAMPTO))
789                                 {
790                                         /* These constraints require path geometry data. */
791                                         ComponentKey target_key(&ct->tar->id, DEG_NODE_TYPE_GEOMETRY);
792                                         add_relation(target_key, constraint_op_key, cti->name);
793                                         ComponentKey target_transform_key(&ct->tar->id,
794                                                                           DEG_NODE_TYPE_TRANSFORM);
795                                         add_relation(target_transform_key, constraint_op_key, cti->name);
796                                 }
797                                 else if ((ct->tar->type == OB_ARMATURE) && (ct->subtarget[0])) {
798                                         /* bone */
799                                         if (&ct->tar->id == id) {
800                                                 /* same armature  */
801                                                 eDepsOperation_Code target_key_opcode;
802                                                 /* Using "done" here breaks in-chain deps, while using
803                                                  * "ready" here breaks most production rigs instead.
804                                                  * So, we do a compromise here, and only do this when an
805                                                  * IK chain conflict may occur.
806                                                  */
807                                                 if (root_map->has_common_root(component_subdata,
808                                                                               ct->subtarget))
809                                                 {
810                                                         target_key_opcode = DEG_OPCODE_BONE_READY;
811                                                 }
812                                                 else {
813                                                         target_key_opcode = DEG_OPCODE_BONE_DONE;
814                                                 }
815                                                 OperationKey target_key(&ct->tar->id,
816                                                                         DEG_NODE_TYPE_BONE,
817                                                                         ct->subtarget,
818                                                                         target_key_opcode);
819                                                 add_relation(target_key, constraint_op_key, cti->name);
820                                         }
821                                         else {
822                                                 /* Different armature - we can safely use the result
823                                                  * of that.
824                                                  */
825                                                 OperationKey target_key(&ct->tar->id,
826                                                                         DEG_NODE_TYPE_BONE,
827                                                                         ct->subtarget,
828                                                                         DEG_OPCODE_BONE_DONE);
829                                                 add_relation(target_key, constraint_op_key, cti->name);
830                                         }
831                                 }
832                                 else if (ELEM(ct->tar->type, OB_MESH, OB_LATTICE) &&
833                                          (ct->subtarget[0]))
834                                 {
835                                         /* Vertex group. */
836                                         /* NOTE: for now, we don't need to represent vertex groups
837                                          * separately.
838                                          */
839                                         ComponentKey target_key(&ct->tar->id, DEG_NODE_TYPE_GEOMETRY);
840                                         add_relation(target_key, constraint_op_key, cti->name);
841                                         if (ct->tar->type == OB_MESH) {
842                                                 OperationDepsNode *node2 = find_operation_node(target_key);
843                                                 if (node2 != NULL) {
844                                                         node2->customdata_mask |= CD_MASK_MDEFORMVERT;
845                                                 }
846                                         }
847                                 }
848                                 else if (con->type == CONSTRAINT_TYPE_SHRINKWRAP) {
849                                         /* Constraints which requires the target object surface. */
850                                         ComponentKey target_key(&ct->tar->id, DEG_NODE_TYPE_GEOMETRY);
851                                         add_relation(target_key, constraint_op_key, cti->name);
852                                         /* NOTE: obdata eval now doesn't necessarily depend on the
853                                          * object's transform.
854                                          */
855                                         ComponentKey target_transform_key(&ct->tar->id,
856                                                                           DEG_NODE_TYPE_TRANSFORM);
857                                         add_relation(target_transform_key, constraint_op_key, cti->name);
858                                 }
859                                 else {
860                                         /* Standard object relation. */
861                                         // TODO: loc vs rot vs scale?
862                                         if (&ct->tar->id == id) {
863                                                 /* Constraint targetting own object:
864                                                  * - This case is fine IFF we're dealing with a bone
865                                                  *   constraint pointing to its own armature. In that
866                                                  *   case, it's just transform -> bone.
867                                                  * - If however it is a real self targetting case, just
868                                                  *   make it depend on the previous constraint (or the
869                                                  *   pre-constraint state).
870                                                  */
871                                                 if ((ct->tar->type == OB_ARMATURE) &&
872                                                     (component_type == DEG_NODE_TYPE_BONE))
873                                                 {
874                                                         OperationKey target_key(&ct->tar->id,
875                                                                                 DEG_NODE_TYPE_TRANSFORM,
876                                                                                 DEG_OPCODE_TRANSFORM_FINAL);
877                                                         add_relation(target_key, constraint_op_key, cti->name);
878                                                 }
879                                                 else {
880                                                         OperationKey target_key(&ct->tar->id,
881                                                                                 DEG_NODE_TYPE_TRANSFORM,
882                                                                                 DEG_OPCODE_TRANSFORM_LOCAL);
883                                                         add_relation(target_key, constraint_op_key, cti->name);
884                                                 }
885                                         }
886                                         else {
887                                                 /* Normal object dependency. */
888                                                 OperationKey target_key(&ct->tar->id,
889                                                                         DEG_NODE_TYPE_TRANSFORM,
890                                                                         DEG_OPCODE_TRANSFORM_FINAL);
891                                                 add_relation(target_key, constraint_op_key, cti->name);
892                                         }
893                                 }
894                                 /* Constraints which needs world's matrix for transform.
895                                  * TODO(sergey): More constraints here?
896                                  */
897                                 if (ELEM(con->type,
898                                          CONSTRAINT_TYPE_ROTLIKE,
899                                          CONSTRAINT_TYPE_SIZELIKE,
900                                          CONSTRAINT_TYPE_LOCLIKE,
901                                          CONSTRAINT_TYPE_TRANSLIKE))
902                                 {
903                                         /* TODO(sergey): Add used space check. */
904                                         ComponentKey target_transform_key(&ct->tar->id,
905                                                                           DEG_NODE_TYPE_TRANSFORM);
906                                         add_relation(target_transform_key, constraint_op_key, cti->name);
907                                 }
908                         }
909                         if (cti->flush_constraint_targets) {
910                                 cti->flush_constraint_targets(con, &targets, 1);
911                         }
912                 }
913         }
914 }
915
916 void DepsgraphRelationBuilder::build_animdata(ID *id)
917 {
918         /* Animation curves and NLA. */
919         build_animdata_curves(id);
920         /* Drivers. */
921         build_animdata_drivers(id);
922 }
923
924 void DepsgraphRelationBuilder::build_animdata_curves(ID *id)
925 {
926         AnimData *adt = BKE_animdata_from_id(id);
927         if (adt == NULL) {
928                 return;
929         }
930         if (adt->action == NULL && adt->nla_tracks.first == NULL) {
931                 return;
932         }
933         /* Wire up dependency to time source. */
934         ComponentKey adt_key(id, DEG_NODE_TYPE_ANIMATION);
935         TimeSourceKey time_src_key;
936         add_relation(time_src_key, adt_key, "TimeSrc -> Animation");
937         /* Get source operations. */
938         DepsNode *node_from = get_node(adt_key);
939         BLI_assert(node_from != NULL);
940         if (node_from == NULL) {
941                 return;
942         }
943         OperationDepsNode *operation_from = node_from->get_exit_operation();
944         BLI_assert(operation_from != NULL);
945         /* Build relations from animation operation to properties it changes. */
946         if (adt->action != NULL) {
947                 build_animdata_curves_targets(id, adt_key,
948                                       operation_from,
949                                       &adt->action->curves);
950         }
951         LISTBASE_FOREACH(NlaTrack *, nlt, &adt->nla_tracks) {
952                 build_animdata_nlastrip_targets(id, adt_key,
953                                                 operation_from,
954                                                 &nlt->strips);
955         }
956 }
957
958 void DepsgraphRelationBuilder::build_animdata_curves_targets(
959         ID *id, ComponentKey &adt_key,
960         OperationDepsNode *operation_from,
961         ListBase *curves)
962 {
963         /* Iterate over all curves and build relations. */
964         PointerRNA id_ptr;
965         RNA_id_pointer_create(id, &id_ptr);
966         LISTBASE_FOREACH(FCurve *, fcu, curves) {
967                 PointerRNA ptr;
968                 PropertyRNA *prop;
969                 int index;
970                 if (!RNA_path_resolve_full(&id_ptr, fcu->rna_path,
971                                            &ptr, &prop, &index))
972                 {
973                         continue;
974                 }
975                 DepsNode *node_to = graph_->find_node_from_pointer(&ptr, prop);
976                 if (node_to == NULL) {
977                         continue;
978                 }
979                 OperationDepsNode *operation_to = node_to->get_entry_operation();
980                 /* NOTE: Special case for bones, avoid relation from animation to
981                  * each of the bones. Bone evaluation could only start from pose
982                  * init anyway.
983                  */
984                 if (operation_to->opcode == DEG_OPCODE_BONE_LOCAL) {
985                         OperationKey pose_init_key(id,
986                                                    DEG_NODE_TYPE_EVAL_POSE,
987                                                    DEG_OPCODE_POSE_INIT);
988                         add_relation(adt_key, pose_init_key, "Animation -> Prop", true);
989                         continue;
990                 }
991                 graph_->add_new_relation(operation_from, operation_to,
992                                          "Animation -> Prop",
993                                          true);
994                 /* It is possible that animation is writing to a nested ID datablock,
995                  * need to make sure animation is evaluated after target ID is copied.
996                  */
997                 if (DEG_depsgraph_use_copy_on_write()) {
998                         const IDDepsNode *id_node_from = operation_from->owner->owner;
999                         const IDDepsNode *id_node_to = operation_to->owner->owner;
1000                         if (id_node_from != id_node_to) {
1001                                 ComponentKey cow_key(id_node_to->id_orig,
1002                                                      DEG_NODE_TYPE_COPY_ON_WRITE);
1003                                 add_relation(cow_key, adt_key, "Target CoW -> Animation", true);
1004                         }
1005                 }
1006         }
1007 }
1008
1009 void DepsgraphRelationBuilder::build_animdata_nlastrip_targets(
1010         ID *id, ComponentKey &adt_key,
1011         OperationDepsNode *operation_from,
1012         ListBase *strips)
1013 {
1014         LISTBASE_FOREACH(NlaStrip *, strip, strips) {
1015                 if (strip->act != NULL) {
1016                         build_animdata_curves_targets(id, adt_key,
1017                                                       operation_from,
1018                                                       &strip->act->curves);
1019                 }
1020                 else if (strip->strips.first != NULL) {
1021                         build_animdata_nlastrip_targets(id, adt_key,
1022                                                         operation_from,
1023                                                         &strip->strips);
1024                 }
1025         }
1026 }
1027
1028 void DepsgraphRelationBuilder::build_animdata_drivers(ID *id)
1029 {
1030         AnimData *adt = BKE_animdata_from_id(id);
1031         if (adt == NULL) {
1032                 return;
1033         }
1034         ComponentKey adt_key(id, DEG_NODE_TYPE_ANIMATION);
1035         LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) {
1036                 OperationKey driver_key(id,
1037                                         DEG_NODE_TYPE_PARAMETERS,
1038                                         DEG_OPCODE_DRIVER,
1039                                         fcu->rna_path ? fcu->rna_path : "",
1040                                         fcu->array_index);
1041
1042                 /* create the driver's relations to targets */
1043                 build_driver(id, fcu);
1044                 /* Special case for array drivers: we can not multithread them because
1045                  * of the way how they work internally: animation system will write the
1046                  * whole array back to RNA even when changing individual array value.
1047                  *
1048                  * Some tricky things here:
1049                  * - array_index is -1 for single channel drivers, meaning we only have
1050                  *   to do some magic when array_index is not -1.
1051                  * - We do relation from next array index to a previous one, so we don't
1052                  *   have to deal with array index 0.
1053                  *
1054                  * TODO(sergey): Avoid liner lookup somehow.
1055                  */
1056                 if (fcu->array_index > 0) {
1057                         FCurve *fcu_prev = NULL;
1058                         LISTBASE_FOREACH (FCurve *, fcu_candidate, &adt->drivers) {
1059                                 /* Writing to different RNA paths is  */
1060                                 const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1061                                 if (!STREQ(fcu_candidate->rna_path, rna_path)) {
1062                                         continue;
1063                                 }
1064                                 /* We only do relation from previous fcurve to previous one. */
1065                                 if (fcu_candidate->array_index >= fcu->array_index) {
1066                                         continue;
1067                                 }
1068                                 /* Choose fcurve with highest possible array index. */
1069                                 if (fcu_prev == NULL ||
1070                                     fcu_candidate->array_index > fcu_prev->array_index)
1071                                 {
1072                                         fcu_prev = fcu_candidate;
1073                                 }
1074                         }
1075                         if (fcu_prev != NULL) {
1076                                 OperationKey prev_driver_key(id,
1077                                                              DEG_NODE_TYPE_PARAMETERS,
1078                                                              DEG_OPCODE_DRIVER,
1079                                                              fcu_prev->rna_path ? fcu_prev->rna_path : "",
1080                                                              fcu_prev->array_index);
1081                                 OperationKey driver_key(id,
1082                                                         DEG_NODE_TYPE_PARAMETERS,
1083                                                         DEG_OPCODE_DRIVER,
1084                                                         fcu->rna_path ? fcu->rna_path : "",
1085                                                         fcu->array_index);
1086                                 add_relation(prev_driver_key, driver_key, "Driver Order");
1087                         }
1088                 }
1089
1090                 /* prevent driver from occurring before own animation... */
1091                 if (adt->action || adt->nla_tracks.first) {
1092                         add_relation(adt_key, driver_key, "AnimData Before Drivers");
1093                 }
1094         }
1095 }
1096
1097 void DepsgraphRelationBuilder::build_driver(ID *id, FCurve *fcu)
1098 {
1099         ChannelDriver *driver = fcu->driver;
1100         OperationKey driver_key(id,
1101                                 DEG_NODE_TYPE_PARAMETERS,
1102                                 DEG_OPCODE_DRIVER,
1103                                 fcu->rna_path ? fcu->rna_path : "",
1104                                 fcu->array_index);
1105         /* Driver -> data components (for interleaved evaluation
1106          * bones/constraints/modifiers).
1107          */
1108         build_driver_data(id, fcu);
1109         /* Loop over variables to get the target relationships. */
1110         build_driver_variables(id, fcu);
1111         /* It's quite tricky to detect if the driver actually depends on time or
1112          * not, so for now we'll be quite conservative here about optimization and
1113          * consider all python drivers to be depending on time.
1114          */
1115         if ((driver->type == DRIVER_TYPE_PYTHON) &&
1116             python_driver_depends_on_time(driver))
1117         {
1118                 TimeSourceKey time_src_key;
1119                 add_relation(time_src_key, driver_key, "TimeSrc -> Driver");
1120         }
1121 }
1122
1123 void DepsgraphRelationBuilder::build_driver_data(ID *id, FCurve *fcu)
1124 {
1125         OperationKey driver_key(id,
1126                                 DEG_NODE_TYPE_PARAMETERS,
1127                                 DEG_OPCODE_DRIVER,
1128                                 fcu->rna_path ? fcu->rna_path : "",
1129                                 fcu->array_index);
1130         const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1131         const RNAPathKey self_key(id, rna_path);
1132         if (GS(id->name) == ID_AR && strstr(rna_path, "bones[")) {
1133                 /* Drivers on armature-level bone settings (i.e. bbone stuff),
1134                  * which will affect the evaluation of corresponding pose bones.
1135                  */
1136                 IDDepsNode *arm_node = graph_->find_id_node(id);
1137                 char *bone_name = BLI_str_quoted_substrN(rna_path, "bones[");
1138                 if (arm_node != NULL && bone_name != NULL) {
1139                         /* Find objects which use this, and make their eval callbacks
1140                          * depend on this.
1141                          */
1142                         foreach (DepsRelation *rel, arm_node->outlinks) {
1143                                 IDDepsNode *to_node = (IDDepsNode *)rel->to;
1144                                 /* We only care about objects with pose data which use this. */
1145                                 if (GS(to_node->id_orig->name) == ID_OB) {
1146                                         Object *object = (Object *)to_node->id_orig;
1147                                         // NOTE: object->pose may be NULL
1148                                         bPoseChannel *pchan = BKE_pose_channel_find_name(object->pose,
1149                                                                                          bone_name);
1150                                         if (pchan != NULL) {
1151                                                 OperationKey bone_key(&object->id,
1152                                                                       DEG_NODE_TYPE_BONE,
1153                                                                       pchan->name,
1154                                                                       DEG_OPCODE_BONE_LOCAL);
1155                                                 add_relation(driver_key,
1156                                                              bone_key,
1157                                                              "Arm Bone -> Driver -> Bone");
1158                                         }
1159                                 }
1160                         }
1161                         /* Free temp data. */
1162                         MEM_freeN(bone_name);
1163                         bone_name = NULL;
1164                 }
1165                 else {
1166                         fprintf(stderr,
1167                                 "Couldn't find armature bone name for driver path - '%s'\n",
1168                                 rna_path);
1169                 }
1170         }
1171         else {
1172                 RNAPathKey target_key(id, rna_path);
1173                 add_relation(driver_key, target_key, "Driver -> Target");
1174                 /* Similar to the case with f-curves, driver might drive a nested
1175                  * datablock, which means driver execution should wait for that
1176                  * datablock to be copied.
1177                  */
1178                 if (DEG_depsgraph_use_copy_on_write()) {
1179                         PointerRNA id_ptr;
1180                         PointerRNA ptr;
1181                         RNA_id_pointer_create(id, &id_ptr);
1182                         if (RNA_path_resolve_full(&id_ptr, fcu->rna_path, &ptr, NULL, NULL)) {
1183                                 if (id_ptr.id.data != ptr.id.data) {
1184                                         ComponentKey cow_key((ID *)ptr.id.data,
1185                                                              DEG_NODE_TYPE_COPY_ON_WRITE);
1186                                         add_relation(cow_key,
1187                                                      driver_key,
1188                                                      "Target CoW -> Driver",
1189                                                      true);
1190                                 }
1191                         }
1192                 }
1193                 if (RNA_pointer_is_null(&target_key.ptr)) {
1194                         /* TODO(sergey): This would only mean that driver is broken.
1195                          * so we can't create relation anyway. However, we need to avoid
1196                          * adding drivers which are known to be buggy to a dependency
1197                          * graph, in order to save computational power.
1198                          */
1199                 }
1200                 else {
1201                         if (target_key.prop != NULL &&
1202                             RNA_property_is_idprop(target_key.prop))
1203                         {
1204                                 OperationKey parameters_key(id,
1205                                                             DEG_NODE_TYPE_PARAMETERS,
1206                                                             DEG_OPCODE_PARAMETERS_EVAL);
1207                                 add_relation(target_key,
1208                                              parameters_key,
1209                                              "Driver Target -> Properties");
1210                         }
1211                         add_relation(driver_key, target_key, "Driver -> Target");
1212                 }
1213         }
1214 }
1215
1216 void DepsgraphRelationBuilder::build_driver_variables(ID *id, FCurve *fcu)
1217 {
1218         ChannelDriver *driver = fcu->driver;
1219         OperationKey driver_key(id,
1220                                 DEG_NODE_TYPE_PARAMETERS,
1221                                 DEG_OPCODE_DRIVER,
1222                                 fcu->rna_path ? fcu->rna_path : "",
1223                                 fcu->array_index);
1224         const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1225         const RNAPathKey self_key(id, rna_path);
1226
1227         LISTBASE_FOREACH (DriverVar *, dvar, &driver->variables) {
1228                 /* Only used targets. */
1229                 DRIVER_TARGETS_USED_LOOPER(dvar)
1230                 {
1231                         if (dtar->id == NULL) {
1232                                 continue;
1233                         }
1234                         /* Special handling for directly-named bones. */
1235                         if ((dtar->flag & DTAR_FLAG_STRUCT_REF) &&
1236                             (((Object *)dtar->id)->type == OB_ARMATURE) &&
1237                             (dtar->pchan_name[0]))
1238                         {
1239                                 Object *object = (Object *)dtar->id;
1240                                 bPoseChannel *target_pchan =
1241                                         BKE_pose_channel_find_name(object->pose,
1242                                                                    dtar->pchan_name);
1243                                 if (target_pchan == NULL) {
1244                                         continue;
1245                                 }
1246                                 OperationKey variable_key(dtar->id,
1247                                                           DEG_NODE_TYPE_BONE,
1248                                                           target_pchan->name,
1249                                                           DEG_OPCODE_BONE_DONE);
1250                                 if (is_same_bone_dependency(variable_key, self_key)) {
1251                                         continue;
1252                                 }
1253                                 add_relation(variable_key, driver_key, "Bone Target -> Driver");
1254                         }
1255                         else if (dtar->flag & DTAR_FLAG_STRUCT_REF) {
1256                                 /* Get node associated with the object's transforms. */
1257                                 if (dtar->id == id) {
1258                                         /* Ignore input dependency if we're driving properties of
1259                                          * the same ID, otherwise we'll be ending up in a cyclic
1260                                          * dependency here.
1261                                          */
1262                                         continue;
1263                                 }
1264                                 OperationKey target_key(dtar->id,
1265                                                         DEG_NODE_TYPE_TRANSFORM,
1266                                                         DEG_OPCODE_TRANSFORM_FINAL);
1267                                 add_relation(target_key, driver_key, "Target -> Driver");
1268                         }
1269                         else if (dtar->rna_path) {
1270                                 RNAPathKey variable_key(dtar->id, dtar->rna_path);
1271                                 if (RNA_pointer_is_null(&variable_key.ptr)) {
1272                                         continue;
1273                                 }
1274                                 if (is_same_bone_dependency(variable_key, self_key) ||
1275                                     is_same_nodetree_node_dependency(variable_key, self_key) ||
1276                                     is_same_shapekey_dependency(variable_key, self_key))
1277                                 {
1278                                         continue;
1279                                 }
1280                                 add_relation(variable_key, driver_key, "RNA Target -> Driver");
1281                         }
1282                         else {
1283                                 if (dtar->id == id) {
1284                                         /* Ignore input dependency if we're driving properties of
1285                                          * the same ID, otherwise we'll be ending up in a cyclic
1286                                          * dependency here.
1287                                          */
1288                                         continue;
1289                                 }
1290                                 /* Resolve path to get node. */
1291                                 RNAPathKey target_key(dtar->id,
1292                                                       dtar->rna_path ? dtar->rna_path : "");
1293                                 add_relation(target_key, driver_key, "RNA Target -> Driver");
1294                         }
1295                 }
1296                 DRIVER_TARGETS_LOOPER_END
1297         }
1298 }
1299
1300 void DepsgraphRelationBuilder::build_world(World *world)
1301 {
1302         if (built_map_.checkIsBuiltAndTag(world)) {
1303                 return;
1304         }
1305         build_animdata(&world->id);
1306         /* TODO: other settings? */
1307         /* textures */
1308         build_texture_stack(world->mtex);
1309         /* world's nodetree */
1310         if (world->nodetree != NULL) {
1311                 build_nodetree(world->nodetree);
1312                 ComponentKey ntree_key(&world->nodetree->id, DEG_NODE_TYPE_SHADING);
1313                 ComponentKey world_key(&world->id, DEG_NODE_TYPE_SHADING);
1314                 add_relation(ntree_key, world_key, "NTree->World Shading Update");
1315         }
1316 }
1317
1318 void DepsgraphRelationBuilder::build_rigidbody(Scene *scene)
1319 {
1320         RigidBodyWorld *rbw = scene->rigidbody_world;
1321
1322         OperationKey init_key(&scene->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_REBUILD);
1323         OperationKey sim_key(&scene->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_SIM);
1324
1325         /* rel between the two sim-nodes */
1326         add_relation(init_key, sim_key, "Rigidbody [Init -> SimStep]");
1327
1328         /* set up dependencies between these operations and other builtin nodes --------------- */
1329
1330         /* time dependency */
1331         TimeSourceKey time_src_key;
1332         add_relation(time_src_key, init_key, "TimeSrc -> Rigidbody Reset/Rebuild (Optional)");
1333
1334         /* objects - simulation participants */
1335         if (rbw->group) {
1336                 LISTBASE_FOREACH (Base *, base, &rbw->group->view_layer->object_bases) {
1337                         Object *object = base->object;
1338                         if (object == NULL || object->type != OB_MESH) {
1339                                 continue;
1340                         }
1341
1342                         /* hook up evaluation order...
1343                          * 1) flushing rigidbody results follows base transforms being applied
1344                          * 2) rigidbody flushing can only be performed after simulation has been run
1345                          *
1346                          * 3) simulation needs to know base transforms to figure out what to do
1347                          *    XXX: there's probably a difference between passive and active
1348                          *         - passive don't change, so may need to know full transform...
1349                          */
1350                         OperationKey rbo_key(&object->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_TRANSFORM_COPY);
1351
1352                         eDepsOperation_Code trans_opcode = object->parent ? DEG_OPCODE_TRANSFORM_PARENT : DEG_OPCODE_TRANSFORM_LOCAL;
1353                         OperationKey trans_op(&object->id, DEG_NODE_TYPE_TRANSFORM, trans_opcode);
1354
1355                         add_relation(sim_key, rbo_key, "Rigidbody Sim Eval -> RBO Sync");
1356
1357                         /* if constraints exist, those depend on the result of the rigidbody sim
1358                          * - This allows constraints to modify the result of the sim (i.e. clamping)
1359                          *   while still allowing the sim to depend on some changes to the objects.
1360                          *   Also, since constraints are hooked up to the final nodes, this link
1361                          *   means that we can also fit in there too...
1362                          * - Later, it might be good to include a constraint in the stack allowing us
1363                          *   to control whether rigidbody eval gets interleaved into the constraint stack
1364                          */
1365                         if (object->constraints.first) {
1366                                 OperationKey constraint_key(&object->id,
1367                                                             DEG_NODE_TYPE_TRANSFORM,
1368                                                             DEG_OPCODE_TRANSFORM_CONSTRAINTS);
1369                                 add_relation(rbo_key, constraint_key, "RBO Sync -> Ob Constraints");
1370                         }
1371                         else {
1372                                 /* Final object transform depends on rigidbody.
1373                                  *
1374                                  * NOTE: Currently we consider final here an ubereval node.
1375                                  * If it is gone we'll need to reconsider relation here.
1376                                  */
1377                                 OperationKey uber_key(&object->id,
1378                                                       DEG_NODE_TYPE_TRANSFORM,
1379                                                       DEG_OPCODE_TRANSFORM_OBJECT_UBEREVAL);
1380                                 add_relation(rbo_key, uber_key, "RBO Sync -> Uber (Temp)");
1381                         }
1382
1383                         /* Needed to get correct base values. */
1384                         add_relation(trans_op, sim_key, "Base Ob Transform -> Rigidbody Sim Eval");
1385                 }
1386         }
1387
1388         /* constraints */
1389         if (rbw->constraints) {
1390                 LISTBASE_FOREACH (Base *, base, &rbw->constraints->view_layer->object_bases) {
1391                         Object *object = base->object;
1392                         if (object == NULL || !object->rigidbody_constraint) {
1393                                 continue;
1394                         }
1395
1396                         RigidBodyCon *rbc = object->rigidbody_constraint;
1397
1398                         /* final result of the constraint object's transform controls how the
1399                          * constraint affects the physics sim for these objects
1400                          */
1401                         ComponentKey trans_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
1402                         OperationKey ob1_key(&rbc->ob1->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_TRANSFORM_COPY);
1403                         OperationKey ob2_key(&rbc->ob2->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_TRANSFORM_COPY);
1404
1405                         /* - constrained-objects sync depends on the constraint-holder */
1406                         add_relation(trans_key, ob1_key, "RigidBodyConstraint -> RBC.Object_1");
1407                         add_relation(trans_key, ob2_key, "RigidBodyConstraint -> RBC.Object_2");
1408
1409                         /* - ensure that sim depends on this constraint's transform */
1410                         add_relation(trans_key, sim_key, "RigidBodyConstraint Transform -> RB Simulation");
1411                 }
1412         }
1413 }
1414
1415 void DepsgraphRelationBuilder::build_particles(Object *object)
1416 {
1417         TimeSourceKey time_src_key;
1418         OperationKey obdata_ubereval_key(&object->id,
1419                                          DEG_NODE_TYPE_GEOMETRY,
1420                                          DEG_OPCODE_GEOMETRY_UBEREVAL);
1421         OperationKey eval_init_key(&object->id,
1422                                    DEG_NODE_TYPE_EVAL_PARTICLES,
1423                                    DEG_OPCODE_PARTICLE_SYSTEM_EVAL_INIT);
1424
1425         /* Particle systems. */
1426         LISTBASE_FOREACH (ParticleSystem *, psys, &object->particlesystem) {
1427                 ParticleSettings *part = psys->part;
1428
1429                 /* Build particle settings relations.
1430                  *
1431                  * NOTE: The call itself ensures settings are only build once.
1432                  */
1433                 build_particle_settings(part);
1434
1435                 /* This particle system. */
1436                 OperationKey psys_key(&object->id,
1437                                       DEG_NODE_TYPE_EVAL_PARTICLES,
1438                                       DEG_OPCODE_PARTICLE_SYSTEM_EVAL,
1439                                       psys->name);
1440
1441                 /* Update particle system when settings changes. */
1442                 OperationKey particle_settings_key(&part->id,
1443                                                    DEG_NODE_TYPE_PARAMETERS,
1444                                                    DEG_OPCODE_PARTICLE_SETTINGS_EVAL);
1445                 add_relation(particle_settings_key, eval_init_key, "Particle Settings Change");
1446                 add_relation(eval_init_key, psys_key, "Init -> PSys");
1447                 /* TODO(sergey): Currently particle update is just a placeholder,
1448                  * hook it to the ubereval node so particle system is getting updated
1449                  * on playback.
1450                  */
1451                 add_relation(psys_key, obdata_ubereval_key, "PSys -> UberEval");
1452                 /* Collisions */
1453                 if (part->type != PART_HAIR) {
1454                         add_collision_relations(psys_key,
1455                                                 scene_,
1456                                                 object,
1457                                                 part->collision_group,
1458                                                 true,
1459                                                 "Particle Collision");
1460                 }
1461                 else if ((psys->flag & PSYS_HAIR_DYNAMICS) &&
1462                          psys->clmd != NULL &&
1463                          psys->clmd->coll_parms != NULL)
1464                 {
1465                         add_collision_relations(psys_key,
1466                                                 scene_,
1467                                                 object,
1468                                                 psys->clmd->coll_parms->group,
1469                                                 true,
1470                                                 "Hair Collision");
1471                 }
1472                 /* Effectors. */
1473                 add_forcefield_relations(psys_key,
1474                                          scene_,
1475                                          object,
1476                                          psys,
1477                                          part->effector_weights,
1478                                          part->type == PART_HAIR,
1479                                          "Particle Field");
1480                 /* Boids .*/
1481                 if (part->boids) {
1482                         LISTBASE_FOREACH (BoidState *, state, &part->boids->states) {
1483                                 LISTBASE_FOREACH (BoidRule *, rule, &state->rules) {
1484                                         Object *ruleob = NULL;
1485                                         if (rule->type == eBoidRuleType_Avoid) {
1486                                                 ruleob = ((BoidRuleGoalAvoid *)rule)->ob;
1487                                         }
1488                                         else if (rule->type == eBoidRuleType_FollowLeader) {
1489                                                 ruleob = ((BoidRuleFollowLeader *)rule)->ob;
1490                                         }
1491                                         if (ruleob) {
1492                                                 ComponentKey ruleob_key(&ruleob->id,
1493                                                                         DEG_NODE_TYPE_TRANSFORM);
1494                                                 add_relation(ruleob_key, psys_key, "Boid Rule");
1495                                         }
1496                                 }
1497                         }
1498                 }
1499                 switch (part->ren_as) {
1500                         case PART_DRAW_OB:
1501                                 if (part->dup_ob != NULL) {
1502                                         /* Make sure object's relations are all built.  */
1503                                         build_object(NULL, part->dup_ob);
1504                                         /* Build relation for the particle visualization. */
1505                                         build_particles_visualization_object(object,
1506                                                                              psys,
1507                                                                              part->dup_ob);
1508                                 }
1509                                 break;
1510                         case PART_DRAW_GR:
1511                                 if (part->dup_group != NULL) {
1512                                         build_group(NULL, part->dup_group);
1513                                         LISTBASE_FOREACH (GroupObject *, go, &part->dup_group->gobject) {
1514                                                 build_particles_visualization_object(object,
1515                                                                                      psys,
1516                                                                                      go->ob);
1517                                         }
1518                                 }
1519                                 break;
1520                 }
1521         }
1522
1523         /* Particle depends on the object transform, so that channel is to be ready
1524          * first.
1525          *
1526          * TODO(sergey): This relation should be altered once real granular update
1527          * is implemented.
1528          */
1529         ComponentKey transform_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
1530         add_relation(transform_key, obdata_ubereval_key, "Partcile Eval");
1531
1532         OperationKey point_cache_reset_key(&object->id,
1533                                            DEG_NODE_TYPE_CACHE,
1534                                            DEG_OPCODE_POINT_CACHE_RESET);
1535         add_relation(transform_key, point_cache_reset_key, "Object Transform -> Point Cache Reset");
1536         add_relation(point_cache_reset_key, obdata_ubereval_key, "Point Cache Reset -> UberEval");
1537 }
1538
1539 void DepsgraphRelationBuilder::build_particle_settings(ParticleSettings *part)
1540 {
1541         if (built_map_.checkIsBuiltAndTag(part)) {
1542                 return;
1543         }
1544         /* Animation data relations. */
1545         build_animdata(&part->id);
1546 }
1547
1548 void DepsgraphRelationBuilder::build_particles_visualization_object(
1549         Object *object,
1550         ParticleSystem *psys,
1551         Object *draw_object)
1552 {
1553         OperationKey psys_key(&object->id,
1554                               DEG_NODE_TYPE_EVAL_PARTICLES,
1555                               DEG_OPCODE_PARTICLE_SYSTEM_EVAL,
1556                               psys->name);
1557         OperationKey obdata_ubereval_key(&object->id,
1558                                          DEG_NODE_TYPE_GEOMETRY,
1559                                          DEG_OPCODE_GEOMETRY_UBEREVAL);
1560         ComponentKey dup_ob_key(&draw_object->id, DEG_NODE_TYPE_TRANSFORM);
1561         add_relation(dup_ob_key, psys_key, "Particle Object Visualization");
1562         if (draw_object->type == OB_MBALL) {
1563                 ComponentKey dup_geometry_key(&draw_object->id, DEG_NODE_TYPE_GEOMETRY);
1564                 add_relation(obdata_ubereval_key,
1565                              dup_geometry_key,
1566                              "Particle MBall Visualization");
1567         }
1568 }
1569
1570 void DepsgraphRelationBuilder::build_cloth(Object *object,
1571                                            ModifierData * /*md*/)
1572 {
1573         OperationKey cache_key(&object->id,
1574                                DEG_NODE_TYPE_CACHE,
1575                                DEG_OPCODE_GEOMETRY_CLOTH_MODIFIER);
1576         /* Cache component affects on modifier. */
1577         OperationKey modifier_key(&object->id,
1578                                   DEG_NODE_TYPE_GEOMETRY,
1579                                   DEG_OPCODE_GEOMETRY_UBEREVAL);
1580         add_relation(cache_key, modifier_key, "Cloth Cache -> Cloth");
1581 }
1582
1583 /* Shapekeys */
1584 void DepsgraphRelationBuilder::build_shapekeys(ID *obdata, Key *key)
1585 {
1586         ComponentKey obdata_key(obdata, DEG_NODE_TYPE_GEOMETRY);
1587
1588         /* attach animdata to geometry */
1589         build_animdata(&key->id);
1590
1591         if (key->adt) {
1592                 // TODO: this should really be handled in build_animdata, since many of these cases will need it
1593                 if (key->adt->action || key->adt->nla_tracks.first) {
1594                         ComponentKey adt_key(&key->id, DEG_NODE_TYPE_ANIMATION);
1595                         add_relation(adt_key, obdata_key, "Animation");
1596                 }
1597
1598                 /* NOTE: individual shapekey drivers are handled above already */
1599         }
1600
1601         /* attach to geometry */
1602         // XXX: aren't shapekeys now done as a pseudo-modifier on object?
1603         //ComponentKey key_key(&key->id, DEG_NODE_TYPE_GEOMETRY); // FIXME: this doesn't exist
1604         //add_relation(key_key, obdata_key, "Shapekeys");
1605 }
1606
1607 /**
1608  * ObData Geometry Evaluation
1609  * ==========================
1610  *
1611  * The evaluation of geometry on objects is as follows:
1612  * - The actual evaluated of the derived geometry (e.g. DerivedMesh, DispList, etc.)
1613  *   occurs in the Geometry component of the object which references this. This includes
1614  *   modifiers, and the temporary "ubereval" for geometry.
1615  * - Therefore, each user of a piece of shared geometry data ends up evaluating its own
1616  *   version of the stuff, complete with whatever modifiers it may use.
1617  *
1618  * - The datablocks for the geometry data - "obdata" (e.g. ID_ME, ID_CU, ID_LT, etc.) are used for
1619  *     1) calculating the bounding boxes of the geometry data,
1620  *     2) aggregating inward links from other objects (e.g. for text on curve, etc.)
1621  *        and also for the links coming from the shapekey datablocks
1622  * - Animation/Drivers affecting the parameters of the geometry are made to trigger
1623  *   updates on the obdata geometry component, which then trigger downstream
1624  *   re-evaluation of the individual instances of this geometry.
1625  */
1626 // TODO: Materials and lighting should probably get their own component, instead of being lumped under geometry?
1627 void DepsgraphRelationBuilder::build_obdata_geom(Object *object)
1628 {
1629         ID *obdata = (ID *)object->data;
1630
1631         /* Init operation of object-level geometry evaluation. */
1632         OperationKey geom_init_key(&object->id, DEG_NODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Eval Init");
1633
1634         /* get nodes for result of obdata's evaluation, and geometry evaluation on object */
1635         ComponentKey obdata_geom_key(obdata, DEG_NODE_TYPE_GEOMETRY);
1636         ComponentKey geom_key(&object->id, DEG_NODE_TYPE_GEOMETRY);
1637
1638         /* link components to each other */
1639         add_relation(obdata_geom_key, geom_key, "Object Geometry Base Data");
1640
1641         OperationKey obdata_ubereval_key(&object->id,
1642                                          DEG_NODE_TYPE_GEOMETRY,
1643                                          DEG_OPCODE_GEOMETRY_UBEREVAL);
1644
1645         /* Special case: modifiers and DerivedMesh creation queries scene for various
1646          * things like data mask to be used. We add relation here to ensure object is
1647          * never evaluated prior to Scene's CoW is ready.
1648          */
1649         OperationKey scene_key(&scene_->id,
1650                                DEG_NODE_TYPE_PARAMETERS,
1651                                DEG_OPCODE_PLACEHOLDER,
1652                                "Scene Eval");
1653         add_relation(scene_key, obdata_ubereval_key, "CoW Relation");
1654
1655         /* Modifiers */
1656         if (object->modifiers.first != NULL) {
1657                 ModifierUpdateDepsgraphContext ctx = {};
1658                 ctx.scene = scene_;
1659                 ctx.object = object;
1660
1661                 LISTBASE_FOREACH (ModifierData *, md, &object->modifiers) {
1662                         const ModifierTypeInfo *mti = modifierType_getInfo((ModifierType)md->type);
1663                         if (mti->updateDepsgraph) {
1664                                 DepsNodeHandle handle = create_node_handle(obdata_ubereval_key);
1665                                 ctx.node = reinterpret_cast< ::DepsNodeHandle* >(&handle);
1666                                 mti->updateDepsgraph(md, &ctx);
1667                         }
1668                         if (BKE_object_modifier_use_time(object, md)) {
1669                                 TimeSourceKey time_src_key;
1670                                 add_relation(time_src_key, obdata_ubereval_key, "Time Source");
1671                         }
1672                         if (md->type == eModifierType_Cloth) {
1673                                 build_cloth(object, md);
1674                         }
1675                 }
1676         }
1677
1678         /* materials */
1679         if (object->totcol) {
1680                 for (int a = 1; a <= object->totcol; a++) {
1681                         Material *ma = give_current_material(object, a);
1682                         if (ma != NULL) {
1683                                 build_material(ma);
1684
1685                                 if (object->type == OB_MESH) {
1686                                         OperationKey material_key(&ma->id,
1687                                                                   DEG_NODE_TYPE_SHADING,
1688                                                                   DEG_OPCODE_MATERIAL_UPDATE);
1689                                         OperationKey shading_key(&object->id, DEG_NODE_TYPE_SHADING, DEG_OPCODE_SHADING);
1690                                         add_relation(material_key, shading_key, "Material Update");
1691                                 }
1692                         }
1693                 }
1694         }
1695
1696         /* geometry collision */
1697         if (ELEM(object->type, OB_MESH, OB_CURVE, OB_LATTICE)) {
1698                 // add geometry collider relations
1699         }
1700
1701         /* Make sure uber update is the last in the dependencies.
1702          *
1703          * TODO(sergey): Get rid of this node.
1704          */
1705         if (object->type != OB_ARMATURE) {
1706                 /* Armatures does no longer require uber node. */
1707                 OperationKey obdata_ubereval_key(&object->id, DEG_NODE_TYPE_GEOMETRY, DEG_OPCODE_GEOMETRY_UBEREVAL);
1708                 add_relation(geom_init_key, obdata_ubereval_key, "Object Geometry UberEval");
1709         }
1710
1711         if (built_map_.checkIsBuiltAndTag(obdata)) {
1712                 return;
1713         }
1714
1715         /* Link object data evaluation node to exit operation. */
1716         OperationKey obdata_geom_eval_key(obdata, DEG_NODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Geometry Eval");
1717         OperationKey obdata_geom_done_key(obdata, DEG_NODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Eval Done");
1718         add_relation(obdata_geom_eval_key, obdata_geom_done_key, "ObData Geom Eval Done");
1719
1720         /* type-specific node/links */
1721         switch (object->type) {
1722                 case OB_MESH:
1723                         /* NOTE: This is compatibility code to support particle systems
1724                          *
1725                          * for viewport being properly rendered in final render mode.
1726                          * This relation is similar to what dag_object_time_update_flags()
1727                          * was doing for mesh objects with particle system.
1728                          *
1729                          * Ideally we need to get rid of this relation.
1730                          */
1731                         if (object_particles_depends_on_time(object)) {
1732                                 TimeSourceKey time_key;
1733                                 OperationKey obdata_ubereval_key(&object->id,
1734                                                                  DEG_NODE_TYPE_GEOMETRY,
1735                                                                  DEG_OPCODE_GEOMETRY_UBEREVAL);
1736                                 add_relation(time_key, obdata_ubereval_key, "Legacy particle time");
1737                         }
1738                         break;
1739
1740                 case OB_MBALL:
1741                 {
1742                         Object *mom = BKE_mball_basis_find(scene_, object);
1743                         ComponentKey mom_geom_key(&mom->id, DEG_NODE_TYPE_GEOMETRY);
1744                         /* motherball - mom depends on children! */
1745                         if (mom == object) {
1746                                 ComponentKey mom_transform_key(&mom->id,
1747                                                                DEG_NODE_TYPE_TRANSFORM);
1748                                 add_relation(mom_transform_key,
1749                                              mom_geom_key,
1750                                              "Metaball Motherball Transform -> Geometry");
1751                         }
1752                         else {
1753                                 ComponentKey transform_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
1754                                 add_relation(geom_key, mom_geom_key, "Metaball Motherball");
1755                                 add_relation(transform_key, mom_geom_key, "Metaball Motherball");
1756                         }
1757                         break;
1758                 }
1759
1760                 case OB_CURVE:
1761                 case OB_FONT:
1762                 {
1763                         Curve *cu = (Curve *)obdata;
1764
1765                         /* curve's dependencies */
1766                         // XXX: these needs geom data, but where is geom stored?
1767                         if (cu->bevobj) {
1768                                 ComponentKey bevob_key(&cu->bevobj->id, DEG_NODE_TYPE_GEOMETRY);
1769                                 build_object(NULL, cu->bevobj);
1770                                 add_relation(bevob_key, geom_key, "Curve Bevel");
1771                         }
1772                         if (cu->taperobj) {
1773                                 ComponentKey taperob_key(&cu->taperobj->id, DEG_NODE_TYPE_GEOMETRY);
1774                                 build_object(NULL, cu->taperobj);
1775                                 add_relation(taperob_key, geom_key, "Curve Taper");
1776                         }
1777                         if (object->type == OB_FONT) {
1778                                 if (cu->textoncurve) {
1779                                         ComponentKey textoncurve_key(&cu->textoncurve->id, DEG_NODE_TYPE_GEOMETRY);
1780                                         build_object(NULL, cu->textoncurve);
1781                                         add_relation(textoncurve_key, geom_key, "Text on Curve");
1782                                 }
1783                         }
1784                         break;
1785                 }
1786
1787                 case OB_SURF: /* Nurbs Surface */
1788                 {
1789                         break;
1790                 }
1791
1792                 case OB_LATTICE: /* Lattice */
1793                 {
1794                         break;
1795                 }
1796         }
1797
1798         /* ShapeKeys */
1799         Key *key = BKE_key_from_object(object);
1800         if (key) {
1801                 build_shapekeys(obdata, key);
1802         }
1803 }
1804
1805 /* Cameras */
1806 // TODO: Link scene-camera links in somehow...
1807 void DepsgraphRelationBuilder::build_camera(Object *object)
1808 {
1809         Camera *camera = (Camera *)object->data;
1810         if (built_map_.checkIsBuiltAndTag(camera)) {
1811                 return;
1812         }
1813
1814         ComponentKey object_parameters_key(&object->id, DEG_NODE_TYPE_PARAMETERS);
1815         ComponentKey camera_parameters_key(&camera->id, DEG_NODE_TYPE_PARAMETERS);
1816
1817         add_relation(camera_parameters_key, object_parameters_key,
1818                      "Camera -> Object");
1819
1820         /* DOF */
1821         if (camera->dof_ob != NULL) {
1822                 ComponentKey dof_ob_key(&camera->dof_ob->id, DEG_NODE_TYPE_TRANSFORM);
1823                 add_relation(dof_ob_key, object_parameters_key, "Camera DOF");
1824         }
1825 }
1826
1827 /* Lamps */
1828 void DepsgraphRelationBuilder::build_lamp(Object *object)
1829 {
1830         Lamp *lamp = (Lamp *)object->data;
1831         if (built_map_.checkIsBuiltAndTag(lamp)) {
1832                 return;
1833         }
1834
1835         ComponentKey object_parameters_key(&object->id, DEG_NODE_TYPE_PARAMETERS);
1836         ComponentKey lamp_parameters_key(&lamp->id, DEG_NODE_TYPE_PARAMETERS);
1837
1838         add_relation(lamp_parameters_key, object_parameters_key,
1839                      "Lamp -> Object");
1840
1841         /* lamp's nodetree */
1842         if (lamp->nodetree != NULL) {
1843                 build_nodetree(lamp->nodetree);
1844                 ComponentKey nodetree_key(&lamp->nodetree->id, DEG_NODE_TYPE_SHADING);
1845                 add_relation(nodetree_key, lamp_parameters_key, "NTree->Lamp Parameters");
1846         }
1847         /* textures */
1848         build_texture_stack(lamp->mtex);
1849
1850         if (DEG_depsgraph_use_copy_on_write()) {
1851                 /* Make sure copy on write of lamp data is always properly updated for
1852                  * visible lamps.
1853                  */
1854                 OperationKey ob_copy_on_write_key(&object->id,
1855                                                   DEG_NODE_TYPE_COPY_ON_WRITE,
1856                                                   DEG_OPCODE_COPY_ON_WRITE);
1857                 OperationKey lamp_copy_on_write_key(&lamp->id,
1858                                                     DEG_NODE_TYPE_COPY_ON_WRITE,
1859                                                     DEG_OPCODE_COPY_ON_WRITE);
1860                 add_relation(lamp_copy_on_write_key, ob_copy_on_write_key, "Eval Order");
1861         }
1862 }
1863
1864 void DepsgraphRelationBuilder::build_nodetree(bNodeTree *ntree)
1865 {
1866         if (ntree == NULL) {
1867                 return;
1868         }
1869         if (built_map_.checkIsBuiltAndTag(ntree)) {
1870                 return;
1871         }
1872         build_animdata(&ntree->id);
1873         ComponentKey shading_key(&ntree->id, DEG_NODE_TYPE_SHADING);
1874         /* nodetree's nodes... */
1875         LISTBASE_FOREACH (bNode *, bnode, &ntree->nodes) {
1876                 ID *id = bnode->id;
1877                 if (id == NULL) {
1878                         continue;
1879                 }
1880                 ID_Type id_type = GS(id->name);
1881                 if (id_type == ID_MA) {
1882                         build_material((Material *)bnode->id);
1883                 }
1884                 else if (id_type == ID_TE) {
1885                         build_texture((Tex *)bnode->id);
1886                 }
1887                 else if (id_type == ID_IM) {
1888                         /* nothing for now. */
1889                 }
1890                 else if (id_type == ID_OB) {
1891                         build_object(NULL, (Object *)id);
1892                 }
1893                 else if (id_type == ID_SCE) {
1894                         /* Scenes are used by compositor trees, and handled by render
1895                          * pipeline. No need to build dependencies for them here.
1896                          */
1897                 }
1898                 else if (id_type == ID_TXT) {
1899                         /* Ignore script nodes. */
1900                 }
1901                 else if (bnode->type == NODE_GROUP) {
1902                         bNodeTree *group_ntree = (bNodeTree *)id;
1903                         build_nodetree(group_ntree);
1904                         ComponentKey group_shading_key(&group_ntree->id,
1905                                                        DEG_NODE_TYPE_SHADING);
1906                         add_relation(group_shading_key, shading_key, "Group Node");
1907                 }
1908                 else {
1909                         BLI_assert(!"Unknown ID type used for node");
1910                 }
1911         }
1912
1913         OperationKey shading_update_key(&ntree->id,
1914                                         DEG_NODE_TYPE_SHADING,
1915                                         DEG_OPCODE_MATERIAL_UPDATE);
1916         OperationKey shading_parameters_key(&ntree->id,
1917                                             DEG_NODE_TYPE_SHADING_PARAMETERS,
1918                                             DEG_OPCODE_MATERIAL_UPDATE);
1919         add_relation(shading_parameters_key, shading_update_key, "NTree Shading Parameters");
1920 }
1921
1922 /* Recursively build graph for material */
1923 void DepsgraphRelationBuilder::build_material(Material *material)
1924 {
1925         if (built_map_.checkIsBuiltAndTag(material)) {
1926                 return;
1927         }
1928         /* animation */
1929         build_animdata(&material->id);
1930         /* textures */
1931         build_texture_stack(material->mtex);
1932         /* material's nodetree */
1933         if (material->nodetree != NULL) {
1934                 build_nodetree(material->nodetree);
1935                 OperationKey ntree_key(&material->nodetree->id,
1936                                        DEG_NODE_TYPE_SHADING,
1937                                        DEG_OPCODE_MATERIAL_UPDATE);
1938                 OperationKey material_key(&material->id,
1939                                           DEG_NODE_TYPE_SHADING,
1940                                           DEG_OPCODE_MATERIAL_UPDATE);
1941                 add_relation(ntree_key, material_key, "Material's NTree");
1942         }
1943 }
1944
1945 /* Recursively build graph for texture */
1946 void DepsgraphRelationBuilder::build_texture(Tex *texture)
1947 {
1948         if (built_map_.checkIsBuiltAndTag(texture)) {
1949                 return;
1950         }
1951         /* texture itself */
1952         build_animdata(&texture->id);
1953         /* texture's nodetree */
1954         build_nodetree(texture->nodetree);
1955 }
1956
1957 /* Texture-stack attached to some shading datablock */
1958 void DepsgraphRelationBuilder::build_texture_stack(MTex **texture_stack)
1959 {
1960         /* for now assume that all texture-stacks have same number of max items */
1961         for (int i = 0; i < MAX_MTEX; i++) {
1962                 MTex *mtex = texture_stack[i];
1963                 if (mtex && mtex->tex)
1964                         build_texture(mtex->tex);
1965         }
1966 }
1967
1968 void DepsgraphRelationBuilder::build_compositor(Scene *scene)
1969 {
1970         /* For now, just a plain wrapper? */
1971         build_nodetree(scene->nodetree);
1972 }
1973
1974 void DepsgraphRelationBuilder::build_gpencil(bGPdata *gpd)
1975 {
1976         /* animation */
1977         build_animdata(&gpd->id);
1978
1979         // TODO: parent object (when that feature is implemented)
1980 }
1981
1982 void DepsgraphRelationBuilder::build_cachefile(CacheFile *cache_file)
1983 {
1984         /* Animation. */
1985         build_animdata(&cache_file->id);
1986 }
1987
1988 void DepsgraphRelationBuilder::build_mask(Mask *mask)
1989 {
1990         ID *mask_id = &mask->id;
1991         /* F-Curve animation. */
1992         build_animdata(mask_id);
1993         /* Own mask animation. */
1994         OperationKey mask_animation_key(mask_id,
1995                                         DEG_NODE_TYPE_ANIMATION,
1996                                         DEG_OPCODE_MASK_ANIMATION);
1997         TimeSourceKey time_src_key;
1998         add_relation(time_src_key, mask_animation_key, "TimeSrc -> Mask Animation");
1999         /* Final mask evaluation. */
2000         ComponentKey parameters_key(mask_id, DEG_NODE_TYPE_PARAMETERS);
2001         add_relation(mask_animation_key, parameters_key, "Mask Animation -> Mask Eval");
2002 }
2003
2004 void DepsgraphRelationBuilder::build_movieclip(MovieClip *clip)
2005 {
2006         /* Animation. */
2007         build_animdata(&clip->id);
2008 }
2009
2010 void DepsgraphRelationBuilder::build_lightprobe(Object *object)
2011 {
2012         LightProbe *probe = (LightProbe *)object->data;
2013         if (built_map_.checkIsBuiltAndTag(probe)) {
2014                 return;
2015         }
2016         build_animdata(&probe->id);
2017
2018         OperationKey probe_key(&probe->id,
2019                                DEG_NODE_TYPE_PARAMETERS,
2020                                DEG_OPCODE_PLACEHOLDER,
2021                                "LightProbe Eval");
2022         OperationKey object_key(&object->id,
2023                                 DEG_NODE_TYPE_PARAMETERS,
2024                                 DEG_OPCODE_PLACEHOLDER,
2025                                 "LightProbe Eval");
2026         add_relation(probe_key, object_key, "LightProbe Update");
2027 }
2028
2029 void DepsgraphRelationBuilder::build_copy_on_write_relations()
2030 {
2031         foreach (IDDepsNode *id_node, graph_->id_nodes) {
2032                 build_copy_on_write_relations(id_node);
2033         }
2034 }
2035
2036 void DepsgraphRelationBuilder::build_copy_on_write_relations(IDDepsNode *id_node)
2037 {
2038         ID *id_orig = id_node->id_orig;
2039
2040         TimeSourceKey time_source_key;
2041         OperationKey copy_on_write_key(id_orig,
2042                                        DEG_NODE_TYPE_COPY_ON_WRITE,
2043                                        DEG_OPCODE_COPY_ON_WRITE);
2044         /* XXX: This is a quick hack to make Alt-A to work. */
2045         // add_relation(time_source_key, copy_on_write_key, "Fluxgate capacitor hack");
2046         /* Resat of code is using rather low level trickery, so need to get some
2047          * explicit pointers.
2048          */
2049         DepsNode *node_cow = find_node(copy_on_write_key);
2050         OperationDepsNode *op_cow = node_cow->get_exit_operation();
2051         /* Plug any other components to this one. */
2052         GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, id_node->components)
2053         {
2054                 if (comp_node->type == DEG_NODE_TYPE_COPY_ON_WRITE) {
2055                         /* Copy-on-write component never depends on itself. */
2056                         continue;
2057                 }
2058                 if (!comp_node->depends_on_cow()) {
2059                         /* Component explicitly requests to not add relation. */
2060                         continue;
2061                 }
2062                 /* All entry operations of each component should wait for a proper
2063                  * copy of ID.
2064                  */
2065                 OperationDepsNode *op_entry = comp_node->get_entry_operation();
2066                 if (op_entry != NULL) {
2067                         graph_->add_new_relation(op_cow, op_entry, "CoW Dependency");
2068                 }
2069                 /* All dangling operations should also be executed after copy-on-write. */
2070                 GHASH_FOREACH_BEGIN(OperationDepsNode *, op_node, comp_node->operations_map)
2071                 {
2072                         if (op_node->inlinks.size() == 0) {
2073                                 graph_->add_new_relation(op_cow, op_node, "CoW Dependency");
2074                         }
2075                         else {
2076                                 bool has_same_id_dependency = false;
2077                                 foreach (DepsRelation *rel, op_node->inlinks) {
2078                                         if (rel->from->type != DEG_NODE_TYPE_OPERATION) {
2079                                                 continue;
2080                                         }
2081                                         OperationDepsNode *op_node_from = (OperationDepsNode *)rel->from;
2082                                         if (op_node_from->owner->owner == op_node->owner->owner) {
2083                                                 has_same_id_dependency = true;
2084                                                 break;
2085                                         }
2086                                 }
2087                                 if (!has_same_id_dependency) {
2088                                         graph_->add_new_relation(op_cow, op_node, "CoW Dependency");
2089                                 }
2090                         }
2091                 }
2092                 GHASH_FOREACH_END();
2093                 /* NOTE: We currently ignore implicit relations to an external
2094                  * datablocks for copy-on-write operations. This means, for example,
2095                  * copy-on-write component of Object will not wait for copy-on-write
2096                  * component of it's Mesh. This is because pointers are all known
2097                  * already so remapping will happen all correct. And then If some object
2098                  * evaluation step needs geometry, it will have transitive dependency
2099                  * to Mesh copy-on-write already.
2100                  */
2101         }
2102         GHASH_FOREACH_END();
2103         /* TODO(sergey): This solves crash for now, but causes too many
2104          * updates potentially.
2105          */
2106         if (GS(id_orig->name) == ID_OB) {
2107                 Object *object = (Object *)id_orig;
2108                 ID *object_data_id = (ID *)object->data;
2109                 if (object_data_id != NULL) {
2110                         OperationKey data_copy_on_write_key(object_data_id,
2111                                                             DEG_NODE_TYPE_COPY_ON_WRITE,
2112                                                             DEG_OPCODE_COPY_ON_WRITE);
2113                         add_relation(data_copy_on_write_key, copy_on_write_key, "Eval Order");
2114                 }
2115                 else {
2116                         BLI_assert(object->type == OB_EMPTY);
2117                 }
2118         }
2119 }
2120
2121 }  // namespace DEG