Blender V5.3
node_geo_index_of_nearest.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 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_kdtree_new.hh"
9#include "BLI_map.hh"
10#include "BLI_offset_indices.hh"
11#include "BLI_task.hh"
12
13#include "node_geometry_util.hh"
14
16
18{
19 b.add_input<decl::Vector>("Position"_ustr)
20 .default_input_type(NODE_DEFAULT_INPUT_POSITION_FIELD)
21 .structure_type(StructureType::Field);
22 b.add_input<decl::Int>("Group ID"_ustr).structure_type(StructureType::Field).hide_value();
23
24 b.add_output<decl::Int>("Index"_ustr)
25 .structure_type(StructureType::Field)
26 .propagate_references()
27 .description("Index of nearest element");
28 b.add_output<decl::Bool>("Has Neighbor"_ustr)
29 .structure_type(StructureType::Field)
30 .propagate_references();
31}
32
34 const float3 &position,
35 const int index)
36{
37 return tree.find_nearest_filtered(position, [index](const int other) { return other != index; });
38}
39
40static void find_neighbors(const KDTreeNew<float3> &tree,
41 const Span<float3> positions,
42 const IndexMask &mask,
43 MutableSpan<int> r_indices)
44{
45 mask.foreach_index(
46 [&](const int index) {
47 r_indices[index] = find_nearest_non_self(tree, positions[index], index);
48 },
50}
51
52static void find_neighbors(const KDTreeNew<float3> &tree,
53 const Span<float3> positions,
54 const Span<int> indices,
55 MutableSpan<int> r_indices)
56{
57 threading::parallel_for(indices.index_range(), 1024, [&](const IndexRange range) {
58 for (const int index : indices.slice(range)) {
59 r_indices[index] = find_nearest_non_self(tree, positions[index], index);
60 }
61 });
62}
63
65 private:
66 const Field<float3> positions_field_;
67 const Field<int> group_field_;
68
69 public:
71 : bke::GeometryFieldInput(CPPType::get<int>(), "Index of Nearest"),
72 positions_field_(std::move(positions_field)),
73 group_field_(std::move(group_field))
74 {
75 }
76
78 const IndexMask &mask) const final
79 {
80 if (!context.attributes()) {
81 return {};
82 }
83 const int domain_size = context.attributes()->domain_size(context.domain());
84 fn::FieldEvaluator evaluator{context, domain_size};
85 evaluator.add(positions_field_);
86 evaluator.add(group_field_);
87 evaluator.evaluate();
88 const VArraySpan<float3> positions = evaluator.get_evaluated<float3>(0);
89 const VArray<int> group_ids = evaluator.get_evaluated<int>(1);
90
92
93 /* With a full mask, we can run query's in the tree's internal index order, which can be much
94 * faster because neighboring indices will be spatially contiguous and therefore make better
95 * use of caches during traversal. Even with scattered writes from multiple threads, lookup
96 * cost dominates and this is a significant performance improvement. */
97 const bool query_all = mask.size() == domain_size;
98
99 if (group_ids.is_single()) {
100 result.reinitialize(mask.min_array_size());
101 const KDTreeNew<float3> tree(positions);
102 if (query_all) {
103 find_neighbors(tree, positions, tree.tree_indices(), result);
104 }
105 else {
106 find_neighbors(tree, positions, mask, result);
107 }
108 return VArray<int>::from_container(std::move(result));
109 }
110 const VArraySpan<int> group_ids_span(group_ids);
111
112 Array<int> group_indices(domain_size);
113 const int groups_num = array_utils::group_ids_to_indices(
114 group_ids_span, IndexMask(domain_size), group_indices);
115
116 Array<int> tree_offset_data;
117 Array<int> tree_index_data;
119 group_indices, groups_num, tree_offset_data, tree_index_data);
120
121 /* When only some elements are looked up, they are grouped separately. */
122 GroupedSpan<int> lookup_indices_by_group;
123 Array<int> lookup_offset_data;
124 Array<int> lookup_index_data;
125 if (query_all) {
126 result.reinitialize(domain_size);
127 }
128 else {
129 Array<int> lookup_group_indices(mask.size());
130 array_utils::gather(group_indices.as_span(), mask, lookup_group_indices.as_mutable_span());
131 lookup_indices_by_group = offset_indices::build_groups_from_indices(
132 lookup_group_indices, groups_num, lookup_offset_data, lookup_index_data, mask);
133 result.reinitialize(mask.min_array_size());
134 }
135
136 /* The grain size should be larger as each tree gets smaller. */
137 const int avg_tree_size = domain_size / groups_num;
138 const int grain_size = std::max(8192 / avg_tree_size, 1);
139 threading::parallel_for(IndexRange(groups_num), grain_size, [&](const IndexRange range) {
140 AlignedBuffer<4096, 8> tree_buffer;
141 for (const int group_index : range) {
142 LinearAllocator<> tree_memory;
143 tree_memory.provide_buffer(tree_buffer);
144 const KDTreeNew<float3> tree(positions, tree_indices_by_group[group_index], tree_memory);
145 find_neighbors(tree,
146 positions,
147 query_all ? tree.tree_indices() : lookup_indices_by_group[group_index],
148 result);
149 }
150 });
151
152 return VArray<int>::from_container(std::move(result));
153 }
154
155 void foreach_recursive_field(FunctionRef<void(const GField &)> fn) const override
156 {
157 fn(positions_field_);
158 fn(group_field_);
159 }
160
161 void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const override
162 {
163 static constexpr int8_t id = 0;
164 hash.add(&id);
165 hash.add(deep_hash_cache.ensure(positions_field_));
166 hash.add(deep_hash_cache.ensure(group_field_));
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 private:
177 const Field<int> group_field_;
178
179 public:
181 : bke::GeometryFieldInput(CPPType::get<bool>(), "Has Neighbor"),
182 group_field_(std::move(group_field))
183 {
184 }
185
187 const IndexMask &mask) const final
188 {
189 if (!context.attributes()) {
190 return {};
191 }
192 const int domain_size = context.attributes()->domain_size(context.domain());
193 if (domain_size == 1) {
194 return VArray<bool>::from_single(false, mask.min_array_size());
195 }
196
197 fn::FieldEvaluator evaluator{context, domain_size};
198 evaluator.add(group_field_);
199 evaluator.evaluate();
200 const VArray<int> group = evaluator.get_evaluated<int>(0);
201
202 if (group.is_single()) {
203 return VArray<bool>::from_single(true, mask.min_array_size());
204 }
205
206 Map<int, int> counts;
207 const VArraySpan<int> group_span(group);
208 mask.foreach_index([&](const int i) {
209 counts.add_or_modify(
210 group_span[i], [](int *count) { *count = 1; }, [](int *count) { (*count)++; });
211 });
212 Array<bool> result(mask.min_array_size());
213 mask.foreach_index([&](const int i) { result[i] = counts.lookup(group_span[i]) > 1; });
214 return VArray<bool>::from_container(std::move(result));
215 }
216
217 void foreach_recursive_field(FunctionRef<void(const GField &)> fn) const override
218 {
219 fn(group_field_);
220 }
221
222 void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const final
223 {
224 static constexpr int8_t id = 0;
225 hash.add(&id);
226 hash.add(deep_hash_cache.ensure(group_field_));
227 }
228
229 std::optional<AttrDomain> preferred_domain(const GeometryComponent &component) const final
230 {
231 return bke::try_detect_field_domain(component, group_field_);
232 }
233};
234
236{
237 Field<float3> position_field = params.extract_input<Field<float3>>("Position"_ustr);
238 Field<int> group_field = params.extract_input<Field<int>>("Group ID"_ustr);
239
240 if (params.output_is_required("Index"_ustr)) {
241 params.set_output(
242 "Index"_ustr,
243 Field<int>::from_input<IndexOfNearestFieldInput>(std::move(position_field), group_field));
244 }
245
246 if (params.output_is_required("Has Neighbor"_ustr)) {
247 params.set_output("Has Neighbor"_ustr,
248 Field<bool>::from_input<HasNeighborFieldInput>(std::move(group_field)));
249 }
250}
251
252static void node_register()
253{
254 static bke::bNodeType ntype;
255
256 geo_node_type_base(&ntype, "GeometryNodeIndexOfNearest"_ustr, GEO_NODE_INDEX_OF_NEAREST);
257 ntype.ui_name = "Index of Nearest";
258 ntype.ui_description =
259 "Find the nearest element in a group. Similar to the \"Sample Nearest\" node";
260 ntype.enum_name_legacy = "INDEX_OF_NEAREST";
263 ntype.declare = node_declare;
265}
266NOD_REGISTER_NODE(node_register)
267
268} // namespace blender::nodes::node_geo_index_of_nearest_cc
#define NODE_CLASS_CONVERTER
Definition BKE_node.hh:484
#define GEO_NODE_INDEX_OF_NEAREST
#define final(a, b, c)
Definition BLI_hash_c.hh:21
#define NOD_REGISTER_NODE(REGISTER_FUNC)
Span< T > as_span() const
Definition BLI_array.hh:254
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
Span< int > tree_indices() const
int find_nearest_filtered(const T &position, Filter &&filter, value_type *r_distance_sq=nullptr) const
void provide_buffer(void *buffer, const int64_t size)
const Value & lookup(const Key &key) const
Definition BLI_map.hh:545
auto add_or_modify(const Key &key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
Definition BLI_map.hh:481
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
static VArray from_single(T value, const int64_t size)
static VArray from_container(ContainerT container)
int add(GField field, GVArray *varray_ptr)
const GVArray & get_evaluated(const int field_index) const
uint64_t hash() const
Definition field.cc:185
static Field from_input(Args &&...args)
T extract_input(const UString identifier)
bool output_is_required(const UString identifier) const
void set_output(const UString identifier, T &&value)
GVArray get_varray_for_context(const bke::GeometryFieldContext &context, const IndexMask &mask) const final
std::optional< AttrDomain > preferred_domain(const GeometryComponent &component) const final
void foreach_recursive_field(FunctionRef< void(const GField &)> fn) const override
void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const final
IndexOfNearestFieldInput(Field< float3 > positions_field, Field< int > group_field)
GVArray get_varray_for_context(const bke::GeometryFieldContext &context, const IndexMask &mask) const final
std::optional< AttrDomain > preferred_domain(const GeometryComponent &component) const final
void hash_unique(UniqueHashBytes &hash, fn::FieldHashDeep &deep_hash_cache) const override
void foreach_recursive_field(FunctionRef< void(const GField &)> fn) const override
#define position
void gather(const GVArray &src, const IndexMask &indices, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
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)
static void node_geo_exec(GeoNodeExecParams params)
static void node_declare(NodeDeclarationBuilder &b)
static int find_nearest_non_self(const KDTreeNew< float3 > &tree, const float3 &position, const int index)
static void find_neighbors(const KDTreeNew< float3 > &tree, const Span< float3 > positions, const IndexMask &mask, MutableSpan< int > r_indices)
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
VecBase< float, 3 > float3
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
const char * enum_name_legacy
Definition BKE_node.hh:274
NodeDeclareFunction declare
Definition BKE_node.hh:393
UniqueHash ensure(const GFieldRef &field)
Definition field.cc:113