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
This commit is contained in:
parent
9ac81ed6ab
commit
c8ae1fce60
Notes:
blender-bot
2023-06-21 19:23:24 +02:00
Referenced by commit 344c53561a
, Fix: Incorrect field node deduplication for shortest path nodes
|
@ -109,6 +109,8 @@ def mesh_node_items(context):
|
|||
if not space:
|
||||
return
|
||||
yield NodeItem("GeometryNodeDualMesh")
|
||||
yield NodeItem("GeometryNodeEdgePathsToCurves")
|
||||
yield NodeItem("GeometryNodeEdgePathsToSelection")
|
||||
yield NodeItem("GeometryNodeExtrudeMesh")
|
||||
yield NodeItem("GeometryNodeFlipFaces")
|
||||
yield NodeItem("GeometryNodeMeshBoolean")
|
||||
|
@ -129,6 +131,7 @@ def mesh_node_items(context):
|
|||
yield NodeItem("GeometryNodeInputMeshFaceIsPlanar")
|
||||
yield NodeItem("GeometryNodeInputMeshIsland")
|
||||
yield NodeItem("GeometryNodeInputShadeSmooth")
|
||||
yield NodeItem("GeometryNodeInputShortestEdgePaths")
|
||||
yield NodeItem("GeometryNodeInputMeshVertexNeighbors")
|
||||
yield NodeItemCustom(draw=lambda self, layout, context: layout.separator())
|
||||
yield NodeItem("GeometryNodeSetShadeSmooth")
|
||||
|
|
|
@ -1506,6 +1506,9 @@ struct TexResult;
|
|||
#define GEO_NODE_UV_UNWRAP 1165
|
||||
#define GEO_NODE_UV_PACK_ISLANDS 1166
|
||||
#define GEO_NODE_DEFORM_CURVES_ON_SURFACE 1167
|
||||
#define GEO_NODE_INPUT_SHORTEST_EDGE_PATHS 1168
|
||||
#define GEO_NODE_EDGE_PATHS_TO_CURVES 1169
|
||||
#define GEO_NODE_EDGE_PATHS_TO_SELECTION 1170
|
||||
|
||||
/** \} */
|
||||
|
||||
|
|
|
@ -4754,6 +4754,8 @@ static void registerGeometryNodes()
|
|||
register_node_type_geo_duplicate_elements();
|
||||
register_node_type_geo_distribute_points_on_faces();
|
||||
register_node_type_geo_dual_mesh();
|
||||
register_node_type_geo_edge_paths_to_curves();
|
||||
register_node_type_geo_edge_paths_to_selection();
|
||||
register_node_type_geo_edge_split();
|
||||
register_node_type_geo_extrude_mesh();
|
||||
register_node_type_geo_field_at_index();
|
||||
|
@ -4783,6 +4785,7 @@ static void registerGeometryNodes()
|
|||
register_node_type_geo_input_radius();
|
||||
register_node_type_geo_input_scene_time();
|
||||
register_node_type_geo_input_shade_smooth();
|
||||
register_node_type_geo_input_shortest_edge_paths();
|
||||
register_node_type_geo_input_spline_cyclic();
|
||||
register_node_type_geo_input_spline_length();
|
||||
register_node_type_geo_input_spline_resolution();
|
||||
|
|
|
@ -21,4 +21,9 @@ namespace blender::geometry {
|
|||
*/
|
||||
bke::CurvesGeometry mesh_to_curve_convert(const Mesh &mesh, const IndexMask selection);
|
||||
|
||||
bke::CurvesGeometry create_curve_from_vert_indices(const Mesh &mesh,
|
||||
Span<int> vert_indices,
|
||||
Span<int> curve_offsets,
|
||||
IndexRange cyclic_curves);
|
||||
|
||||
} // namespace blender::geometry
|
||||
|
|
|
@ -30,10 +30,10 @@ static void copy_with_map(const VArray<T> &src, Span<int> map, MutableSpan<T> ds
|
|||
});
|
||||
}
|
||||
|
||||
static bke::CurvesGeometry create_curve_from_vert_indices(const Mesh &mesh,
|
||||
const Span<int> vert_indices,
|
||||
const Span<int> curve_offsets,
|
||||
const IndexRange cyclic_curves)
|
||||
bke::CurvesGeometry create_curve_from_vert_indices(const Mesh &mesh,
|
||||
const Span<int> vert_indices,
|
||||
const Span<int> curve_offsets,
|
||||
const IndexRange cyclic_curves)
|
||||
{
|
||||
bke::CurvesGeometry curves(vert_indices.size(), curve_offsets.size());
|
||||
curves.offsets_for_write().drop_back(1).copy_from(curve_offsets);
|
||||
|
|
|
@ -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);
|
||||
|
|
|
@ -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")
|
||||
|
|
|
@ -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
|
||||
|
|
|
@ -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);
|
||||
}
|
|
@ -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);
|
||||
}
|
|
@ -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);
|
||||
}
|
Loading…
Reference in New Issue