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