Blender V5.3
node_geo_cluster_by_connected.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#include "BLI_array_utils.hh"
6#include "BLI_disjoint_set.hh"
7#include "BLI_math_vector.hh"
8#include "BLI_task.hh"
9
11#include "BKE_mesh.hh"
12
13#include "node_geometry_util.hh"
14
16
18{
19 b.add_input<decl::Bool>("Selection"_ustr)
20 .default_value(true)
21 .hide_value()
22 .structure_type(StructureType::Field);
23 b.add_input<decl::Vector>("Position"_ustr)
24 .default_input_type(NODE_DEFAULT_INPUT_POSITION_FIELD)
25 .structure_type(StructureType::Field);
26 b.add_input<decl::Float>("Distance"_ustr).default_value(0.001f).min(0.0f).subtype(PROP_DISTANCE);
27
28 b.add_output<decl::Int>("Cluster ID"_ustr)
29 .structure_type(StructureType::Field)
30 .propagate_references();
31}
32
34 private:
35 Field<bool> selection_field_;
36 Field<float3> position_field_;
37 float min_distance_;
38
39 public:
41 Field<float3> position_field,
42 float min_distance)
43 : bke::GeometryFieldInput(CPPType::get<int>(), "Cluster by Connected"),
44 selection_field_(std::move(selection_field)),
45 position_field_(std::move(position_field)),
46 min_distance_(min_distance)
47 {
48 }
49
51 const IndexMask &mask) const override
52 {
53 if (context.type() != bke::GeometryComponent::Type::Mesh) {
55 }
56 const Mesh &mesh = *context.mesh();
57 const Span<int2> edges = mesh.edges();
58
59 const bke::MeshFieldContext edge_context(mesh, AttrDomain::Edge);
60 fn::FieldEvaluator edge_evaluator(edge_context, mesh.edges_num);
61 edge_evaluator.set_selection(selection_field_);
62 edge_evaluator.evaluate();
63 const IndexMask selection = edge_evaluator.get_evaluated_selection_as_mask();
64 if (selection.is_empty()) {
66 }
67
68 const bke::MeshFieldContext vert_context(mesh, AttrDomain::Point);
69 fn::FieldEvaluator point_evaluator(vert_context, mesh.verts_num);
70 point_evaluator.add(position_field_);
71 point_evaluator.evaluate();
72 const VArraySpan<float3> position = point_evaluator.get_evaluated<float3>(0);
73
74 DisjointSet<int> vertex_cluster(mesh.verts_num);
75
76 Array<float3> vert_cluster_center(mesh.verts_num);
77 array_utils::copy(position, vert_cluster_center.as_mutable_span());
78 Array<int> vert_cluster_size(mesh.verts_num, 1);
79
80 selection.foreach_index([&](const int edge_i) {
81 const int2 edge = edges[edge_i];
82 const int2 edge_clusters(vertex_cluster.find_root(edge[0]),
83 vertex_cluster.find_root(edge[1]));
84 if (edge_clusters[0] == edge_clusters[1]) {
85 return;
86 }
87
88 const float3 vert_a_cluster = vert_cluster_center[edge_clusters[0]];
89 const float3 vert_b_cluster = vert_cluster_center[edge_clusters[1]];
90 const float distance = math::distance(vert_a_cluster, vert_b_cluster);
91 if (distance >= min_distance_) {
92 return;
93 }
94
95 /* Use original vertices instead of already found roots to keep path folding optimization. */
96 const int new_cluster_root = vertex_cluster.join(edge[0], edge[1]);
97
98 const int new_cluster_size = vert_cluster_size[edge_clusters[0]] +
99 vert_cluster_size[edge_clusters[1]];
100 const float3 new_cluster_center = math::interpolate(vert_a_cluster,
101 vert_b_cluster,
102 vert_cluster_size[edge_clusters[1]] /
103 float(new_cluster_size));
104
105 vert_cluster_center[new_cluster_root] = new_cluster_center;
106 vert_cluster_size[new_cluster_root] = new_cluster_size;
107 });
108
109 Array<int> cluster_indices(mesh.verts_num);
110 threading::parallel_for(IndexRange(mesh.verts_num), 1024, [&](const IndexRange range) {
111 for (const int i : range) {
112 cluster_indices[i] = std::as_const(vertex_cluster).find_root(i);
113 }
114 });
115
116 return mesh.attributes().adapt_domain<int>(
117 VArray<int>::from_container(std::move(cluster_indices)),
118 AttrDomain::Point,
119 context.domain());
120 }
121
122 void foreach_recursive_field(FunctionRef<void(const GField &)> fn) const override
123 {
124 fn(selection_field_);
125 fn(position_field_);
126 }
127
128 void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const override
129 {
130 static constexpr int8_t id = 0;
131 hash.add(&id);
132 hash.add(deep_hash_cache.ensure(selection_field_));
133 hash.add(deep_hash_cache.ensure(position_field_));
134 hash.add(min_distance_);
135 }
136
137 std::optional<AttrDomain> preferred_domain(
138 const GeometryComponent & /*component*/) const override
139 {
140 return AttrDomain::Point;
141 }
142};
143
145{
146 params.set_output("Cluster ID"_ustr,
148 params.extract_input<Field<bool>>("Selection"_ustr),
149 params.extract_input<Field<float3>>("Position"_ustr),
150 params.extract_input<float>("Distance"_ustr)));
151}
152
153static void node_register()
154{
155 static bke::bNodeType ntype;
156
157 geo_node_type_base(&ntype, "GeometryNodeClusterByConnected"_ustr);
158 ntype.ui_name = "Cluster by Connected";
159 ntype.ui_description =
160 "Group mesh vertices connected by edges when they are within a specified distance";
162 ntype.declare = node_declare;
166}
167NOD_REGISTER_NODE(node_register)
168
169} // namespace blender::nodes::node_geo_input_cluster_by_connected_cc
#define NODE_CLASS_CONVERTER
Definition BKE_node.hh:484
#define final(a, b, c)
Definition BLI_hash_c.hh:21
#define NOD_REGISTER_NODE(REGISTER_FUNC)
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
constexpr IndexRange()=default
static VArray from_container(ContainerT container)
void set_selection(Field< bool > selection)
int add(GField field, GVArray *varray_ptr)
IndexMask get_evaluated_selection_as_mask() const
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)
void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const override
std::optional< AttrDomain > preferred_domain(const GeometryComponent &) const override
GVArray get_varray_for_context(const bke::GeometryFieldContext &context, const IndexMask &mask) const override
ClusterByConnectedFieldInput(Field< bool > selection_field, Field< float3 > position_field, float min_distance)
#define position
float distance(float, float) RET
void copy(const GVArray &src, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
void node_register_type(bNodeType &ntype)
Definition node.cc:2920
T distance(const T &a, const T &b)
T interpolate(const T &a, const T &b, const FactorT &t)
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
VecBase< int32_t, 2 > int2
VecBase< float, 3 > float3
@ PROP_DISTANCE
Definition RNA_types.hh:313
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
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
NodeDeclareFunction declare
Definition BKE_node.hh:393
UniqueHash ensure(const GFieldRef &field)
Definition field.cc:113