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