Blender V5.3
node_geo_cluster_by_distance.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.hh"
6#include "BLI_array_utils.hh"
7#include "BLI_index_mask.hh"
8#include "BLI_kdtree_new.hh"
10
12
13#include "node_geometry_util.hh"
14
16
18{
19 b.add_input<decl::Bool>("Selection"_ustr)
20 .default_value(true)
21 .structure_type(StructureType::Field)
22 .hide_value();
23 b.add_input<decl::Int>("Group ID"_ustr).structure_type(StructureType::Field).hide_value();
24 b.add_input<decl::Vector>("Position"_ustr)
25 .default_input_type(NODE_DEFAULT_INPUT_POSITION_FIELD)
26 .structure_type(StructureType::Field);
27 b.add_input<decl::Float>("Distance"_ustr).default_value(0.001f).min(0.0f).subtype(PROP_DISTANCE);
28
29 b.add_output<decl::Int>("Cluster ID"_ustr)
30 .structure_type(StructureType::Field)
31 .propagate_references();
32}
33
34constexpr int NO_CLUSTER_VALUE = -1;
35
36static void set_no_cluster_value(MutableSpan<int> r_cluster_ids, const IndexMask &mask)
37{
38 mask.foreach_index_optimized<int>(
39 [&](const int i) {
40 if (r_cluster_ids[i] == NO_CLUSTER_VALUE) {
41 r_cluster_ids[i] = i;
42 }
43 },
45}
46
48 private:
49 Field<float3> positions_field_;
50 Field<int> group_field_;
51 Field<bool> selection_field_;
52 float distance_;
53
54 public:
56 Field<int> group_field,
57 Field<bool> selection_field,
58 const float distance)
59 : bke::GeometryFieldInput(CPPType::get<int>(), "Cluster by Distance"),
60 positions_field_(std::move(positions_field)),
61 group_field_(std::move(group_field)),
62 selection_field_(std::move(selection_field)),
63 distance_(distance)
64 {
65 }
66
68 const IndexMask &mask) const final
69 {
70 if (!context.attributes()) {
71 return {};
72 }
73
74 const int domain_size = context.attributes()->domain_size(context.domain());
75 fn::FieldEvaluator evaluator{context, domain_size};
76 evaluator.add(positions_field_);
77 evaluator.add(group_field_);
78 evaluator.set_selection(selection_field_);
79 evaluator.evaluate();
80 const VArraySpan<float3> positions = evaluator.get_evaluated<float3>(0);
81 const VArray<int> group_ids = evaluator.get_evaluated<int>(1);
82 const IndexMask selection = evaluator.get_evaluated_selection_as_mask();
83
84 IndexMaskMemory memory;
85 /* With context info about mask to compute we can skip processing of the rest of the values.
86 * But in current case this will affect result values since some cluster might have lowest ID
87 * of element outside of visible mask. */
88 const IndexMask mask_to_cluster = IndexMask::from_intersection(mask, selection, memory);
89 if (mask_to_cluster.is_empty()) {
91 }
92
93 Array<int> cluster_ids(mask.min_array_size());
94
95 const IndexMask mask_to_fallback = IndexMask::from_difference(mask, mask_to_cluster, memory);
96 array_utils::fill_index_range<int>(mask_to_fallback, cluster_ids);
97
98 Array<int> point_groups;
99 int groups_num = 1;
100 if (!group_ids.is_single()) {
101 point_groups.reinitialize(mask_to_cluster.size());
103 VArraySpan<int>(group_ids), mask_to_cluster, point_groups);
104 }
105 if (groups_num == 1) {
106 index_mask::masked_fill<int>(cluster_ids, NO_CLUSTER_VALUE, mask_to_cluster);
107 const KDTreeNew<float3> tree(positions, mask_to_cluster);
108 /* Visiting the points in index order keeps the result from depending on the tree's
109 * layout, which changes as points move. See #calc_duplicates. */
110 kdtree::calc_duplicates(tree, distance_, mask_to_cluster, cluster_ids);
111 set_no_cluster_value(cluster_ids, mask_to_cluster);
112 return VArray<int>::from_container(std::move(cluster_ids));
113 }
114
115 Array<int> group_offset_data;
116 Array<int> indices_by_group_data;
118 point_groups, groups_num, group_offset_data, indices_by_group_data, mask_to_cluster);
119 const OffsetIndices<int> group_offsets = indices_by_group.offsets;
120
122 IndexRange(groups_num),
123 1024,
124 [&](const IndexRange range) {
125 AlignedBuffer<4096, 8> tree_buffer;
126 for (const int group_i : range) {
127 const Span<int> group = indices_by_group[group_i];
128 /* Groups don't share indices, so the shared array can be written to directly. */
129 cluster_ids.as_mutable_span().fill_indices(group, NO_CLUSTER_VALUE);
130 LinearAllocator<> tree_memory;
131 tree_memory.provide_buffer(tree_buffer);
132 const KDTreeNew<float3> tree(positions, group, tree_memory);
133 /* The group's indices are sorted, so this visits the points in index order. */
134 kdtree::calc_duplicates(tree, distance_, group, cluster_ids);
135 for (const int i : group) {
136 if (cluster_ids[i] == NO_CLUSTER_VALUE) {
137 cluster_ids[i] = i;
138 }
139 }
140 }
141 },
143 [&](const IndexRange range) { return group_offsets[range].size(); }));
144
145#ifndef NDEBUG
146 mask.foreach_index([&](const int i) { BLI_assert(cluster_ids[i] != NO_CLUSTER_VALUE); });
147#endif
148
149 return VArray<int>::from_container(std::move(cluster_ids));
150 }
151
152 void foreach_recursive_field(FunctionRef<void(const GField &)> fn) const override
153 {
154 fn(positions_field_);
155 fn(group_field_);
156 fn(selection_field_);
157 }
158
159 void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const override
160 {
161 static constexpr int8_t id = 0;
162 hash.add(&id);
163 hash.add(deep_hash_cache.ensure(positions_field_));
164 hash.add(deep_hash_cache.ensure(group_field_));
165 hash.add(deep_hash_cache.ensure(selection_field_));
166 hash.add(distance_);
167 }
168
169 std::optional<AttrDomain> preferred_domain(const GeometryComponent &component) const final
170 {
171 return bke::try_detect_field_domain(component, positions_field_);
172 }
173};
174
176{
177 params.set_output("Cluster ID"_ustr,
179 params.extract_input<Field<float3>>("Position"_ustr),
180 params.extract_input<Field<int>>("Group ID"_ustr),
181 params.extract_input<Field<bool>>("Selection"_ustr),
182 params.extract_input<float>("Distance"_ustr)));
183}
184
185static void node_register()
186{
187 static bke::bNodeType ntype;
188
189 geo_node_type_base(&ntype, "GeometryNodeClusterByDistance"_ustr);
190 ntype.ui_name = "Cluster by Distance";
191 ntype.ui_description = "Group elements into integer IDs based on proximity of vector values";
193 ntype.declare = node_declare;
196}
198
199} // namespace blender::nodes::node_geo_cluster_by_distance_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
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
static IndexMask from_difference(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
static IndexMask from_intersection(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
constexpr IndexRange()=default
void provide_buffer(void *buffer, const int64_t size)
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
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 &component) const final
void foreach_recursive_field(FunctionRef< void(const GField &)> fn) const override
ClusterByDistanceFieldInput(Field< float3 > positions_field, Field< int > group_field, Field< bool > selection_field, const float distance)
GVArray get_varray_for_context(const bke::GeometryFieldContext &context, const IndexMask &mask) const final
float distance(float, float) RET
void fill_index_range(MutableSpan< T > span, const T start=0)
int group_ids_to_indices(Span< int > ids, const IndexMask &mask, MutableSpan< int > r_group_indices, Vector< int > *r_first_indices=nullptr)
std::optional< AttrDomain > try_detect_field_domain(const GeometryComponent &component, const fn::GField &field)
void node_register_type(bNodeType &ntype)
Definition node.cc:2920
constexpr ParallelGrainSize grain_size(int grain_size)
void masked_fill(MutableSpan< T > data, const T &value, const IndexMask &mask)
int calc_duplicates(const KDTreeNew< T > &tree, typename T::base_type range, Span< int > visit_order, MutableSpan< int > duplicates)
Definition kdtree.cc:867
static void set_no_cluster_value(MutableSpan< int > r_cluster_ids, const IndexMask &mask)
GroupedSpan< int > build_groups_from_indices(Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data)
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
auto accumulated_task_sizes(Fn &&fn)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
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
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