Blender  V3.3
point_merge_by_distance.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #include "BLI_kdtree.h"
4 #include "BLI_task.hh"
5 
6 #include "DNA_pointcloud_types.h"
7 
8 #include "BKE_attribute_math.hh"
9 #include "BKE_geometry_set.hh"
10 #include "BKE_pointcloud.h"
11 
13 
14 namespace blender::geometry {
15 
17  const float merge_distance,
18  const IndexMask selection)
19 {
20  const bke::AttributeAccessor src_attributes = bke::pointcloud_attributes(src_points);
22  "position", ATTR_DOMAIN_POINT, float3(0));
23  const int src_size = positions.size();
24 
25  /* Create the KD tree based on only the selected points, to speed up merge detection and
26  * balancing. */
27  KDTree_3d *tree = BLI_kdtree_3d_new(selection.size());
28  for (const int i : selection.index_range()) {
29  BLI_kdtree_3d_insert(tree, i, positions[selection[i]]);
30  }
31  BLI_kdtree_3d_balance(tree);
32 
33  /* Find the duplicates in the KD tree. Because the tree only contains the selected points, the
34  * resulting indices are indices into the selection, rather than indices of the source point
35  * cloud. */
36  Array<int> selection_merge_indices(selection.size(), -1);
37  const int duplicate_count = BLI_kdtree_3d_calc_duplicates_fast(
38  tree, merge_distance, false, selection_merge_indices.data());
39  BLI_kdtree_3d_free(tree);
40 
41  /* Create the new point cloud and add it to a temporary component for the attribute API. */
42  const int dst_size = src_size - duplicate_count;
43  PointCloud *dst_pointcloud = BKE_pointcloud_new_nomain(dst_size);
45  *dst_pointcloud);
46 
47  /* By default, every point is just "merged" with itself. Then fill in the results of the merge
48  * finding, converting from indices into the selection to indices into the full input point
49  * cloud. */
50  Array<int> merge_indices(src_size);
51  for (const int i : merge_indices.index_range()) {
52  merge_indices[i] = i;
53  }
54  for (const int i : selection_merge_indices.index_range()) {
55  const int merge_index = selection_merge_indices[i];
56  if (merge_index != -1) {
57  const int src_merge_index = selection[merge_index];
58  const int src_index = selection[i];
59  merge_indices[src_index] = src_merge_index;
60  }
61  }
62 
63  /* For every source index, find the corresponding index in the result by iterating through the
64  * source indices and counting how many merges happened before that point. */
65  int merged_points = 0;
66  Array<int> src_to_dst_indices(src_size);
67  for (const int i : IndexRange(src_size)) {
68  src_to_dst_indices[i] = i - merged_points;
69  if (merge_indices[i] != i) {
70  merged_points++;
71  }
72  }
73 
74  /* In order to use a contiguous array as the storage for every destination point's source
75  * indices, first the number of source points must be counted for every result point. */
76  Array<int> point_merge_counts(dst_size, 0);
77  for (const int i : IndexRange(src_size)) {
78  const int merge_index = merge_indices[i];
79  const int dst_index = src_to_dst_indices[merge_index];
80  point_merge_counts[dst_index]++;
81  }
82 
83  /* This array stores an offset into `merge_map` for every result point. */
84  Array<int> map_offsets(dst_size + 1);
85  int offset = 0;
86  for (const int i : IndexRange(dst_size)) {
87  map_offsets[i] = offset;
88  offset += point_merge_counts[i];
89  }
90  map_offsets.last() = offset;
91 
92  point_merge_counts.fill(0);
93 
94  /* This array stores all of the source indices for every result point. The size is the source
95  * size because every input point is either merged with another or copied directly. */
96  Array<int> merge_map(src_size);
97  for (const int i : IndexRange(src_size)) {
98  const int merge_index = merge_indices[i];
99  const int dst_index = src_to_dst_indices[merge_index];
100 
101  const IndexRange points(map_offsets[dst_index],
102  map_offsets[dst_index + 1] - map_offsets[dst_index]);
103  MutableSpan<int> point_merge_indices = merge_map.as_mutable_span().slice(points);
104  point_merge_indices[point_merge_counts[dst_index]] = i;
105  point_merge_counts[dst_index]++;
106  }
107 
108  Set<bke::AttributeIDRef> attribute_ids = src_attributes.all_ids();
109 
110  /* Transfer the ID attribute if it exists, using the ID of the first merged point. */
111  if (attribute_ids.contains("id")) {
112  VArraySpan<int> src = src_attributes.lookup_or_default<int>("id", ATTR_DOMAIN_POINT, 0);
114  "id", ATTR_DOMAIN_POINT);
115 
116  threading::parallel_for(IndexRange(dst_size), 1024, [&](IndexRange range) {
117  for (const int i_dst : range) {
118  const IndexRange points(map_offsets[i_dst], map_offsets[i_dst + 1] - map_offsets[i_dst]);
119  dst.span[i_dst] = src[points.first()];
120  }
121  });
122 
123  dst.finish();
124  attribute_ids.remove_contained("id");
125  }
126 
127  /* Transfer all other attributes. */
128  for (const bke::AttributeIDRef &id : attribute_ids) {
129  if (!id.should_be_kept()) {
130  continue;
131  }
132 
133  bke::GAttributeReader src_attribute = src_attributes.lookup(id);
134  attribute_math::convert_to_static_type(src_attribute.varray.type(), [&](auto dummy) {
135  using T = decltype(dummy);
136  if constexpr (!std::is_void_v<attribute_math::DefaultMixer<T>>) {
137  bke::SpanAttributeWriter<T> dst_attribute =
138  dst_attributes.lookup_or_add_for_write_only_span<T>(id, ATTR_DOMAIN_POINT);
139  VArraySpan<T> src = src_attribute.varray.typed<T>();
140 
141  threading::parallel_for(IndexRange(dst_size), 1024, [&](IndexRange range) {
142  for (const int i_dst : range) {
143  /* Create a separate mixer for every point to avoid allocating temporary buffers
144  * in the mixer the size of the result point cloud and to improve memory locality. */
145  attribute_math::DefaultMixer<T> mixer{dst_attribute.span.slice(i_dst, 1)};
146 
147  const IndexRange points(map_offsets[i_dst],
148  map_offsets[i_dst + 1] - map_offsets[i_dst]);
149  Span<int> src_merge_indices = merge_map.as_span().slice(points);
150  for (const int i_src : src_merge_indices) {
151  mixer.mix_in(0, src[i_src]);
152  }
153 
154  mixer.finalize();
155  }
156  });
157 
158  dst_attribute.finish();
159  }
160  });
161  }
162 
163  return dst_pointcloud;
164 }
165 
166 } // namespace blender::geometry
@ ATTR_DOMAIN_POINT
Definition: BKE_attribute.h:27
General operations for point clouds.
struct PointCloud * BKE_pointcloud_new_nomain(int totpoint)
Definition: pointcloud.cc:243
A KD-tree for nearest neighbor search.
const T & last(const int64_t n=0) const
Definition: BLI_array.hh:284
const T * data() const
Definition: BLI_array.hh:300
IndexRange index_range() const
Definition: BLI_array.hh:348
void fill(const T &value) const
Definition: BLI_array.hh:260
MutableSpan< T > as_mutable_span()
Definition: BLI_array.hh:236
const CPPType & type() const
int64_t size() const
IndexRange index_range() const
constexpr int64_t first() const
void remove_contained(const Key &key)
Definition: BLI_set.hh:383
bool contains(const Key &key) const
Definition: BLI_set.hh:296
Set< AttributeIDRef > all_ids() const
GAttributeReader lookup(const AttributeIDRef &attribute_id) const
GVArray lookup_or_default(const AttributeIDRef &attribute_id, const eAttrDomain domain, const eCustomDataType data_type, const void *default_value=nullptr) const
GSpanAttributeWriter lookup_or_add_for_write_only_span(const AttributeIDRef &attribute_id, const eAttrDomain domain, const eCustomDataType data_type)
SyclQueue void void * src
void * tree
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
void convert_to_static_type(const CPPType &cpp_type, const Func &func)
AttributeAccessor pointcloud_attributes(const PointCloud &pointcloud)
MutableAttributeAccessor pointcloud_attributes_for_write(PointCloud &pointcloud)
PointCloud * point_merge_by_distance(const PointCloud &src_points, const float merge_distance, const IndexMask selection)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
vec_base< float, 3 > float3
MutableSpan< float3 > positions