25 .structure_type(StructureType::Field);
29 .structure_type(StructureType::Field);
30 b.add_output<
decl::Int>(
"Next Vertex Index"_ustr)
31 .structure_type(StructureType::Field)
32 .propagate_references();
34 .structure_type(StructureType::Field)
35 .propagate_references();
50 std::priority_queue<VertPriority, std::vector<VertPriority>, std::greater<>> queue;
53 r_cost[start_vert_i] = 0.0f;
54 queue.emplace(0.0f, start_vert_i);
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]],
69 while (!queue.empty()) {
70 const float cost_i = queue.top().first;
71 const int vert_i = queue.top().second;
73 if (visited[vert_i]) {
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]) {
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);
102 end_selection_(end_selection),
113 edge_evaluator.
add(cost_);
119 point_evaluator.
add(end_selection_);
124 if (domain == AttrDomain::Point) {
130 return mesh.attributes().adapt_domain<
int>(
141 edges,
mesh.verts_num, vert_to_edge_offset_data, vert_to_edge_indices);
145 for (const int i : range) {
146 if (next_index[i] == -1) {
151 return mesh.attributes().adapt_domain<
int>(
163 static constexpr int8_t id = 0;
165 hash.add(deep_hash_cache.
ensure(end_selection_));
171 return AttrDomain::Point;
183 end_selection_(end_selection),
194 edge_evaluator.
add(cost_);
200 point_evaluator.
add(end_selection_);
205 return mesh.attributes().adapt_domain<
float>(
216 edges,
mesh.verts_num, vert_to_edge_offset_data, vert_to_edge_indices);
220 for (const int i : range) {
221 if (cost[i] == FLT_MAX) {
226 return mesh.attributes().adapt_domain<
float>(
238 static constexpr int8_t id = 0;
240 hash.add(deep_hash_cache.
ensure(end_selection_));
246 return AttrDomain::Point;
256 "Next Vertex Index"_ustr,
269 ntype.
ui_name =
"Shortest Edge Paths";
271 "Find the shortest paths along mesh edges to selected end vertices, with customizable cost "
#define GEO_NODE_INPUT_SHORTEST_EDGE_PATHS
#define NOD_REGISTER_NODE(REGISTER_FUNC)
IndexRange index_range() const
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
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)
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)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
void geo_node_type_base(bke::bNodeType *ntype, UString idname, const std::optional< int16_t > legacy_type)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
static constexpr int _160
std::string ui_description
NodeGeometryExecFunction geometry_node_execute
const char * enum_name_legacy
NodeDeclareFunction declare
UniqueHash ensure(const GFieldRef &field)
IndexRange index_range() const