diff options
author | Erik Abrahamsson <erik85> | 2022-07-27 16:38:30 +0300 |
---|---|---|
committer | Jacques Lucke <jacques@blender.org> | 2022-07-27 16:38:44 +0300 |
commit | c8ae1fce6024556b72c9e48c2b97c310aceb556c (patch) | |
tree | 31328550a7a4511f23a33a122cc4d671d4681400 /source/blender/nodes | |
parent | 9ac81ed6abfbd431aafd75969f8590703ebe122f (diff) |
Geometry Nodes: Shortest Paths nodes
This adds three new nodes:
* `Shortest Edge Paths`: Actually finds the shortest paths.
* `Edge Paths to Curves`: Converts the paths to separate curves.
This may generate a quadratic amount of data, making it slow
for large meshes.
* `Edge Paths to Selection`: Generates an edge selection that
contains all edges that are part of a path. This can be used
with the Separate Geometry node to only keep the edges that
are part of a path. For large meshes, this approach can be
much faster than the `Edge Paths to Curves` node, because
less data is created.
Differential Revision: https://developer.blender.org/D15274
Diffstat (limited to 'source/blender/nodes')
6 files changed, 509 insertions, 0 deletions
diff --git a/source/blender/nodes/NOD_geometry.h b/source/blender/nodes/NOD_geometry.h index 86c276fbd6f..7dcbfb50a2c 100644 --- a/source/blender/nodes/NOD_geometry.h +++ b/source/blender/nodes/NOD_geometry.h @@ -52,6 +52,8 @@ void register_node_type_geo_delete_geometry(void); void register_node_type_geo_duplicate_elements(void); void register_node_type_geo_distribute_points_on_faces(void); void register_node_type_geo_dual_mesh(void); +void register_node_type_geo_edge_paths_to_curves(void); +void register_node_type_geo_edge_paths_to_selection(void); void register_node_type_geo_edge_split(void); void register_node_type_geo_extrude_mesh(void); void register_node_type_geo_field_at_index(void); @@ -81,6 +83,7 @@ void register_node_type_geo_input_position(void); void register_node_type_geo_input_radius(void); void register_node_type_geo_input_scene_time(void); void register_node_type_geo_input_shade_smooth(void); +void register_node_type_geo_input_shortest_edge_paths(void); void register_node_type_geo_input_spline_cyclic(void); void register_node_type_geo_input_spline_length(void); void register_node_type_geo_input_spline_resolution(void); diff --git a/source/blender/nodes/NOD_static_types.h b/source/blender/nodes/NOD_static_types.h index db0204c5426..10bb336fc1b 100644 --- a/source/blender/nodes/NOD_static_types.h +++ b/source/blender/nodes/NOD_static_types.h @@ -307,6 +307,8 @@ DefNode(GeometryNode, GEO_NODE_DUPLICATE_ELEMENTS, def_geo_duplicate_elements, " DefNode(GeometryNode, GEO_NODE_DISTRIBUTE_POINTS_ON_FACES, def_geo_distribute_points_on_faces, "DISTRIBUTE_POINTS_ON_FACES", DistributePointsOnFaces, "Distribute Points on Faces", "Generate points spread out on the surface of a mesh") DefNode(GeometryNode, GEO_NODE_ACCUMULATE_FIELD, def_geo_accumulate_field, "ACCUMULATE_FIELD", AccumulateField, "Accumulate Field", "Add the values of an evaluated field together and output the running total for each element") DefNode(GeometryNode, GEO_NODE_DUAL_MESH, 0, "DUAL_MESH", DualMesh, "Dual Mesh", "Convert Faces into vertices and vertices into faces") +DefNode(GeometryNode, GEO_NODE_EDGE_PATHS_TO_CURVES, 0, "EDGE_PATHS_TO_CURVES", EdgePathsToCurves, "Edge Paths to Curves", "") +DefNode(GeometryNode, GEO_NODE_EDGE_PATHS_TO_SELECTION, 0, "EDGE_PATHS_TO_SELECTION", EdgePathsToSelection, "Edge Paths to Selection", "") DefNode(GeometryNode, GEO_NODE_EXTRUDE_MESH, def_geo_extrude_mesh, "EXTRUDE_MESH", ExtrudeMesh, "Extrude Mesh", "Generate new vertices, edges, or faces from selected elements and move them based on an offset while keeping them connected by their boundary") DefNode(GeometryNode, GEO_NODE_FIELD_AT_INDEX, def_geo_field_at_index, "FIELD_AT_INDEX", FieldAtIndex, "Field at Index", "Retrieve data of other elements in the context's geometry") DefNode(GeometryNode, GEO_NODE_FIELD_ON_DOMAIN, def_geo_field_on_domain, "FIELD_ON_DOMAIN", FieldOnDomain, "Field on Domain", "Retrieve values from a field on a different domain besides the domain from the context") @@ -337,6 +339,7 @@ DefNode(GeometryNode, GEO_NODE_INPUT_POSITION, 0, "POSITION", InputPosition, "Po DefNode(GeometryNode, GEO_NODE_INPUT_RADIUS, 0, "INPUT_RADIUS", InputRadius, "Radius", "Retrieve the radius at each point on curve or point cloud geometry") DefNode(GeometryNode, GEO_NODE_INPUT_SCENE_TIME, 0, "INPUT_SCENE_TIME", InputSceneTime, "Scene Time", "Retrieve the current time in the scene's animation in units of seconds or frames") DefNode(GeometryNode, GEO_NODE_INPUT_SHADE_SMOOTH, 0, "INPUT_SHADE_SMOOTH", InputShadeSmooth, "Is Shade Smooth", "Retrieve whether each face is marked for smooth shading") +DefNode(GeometryNode, GEO_NODE_INPUT_SHORTEST_EDGE_PATHS, 0, "SHORTEST_EDGE_PATHS", InputShortestEdgePaths, "Shortest Edge Paths", "") DefNode(GeometryNode, GEO_NODE_INPUT_SPLINE_CYCLIC, 0, "INPUT_SPLINE_CYCLIC",InputSplineCyclic, "Is Spline Cyclic", "Retrieve whether each spline endpoint connects to the beginning") DefNode(GeometryNode, GEO_NODE_INPUT_SPLINE_LENGTH, 0, "SPLINE_LENGTH", SplineLength, "Spline Length", "Retrieve the total length of each spline, as a distance or as a number of points") DefNode(GeometryNode, GEO_NODE_INPUT_SPLINE_RESOLUTION, 0, "INPUT_SPLINE_RESOLUTION", InputSplineResolution, "Spline Resolution", "Retrieve the number of evaluated points that will be generated for every control point on curves") diff --git a/source/blender/nodes/geometry/CMakeLists.txt b/source/blender/nodes/geometry/CMakeLists.txt index d87f0312958..97353000b8a 100644 --- a/source/blender/nodes/geometry/CMakeLists.txt +++ b/source/blender/nodes/geometry/CMakeLists.txt @@ -62,6 +62,8 @@ set(SRC nodes/node_geo_distribute_points_on_faces.cc nodes/node_geo_dual_mesh.cc nodes/node_geo_duplicate_elements.cc + nodes/node_geo_edge_paths_to_curves.cc + nodes/node_geo_edge_paths_to_selection.cc nodes/node_geo_edge_split.cc nodes/node_geo_extrude_mesh.cc nodes/node_geo_field_at_index.cc @@ -91,6 +93,7 @@ set(SRC nodes/node_geo_input_radius.cc nodes/node_geo_input_scene_time.cc nodes/node_geo_input_shade_smooth.cc + nodes/node_geo_input_shortest_edge_paths.cc nodes/node_geo_input_spline_cyclic.cc nodes/node_geo_input_spline_length.cc nodes/node_geo_input_spline_resolution.cc diff --git a/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_curves.cc b/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_curves.cc new file mode 100644 index 00000000000..89abfa0aa88 --- /dev/null +++ b/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_curves.cc @@ -0,0 +1,113 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#include "BKE_curves.hh" + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +#include "GEO_mesh_to_curve.hh" + +#include "node_geometry_util.hh" + +namespace blender::nodes::node_geo_edge_paths_to_curves_cc { + +static void node_declare(NodeDeclarationBuilder &b) +{ + b.add_input<decl::Geometry>(N_("Mesh")).supported_type(GEO_COMPONENT_TYPE_MESH); + b.add_input<decl::Bool>(N_("Start Vertices")).default_value(true).hide_value().supports_field(); + b.add_input<decl::Int>(N_("Next Vertex Index")).default_value(-1).hide_value().supports_field(); + b.add_output<decl::Geometry>(N_("Curves")); +} + +static Curves *edge_paths_to_curves_convert(const Mesh &mesh, + const IndexMask start_verts_mask, + const Span<int> next_indices) +{ + const Span<MVert> mvert{mesh.mvert, mesh.totvert}; + Vector<int> vert_indices; + Vector<int> curve_offsets; + Array<bool> visited(mesh.totvert, false); + for (const int first_vert : start_verts_mask) { + const int second_vert = next_indices[first_vert]; + if (first_vert == second_vert) { + continue; + } + if (second_vert < 0 || second_vert >= mesh.totvert) { + continue; + } + + curve_offsets.append(vert_indices.size()); + + /* Iterate through path defined by #next_indices. */ + int current_vert = first_vert; + while (!visited[current_vert]) { + visited[current_vert] = true; + vert_indices.append(current_vert); + const int next_vert = next_indices[current_vert]; + if (next_vert < 0 || next_vert >= mesh.totvert) { + break; + } + current_vert = next_vert; + } + + /* Reset visited status. */ + const int points_in_curve_num = vert_indices.size() - curve_offsets.last(); + for (const int vert_in_curve : vert_indices.as_span().take_back(points_in_curve_num)) { + visited[vert_in_curve] = false; + } + } + + if (vert_indices.is_empty()) { + return nullptr; + } + Curves *curves_id = bke::curves_new_nomain( + geometry::create_curve_from_vert_indices(mesh, vert_indices, curve_offsets, IndexRange(0))); + return curves_id; +} + +static void node_geo_exec(GeoNodeExecParams params) +{ + GeometrySet geometry_set = params.extract_input<GeometrySet>("Mesh"); + + geometry_set.modify_geometry_sets([&](GeometrySet &geometry_set) { + if (!geometry_set.has_mesh()) { + geometry_set.keep_only({GEO_COMPONENT_TYPE_INSTANCES}); + return; + } + + const MeshComponent &component = *geometry_set.get_component_for_read<MeshComponent>(); + GeometryComponentFieldContext context{component, ATTR_DOMAIN_POINT}; + fn::FieldEvaluator evaluator{context, component.attribute_domain_size(ATTR_DOMAIN_POINT)}; + evaluator.add(params.get_input<Field<int>>("Next Vertex Index")); + evaluator.add(params.get_input<Field<bool>>("Start Vertices")); + evaluator.evaluate(); + const VArraySpan<int> next_vert = evaluator.get_evaluated<int>(0); + IndexMask start_verts = evaluator.get_evaluated_as_mask(1); + + if (start_verts.is_empty()) { + geometry_set.keep_only({GEO_COMPONENT_TYPE_INSTANCES}); + return; + } + + const Mesh &mesh = *component.get_for_read(); + geometry_set.replace_curves(edge_paths_to_curves_convert(mesh, start_verts, next_vert)); + geometry_set.keep_only({GEO_COMPONENT_TYPE_CURVE, GEO_COMPONENT_TYPE_INSTANCES}); + }); + + params.set_output("Curves", std::move(geometry_set)); +} + +} // namespace blender::nodes::node_geo_edge_paths_to_curves_cc + +void register_node_type_geo_edge_paths_to_curves() +{ + namespace file_ns = blender::nodes::node_geo_edge_paths_to_curves_cc; + + static bNodeType ntype; + + geo_node_type_base( + &ntype, GEO_NODE_EDGE_PATHS_TO_CURVES, "Edge Paths to Curves", NODE_CLASS_GEOMETRY); + ntype.declare = file_ns::node_declare; + ntype.geometry_node_execute = file_ns::node_geo_exec; + nodeRegisterType(&ntype); +} diff --git a/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_selection.cc b/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_selection.cc new file mode 100644 index 00000000000..efdf0911ec9 --- /dev/null +++ b/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_selection.cc @@ -0,0 +1,140 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#include "BKE_attribute_math.hh" +#include "BKE_mesh.h" + +#include "BLI_map.hh" +#include "BLI_set.hh" +#include "BLI_task.hh" + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +#include "node_geometry_util.hh" + +#include <set> + +namespace blender::nodes::node_geo_edge_paths_to_selection_cc { + +static void node_declare(NodeDeclarationBuilder &b) +{ + b.add_input<decl::Bool>(N_("Start Vertices")).default_value(true).hide_value().supports_field(); + b.add_input<decl::Int>(N_("Next Vertex Index")).default_value(-1).hide_value().supports_field(); + b.add_output<decl::Bool>(N_("Selection")).field_source(); +} + +static void edge_paths_to_selection(const Mesh &src_mesh, + const IndexMask start_selection, + const Span<int> next_indices, + MutableSpan<bool> r_selection) +{ + Array<bool> selection(src_mesh.totvert, false); + + for (const int start_vert : start_selection) { + selection[start_vert] = true; + } + + for (const int start_i : start_selection) { + int iter = start_i; + while (iter != next_indices[iter] && !selection[next_indices[iter]]) { + if (next_indices[iter] < 0 || next_indices[iter] >= src_mesh.totvert) { + break; + } + selection[next_indices[iter]] = true; + iter = next_indices[iter]; + } + } + + for (const int i : IndexRange(src_mesh.totedge)) { + const MEdge &edge = src_mesh.medge[i]; + if ((selection[edge.v1] && selection[edge.v2]) && + (edge.v1 == next_indices[edge.v2] || edge.v2 == next_indices[edge.v1])) { + r_selection[i] = true; + } + } +} + +class PathToEdgeSelectionFieldInput final : public GeometryFieldInput { + private: + Field<bool> start_vertices_; + Field<int> next_vertex_; + + public: + PathToEdgeSelectionFieldInput(Field<bool> start_vertices, Field<int> next_vertex) + : GeometryFieldInput(CPPType::get<bool>(), "Edge Selection"), + start_vertices_(start_vertices), + next_vertex_(next_vertex) + { + category_ = Category::Generated; + } + + GVArray get_varray_for_context(const GeometryComponent &component, + const eAttrDomain domain, + [[maybe_unused]] IndexMask mask) const final + { + if (component.type() != GEO_COMPONENT_TYPE_MESH) { + return {}; + } + + const MeshComponent &mesh_component = static_cast<const MeshComponent &>(component); + const Mesh *mesh = mesh_component.get_for_read(); + if (mesh == nullptr) { + return {}; + } + + GeometryComponentFieldContext context{mesh_component, ATTR_DOMAIN_POINT}; + fn::FieldEvaluator evaluator{context, mesh_component.attribute_domain_size(ATTR_DOMAIN_POINT)}; + evaluator.add(next_vertex_); + evaluator.add(start_vertices_); + evaluator.evaluate(); + const VArraySpan<int> next_vert = evaluator.get_evaluated<int>(0); + const IndexMask start_verts = evaluator.get_evaluated_as_mask(1); + + if (start_verts.is_empty()) { + return {}; + } + + Array<bool> selection(mesh->totedge, false); + MutableSpan<bool> selection_span = selection.as_mutable_span(); + + edge_paths_to_selection(*mesh, start_verts, next_vert, selection_span); + + return mesh_component.attributes()->adapt_domain<bool>( + VArray<bool>::ForContainer(std::move(selection)), ATTR_DOMAIN_EDGE, domain); + } + + uint64_t hash() const override + { + return get_default_hash_2(start_vertices_, next_vertex_); + } + + bool is_equal_to(const fn::FieldNode &other) const override + { + return dynamic_cast<const PathToEdgeSelectionFieldInput *>(&other) != nullptr; + } +}; + +static void node_geo_exec(GeoNodeExecParams params) +{ + Field<bool> start_vertices = params.extract_input<Field<bool>>("Start Vertices"); + Field<int> next_vertex = params.extract_input<Field<int>>("Next Vertex Index"); + Field<bool> selection_field{ + std::make_shared<PathToEdgeSelectionFieldInput>(start_vertices, next_vertex)}; + params.set_output("Selection", std::move(selection_field)); +} + +} // namespace blender::nodes::node_geo_edge_paths_to_selection_cc + +void register_node_type_geo_edge_paths_to_selection() +{ + namespace file_ns = blender::nodes::node_geo_edge_paths_to_selection_cc; + + static bNodeType ntype; + + geo_node_type_base( + &ntype, GEO_NODE_EDGE_PATHS_TO_SELECTION, "Edge Paths to Selection", NODE_CLASS_INPUT); + ntype.declare = file_ns::node_declare; + node_type_size(&ntype, 150, 100, 300); + ntype.geometry_node_execute = file_ns::node_geo_exec; + nodeRegisterType(&ntype); +} diff --git a/source/blender/nodes/geometry/nodes/node_geo_input_shortest_edge_paths.cc b/source/blender/nodes/geometry/nodes/node_geo_input_shortest_edge_paths.cc new file mode 100644 index 00000000000..89abaca3c66 --- /dev/null +++ b/source/blender/nodes/geometry/nodes/node_geo_input_shortest_edge_paths.cc @@ -0,0 +1,247 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#include <queue> + +#include "BKE_curves.hh" + +#include "BLI_map.hh" +#include "BLI_math_vec_types.hh" +#include "BLI_set.hh" + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +#include "node_geometry_util.hh" + +namespace blender::nodes::node_geo_input_shortest_edge_paths_cc { + +static void node_declare(NodeDeclarationBuilder &b) +{ + b.add_input<decl::Bool>(N_("End Vertex")).default_value(false).hide_value().supports_field(); + b.add_input<decl::Float>(N_("Edge Cost")).default_value(1.0f).hide_value().supports_field(); + b.add_output<decl::Int>(N_("Next Vertex Index")).field_source(); + b.add_output<decl::Float>(N_("Total Cost")).field_source(); +} + +typedef std::pair<float, int> VertPriority; + +struct EdgeVertMap { + Array<Vector<int>> edges_by_vertex_map; + + EdgeVertMap(const Mesh *mesh) + { + const Span<MEdge> edges{mesh->medge, mesh->totedge}; + edges_by_vertex_map.reinitialize(mesh->totvert); + for (const int edge_i : edges.index_range()) { + const MEdge &edge = edges[edge_i]; + edges_by_vertex_map[edge.v1].append(edge_i); + edges_by_vertex_map[edge.v2].append(edge_i); + } + } +}; + +static void shortest_paths(const Mesh *mesh, + EdgeVertMap &maps, + const IndexMask end_selection, + const VArray<float> &input_cost, + MutableSpan<int> r_next_index, + MutableSpan<float> r_cost) +{ + const Span<MVert> verts{mesh->mvert, mesh->totvert}; + const Span<MEdge> edges{mesh->medge, mesh->totedge}; + Array<bool> visited(mesh->totvert, false); + + std::priority_queue<VertPriority, std::vector<VertPriority>, std::greater<VertPriority>> queue; + + for (const int start_vert_i : end_selection) { + r_cost[start_vert_i] = 0.0f; + queue.emplace(0.0f, start_vert_i); + } + + while (!queue.empty()) { + const float cost_i = queue.top().first; + const int vert_i = queue.top().second; + queue.pop(); + if (visited[vert_i]) { + continue; + } + visited[vert_i] = true; + const Span<int> incident_edge_indices = maps.edges_by_vertex_map[vert_i]; + for (const int edge_i : incident_edge_indices) { + const MEdge &edge = edges[edge_i]; + const int neighbor_vert_i = edge.v1 + edge.v2 - vert_i; + if (visited[neighbor_vert_i]) { + continue; + } + const float edge_cost = std::max(0.0f, input_cost[edge_i]); + const float new_neighbour_cost = cost_i + edge_cost; + if (new_neighbour_cost < r_cost[neighbor_vert_i]) { + r_cost[neighbor_vert_i] = new_neighbour_cost; + r_next_index[neighbor_vert_i] = vert_i; + queue.emplace(new_neighbour_cost, neighbor_vert_i); + } + } + } +} + +class ShortestEdgePathsNextVertFieldInput final : public GeometryFieldInput { + private: + Field<bool> end_selection_; + Field<float> cost_; + + public: + ShortestEdgePathsNextVertFieldInput(Field<bool> end_selection, Field<float> cost) + : GeometryFieldInput(CPPType::get<int>(), "Shortest Edge Paths Next Vertex Field"), + end_selection_(end_selection), + cost_(cost) + { + category_ = Category::Generated; + } + + GVArray get_varray_for_context(const GeometryComponent &component, + const eAttrDomain domain, + [[maybe_unused]] IndexMask mask) const final + { + if (component.type() != GEO_COMPONENT_TYPE_MESH) { + return {}; + } + const MeshComponent &mesh_component = static_cast<const MeshComponent &>(component); + const Mesh *mesh = mesh_component.get_for_read(); + if (mesh == nullptr) { + return {}; + } + GeometryComponentFieldContext edge_context{component, ATTR_DOMAIN_EDGE}; + fn::FieldEvaluator edge_evaluator{edge_context, mesh->totedge}; + edge_evaluator.add(cost_); + edge_evaluator.evaluate(); + const VArray<float> input_cost = edge_evaluator.get_evaluated<float>(0); + + GeometryComponentFieldContext point_context{component, ATTR_DOMAIN_POINT}; + fn::FieldEvaluator point_evaluator{point_context, mesh->totvert}; + point_evaluator.add(end_selection_); + point_evaluator.evaluate(); + const IndexMask end_selection = point_evaluator.get_evaluated_as_mask(0); + + Array<int> next_index(mesh->totvert, -1); + Array<float> cost(mesh->totvert, FLT_MAX); + + if (!end_selection.is_empty()) { + EdgeVertMap maps(mesh); + shortest_paths(mesh, maps, end_selection, input_cost, next_index, cost); + } + threading::parallel_for(next_index.index_range(), 1024, [&](const IndexRange range) { + for (const int i : range) { + if (next_index[i] == -1) { + next_index[i] = i; + } + } + }); + return component.attributes()->adapt_domain<int>( + VArray<int>::ForContainer(std::move(next_index)), ATTR_DOMAIN_POINT, domain); + } + + uint64_t hash() const override + { + /* Some random constant hash. */ + return 8466507837; + } + + bool is_equal_to(const fn::FieldNode &other) const override + { + return dynamic_cast<const ShortestEdgePathsNextVertFieldInput *>(&other) != nullptr; + } +}; + +class ShortestEdgePathsCostFieldInput final : public GeometryFieldInput { + private: + Field<bool> end_selection_; + Field<float> cost_; + + public: + ShortestEdgePathsCostFieldInput(Field<bool> end_selection, Field<float> cost) + : GeometryFieldInput(CPPType::get<float>(), "Shortest Edge Paths Cost Field"), + end_selection_(end_selection), + cost_(cost) + { + category_ = Category::Generated; + } + + GVArray get_varray_for_context(const GeometryComponent &component, + const eAttrDomain domain, + [[maybe_unused]] IndexMask mask) const final + { + if (component.type() != GEO_COMPONENT_TYPE_MESH) { + return {}; + } + const MeshComponent &mesh_component = static_cast<const MeshComponent &>(component); + const Mesh *mesh = mesh_component.get_for_read(); + if (mesh == nullptr) { + return {}; + } + GeometryComponentFieldContext edge_context{component, ATTR_DOMAIN_EDGE}; + fn::FieldEvaluator edge_evaluator{edge_context, mesh->totedge}; + edge_evaluator.add(cost_); + edge_evaluator.evaluate(); + const VArray<float> input_cost = edge_evaluator.get_evaluated<float>(0); + + GeometryComponentFieldContext point_context{component, ATTR_DOMAIN_POINT}; + fn::FieldEvaluator point_evaluator{point_context, mesh->totvert}; + point_evaluator.add(end_selection_); + point_evaluator.evaluate(); + const IndexMask end_selection = point_evaluator.get_evaluated_as_mask(0); + + Array<int> next_index(mesh->totvert, -1); + Array<float> cost(mesh->totvert, FLT_MAX); + + if (!end_selection.is_empty()) { + EdgeVertMap maps(mesh); + shortest_paths(mesh, maps, end_selection, input_cost, next_index, cost); + } + threading::parallel_for(cost.index_range(), 1024, [&](const IndexRange range) { + for (const int i : range) { + if (cost[i] == FLT_MAX) { + cost[i] = 0; + } + } + }); + return component.attributes()->adapt_domain<float>( + VArray<float>::ForContainer(std::move(cost)), ATTR_DOMAIN_POINT, domain); + } + + uint64_t hash() const override + { + return get_default_hash_2(end_selection_, cost_); + } + + bool is_equal_to(const fn::FieldNode &other) const override + { + return dynamic_cast<const ShortestEdgePathsCostFieldInput *>(&other) != nullptr; + } +}; + +static void node_geo_exec(GeoNodeExecParams params) +{ + Field<bool> end_selection = params.extract_input<Field<bool>>("End Vertex"); + Field<float> cost = params.extract_input<Field<float>>("Edge Cost"); + + Field<int> next_vert_field{ + std::make_shared<ShortestEdgePathsNextVertFieldInput>(end_selection, cost)}; + Field<float> cost_field{std::make_shared<ShortestEdgePathsCostFieldInput>(end_selection, cost)}; + params.set_output("Next Vertex Index", std::move(next_vert_field)); + params.set_output("Total Cost", std::move(cost_field)); +} + +} // namespace blender::nodes::node_geo_input_shortest_edge_paths_cc + +void register_node_type_geo_input_shortest_edge_paths() +{ + namespace file_ns = blender::nodes::node_geo_input_shortest_edge_paths_cc; + + static bNodeType ntype; + + geo_node_type_base( + &ntype, GEO_NODE_INPUT_SHORTEST_EDGE_PATHS, "Shortest Edge Paths", NODE_CLASS_INPUT); + ntype.declare = file_ns::node_declare; + ntype.geometry_node_execute = file_ns::node_geo_exec; + nodeRegisterType(&ntype); +} |