Merge branch 'master' into blender2.8
[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 // #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 }