Subsurf: Allow partial threading over geometry arrays
[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 "util/deg_util_foreach.h"
55
56 namespace DEG {
57
58 enum {
59         ID_STATE_NONE     = 0,
60         ID_STATE_MODIFIED = 1,
61 };
62
63 enum {
64         COMPONENT_STATE_NONE      = 0,
65         COMPONENT_STATE_SCHEDULED = 1,
66         COMPONENT_STATE_DONE      = 2,
67 };
68
69 typedef std::deque<OperationDepsNode *> FlushQueue;
70
71 namespace {
72
73 // TODO(sergey): De-duplicate with depsgraph_tag,cc
74 void lib_id_recalc_tag(Main *bmain, ID *id)
75 {
76         id->recalc |= ID_RECALC;
77         DEG_id_type_tag(bmain, GS(id->name));
78 }
79
80 void lib_id_recalc_data_tag(Main *bmain, ID *id)
81 {
82         id->recalc |= ID_RECALC_DATA;
83         DEG_id_type_tag(bmain, GS(id->name));
84 }
85
86 void flush_init_operation_node_func(
87         void *__restrict data_v,
88         const int i,
89         const ParallelRangeTLS *__restrict /*tls*/)
90 {
91         Depsgraph *graph = (Depsgraph *)data_v;
92         OperationDepsNode *node = graph->operations[i];
93         node->scheduled = false;
94 }
95
96 void flush_init_id_node_func(
97         void *__restrict data_v,
98         const int i,
99         const ParallelRangeTLS *__restrict /*tls*/)
100 {
101         Depsgraph *graph = (Depsgraph *)data_v;
102         IDDepsNode *id_node = graph->id_nodes[i];
103         id_node->done = ID_STATE_NONE;
104         GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, id_node->components)
105                 comp_node->done = COMPONENT_STATE_NONE;
106         GHASH_FOREACH_END();
107 }
108
109 BLI_INLINE void flush_prepare(Depsgraph *graph)
110 {
111         {
112                 const int num_operations = graph->operations.size();
113                 ParallelRangeSettings settings;
114                 BLI_parallel_range_settings_defaults(&settings);
115                 settings.min_iter_per_thread = 1024;
116                 BLI_task_parallel_range(0, num_operations,
117                                         graph,
118                                         flush_init_operation_node_func,
119                                         &settings);
120         }
121         {
122                 const int num_id_nodes = graph->id_nodes.size();
123                 ParallelRangeSettings settings;
124                 BLI_parallel_range_settings_defaults(&settings);
125                 settings.min_iter_per_thread = 1024;
126                 BLI_task_parallel_range(0, num_id_nodes,
127                                         graph,
128                                         flush_init_id_node_func,
129                                         &settings);
130         }
131 }
132
133 BLI_INLINE void flush_schedule_entrypoints(Depsgraph *graph, FlushQueue *queue)
134 {
135         GSET_FOREACH_BEGIN(OperationDepsNode *, op_node, graph->entry_tags)
136         {
137                 queue->push_back(op_node);
138                 op_node->scheduled = true;
139         }
140         GSET_FOREACH_END();
141 }
142
143 BLI_INLINE void flush_handle_id_node(IDDepsNode *id_node)
144 {
145         id_node->done = ID_STATE_MODIFIED;
146 }
147
148 /* TODO(sergey): We can reduce number of arguments here. */
149 BLI_INLINE void flush_handle_component_node(Depsgraph * /*graph*/,
150                                             IDDepsNode *id_node,
151                                             ComponentDepsNode *comp_node,
152                                             FlushQueue *queue)
153 {
154         /* We only handle component once. */
155         if (comp_node->done == COMPONENT_STATE_DONE) {
156                 return;
157         }
158         comp_node->done = COMPONENT_STATE_DONE;
159         /* Tag all required operations in component for update.  */
160         foreach (OperationDepsNode *op, comp_node->operations) {
161                 op->flag |= DEPSOP_FLAG_NEEDS_UPDATE;
162         }
163         if (GS(id_node->id->name) == ID_OB) {
164                 Object *object = (Object *)id_node->id;
165                 /* This code is used to preserve those areas which does
166                  * direct object update,
167                  *
168                  * Plus it ensures visibility changes and relations and
169                  * layers visibility update has proper flags to work with.
170                  */
171                 switch (comp_node->type) {
172                         case DEG_NODE_TYPE_UNDEFINED:
173                         case DEG_NODE_TYPE_OPERATION:
174                         case DEG_NODE_TYPE_TIMESOURCE:
175                         case DEG_NODE_TYPE_ID_REF:
176                         case DEG_NODE_TYPE_SEQUENCER:
177                         case NUM_DEG_NODE_TYPES:
178                                 /* Ignore, does not translate to object component. */
179                                 BLI_assert(!"This should never happen!");
180                                 break;
181                         case DEG_NODE_TYPE_ANIMATION:
182                                 object->recalc |= OB_RECALC_TIME;
183                                 break;
184                         case DEG_NODE_TYPE_TRANSFORM:
185                                 object->recalc |= OB_RECALC_OB;
186                                 break;
187                         case DEG_NODE_TYPE_GEOMETRY:
188                         case DEG_NODE_TYPE_EVAL_POSE:
189                         case DEG_NODE_TYPE_BONE:
190                         case DEG_NODE_TYPE_EVAL_PARTICLES:
191                         case DEG_NODE_TYPE_SHADING:
192                         case DEG_NODE_TYPE_CACHE:
193                         case DEG_NODE_TYPE_PROXY:
194                                 object->recalc |= OB_RECALC_DATA;
195                                 break;
196                         case DEG_NODE_TYPE_PARAMETERS:
197                                 break;
198                 }
199         }
200         /* When some target changes bone, we might need to re-run the
201          * whole IK solver, otherwise result might be unpredictable.
202          */
203         if (comp_node->type == DEG_NODE_TYPE_BONE) {
204                 ComponentDepsNode *pose_comp =
205                         id_node->find_component(DEG_NODE_TYPE_EVAL_POSE);
206                 BLI_assert(pose_comp != NULL);
207                 if (pose_comp->done == COMPONENT_STATE_NONE) {
208                         queue->push_front(pose_comp->get_entry_operation());
209                         pose_comp->done = COMPONENT_STATE_SCHEDULED;
210                 }
211         }
212 }
213
214 /* Schedule children of the given operation node for traversal.
215  *
216  * One of the children will by-pass the queue and will be returned as a function
217  * return value, so it can start being handled right away, without building too
218  * much of a queue.
219  */
220 BLI_INLINE OperationDepsNode *flush_schedule_children(
221         OperationDepsNode *op_node,
222         FlushQueue *queue)
223 {
224         OperationDepsNode *result = NULL;
225         foreach (DepsRelation *rel, op_node->outlinks) {
226                 OperationDepsNode *to_node = (OperationDepsNode *)rel->to;
227                 if (to_node->scheduled == false) {
228                         if (result != NULL) {
229                                 queue->push_front(to_node);
230                         }
231                         else {
232                                 result = to_node;
233                         }
234                         to_node->scheduled = true;
235                 }
236         }
237         return result;
238 }
239
240 BLI_INLINE void flush_editors_id_update(Main *bmain,
241                                         Depsgraph *graph)
242 {
243         foreach (IDDepsNode *id_node, graph->id_nodes) {
244                 if (id_node->done != ID_STATE_MODIFIED) {
245                         continue;
246                 }
247                 /* TODO(sergey): Do we need to pass original or evaluated ID here? */
248                 ID *id = id_node->id;
249                 deg_editors_id_update(bmain, id);
250                 lib_id_recalc_tag(bmain, id);
251                 /* TODO(sergey): For until we've got proper data nodes in the graph. */
252                 lib_id_recalc_data_tag(bmain, id);
253         }
254 }
255
256 }  // namespace
257
258 /* Flush updates from tagged nodes outwards until all affected nodes
259  * are tagged.
260  */
261 void deg_graph_flush_updates(Main *bmain, Depsgraph *graph)
262 {
263         /* Sanity checks. */
264         BLI_assert(bmain != NULL);
265         BLI_assert(graph != NULL);
266         /* Nothing to update, early out. */
267         if (BLI_gset_size(graph->entry_tags) == 0) {
268                 return;
269         }
270         /* Reset all flags, get ready for the flush. */
271         flush_prepare(graph);
272         /* Starting from the tagged "entry" nodes, flush outwards. */
273         FlushQueue queue;
274         flush_schedule_entrypoints(graph, &queue);
275         /* Do actual flush. */
276         while (!queue.empty()) {
277                 OperationDepsNode *op_node = queue.front();
278                 queue.pop_front();
279                 while (op_node != NULL) {
280                         /* Tag operation as required for update. */
281                         op_node->flag |= DEPSOP_FLAG_NEEDS_UPDATE;
282                         /* Inform corresponding ID and component nodes about the change. */
283                         ComponentDepsNode *comp_node = op_node->owner;
284                         IDDepsNode *id_node = comp_node->owner;
285                         flush_handle_id_node(id_node);
286                         flush_handle_component_node(graph,
287                                                     id_node,
288                                                     comp_node,
289                                                     &queue);
290                         /* Flush to nodes along links. */
291                         op_node = flush_schedule_children(op_node, &queue);
292                 }
293         }
294         /* Inform editors about all changes. */
295         flush_editors_id_update(bmain, graph);
296 }
297
298 static void graph_clear_func(
299         void *__restrict data_v,
300         const int i,
301         const ParallelRangeTLS *__restrict /*tls*/)
302 {
303         Depsgraph *graph = (Depsgraph *)data_v;
304         OperationDepsNode *node = graph->operations[i];
305         /* Clear node's "pending update" settings. */
306         node->flag &= ~(DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE);
307 }
308
309 /* Clear tags from all operation nodes. */
310 void deg_graph_clear_tags(Depsgraph *graph)
311 {
312         /* Go over all operation nodes, clearing tags. */
313         const int num_operations = graph->operations.size();
314         ParallelRangeSettings settings;
315         BLI_parallel_range_settings_defaults(&settings);
316         settings.min_iter_per_thread = 1024;
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