source/blender/depsgraph/intern/depsgraph_build.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/depsgraph_build.cc
  28  *  \ingroup depsgraph
  29  *
  30  * Methods for constructing depsgraph.
  31  */
  32
  33 #include "MEM_guardedalloc.h"
  34
  35 // #define DEBUG_TIME
  36
  37 #include "BLI_utildefines.h"
  38 #include "BLI_ghash.h"
  39 #include "BLI_listbase.h"
  40
  41 #ifdef DEBUG_TIME
  42 #  include "PIL_time.h"
  43 #  include "PIL_time_utildefines.h"
  44 #endif
  45
  46 extern "C" {
  47 #include "DNA_cachefile_types.h"
  48 #include "DNA_object_types.h"
  49 #include "DNA_scene_types.h"
  50 #include "DNA_object_force.h"
  51
  52 #include "BKE_main.h"
  53 #include "BKE_collision.h"
  54 #include "BKE_effect.h"
  55 #include "BKE_modifier.h"
  56 #include "BKE_scene.h"
  57 } /* extern "C" */
  58
  59 #include "DEG_depsgraph.h"
  60 #include "DEG_depsgraph_debug.h"
  61 #include "DEG_depsgraph_build.h"
  62
  63 #include "builder/deg_builder.h"
  64 #include "builder/deg_builder_cycle.h"
  65 #include "builder/deg_builder_nodes.h"
  66 #include "builder/deg_builder_relations.h"
  67 #include "builder/deg_builder_transitive.h"
  68
  69 #include "intern/nodes/deg_node.h"
  70 #include "intern/nodes/deg_node_component.h"
  71 #include "intern/nodes/deg_node_id.h"
  72 #include "intern/nodes/deg_node_operation.h"
  73
  74 #include "intern/depsgraph_types.h"
  75 #include "intern/depsgraph_intern.h"
  76
  77 #include "util/deg_util_foreach.h"
  78
  79 /* ****************** */
  80 /* External Build API */
  81
  82 static DEG::eDepsNode_Type deg_build_scene_component_type(
  83         eDepsSceneComponentType component)
  84 {
  85         switch (component) {
  86                 case DEG_SCENE_COMP_PARAMETERS:     return DEG::DEG_NODE_TYPE_PARAMETERS;
  87                 case DEG_SCENE_COMP_ANIMATION:      return DEG::DEG_NODE_TYPE_ANIMATION;
  88                 case DEG_SCENE_COMP_SEQUENCER:      return DEG::DEG_NODE_TYPE_SEQUENCER;
  89         }
  90         return DEG::DEG_NODE_TYPE_UNDEFINED;
  91 }
  92
  93 static DEG::eDepsNode_Type deg_build_object_component_type(
  94         eDepsObjectComponentType component)
  95 {
  96         switch (component) {
  97                 case DEG_OB_COMP_PARAMETERS:        return DEG::DEG_NODE_TYPE_PARAMETERS;
  98                 case DEG_OB_COMP_PROXY:             return DEG::DEG_NODE_TYPE_PROXY;
  99                 case DEG_OB_COMP_ANIMATION:         return DEG::DEG_NODE_TYPE_ANIMATION;
 100                 case DEG_OB_COMP_TRANSFORM:         return DEG::DEG_NODE_TYPE_TRANSFORM;
 101                 case DEG_OB_COMP_GEOMETRY:          return DEG::DEG_NODE_TYPE_GEOMETRY;
 102                 case DEG_OB_COMP_EVAL_POSE:         return DEG::DEG_NODE_TYPE_EVAL_POSE;
 103                 case DEG_OB_COMP_BONE:              return DEG::DEG_NODE_TYPE_BONE;
 104                 case DEG_OB_COMP_EVAL_PARTICLES:    return DEG::DEG_NODE_TYPE_EVAL_PARTICLES;
 105                 case DEG_OB_COMP_SHADING:           return DEG::DEG_NODE_TYPE_SHADING;
 106                 case DEG_OB_COMP_CACHE:             return DEG::DEG_NODE_TYPE_CACHE;
 107         }
 108         return DEG::DEG_NODE_TYPE_UNDEFINED;
 109 }
 110
 111 static DEG::DepsNodeHandle *get_handle(DepsNodeHandle *handle)
 112 {
 113         return reinterpret_cast<DEG::DepsNodeHandle *>(handle);
 114 }
 115
 116 void DEG_add_scene_relation(DepsNodeHandle *handle,
 117                             Scene *scene,
 118                             eDepsSceneComponentType component,
 119                             const char *description)
 120 {
 121         DEG::eDepsNode_Type type = deg_build_scene_component_type(component);
 122         DEG::ComponentKey comp_key(&scene->id, type);
 123         DEG::DepsNodeHandle *deg_handle = get_handle(handle);
 124         deg_handle->builder->add_node_handle_relation(comp_key,
 125                                                       deg_handle,
 126                                                       description);
 127 }
 128
 129 void DEG_add_object_relation(DepsNodeHandle *handle,
 130                              Object *object,
 131                              eDepsObjectComponentType component,
 132                              const char *description)
 133 {
 134         DEG::eDepsNode_Type type = deg_build_object_component_type(component);
 135         DEG::ComponentKey comp_key(&object->id, type);
 136         DEG::DepsNodeHandle *deg_handle = get_handle(handle);
 137         deg_handle->builder->add_node_handle_relation(comp_key,
 138                                                       deg_handle,
 139                                                       description);
 140 }
 141
 142 void DEG_add_object_cache_relation(DepsNodeHandle *handle,
 143                                    CacheFile *cache_file,
 144                                    eDepsObjectComponentType component,
 145                                    const char *description)
 146 {
 147         DEG::eDepsNode_Type type = deg_build_object_component_type(component);
 148         DEG::ComponentKey comp_key(&cache_file->id, type);
 149         DEG::DepsNodeHandle *deg_handle = get_handle(handle);
 150         deg_handle->builder->add_node_handle_relation(comp_key,
 151                                                       deg_handle,
 152                                                       description);
 153 }
 154
 155 void DEG_add_bone_relation(DepsNodeHandle *handle,
 156                            Object *object,
 157                            const char *bone_name,
 158                            eDepsObjectComponentType component,
 159                            const char *description)
 160 {
 161         DEG::eDepsNode_Type type = deg_build_object_component_type(component);
 162         DEG::ComponentKey comp_key(&object->id, type, bone_name);
 163         DEG::DepsNodeHandle *deg_handle = get_handle(handle);
 164         /* XXX: "Geometry Eval" might not always be true, but this only gets called
 165          * from modifier building now.
 166          */
 167         deg_handle->builder->add_node_handle_relation(comp_key,
 168                                                       deg_handle,
 169                                                       description);
 170 }
 171
 172 struct Depsgraph *DEG_get_graph_from_handle(struct DepsNodeHandle *handle)
 173 {
 174         DEG::DepsNodeHandle *deg_handle = get_handle(handle);
 175         DEG::DepsgraphRelationBuilder *relation_builder = deg_handle->builder;
 176         return reinterpret_cast<Depsgraph *>(relation_builder->getGraph());
 177 }
 178
 179 void DEG_add_special_eval_flag(Depsgraph *graph, ID *id, short flag)
 180 {
 181         DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph);
 182         if (graph == NULL) {
 183                 BLI_assert(!"Graph should always be valid");
 184                 return;
 185         }
 186         DEG::IDDepsNode *id_node = deg_graph->find_id_node(id);
 187         if (id_node == NULL) {
 188                 BLI_assert(!"ID should always be valid");
 189                 return;
 190         }
 191         id_node->eval_flags |= flag;
 192 }
 193
 194 /* ******************** */
 195 /* Graph Building API's */
 196
 197 /* Build depsgraph for the given scene layer, and dump results in given
 198  * graph container.
 199  */
 200 void DEG_graph_build_from_view_layer(Depsgraph *graph,
 201                                       Main *bmain,
 202                                       Scene *scene,
 203                                       ViewLayer *view_layer)
 204 {
 205 #ifdef DEBUG_TIME
 206         TIMEIT_START(DEG_graph_build_from_view_layer);
 207 #endif
 208
 209         DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph);
 210         BLI_assert(BLI_findindex(&scene->view_layers, view_layer) != -1);
 211
 212         /* TODO(sergey): This is a bit tricky, but ensures that all the data
 213          * is evaluated properly when depsgraph is becoming "visible".
 214          *
 215          * This now could happen for both visible scene is changed and extra
 216          * dependency graph was created for render engine.
 217          */
 218         const bool need_on_visible_update = (deg_graph->scene == NULL);
 219
 220         /* 1) Generate all the nodes in the graph first */
 221         DEG::DepsgraphNodeBuilder node_builder(bmain, deg_graph);
 222         node_builder.begin_build();
 223         node_builder.build_view_layer(scene,
 224                                        view_layer,
 225                                        DEG::DEG_ID_LINKED_DIRECTLY);
 226         node_builder.end_build();
 227
 228         /* 2) Hook up relationships between operations - to determine evaluation
 229          *    order.
 230          */
 231         DEG::DepsgraphRelationBuilder relation_builder(bmain, deg_graph);
 232         relation_builder.begin_build();
 233         relation_builder.build_view_layer(scene, view_layer);
 234         if (DEG_depsgraph_use_copy_on_write()) {
 235                 relation_builder.build_copy_on_write_relations();
 236         }
 237
 238         /* Detect and solve cycles. */
 239         DEG::deg_graph_detect_cycles(deg_graph);
 240
 241         /* 3) Simplify the graph by removing redundant relations (to optimize
 242          *    traversal later). */
 243         /* TODO: it would be useful to have an option to disable this in cases where
 244          *       it is causing trouble.
 245          */
 246         if (G.debug_value == 799) {
 247                 DEG::deg_graph_transitive_reduction(deg_graph);
 248         }
 249
 250         /* 4) Flush visibility layer and re-schedule nodes for update. */
 251         DEG::deg_graph_build_finalize(bmain, deg_graph);
 252
 253 #if 0
 254         if (!DEG_debug_consistency_check(deg_graph)) {
 255                 printf("Consistency validation failed, ABORTING!\n");
 256                 abort();
 257         }
 258 #endif
 259
 260 #ifdef DEBUG_TIME
 261         TIMEIT_END(DEG_graph_build_from_view_layer);
 262 #endif
 263
 264         /* Relations are up to date. */
 265         deg_graph->need_update = false;
 266
 267         if (need_on_visible_update) {
 268                 DEG_graph_on_visible_update(bmain, graph);
 269         }
 270 }
 271
 272 /* Tag graph relations for update. */
 273 void DEG_graph_tag_relations_update(Depsgraph *graph)
 274 {
 275         DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph);
 276         deg_graph->need_update = true;
 277 }
 278
 279 /* Create or update relations in the specified graph. */
 280 void DEG_graph_relations_update(Depsgraph *graph,
 281                                 Main *bmain,
 282                                 Scene *scene,
 283                                 ViewLayer *view_layer)
 284 {
 285         DEG::Depsgraph *deg_graph = (DEG::Depsgraph *)graph;
 286         if (!deg_graph->need_update) {
 287                 /* Graph is up to date, nothing to do. */
 288                 return;
 289         }
 290         DEG_graph_build_from_view_layer(graph, bmain, scene, view_layer);
 291 }
 292
 293 /* Tag all relations for update. */
 294 void DEG_relations_tag_update(Main *bmain)
 295 {
 296         DEG_DEBUG_PRINTF("%s: Tagging relations for update.\n", __func__);
 297         LINKLIST_FOREACH(Scene *, scene, &bmain->scene) {
 298                 LINKLIST_FOREACH(ViewLayer *, view_layer, &scene->view_layers) {
 299                         Depsgraph *depsgraph =
 300                                 (Depsgraph *)BKE_scene_get_depsgraph(scene,
 301                                                                      view_layer,
 302                                                                      false);
 303                         if (depsgraph != NULL) {
 304                                 DEG_graph_tag_relations_update(depsgraph);
 305                         }
 306                 }
 307         }
 308 }
 309
 310 void DEG_add_collision_relations(DepsNodeHandle *handle,
 311                                  Scene *scene,
 312                                  Object *object,
 313                                  Group *group,
 314                                  unsigned int modifier_type,
 315                                  DEG_CollobjFilterFunction fn,
 316                                  bool dupli,
 317                                  const char *name)
 318 {
 319         unsigned int numcollobj;
 320         Object **collobjs = get_collisionobjects_ext(scene, object, group, &numcollobj, modifier_type, dupli);
 321
 322         for (unsigned int i = 0; i < numcollobj; i++) {
 323                 Object *ob1 = collobjs[i];
 324
 325                 if (!fn || fn(ob1, modifiers_findByType(ob1, (ModifierType)modifier_type))) {
 326                         DEG_add_object_relation(handle, ob1, DEG_OB_COMP_TRANSFORM, name);
 327                         DEG_add_object_relation(handle, ob1, DEG_OB_COMP_GEOMETRY, name);
 328                 }
 329         }
 330
 331         if (collobjs)
 332                 MEM_freeN(collobjs);
 333 }
 334
 335 void DEG_add_forcefield_relations(DepsNodeHandle *handle,
 336                                   Scene *scene,
 337                                   Object *object,
 338                                   EffectorWeights *effector_weights,
 339                                   bool add_absorption,
 340                                   int skip_forcefield,
 341                                   const char *name)
 342 {
 343         ListBase *effectors = pdInitEffectors(NULL, scene, object, NULL, effector_weights, false);
 344
 345         if (effectors) {
 346                 for (EffectorCache *eff = (EffectorCache*)effectors->first; eff; eff = eff->next) {
 347                         if (eff->ob != object && eff->pd->forcefield != skip_forcefield) {
 348                                 DEG_add_object_relation(handle, eff->ob, DEG_OB_COMP_TRANSFORM, name);
 349
 350                                 if (eff->psys) {
 351                                         DEG_add_object_relation(handle, eff->ob, DEG_OB_COMP_EVAL_PARTICLES, name);
 352
 353                                         /* TODO: remove this when/if EVAL_PARTICLES is sufficient
 354                                          * for up to date particles.
 355                                          */
 356                                         DEG_add_object_relation(handle, eff->ob, DEG_OB_COMP_GEOMETRY, name);
 357                                 }
 358
 359                                 if (eff->pd->forcefield == PFIELD_SMOKEFLOW && eff->pd->f_source) {
 360                                         DEG_add_object_relation(handle,
 361                                                                 eff->pd->f_source,
 362                                                                 DEG_OB_COMP_TRANSFORM,
 363                                                                 "Smoke Force Domain");
 364                                         DEG_add_object_relation(handle,
 365                                                                 eff->pd->f_source,
 366                                                                 DEG_OB_COMP_GEOMETRY,
 367                                                                 "Smoke Force Domain");
 368                                 }
 369
 370                                 if (add_absorption && (eff->pd->flag & PFIELD_VISIBILITY)) {
 371                                         DEG_add_collision_relations(handle,
 372                                                                     scene,
 373                                                                     object,
 374                                                                     NULL,
 375                                                                     eModifierType_Collision,
 376                                                                     NULL,
 377                                                                     true,
 378                                                                     "Force Absorption");
 379                                 }
 380                         }
 381                 }
 382         }
 383
 384         pdEndEffectors(&effectors);
 385 }