Blender V5.3
COM_node_tree_evaluator.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#pragma once
6
7#include <memory>
8#include <optional>
9
10#include "BLI_map.hh"
11#include "BLI_vector.hh"
12
13#include "COM_context.hh"
14#include "COM_domain.hh"
15#include "COM_node_operation.hh"
17
18namespace blender {
19struct bNode;
20struct bNodeSocket;
21} // namespace blender
22
23namespace blender::compositor {
24
25struct Schedule;
26class ZoneOperation;
27
28/* ------------------------------------------------------------------------------------------------
29 * Node Tree Evaluator
30 *
31 * The node tree evaluator is a utility class used to evaluate a compositing node tree and track
32 * its state during evaluation. It compiles the node tree into an operations stream, evaluating
33 * the operations in the process. It should be noted that operations are eagerly evaluated as soon
34 * as they are compiled, as opposed to compiling the whole operations stream and then evaluating it
35 * in a separate step. This is done because the evaluator uses the evaluated results of previously
36 * compiled operations to compile the operations that follow them in an optimized manner.
37 *
38 * Figure (1) shows a sample node tree with the execution schedule denoted by the node numbers. The
39 * evaluator goes over the execution schedule in order and compiles each node into either a Node
40 * Operation or a Pixel Operation, depending on the node type, see the is_pixel_node function. A
41 * pixel operation is constructed from a group of nodes forming a contiguous subset of the node
42 * execution schedule. For instance, in the node tree in Figure (1), nodes 3 and 4 are compiled
43 * together into a pixel operation and node 5 is compiled into its own pixel operation, both of
44 * which are contiguous subsets of the node execution schedule. This process is described in
45 * details in the following section.
46 *
47 * Pixel Operation 1 Pixel Operation 2
48 * +-----------------------------------+ +------------------+
49 * .------------. | .------------. .------------. | | .------------. | .------------.
50 * | Node 1 | | | Node 3 | | Node 4 | | | | Node 5 | | | Node 6 |
51 * | |----|--| |--| |---|-----|--| |--|--| |
52 * | | .-|--| | | | | .--|--| | | | |
53 * '------------' | | '------------' '------------' | | | '------------' | '------------'
54 * | +-----------------------------------+ | +------------------+
55 * .------------. | |
56 * | Node 2 | | |
57 * | |--'----------------------------------------'
58 * | |
59 * '------------' Figure (1)
60 *
61 * For non pixel nodes, the compilation process is straight forward, the compiler instantiates a
62 * node operation from the node, map its inputs to the results of the outputs they are linked to,
63 * and evaluates the operations. However, for pixel nodes, since a group of nodes can be compiled
64 * together into a pixel operation, the compilation process is a bit involved. The compiler stores
65 * the so called "pixel compile unit", which is the current group of nodes that will eventually be
66 * compiled together into a pixel operation. While going over the schedule, the compiler adds the
67 * pixel nodes to the compile unit until it decides that the compile unit is complete and should be
68 * compiled. This is typically decided when the current node is not compatible with the compile
69 * unit and can't be added to it, only then it compiles the compile unit into a pixel operation and
70 * resets it to ready it to track the next potential group of nodes that will form a pixel
71 * operation. This decision is made based on various criteria as will be described in a following
72 * section, but perhaps the most evident of which is whether the node is actually a pixel node, if
73 * it isn't, then it evidently can't be added to the compile unit and the compile unit is should be
74 * compiled.
75 *
76 * For the node tree in Figure (1), the compilation process is as follows. The compiler goes over
77 * the node execution schedule in order considering each node. Nodes 1 and 2 are not pixel node so
78 * they are compiled into node operations and added to the operations stream. The current compile
79 * unit is empty, so it is not compiled. Node 3 is a pixel node, and since the compile unit is
80 * currently empty, it is unconditionally added to it. Node 4 is a pixel node, it was decided---for
81 * the sake of the demonstration---that it is compatible with the compile unit and can be added to
82 * it. Node 5 is a pixel node, but it was decided---for the sake of the demonstration---that it is
83 * not compatible with the compile unit, so the compile unit is considered complete and is compiled
84 * first, adding the first pixel operation to the operations stream and resetting the compile
85 * unit. Node 5 is then added to the now empty compile unit similar to node 3. Node 6 is not a
86 * pixel node, so the compile unit is considered complete and is compiled first, adding the first
87 * pixel operation to the operations stream and resetting the compile unit. Finally, node 6 is
88 * compiled into a node operation similar to nodes 1 and 2 and added to the operations stream.
89 *
90 * Zones are evaluated in a special manner. The scheduler only contains the output node of each
91 * zone, and when the evaluator encounters such a node, it constructs a zone operation that
92 * internally calls the node tree evaluator only on nodes inside the zone, and the same happens for
93 * nested zones recursively. The only complication is external inputs that go into a zone from the
94 * outside. Each of those inputs has a corresponding operation input with an identifier derived
95 * from the origin output as returned by ZoneTreeOperation::get_external_input_identifier, and
96 * those are linked appropriately when needed, additionally, their reference count is incremented
97 * by the number of references inside the zone as in compute_zone_external_input_reference_counts.
98 *
99 * During compilation, the class tracks two important pieces of information, each of which is
100 * described in one of the following sections.
101 *
102 * First, it stores a mapping between all nodes and the operations they were compiled into. The
103 * mapping are stored independently depending on the type of the operation in the node_operations_
104 * pixel_operations_, and zone_operations_ maps. So those maps are mutually exclusive. The compiler
105 * should call the map_node_to_node_operation and map_node_to_pixel_operation methods to populate
106 * those maps as soon as it compiles a node or multiple nodes into an operation. Those maps are
107 * used to retrieve the results of outputs linked to the inputs of operations. For more details,
108 * see the get_result_from_output_socket method. For the node tree in Figure (1), nodes 1, 2, and 6
109 * are mapped to their compiled operations in the node_operation_ map. While nodes 3 and 4 are both
110 * mapped to the first pixel operation, and node 5 is mapped to the second pixel operation in the
111 * pixel_operations_ map.
112 *
113 * Second, it stores the pixel compile unit, whether is operates on single values, and its domain
114 * if it was not operating on single values. The one important detail in this class is the
115 * should_compile_pixel_compile_unit method, which implements the criteria of whether the compile
116 * unit should be compiled given the node currently being processed as an argument. Those criteria
117 * are described as follows. If the compile unit is empty as is the case when processing nodes 1,
118 * 2, and 3, then it plainly shouldn't be compiled. If the given node is not a pixel node, then it
119 * can't be added to the compile unit and the unit is considered complete and should be compiled,
120 * as is the case when processing node 6. If the compile unit operates on single values and the
121 * given node operates on non-single values or vice versa, then it can't be added to the compile
122 * unit and the unit is considered complete and should be compiled, more on that in the next
123 * section. If the computed domain of the given node is not compatible with the domain of the
124 * compiled unit, then it can't be added to the unit and the unit is considered complete and should
125 * be compiled, as is the case when processing node 5, more on this in the next section. Otherwise,
126 * the given node is compatible with the compile unit and can be added to it, so the unit shouldn't
127 * be compiled just yet, as is the case when processing node 4.
128 *
129 * Special attention should be given to the aforementioned single value and domain compatibility
130 * criterion. One should first go over the discussion in COM_domain.hh for more information on
131 * domains. When a compile unit gets eventually compiled to a pixel operation, that operation will
132 * have a certain operation domain, and any node that gets added to the compile unit should itself
133 * have a computed node domain that is compatible with that operation domain, otherwise, had the
134 * node been compiled into its own operation separately, the result would have been be different.
135 * For instance, consider the node tree in Figure (1) where node 1 outputs a 100x100 result, node
136 * 2 outputs a 50x50 result, the first input in node 3 has the highest domain priority, and the
137 * second input in node 5 has the highest domain priority. In this case, pixel operation 1 will
138 * output a 100x100 result, and pixel operation 2 will output a 50x50 result, because that's the
139 * computed operation domain for each of them. So node 6 will get a 50x50 result. Now consider the
140 * same node tree, but where all three nodes 3, 4, and 5 were compiled into a single pixel
141 * operation as shown the node tree in Figure (2). In that case, pixel operation 1 will output a
142 * 100x100 result, because that's its computed operation domain. So node 6 will get a 100x100
143 * result. As can be seen, the final result is different even though the node tree is the same.
144 * That's why the compiler can decide to compile the compile unit early even though further nodes
145 * can still be technically added to it.
146 *
147 * Pixel Operation 1
148 * +------------------------------------------------------+
149 * .------------. | .------------. .------------. .------------. | .------------.
150 * | Node 1 | | | Node 3 | | Node 4 | | Node 5 | | | Node 6 |
151 * | |----|--| |--| |------| |--|--| |
152 * | | .-|--| | | | .---| | | | |
153 * '------------' | | '------------' '------------' | '------------' | '------------'
154 * | +----------------------------------|-------------------+
155 * .------------. | |
156 * | Node 2 | | |
157 * | |--'------------------------------------'
158 * | |
159 * '------------' Figure (2)
160 *
161 * Similarly, all nodes in the compile unit should either be operating on single values or not.
162 * Otherwise, assuming a node operates on single values and its output is used in 1) a non-single
163 * value pixel operation and 2) another node that expects single values, if that node was added to
164 * the pixel operation, its output will be non-single value, while it would have been a single
165 * value if it was not added to the pixel operation.
166 *
167 * To check for the single value type and domain compatibility between the compile unit and the
168 * node being processed, the single value type and the domain of the compile unit is assumed to be
169 * the single value type and the domain of the first node added to the compile unit, noting that
170 * the domain is optional, since it is not used if the compile unit is a single value one. The
171 * single value type and the domain of the compile unit are computed and set in the
172 * add_node_to_pixel_compile_unit method. When processing a node, the computed single value type
173 * and the computed domain of node are compared to the compile unit single value type and domain in
174 * the should_compile_pixel_compile_unit method. Node single value types and domains are computed
175 * in the is_pixel_node_single_value and compute_pixel_node_domain methods respectively, the latter
176 * of which is analogous to the Operation::compute_domain method for nodes that are not yet
177 * compiled. */
179 private:
180 /* The compositor context. */
181 Context &context_;
182 /* The node execution schedule that is being evaluated. */
183 const Schedule &schedule_;
184 /* The operation that uses this evaluator. */
185 Operation &operation_;
186 /* The compute context where the evaluation takes place. */
187 const ComputeContext &compute_context_;
188 /* The compiled operations stream, which contains all compiled operations so far. */
189 Vector<std::unique_ptr<Operation>> operations_stream_;
190 /* Maps that associate each node with the operation it was compiled into, a node in the schedule
191 * must exist exclusively in one of those maps. They are used to retrieve the results of outputs
192 * linked to the inputs of operations. See the get_result_from_output_socket method for more
193 * information. */
195 Map<const bNode *, PixelOperation *> pixel_operations_;
197 /* A contiguous subset of the node execution schedule that contains the group of nodes that will
198 * be compiled together into a pixel operation. See the description of the class for more
199 * information. */
200 PixelCompileUnit pixel_compile_unit_;
201 /* Stores whether the current pixel compile unit operates on single values. Only initialized when
202 * the pixel compile unit is not empty. */
203 bool is_pixel_compile_unit_single_value_;
204 /* The domain of the pixel compile unit if it was not a single value. Only initialized when the
205 * pixel compile unit is not empty and is not a single value. */
206 std::optional<Domain> pixel_compile_unit_domain_;
207
208 public:
209 /* Construct a node tree evaluator for the given node tree execution schedule. The evaluation is
210 * assumed to happen in the given compute context for the given operation. */
211 NodeTreeEvaluator(Context &context,
212 const Schedule &schedule,
213 Operation &operation,
214 const ComputeContext &compute_context);
215
216 /* Evaluates the node tree. */
217 void evaluate();
218
219 /* Returns a reference to the result of the operation corresponding to the given output that the
220 * given output's node was compiled to. */
222
223 /* Get a reference to the pixel compile unit. */
225
226 /* Get a reference to the node execution schedule being compiled. */
227 const Schedule &schedule();
228
229 private:
230 /* Computes and sets the reference count for the inputs representing links that cross the border
231 * of the zone and are connected to outputs outside of the zone. Does nothing if the evaluator
232 * is not evaluating a zone. */
233 void compute_zone_external_input_reference_counts();
234
235 /* Constructs and returns a node operation that represents the given node. */
236 NodeOperation *create_node_operation(const bNode &node);
237
238 /* Compile the given node into a node operation, map each input to the result of the output
239 * linked to it, add the newly created operation to the operations stream, and evaluate the
240 * operation. */
241 void evaluate_node(const bNode &node);
242
243 /* Map the input of the given operation with the identifier of the given input to the value of
244 * the given unlinked input. */
245 void map_unlinked_input(const bNodeSocket &input, Operation *operation);
246
247 /* Map each input of the node operation to the result of the output linked to it. Unlinked inputs
248 * are internally handled through map_unlinked_input. */
249 void map_node_operation_inputs_to_their_results(const bNode &node, NodeOperation *operation);
250
251 /* Create one of the concrete subclasses of the PixelOperation based on the context and currently
252 * active pixel compile unit. Deleting the operation is the caller's responsibility. */
253 PixelOperation *create_pixel_operation();
254
255 /* Compile the pixel compile unit into a pixel operation, map each input of the operation to
256 * the result of the output linked to it, add the newly created operation to the operations
257 * stream, evaluate the operation, and finally reset the pixel compile unit. */
258 void evaluate_pixel_compile_unit();
259
260 /* Map each input of the pixel operation to the result of the output linked to it. This might
261 * also correct the reference counts of the results, see the implementation for more details. */
262 void map_pixel_operation_inputs_to_their_results(PixelOperation *operation);
263
264 /* Create one of the concrete subclasses of the ZoneOperation based on the given zone. Deleting
265 * the operation is the caller's responsibility. */
266 ZoneOperation *create_zone_operation(const bke::bNodeTreeZone &zone);
267
268 /* Compile the zone into a zone operation, map each input of the operation to the result of the
269 * output linked to it, and evaluate the operation. */
270 void evaluate_zone(const bke::bNodeTreeZone &zone);
271
272 /* Map each input of the zone operation to the result of the output linked to it. */
273 void map_zone_operation_inputs_to_their_results(ZoneOperation *operation);
274
275 /* Add the given node to the compile unit. And if the domain of the compile unit is not yet
276 * determined or was determined to be an identity domain, update it to the computed domain for
277 * the given node. */
278 void add_node_to_pixel_compile_unit(const bNode &node);
279
280 /* Returns true if the pixel compile unit operates on single values. */
281 bool is_pixel_compile_unit_single_value();
282
283 /* Clear the compile unit. This should be called once the compile unit is compiled to ready it to
284 * track the next potential compile unit. */
285 void reset_pixel_compile_unit();
286
287 /* Determines if the compile unit should be compiled based on a number of criteria give the node
288 * currently being processed. See the class description for a description of the method. */
289 bool should_compile_pixel_compile_unit(const bNode &node);
290
291 /* Determines if the given pixel node operates on single values or not. The node operates on
292 * single values if all its inputs are single values, and consequently will also output single
293 * values. */
294 bool is_pixel_node_single_value(const bNode &node);
295
296 /* Compute the node domain of the given pixel node. This is analogous to the
297 * Operation::compute_domain method, except it is computed from the node itself as opposed to a
298 * compiled operation. See the discussion in COM_domain.hh for more information. */
299 Domain compute_pixel_node_domain(const bNode &node);
300
301 /* Identify if the number of outputs of the pixel compile unit surpass what is possible. This is
302 * essentially the number of outputs that will be added for the nodes in the pixel compile unit
303 * in ShaderOperation::populate_results_for_node. */
304 bool pixel_compile_unit_has_too_many_outputs(const bool are_node_previews_needed);
305
306 /* Identify if the number of inputs of the pixel compile unit surpass what is possible. This is
307 * essentially the number of inputs that will be added for the nodes in the pixel compile unit in
308 * ShaderOperation::link_node_inputs. */
309 bool pixel_compile_unit_has_too_many_inputs();
310
311 /* Cancels the evaluation by freeing the results of the operations that were already evaluated,
312 * that's because later operations that use the already allocated results will not be evaluated,
313 * so they consequently will not release the results that they use and we need to free them
314 * manually. */
315 void cancel_evaluation();
316
317 /* Get a reference to the compositor context. */
318 Context &context();
319
320 /* Get a reference to the operation that uses the evaluator. */
321 Operation &operation();
322};
323
324} // namespace blender::compositor
#define output
Result & get_result_from_output_socket(const bNodeSocket &output)
NodeTreeEvaluator(Context &context, const Schedule &schedule, Operation &operation, const ComputeContext &compute_context)
VectorSet< const bNode * > PixelCompileUnit
BMesh Iterators.