Merge branch 'master' into blender2.8
[blender.git] / source / blender / depsgraph / intern / eval / deg_eval_flush.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): None Yet
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/depsgraph/intern/eval/deg_eval_flush.cc
28  *  \ingroup depsgraph
29  *
30  * Core routines for how the Depsgraph works.
31  */
32
33 #include "intern/eval/deg_eval_flush.h"
34
35 // TODO(sergey): Use some sort of wrapper.
36 #include <deque>
37
38 #include "BLI_utildefines.h"
39 #include "BLI_task.h"
40 #include "BLI_ghash.h"
41
42 extern "C" {
43 #include "DNA_object_types.h"
44 } /* extern "C" */
45
46 #include "DEG_depsgraph.h"
47
48 #include "intern/nodes/deg_node.h"
49 #include "intern/nodes/deg_node_component.h"
50 #include "intern/nodes/deg_node_id.h"
51 #include "intern/nodes/deg_node_operation.h"
52
53 #include "intern/depsgraph_intern.h"
54 #include "intern/eval/deg_eval_copy_on_write.h"
55 #include "util/deg_util_foreach.h"
56
57 namespace DEG {
58
59 enum {
60         ID_STATE_NONE     = 0,
61         ID_STATE_MODIFIED = 1,
62 };
63
64 enum {
65         COMPONENT_STATE_NONE      = 0,
66         COMPONENT_STATE_SCHEDULED = 1,
67         COMPONENT_STATE_DONE      = 2,
68 };
69
70 typedef std::deque<OperationDepsNode *> FlushQueue;
71
72 namespace {
73
74 void flush_init_operation_node_func(
75         void *__restrict data_v,
76         const int i,
77         const ParallelRangeTLS *__restrict /*tls*/)
78 {
79         Depsgraph *graph = (Depsgraph *)data_v;
80         OperationDepsNode *node = graph->operations[i];
81         node->scheduled = false;
82 }
83
84 void flush_init_id_node_func(
85         void *__restrict data_v,
86         const int i,
87         const ParallelRangeTLS *__restrict /*tls*/)
88 {
89         Depsgraph *graph = (Depsgraph *)data_v;
90         IDDepsNode *id_node = graph->id_nodes[i];
91         id_node->done = ID_STATE_NONE;
92         GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, id_node->components)
93                 comp_node->done = COMPONENT_STATE_NONE;
94         GHASH_FOREACH_END();
95 }
96
97 BLI_INLINE void flush_prepare(Depsgraph *graph)
98 {
99         {
100                 const int num_operations = graph->operations.size();
101                 ParallelRangeSettings settings;
102                 BLI_parallel_range_settings_defaults(&settings);
103                 settings.use_threading = (num_operations > 256);
104                 BLI_task_parallel_range(0, num_operations,
105                                         graph,
106                                         flush_init_operation_node_func,
107                                         &settings);
108         }
109         {
110                 const int num_id_nodes = graph->id_nodes.size();
111                 ParallelRangeSettings settings;
112                 BLI_parallel_range_settings_defaults(&settings);
113                 settings.use_threading = (num_id_nodes > 256);
114                 BLI_task_parallel_range(0, num_id_nodes,
115                                         graph,
116                                         flush_init_id_node_func,
117                                         &settings);
118         }
119 }
120
121 BLI_INLINE void flush_schedule_entrypoints(Depsgraph *graph, FlushQueue *queue)
122 {
123         GSET_FOREACH_BEGIN(OperationDepsNode *, op_node, graph->entry_tags)
124         {
125                 queue->push_back(op_node);
126                 op_node->scheduled = true;
127         }
128         GSET_FOREACH_END();
129 }
130
131 BLI_INLINE void flush_handle_id_node(IDDepsNode *id_node)
132 {
133         id_node->done = ID_STATE_MODIFIED;
134 }
135
136 /* TODO(sergey): We can reduce number of arguments here. */
137 BLI_INLINE void flush_handle_component_node(Depsgraph *graph,
138                                             IDDepsNode *id_node,
139                                             ComponentDepsNode *comp_node,
140                                             bool use_copy_on_write,
141                                             FlushQueue *queue)
142 {
143         /* We only handle component once. */
144         if (comp_node->done == COMPONENT_STATE_DONE) {
145                 return;
146         }
147         comp_node->done = COMPONENT_STATE_DONE;
148         /* Currently this is needed to get object->mesh to be replaced with
149          * original mesh (rather than being evaluated_mesh).
150          *
151          * TODO(sergey): This is something we need to avoid.
152          */
153         if (use_copy_on_write && comp_node->depends_on_cow()) {
154                 ComponentDepsNode *cow_comp =
155                         id_node->find_component(DEG_NODE_TYPE_COPY_ON_WRITE);
156                 cow_comp->tag_update(graph);
157         }
158         /* Tag all required operations in component for update.  */
159         foreach (OperationDepsNode *op, comp_node->operations) {
160                 /* We don't want to flush tags in "upstream" direction for
161                  * certain types of operations.
162                  *
163                  * TODO(sergey): Need a more generic solution for this.
164                  */
165                 if (op->opcode == DEG_OPCODE_PARTICLE_SETTINGS_EVAL) {
166                         continue;
167                 }
168                 op->flag |= DEPSOP_FLAG_NEEDS_UPDATE;
169         }
170         /* When some target changes bone, we might need to re-run the
171          * whole IK solver, otherwise result might be unpredictable.
172          */
173         if (comp_node->type == DEG_NODE_TYPE_BONE) {
174                 ComponentDepsNode *pose_comp =
175                         id_node->find_component(DEG_NODE_TYPE_EVAL_POSE);
176                 BLI_assert(pose_comp != NULL);
177                 if (pose_comp->done == COMPONENT_STATE_NONE) {
178                         queue->push_front(pose_comp->get_entry_operation());
179                         pose_comp->done = COMPONENT_STATE_SCHEDULED;
180                 }
181         }
182 }
183
184 /* Schedule children of the given operation node for traversal.
185  *
186  * One of the children will by-pass the queue and will be returned as a function
187  * return value, so it can start being handled right away, without building too
188  * much of a queue.
189  */
190 BLI_INLINE OperationDepsNode *flush_schedule_children(
191         OperationDepsNode *op_node,
192         FlushQueue *queue)
193 {
194         OperationDepsNode *result = NULL;
195         foreach (DepsRelation *rel, op_node->outlinks) {
196                 OperationDepsNode *to_node = (OperationDepsNode *)rel->to;
197                 if (to_node->scheduled == false) {
198                         if (result != NULL) {
199                                 queue->push_front(to_node);
200                         }
201                         else {
202                                 result = to_node;
203                         }
204                         to_node->scheduled = true;
205                 }
206         }
207         return result;
208 }
209
210 /* NOTE: It will also accumulate flags from changed components. */
211 BLI_INLINE void flush_editors_id_update(Main *bmain,
212                                         Depsgraph *graph,
213                                         const DEGEditorUpdateContext *update_ctx)
214 {
215         foreach (IDDepsNode *id_node, graph->id_nodes) {
216                 if (id_node->done != ID_STATE_MODIFIED) {
217                         continue;
218                 }
219                 DEG_id_type_tag(bmain, GS(id_node->id_orig->name));
220                 /* TODO(sergey): Do we need to pass original or evaluated ID here? */
221                 ID *id_orig = id_node->id_orig;
222                 ID *id_cow = id_node->id_cow;
223                 /* Copy tag from original data to CoW storage.
224                  * This is because DEG_id_tag_update() sets tags on original
225                  * data.
226                  */
227                 id_cow->recalc |= (id_orig->recalc & ID_RECALC_ALL);
228                 /* Gather recalc flags from all changed components. */
229                 GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, id_node->components)
230                 {
231                         if (comp_node->done != COMPONENT_STATE_DONE) {
232                                 continue;
233                         }
234                         DepsNodeFactory *factory = deg_type_get_factory(comp_node->type);
235                         BLI_assert(factory != NULL);
236                         id_cow->recalc |= factory->id_recalc_tag();
237                 }
238                 GHASH_FOREACH_END();
239                 DEG_DEBUG_PRINTF("Accumulated recalc bits for %s: %u\n",
240                                  id_orig->name, (unsigned int)id_cow->recalc);
241                 /* Inform editors. */
242                 if (deg_copy_on_write_is_expanded(id_cow)) {
243                         deg_editors_id_update(update_ctx, id_cow);
244                 }
245         }
246 }
247
248 }  // namespace
249
250 /* Flush updates from tagged nodes outwards until all affected nodes
251  * are tagged.
252  */
253 void deg_graph_flush_updates(Main *bmain, Depsgraph *graph)
254 {
255         const bool use_copy_on_write = DEG_depsgraph_use_copy_on_write();
256         /* Sanity checks. */
257         BLI_assert(bmain != NULL);
258         BLI_assert(graph != NULL);
259         /* Nothing to update, early out. */
260         if (BLI_gset_size(graph->entry_tags) == 0) {
261                 return;
262         }
263         /* Reset all flags, get ready for the flush. */
264         flush_prepare(graph);
265         /* Starting from the tagged "entry" nodes, flush outwards. */
266         FlushQueue queue;
267         flush_schedule_entrypoints(graph, &queue);
268         /* Prepare update context for editors. */
269         DEGEditorUpdateContext update_ctx;
270         update_ctx.bmain = bmain;
271         update_ctx.scene = graph->scene;
272         update_ctx.view_layer = graph->view_layer;
273         /* Do actual flush. */
274         while (!queue.empty()) {
275                 OperationDepsNode *op_node = queue.front();
276                 queue.pop_front();
277                 while (op_node != NULL) {
278                         /* Tag operation as required for update. */
279                         op_node->flag |= DEPSOP_FLAG_NEEDS_UPDATE;
280                         /* Inform corresponding ID and component nodes about the change. */
281                         ComponentDepsNode *comp_node = op_node->owner;
282                         IDDepsNode *id_node = comp_node->owner;
283                         flush_handle_id_node(id_node);
284                         flush_handle_component_node(graph,
285                                                     id_node,
286                                                     comp_node,
287                                                     use_copy_on_write,
288                                                     &queue);
289                         /* Flush to nodes along links. */
290                         op_node = flush_schedule_children(op_node, &queue);
291                 }
292         }
293         /* Inform editors about all changes. */
294         flush_editors_id_update(bmain, graph, &update_ctx);
295 }
296
297 static void graph_clear_func(
298         void *__restrict data_v,
299         const int i,
300         const ParallelRangeTLS *__restrict /*tls*/)
301 {
302         Depsgraph *graph = (Depsgraph *)data_v;
303         OperationDepsNode *node = graph->operations[i];
304         /* Clear node's "pending update" settings. */
305         node->flag &= ~(DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE);
306 }
307
308 /* Clear tags from all operation nodes. */
309 void deg_graph_clear_tags(Depsgraph *graph)
310 {
311         /* Go over all operation nodes, clearing tags. */
312         const int num_operations = graph->operations.size();
313         const bool do_threads = num_operations > 256;
314         ParallelRangeSettings settings;
315         BLI_parallel_range_settings_defaults(&settings);
316         settings.use_threading = do_threads;
317         BLI_task_parallel_range(0, num_operations,
318                                 graph,
319                                 graph_clear_func,
320                                 &settings);
321         /* Clear any entry tags which haven't been flushed. */
322         BLI_gset_clear(graph->entry_tags, NULL);
323 }
324
325 }  // namespace DEG