source/blender/depsgraph/intern/builder/deg_builder_relations.cc

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