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