Blender V5.3
node_geo_input_shortest_edge_paths.cc
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#include <queue>
6
7#include "BLI_array_utils.hh"
9#include "BLI_task.hh"
10
11#include "BKE_mesh.hh"
12#include "BKE_mesh_mapping.hh"
13
14#include "FN_field.hh"
15
16#include "node_geometry_util.hh"
17
19
21{
22 b.add_input<decl::Bool>("End Vertex"_ustr)
23 .default_value(false)
24 .hide_value()
25 .structure_type(StructureType::Field);
26 b.add_input<decl::Float>("Edge Cost"_ustr)
27 .default_value(1.0f)
28 .hide_value()
29 .structure_type(StructureType::Field);
30 b.add_output<decl::Int>("Next Vertex Index"_ustr)
31 .structure_type(StructureType::Field)
32 .propagate_references();
33 b.add_output<decl::Float>("Total Cost"_ustr)
34 .structure_type(StructureType::Field)
35 .propagate_references();
36}
37
38using VertPriority = std::pair<float, int>;
39
40static void shortest_paths(const Mesh &mesh,
41 const GroupedSpan<int> vert_to_edge,
42 const IndexMask end_selection,
43 const VArray<float> &input_cost,
44 MutableSpan<int> r_next_index,
45 MutableSpan<float> r_cost)
46{
47 const Span<int2> edges = mesh.edges();
48 Array<bool> visited(mesh.verts_num, false);
49
50 std::priority_queue<VertPriority, std::vector<VertPriority>, std::greater<>> queue;
51
52 end_selection.foreach_index([&](const int start_vert_i) {
53 r_cost[start_vert_i] = 0.0f;
54 queue.emplace(0.0f, start_vert_i);
55 });
56
57 /* Though it uses more memory, calculating the adjacent vertex
58 * across each edge beforehand is noticeably faster. */
59 Array<int> other_vertex(vert_to_edge.data.size());
60 threading::parallel_for(vert_to_edge.index_range(), 2048, [&](const IndexRange range) {
61 for (const int vert_i : range) {
62 for (const int edge_i : vert_to_edge.offsets[vert_i]) {
63 other_vertex[edge_i] = bke::mesh::edge_other_vert(edges[vert_to_edge.data[edge_i]],
64 vert_i);
65 }
66 }
67 });
68
69 while (!queue.empty()) {
70 const float cost_i = queue.top().first;
71 const int vert_i = queue.top().second;
72 queue.pop();
73 if (visited[vert_i]) {
74 continue;
75 }
76 visited[vert_i] = true;
77 for (const int index : vert_to_edge.offsets[vert_i]) {
78 const int edge_i = vert_to_edge.data[index];
79 const int neighbor_vert_i = other_vertex[index];
80 if (visited[neighbor_vert_i]) {
81 continue;
82 }
83 const float edge_cost = std::max(0.0f, input_cost[edge_i]);
84 const float new_neighbor_cost = cost_i + edge_cost;
85 if (new_neighbor_cost < r_cost[neighbor_vert_i]) {
86 r_cost[neighbor_vert_i] = new_neighbor_cost;
87 r_next_index[neighbor_vert_i] = vert_i;
88 queue.emplace(new_neighbor_cost, neighbor_vert_i);
89 }
90 }
91 }
92}
93
95 private:
96 Field<bool> end_selection_;
97 Field<float> cost_;
98
99 public:
101 : bke::MeshFieldInput(CPPType::get<int>(), "Shortest Edge Paths Next Vertex Field"),
102 end_selection_(end_selection),
103 cost_(cost)
104 {
105 }
106
108 const AttrDomain domain,
109 const IndexMask &mask) const final
110 {
111 const bke::MeshFieldContext edge_context{mesh, AttrDomain::Edge};
112 fn::FieldEvaluator edge_evaluator{edge_context, mesh.edges_num};
113 edge_evaluator.add(cost_);
114 edge_evaluator.evaluate();
115 const VArray<float> input_cost = edge_evaluator.get_evaluated<float>(0);
116
117 const bke::MeshFieldContext point_context{mesh, AttrDomain::Point};
118 fn::FieldEvaluator point_evaluator{point_context, mesh.verts_num};
119 point_evaluator.add(end_selection_);
120 point_evaluator.evaluate();
121 const IndexMask end_selection = point_evaluator.get_evaluated_as_mask(0);
122
123 if (end_selection.is_empty()) {
124 if (domain == AttrDomain::Point) {
126 }
127
128 Array<int> next_index(mesh.verts_num);
130 return mesh.attributes().adapt_domain<int>(
131 VArray<int>::from_container(std::move(next_index)), AttrDomain::Point, domain);
132 }
133
134 Array<int> next_index(mesh.verts_num, -1);
135 Array<float> cost(mesh.verts_num, FLT_MAX);
136
137 const Span<int2> edges = mesh.edges();
138 Array<int> vert_to_edge_offset_data;
139 Array<int> vert_to_edge_indices;
141 edges, mesh.verts_num, vert_to_edge_offset_data, vert_to_edge_indices);
142 shortest_paths(mesh, vert_to_edge, end_selection, input_cost, next_index, cost);
143
144 threading::parallel_for(next_index.index_range(), 1024, [&](const IndexRange range) {
145 for (const int i : range) {
146 if (next_index[i] == -1) {
147 next_index[i] = i;
148 }
149 }
150 });
151 return mesh.attributes().adapt_domain<int>(
152 VArray<int>::from_container(std::move(next_index)), AttrDomain::Point, domain);
153 }
154
155 void foreach_recursive_field(FunctionRef<void(const GField &)> fn) const override
156 {
157 fn(end_selection_);
158 fn(cost_);
159 }
160
161 void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const override
162 {
163 static constexpr int8_t id = 0;
164 hash.add(&id);
165 hash.add(deep_hash_cache.ensure(end_selection_));
166 hash.add(deep_hash_cache.ensure(cost_));
167 }
168
169 std::optional<AttrDomain> preferred_domain(const Mesh & /*mesh*/) const override
170 {
171 return AttrDomain::Point;
172 }
173};
174
176 private:
177 Field<bool> end_selection_;
178 Field<float> cost_;
179
180 public:
182 : bke::MeshFieldInput(CPPType::get<float>(), "Shortest Edge Paths Cost Field"),
183 end_selection_(end_selection),
184 cost_(cost)
185 {
186 }
187
189 const AttrDomain domain,
190 const IndexMask & /*mask*/) const final
191 {
192 const bke::MeshFieldContext edge_context{mesh, AttrDomain::Edge};
193 fn::FieldEvaluator edge_evaluator{edge_context, mesh.edges_num};
194 edge_evaluator.add(cost_);
195 edge_evaluator.evaluate();
196 const VArray<float> input_cost = edge_evaluator.get_evaluated<float>(0);
197
198 const bke::MeshFieldContext point_context{mesh, AttrDomain::Point};
199 fn::FieldEvaluator point_evaluator{point_context, mesh.verts_num};
200 point_evaluator.add(end_selection_);
201 point_evaluator.evaluate();
202 const IndexMask end_selection = point_evaluator.get_evaluated_as_mask(0);
203
204 if (end_selection.is_empty()) {
205 return mesh.attributes().adapt_domain<float>(
206 VArray<float>::from_single(0.0f, mesh.verts_num), AttrDomain::Point, domain);
207 }
208
209 Array<int> next_index(mesh.verts_num, -1);
210 Array<float> cost(mesh.verts_num, FLT_MAX);
211
212 const Span<int2> edges = mesh.edges();
213 Array<int> vert_to_edge_offset_data;
214 Array<int> vert_to_edge_indices;
216 edges, mesh.verts_num, vert_to_edge_offset_data, vert_to_edge_indices);
217 shortest_paths(mesh, vert_to_edge, end_selection, input_cost, next_index, cost);
218
219 threading::parallel_for(cost.index_range(), 1024, [&](const IndexRange range) {
220 for (const int i : range) {
221 if (cost[i] == FLT_MAX) {
222 cost[i] = 0;
223 }
224 }
225 });
226 return mesh.attributes().adapt_domain<float>(
227 VArray<float>::from_container(std::move(cost)), AttrDomain::Point, domain);
228 }
229
230 void foreach_recursive_field(FunctionRef<void(const GField &)> fn) const override
231 {
232 fn(end_selection_);
233 fn(cost_);
234 }
235
236 void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const override
237 {
238 static constexpr int8_t id = 0;
239 hash.add(&id);
240 hash.add(deep_hash_cache.ensure(end_selection_));
241 hash.add(deep_hash_cache.ensure(cost_));
242 }
243
244 std::optional<AttrDomain> preferred_domain(const Mesh & /*mesh*/) const override
245 {
246 return AttrDomain::Point;
247 }
248};
249
251{
252 Field<bool> end_selection = params.extract_input<Field<bool>>("End Vertex"_ustr);
253 Field<float> cost = params.extract_input<Field<float>>("Edge Cost"_ustr);
254
255 params.set_output(
256 "Next Vertex Index"_ustr,
258 params.set_output(
259 "Total Cost"_ustr,
261}
262
263static void node_register()
264{
265 static bke::bNodeType ntype;
266
268 &ntype, "GeometryNodeInputShortestEdgePaths"_ustr, GEO_NODE_INPUT_SHORTEST_EDGE_PATHS);
269 ntype.ui_name = "Shortest Edge Paths";
270 ntype.ui_description =
271 "Find the shortest paths along mesh edges to selected end vertices, with customizable cost "
272 "per edge";
273 ntype.enum_name_legacy = "SHORTEST_EDGE_PATHS";
274 ntype.nclass = NODE_CLASS_INPUT;
275 ntype.declare = node_declare;
279}
280NOD_REGISTER_NODE(node_register)
281
282} // namespace blender::nodes::node_geo_input_shortest_edge_paths_cc
#define NODE_CLASS_INPUT
Definition BKE_node.hh:478
#define GEO_NODE_INPUT_SHORTEST_EDGE_PATHS
#define final(a, b, c)
Definition BLI_hash_c.hh:21
#define NOD_REGISTER_NODE(REGISTER_FUNC)
IndexRange index_range() const
Definition BLI_array.hh:371
static VArray from_single(T value, const int64_t size)
static VArray from_container(ContainerT container)
int add(GField field, GVArray *varray_ptr)
IndexMask get_evaluated_as_mask(int field_index)
const GVArray & get_evaluated(const int field_index) const
uint64_t hash() const
Definition field.cc:185
static GVArray get_index_varray(const IndexMask &mask)
Definition field.cc:536
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
static Field from_input(Args &&...args)
T extract_input(const UString identifier)
void set_output(const UString identifier, T &&value)
GVArray get_varray_for_context(const Mesh &mesh, const AttrDomain domain, const IndexMask &) const final
void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const override
void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const override
GVArray get_varray_for_context(const Mesh &mesh, const AttrDomain domain, const IndexMask &mask) const final
#define FLT_MAX
void fill_index_range(MutableSpan< T > span, const T start=0)
GroupedSpan< int > build_vert_to_edge_map(Span< int2 > edges, int verts_num, Array< int > &r_offsets, Array< int > &r_indices)
void node_register_type(bNodeType &ntype)
Definition node.cc:2920
static void shortest_paths(const Mesh &mesh, const GroupedSpan< int > vert_to_edge, const IndexMask end_selection, const VArray< float > &input_cost, MutableSpan< int > r_next_index, MutableSpan< float > r_cost)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
void geo_node_type_base(bke::bNodeType *ntype, UString idname, const std::optional< int16_t > legacy_type)
signed char int8_t
Definition BKE_text.h:76
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
static constexpr int _160
Definition BKE_node.hh:246
Defines a node type.
Definition BKE_node.hh:265
std::string ui_description
Definition BKE_node.hh:271
NodeGeometryExecFunction geometry_node_execute
Definition BKE_node.hh:385
const char * enum_name_legacy
Definition BKE_node.hh:274
NodeDeclareFunction declare
Definition BKE_node.hh:393
UniqueHash ensure(const GFieldRef &field)
Definition field.cc:113