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