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