Blender V5.3
partial_eval.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2024 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <queue>
10
11#include "NOD_partial_eval.hh"
12
15#include "BKE_node_runtime.hh"
16
18
28
34 const bNode &initial_node)
35{
36 Vector<int> vec;
38 for (const ComputeContext *context = initial_context; context; context = context->parent()) {
39 if (const auto *group_context = dynamic_cast<const bke::GroupNodeComputeContext *>(context)) {
40 const bNode *caller_group_node = group_context->node();
41 BLI_assert(caller_group_node != nullptr);
42 vec.append(caller_group_node->runtime->toposort_right_to_left_index);
43 }
44 }
45 std::reverse(vec.begin(), vec.end());
46 return vec;
47}
48
51 const bNode &initial_node)
52{
53 Vector<int> vec;
55 for (const ComputeContext *context = initial_context; context; context = context->parent()) {
56 if (const auto *group_context = dynamic_cast<const bke::GroupNodeComputeContext *>(context)) {
57 const bNode *caller_group_node = group_context->node();
58 BLI_assert(caller_group_node != nullptr);
59 vec.append(caller_group_node->runtime->toposort_left_to_right_index);
60 }
61 }
62 std::reverse(vec.begin(), vec.end());
63 return vec;
64}
65
73 bool operator()(const NodeInContext &a, const NodeInContext &b) const
74 {
76 const Vector<int> b_sort_vec = get_global_node_sort_vector_right_to_left(b.context, *b.node);
77 const int common_length = std::min(a_sort_vec.size(), b_sort_vec.size());
78 const Span<int> a_common = Span<int>(a_sort_vec).take_front(common_length);
79 const Span<int> b_common = Span<int>(b_sort_vec).take_front(common_length);
80 if (a_common == b_common) {
81 return a_sort_vec.size() < b_sort_vec.size();
82 }
83 return std::lexicographical_compare(
84 b_common.begin(), b_common.end(), a_common.begin(), a_common.end());
85 }
86};
87
95 bool operator()(const NodeInContext &a, const NodeInContext &b) const
96 {
98 const Vector<int> b_sort_vec = get_global_node_sort_vector_left_to_right(b.context, *b.node);
99 const int common_length = std::min(a_sort_vec.size(), b_sort_vec.size());
100 const Span<int> a_common = Span<int>(a_sort_vec).take_front(common_length);
101 const Span<int> b_common = Span<int>(b_sort_vec).take_front(common_length);
102 if (a_common == b_common) {
103 return a_sort_vec.size() < b_sort_vec.size();
104 }
105 return std::lexicographical_compare(
106 b_common.begin(), b_common.end(), a_common.begin(), a_common.end());
107 }
108};
109
111 const Span<SocketInContext> initial_sockets,
112 bke::ComputeContextCache &compute_context_cache,
113 FunctionRef<void(const NodeInContext &ctx_node,
114 Vector<const bNodeSocket *> &r_outputs_to_propagate)> evaluate_node_fn,
115 FunctionRef<bool(const SocketInContext &ctx_from, const SocketInContext &ctx_to)>
116 propagate_value_fn)
117{
118 /* Priority queue that makes sure that nodes are evaluated in the right order. */
119 std::priority_queue<NodeInContext, std::vector<NodeInContext>, NodeInContextDownstreamComparator>
120 scheduled_nodes_queue;
121 /* Used to make sure that the same node is not scheduled more than once. */
122 Set<NodeInContext> scheduled_nodes_set;
123
124 const auto schedule_node = [&](const NodeInContext &ctx_node) {
125 if (scheduled_nodes_set.add(ctx_node)) {
126 scheduled_nodes_queue.push(ctx_node);
127 }
128 };
129
130 const auto forward_group_node_input_into_group =
131 [&](const SocketInContext &ctx_group_node_input) {
132 const bNode &node = ctx_group_node_input.socket->owner_node();
133 BLI_assert(node.is_group());
134 const bNodeTree *group_tree = reinterpret_cast<const bNodeTree *>(node.id);
135 if (!group_tree) {
136 return;
137 }
138 group_tree->ensure_topology_cache();
139 if (group_tree->has_available_link_cycle()) {
140 return;
141 }
142 const auto &group_context = compute_context_cache.for_group_node(
143 ctx_group_node_input.context, node.identifier, &node.owner_tree());
144 const int socket_index = ctx_group_node_input.socket->index();
145 /* Forward the value to every group input node. */
146 for (const bNode *group_input_node : group_tree->group_input_nodes()) {
147 if (propagate_value_fn(ctx_group_node_input,
148 {&group_context, &group_input_node->output_socket(socket_index)}))
149 {
150 schedule_node({&group_context, group_input_node});
151 }
152 }
153 };
154
155 const auto forward_output = [&](const SocketInContext &ctx_output_socket) {
156 const ComputeContext *context = ctx_output_socket.context;
157 for (const bNodeLink *link : ctx_output_socket.socket->directly_linked_links()) {
158 if (!link->is_used()) {
159 continue;
160 }
161 const bNode &target_node = *link->tonode;
162 const bNodeSocket &target_socket = *link->tosock;
163 if (!propagate_value_fn(ctx_output_socket, {context, &target_socket})) {
164 continue;
165 }
166 schedule_node({context, &target_node});
167 if (target_node.is_group()) {
168 forward_group_node_input_into_group({context, &target_socket});
169 }
170 }
171 };
172
173 /* Do initial scheduling based on initial sockets. */
174 for (const SocketInContext &ctx_socket : initial_sockets) {
175 if (ctx_socket.socket->is_input()) {
176 const bNode &node = ctx_socket.socket->owner_node();
177 if (node.is_group()) {
178 forward_group_node_input_into_group(ctx_socket);
179 }
180 schedule_node({ctx_socket.context, &node});
181 }
182 else {
183 forward_output(ctx_socket);
184 }
185 }
186
187 /* Reused in multiple places to avoid allocating it multiple times. Should be cleared before
188 * using it. */
189 Vector<const bNodeSocket *> sockets_vec;
190
191 /* Handle all scheduled nodes in the right order until no more nodes are scheduled. */
192 while (!scheduled_nodes_queue.empty()) {
193 const NodeInContext ctx_node = scheduled_nodes_queue.top();
194 scheduled_nodes_queue.pop();
195
196 const bNode &node = *ctx_node.node;
197 const ComputeContext *context = ctx_node.context;
198
199 if (node.is_reroute()) {
200 if (propagate_value_fn({context, &node.input_socket(0)}, {context, &node.output_socket(0)}))
201 {
202 forward_output({context, &node.output_socket(0)});
203 }
204 }
205 if (node.is_type("NodeImplicitConversion"_ustr)) {
206 if (propagate_value_fn({context, &node.input_socket(0)}, {context, &node.output_socket(0)}))
207 {
208 forward_output({context, &node.output_socket(0)});
209 }
210 }
211 else if (node.is_muted()) {
212 for (const bNodeInternalLink &link : node.internal_links()) {
213 if (propagate_value_fn({context, link.in}, {context, link.out})) {
214 forward_output({context, link.out});
215 }
216 }
217 }
218 else if (node.is_group()) {
219 const bNodeTree *group = reinterpret_cast<const bNodeTree *>(node.id);
220 if (!group) {
221 continue;
222 }
223 group->ensure_topology_cache();
224 if (group->has_available_link_cycle()) {
225 continue;
226 }
227 const bNode *group_output = group->group_output_node();
228 if (!group_output) {
229 continue;
230 }
231 const ComputeContext &group_context = compute_context_cache.for_group_node(
232 context, node.identifier, &node.owner_tree());
233 /* Propagate the values from the group output node to the outputs of the group node and
234 * continue forwarding them from there. */
235 for (const int index : group->interface_outputs().index_range()) {
236 if (propagate_value_fn({&group_context, &group_output->input_socket(index)},
237 {context, &node.output_socket(index)}))
238 {
239 forward_output({context, &node.output_socket(index)});
240 }
241 }
242 }
243 else if (node.is_group_input()) {
244 for (const bNodeSocket *output_socket : node.output_sockets()) {
245 forward_output({context, output_socket});
246 }
247 }
248 else {
249 sockets_vec.clear();
250 evaluate_node_fn(ctx_node, sockets_vec);
251 for (const bNodeSocket *socket : sockets_vec) {
252 forward_output({context, socket});
253 }
254 }
255 }
256}
257
259 const Span<SocketInContext> initial_sockets,
260 bke::ComputeContextCache &compute_context_cache,
261 FunctionRef<void(const NodeInContext &ctx_node,
262 Vector<const bNodeSocket *> &r_modified_inputs)> evaluate_node_fn,
263 FunctionRef<bool(const SocketInContext &ctx_from, const SocketInContext &ctx_to)>
264 propagate_value_fn,
265 FunctionRef<void(const NodeInContext &ctx_node, Vector<const bNodeSocket *> &r_sockets)>
266 get_inputs_to_propagate_fn)
267{
268 /* Priority queue that makes sure that nodes are evaluated in the right order. */
269 std::priority_queue<NodeInContext, std::vector<NodeInContext>, NodeInContextUpstreamComparator>
270 scheduled_nodes_queue;
271 /* Used to make sure that the same node is not scheduled more than once. */
272 Set<NodeInContext> scheduled_nodes_set;
273
274 UpstreamEvalTargets eval_targets;
275
276 const auto schedule_node = [&](const NodeInContext &ctx_node) {
277 if (scheduled_nodes_set.add(ctx_node)) {
278 scheduled_nodes_queue.push(ctx_node);
279 }
280 };
281
282 const auto forward_group_node_output_into_group = [&](const SocketInContext &ctx_output_socket) {
283 const ComputeContext *context = ctx_output_socket.context;
284 const bNode &group_node = ctx_output_socket.socket->owner_node();
285 const bNodeTree *group = reinterpret_cast<const bNodeTree *>(group_node.id);
286 if (!group) {
287 return;
288 }
289 group->ensure_topology_cache();
290 if (group->has_available_link_cycle()) {
291 return;
292 }
293 const bNode *group_output = group->group_output_node();
294 if (!group_output) {
295 return;
296 }
297 const ComputeContext &group_context = compute_context_cache.for_group_node(
298 context, group_node.identifier, &group_node.owner_tree());
299 propagate_value_fn(
300 ctx_output_socket,
301 {&group_context, &group_output->input_socket(ctx_output_socket.socket->index())});
302 schedule_node({&group_context, group_output});
303 };
304
305 const auto forward_group_input_to_parent = [&](const SocketInContext &ctx_output_socket) {
306 const auto *group_context = dynamic_cast<const bke::GroupNodeComputeContext *>(
307 ctx_output_socket.context);
308 if (!group_context) {
309 eval_targets.group_inputs.add(ctx_output_socket);
310 return;
311 }
312 const bNodeTree &caller_tree = *group_context->tree();
313 caller_tree.ensure_topology_cache();
314 if (caller_tree.has_available_link_cycle()) {
315 return;
316 }
317 const bNode &caller_node = *group_context->node();
318 const bNodeSocket &caller_input_socket = caller_node.input_socket(
319 ctx_output_socket.socket->index());
320 const ComputeContext *parent_context = ctx_output_socket.context->parent();
321 /* Note that we might propagate multiple values to the same input of the group node. The
322 * callback has to handle that case gracefully. */
323 propagate_value_fn(ctx_output_socket, {parent_context, &caller_input_socket});
324 schedule_node({parent_context, &caller_node});
325 };
326
327 const auto forward_input = [&](const SocketInContext &ctx_input_socket) {
328 const ComputeContext *context = ctx_input_socket.context;
329 if (!ctx_input_socket.socket->is_logically_linked()) {
330 eval_targets.sockets.add(ctx_input_socket);
331 return;
332 }
333 for (const bNodeLink *link : ctx_input_socket.socket->directly_linked_links()) {
334 if (!link->is_used()) {
335 continue;
336 }
337 const bNode &origin_node = *link->fromnode;
338 const bNodeSocket &origin_socket = *link->fromsock;
339 if (!propagate_value_fn(ctx_input_socket, {context, &origin_socket})) {
340 continue;
341 }
342 schedule_node({context, &origin_node});
343 if (origin_node.is_group()) {
344 forward_group_node_output_into_group({context, &origin_socket});
345 continue;
346 }
347 if (origin_node.is_group_input()) {
348 forward_group_input_to_parent({context, &origin_socket});
349 continue;
350 }
351 }
352 };
353
354 /* Do initial scheduling based on initial sockets. */
355 for (const SocketInContext &ctx_socket : initial_sockets) {
356 if (ctx_socket.socket->is_input()) {
357 forward_input(ctx_socket);
358 }
359 else {
360 const bNode &node = ctx_socket.socket->owner_node();
361 if (node.is_group()) {
362 forward_group_node_output_into_group(ctx_socket);
363 }
364 else if (node.is_group_input()) {
365 forward_group_input_to_parent(ctx_socket);
366 }
367 else {
368 schedule_node({ctx_socket.context, &node});
369 }
370 }
371 }
372
373 /* Reused in multiple places to avoid allocating it multiple times. Should be cleared before
374 * using it. */
375 Vector<const bNodeSocket *> sockets_vec;
376
377 /* Handle all nodes in the right order until there are no more nodes to evaluate. */
378 while (!scheduled_nodes_queue.empty()) {
379 const NodeInContext ctx_node = scheduled_nodes_queue.top();
380 scheduled_nodes_queue.pop();
381
382 const bNode &node = *ctx_node.node;
383 const ComputeContext *context = ctx_node.context;
384
386 /* Can't go back further from here, but remember that we reached a value node. */
387 eval_targets.value_nodes.add(ctx_node);
388 }
389 else if (node.is_reroute()) {
390 propagate_value_fn({context, &node.output_socket(0)}, {context, &node.input_socket(0)});
391 forward_input({context, &node.input_socket(0)});
392 }
393 else if (node.is_type("NodeImplicitConversion"_ustr)) {
394 propagate_value_fn({context, &node.output_socket(0)}, {context, &node.input_socket(0)});
395 forward_input({context, &node.input_socket(0)});
396 }
397 else if (node.is_muted()) {
398 for (const bNodeInternalLink &link : node.internal_links()) {
399 if (propagate_value_fn({context, link.out}, {context, link.in})) {
400 forward_input({context, link.in});
401 }
402 }
403 }
404 else if (node.is_group()) {
405 /* Once we get here, the nodes within the group have all been evaluated already and the
406 * inputs of the group node are already set properly by #forward_group_input_to_parent. */
407 sockets_vec.clear();
408 get_inputs_to_propagate_fn(ctx_node, sockets_vec);
409 for (const bNodeSocket *socket : sockets_vec) {
410 forward_input({context, socket});
411 }
412 }
413 else if (node.is_group_output()) {
414 sockets_vec.clear();
415 get_inputs_to_propagate_fn(ctx_node, sockets_vec);
416 for (const bNodeSocket *socket : sockets_vec) {
417 forward_input({context, socket});
418 }
419 }
420 else {
421 sockets_vec.clear();
422 evaluate_node_fn(ctx_node, sockets_vec);
423 for (const bNodeSocket *input_socket : sockets_vec) {
424 forward_input({context, input_socket});
425 }
426 }
427 }
428
429 return eval_targets;
430}
431
432} // namespace blender::nodes::partial_eval
#define FN_NODE_INPUT_VECTOR
#define SH_NODE_VALUE
#define FN_NODE_INPUT_INT
#define FN_NODE_INPUT_BOOL
#define FN_NODE_INPUT_ROTATION
#define ELEM(...)
const ComputeContext * parent() const
bool add(const Key &key)
Definition BLI_set.hh:248
constexpr const T * end() const
Definition BLI_span.hh:228
constexpr const T * begin() const
Definition BLI_span.hh:224
constexpr Span take_front(int64_t n) const
Definition BLI_span.hh:197
int64_t size() const
void append(const T &value)
const GroupNodeComputeContext & for_group_node(const ComputeContext *parent, int32_t node_id, const bNodeTree *tree=nullptr)
static Vector< int > get_global_node_sort_vector_left_to_right(const ComputeContext *initial_context, const bNode &initial_node)
static Vector< int > get_global_node_sort_vector_right_to_left(const ComputeContext *initial_context, const bNode &initial_node)
UpstreamEvalTargets eval_upstream(const Span< SocketInContext > initial_sockets, bke::ComputeContextCache &compute_context_cache, FunctionRef< void(const NodeInContext &ctx_node, Vector< const bNodeSocket * > &r_modified_inputs)> evaluate_node_fn, FunctionRef< bool(const SocketInContext &ctx_from, const SocketInContext &ctx_to)> propagate_value_fn, FunctionRef< void(const NodeInContext &ctx_node, Vector< const bNodeSocket * > &r_sockets)> get_inputs_to_propagate_fn)
void eval_downstream(const Span< SocketInContext > initial_sockets, bke::ComputeContextCache &compute_context_cache, FunctionRef< void(const NodeInContext &ctx_node, Vector< const bNodeSocket * > &r_outputs_to_propagate)> evaluate_node_fn, FunctionRef< bool(const SocketInContext &ctx_from, const SocketInContext &ctx_to)> propagate_value_fn)
bool is_supported_value_node(const bNode &node)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
bke::bNodeRuntime * runtime
bool operator()(const NodeInContext &a, const NodeInContext &b) const
bool operator()(const NodeInContext &a, const NodeInContext &b) const