Blender V5.3
kdtree.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2008-2009 Marius Muja, David G. Lowe.
2 * SPDX-FileCopyrightText: 2011-2026 Jose Luis Blanco-Claraco.
3 * SPDX-FileCopyrightText: 2026 Blender Authors.
4 *
5 * SPDX-License-Identifier: BSD-2-Clause */
6
15
16#include <algorithm>
17#include <bit>
18#include <cmath>
19#include <numeric>
20#include <optional>
21
22#include "BLI_array.hh"
23#include "BLI_bounds.hh"
25#include "BLI_index_mask.hh"
26#include "BLI_kdtree_new.hh"
28#include "BLI_math_vector.hh"
29#include "BLI_task.hh"
30#include "BLI_threads.hh"
31
32namespace blender {
33
34/* -------------------------------------------------------------------- */
37
39static constexpr int PARALLEL_BUILD_THRESHOLD = 10000;
40
42static constexpr int PARALLEL_BUILD_THRESHOLD_THREADS = 4;
43
45static constexpr int PARALLEL_SUBTREE_GRAIN = 4096;
46
48static constexpr int NODE_BLOCK_SIZE = 8192;
49
51static constexpr int NODE_MAX_BLOCKS = 64;
52
58static constexpr int NODE_BLOCK_FRACTION = 8;
59
64static constexpr int PARTITION_BLOCK_SIZE = 128;
65
78static int parallel_build_threads(const int64_t points_num)
79{
80 const double growth = std::sqrt(
81 std::sqrt(double(points_num) / double(PARALLEL_BUILD_THRESHOLD)));
82 return std::max(int(std::round(double(PARALLEL_BUILD_THRESHOLD_THREADS) * growth)), 1);
83}
84
86
87/* -------------------------------------------------------------------- */
90
91template<typename T> class TreeBuilder {
92 public:
93 using value_type = typename T::base_type;
94 static constexpr int dimensions = T::type_length;
95
96 private:
101 using BuildPoint = VecBase<value_type, dimensions + 1>;
102
103 using Node = kdtree::Node<value_type>;
104
110 struct NodeAllocator {
116 static constexpr int BATCH_SIZE_MAX = 256;
117
118 int batch_size = BATCH_SIZE_MAX;
124 LinearAllocator<> owned_allocator;
125 LinearAllocator<> *allocator = &owned_allocator;
126 MutableSpan<Node> batch;
127 /* Equal to the (empty) batch size, so that the first allocation starts a batch. */
128 int used = 0;
129
131 Node *allocate(const int num)
132 {
133 if (used + num > batch.size()) {
134 this->batch = this->allocator->allocate_array<Node>(batch_size);
135 this->used = 0;
136 /* Only the first batch is sized for the tree, the rest are full size. */
137 this->batch_size = BATCH_SIZE_MAX;
138 }
139 Node *nodes = &this->batch[used];
140 this->used += num;
141 return nodes;
142 }
143 };
144
145 public:
150 * `BLI_kdtree_performance_test`.
151 */
152 static int node_batch_size(const int points_num, const int leaf_size)
153 {
154 const int64_t leaves = std::max<int64_t>(1, points_num * 3 / (int64_t(leaf_size) * 2));
155 return int(std::min<int64_t>(2 * leaves + 1, NodeAllocator::BATCH_SIZE_MAX));
156 }
157
158 private:
159 const Span<T> points_;
161 const MutableSpan<int> indices_;
162 const int leaf_size_;
164 LinearAllocator<> &allocator_;
165
170 MutableSpan<BuildPoint> build_points_;
172 NodeAllocator pool_;
180 std::optional<threading::EnumerableThreadSpecific<NodeAllocator>> thread_allocators_;
182 public:
183 TreeBuilder(const Span<T> points,
184 const MutableSpan<int> indices,
185 const int leaf_size,
186 LinearAllocator<> &allocator)
187 : points_(points), indices_(indices), leaf_size_(leaf_size), allocator_(allocator)
188 {
189 }
190
191 Node *build(const Span<int> indices, Bounds<T> &r_bounds)
192 {
193 const int size = int(indices_.size());
194 BLI_assert(size > 0);
195
196 /* A tree that is a single leaf has nothing to split, and copying the coordinates aside would
197 * cost more than the rest of its build. */
198 if (size <= leaf_size_) {
199 return this->build_single_leaf(indices, r_bounds);
200 }
201
202 /* Splitting the build into tasks costs something even when there is no second thread to run
203 * them, so only ask for it when there is one. */
204 const bool threaded = size >= PARALLEL_BUILD_THRESHOLD && BLI_system_thread_count() > 1;
205 Node *root = nullptr;
206 if (threaded) {
208 [&]() { root = this->build_nodes(indices, r_bounds, true); });
209 }
210 else {
211 root = this->build_nodes(indices, r_bounds, false);
212 }
213 return root;
214 }
215
216 private:
217 /* -------------------------------------------------------------------- */
220
221 Node *build_single_leaf(const Span<int> indices, Bounds<T> &r_bounds)
222 {
223 if (indices.is_empty()) {
224 std::iota(indices_.begin(), indices_.end(), 0);
225 }
226 else if (indices.data() != indices_.data()) {
227 indices_.copy_from(indices);
228 }
229
230 r_bounds = Bounds<T>(points_[indices_.first()]);
231 for (const int index : indices_) {
232 math::min_max(points_[index], r_bounds.min, r_bounds.max);
233 }
234
235 Node *root = allocator_.allocate<Node>();
236 root->children = nullptr;
237 root->leaf.start = 0;
238 root->leaf.end = int(indices_.size());
239 return root;
240 }
241
242 Node *build_nodes(const Span<int> indices, Bounds<T> &r_bounds, const bool threaded)
243 {
244 const int size = int(indices_.size());
245 Array<BuildPoint, 256> build_points(size);
246
247 build_points_ = build_points.as_mutable_span();
248 const Bounds<BuildPoint> bounds = this->init_points(indices, threaded);
249
250 pool_.batch_size = node_batch_size(size, leaf_size_);
251 pool_.allocator = &allocator_;
252 if (threaded) {
253 thread_allocators_.emplace();
254 }
255 NodeAllocator &allocator = threaded ? thread_allocators_->local() : pool_;
256 Node *root = allocator.allocate(1);
257 this->build_node(root, 0, size, bounds, allocator, threaded);
258
259 /* The pool of the build itself took its batches from #allocator_ already, only the ones the
260 * threads filled have buffers of their own to hand over. */
261 if (thread_allocators_.has_value()) {
262 for (NodeAllocator &allocator : *thread_allocators_) {
263 allocator_.transfer_ownership_from(allocator.owned_allocator);
264 }
265 }
266
267 for (const int dim : IndexRange(dimensions)) {
268 r_bounds.min[dim] = bounds.min[dim];
269 r_bounds.max[dim] = bounds.max[dim];
270 }
271
272 /* The points are in the order the tree visits them now, so the indices they carry are the
273 * order to keep. The coordinates are not, since a search reads #points_. */
274 this->collect_indices(threaded);
275 return root;
276 }
277
284 Bounds<BuildPoint> init_points(const Span<int> indices, const bool threaded)
285 {
286 const int size = int(indices_.size());
287 const auto fill = [&](const int start, const int end) {
288 Bounds<BuildPoint> bounds(this->build_point(indices, start));
289 for (const int i : IndexRange(start, end - start)) {
290 const BuildPoint point = this->build_point(indices, i);
291 build_points_[i] = point;
292 bounds.min = math::min(bounds.min, point);
293 bounds.max = math::max(bounds.max, point);
294 }
295 return bounds;
296 };
297
298 const int blocks = threaded ? block_num(size) : 0;
299 if (blocks < 2) {
300 return fill(0, size);
301 }
302
303 Array<Bounds<BuildPoint>, NODE_MAX_BLOCKS> block_bounds(blocks);
304 threading::parallel_for(IndexRange(blocks), 1, [&](const IndexRange range) {
305 for (const int block : range) {
306 block_bounds[block] = fill(block_begin(size, blocks, block),
307 block_begin(size, blocks, block + 1));
308 }
309 });
310 return merge_bounds(block_bounds);
311 }
312
313 BuildPoint build_point(const Span<int> indices, const int i) const
314 {
315 const int index = indices.is_empty() ? i : indices[i];
316 BuildPoint point;
317 for (const int dim : IndexRange(dimensions)) {
318 point[dim] = points_[index][dim];
319 }
320 point[dimensions] = std::bit_cast<value_type>(index);
321 return point;
322 }
323
325 void collect_indices(const bool threaded)
326 {
327 const int size = int(indices_.size());
328 const auto fill = [&](const int start, const int end) {
329 for (const int i : IndexRange(start, end - start)) {
330 indices_[i] = std::bit_cast<int>(build_points_[i][dimensions]);
331 }
332 };
333
334 const int blocks = threaded ? block_num(size) : 0;
335 if (blocks < 2) {
336 fill(0, size);
337 return;
338 }
339 threading::parallel_for(IndexRange(blocks), 1, [&](const IndexRange range) {
340 for (const int block : range) {
341 fill(block_begin(size, blocks, block), block_begin(size, blocks, block + 1));
342 }
343 });
344 }
345
351 void build_node(Node *node,
352 const int start,
353 const int end,
354 const Bounds<BuildPoint> &bounds,
355 NodeAllocator &allocator,
356 const bool threaded)
357 {
358 if (end - start <= leaf_size_) {
359 node->children = nullptr;
360 node->leaf.start = start;
361 node->leaf.end = end;
362 return;
363 }
364
365 /* Split the widest extent of the points in half. */
366 const BuildPoint extent = bounds.max - bounds.min;
367 int dim = 0;
368 for (const int other : IndexRange(1, dimensions - 1)) {
369 if (extent[other] > extent[dim]) {
370 dim = other;
371 }
372 }
373 const value_type split_value = bounds.min[dim] + extent[dim] / 2;
374
375 /* Split the node a block at a time, which a threaded build spreads over its threads. For
376 * determinism, only the range size is used to check whether to use the blocked partitioning,
377 * not whether threading happens to be enabled. Below this size there are enough subtrees to
378 * keep the threads busy on their own, and the blocks would only be extra work. */
379 const bool split_blocks = int64_t(end - start) * NODE_BLOCK_FRACTION > build_points_.size();
380
381 int middle = split_blocks ? this->partition_points_in_blocks(start, end, dim, split_value) :
382 partition_points(build_points_, start, end, dim, split_value);
383 if (middle == start || middle == end) {
384 /* Everything ended up on one side, which means the coordinates of the points are within
385 * rounding distance of each other in every dimension. Split them in the middle so that the
386 * recursion still terminates. */
387 middle = start + (end - start) / 2;
388 }
389
390 Bounds<BuildPoint> left_bounds, right_bounds;
391 if (split_blocks) {
392 left_bounds = this->compute_bounds_in_blocks(start, middle);
393 right_bounds = this->compute_bounds_in_blocks(middle, end);
394 }
395 else {
396 left_bounds = compute_bounds(build_points_, start, middle);
397 right_bounds = compute_bounds(build_points_, middle, end);
398 }
399
400 node->dim = dim;
401 node->children = allocator.allocate(2);
402 if (threaded && end - start > PARALLEL_SUBTREE_GRAIN) {
404 [&]() {
405 this->build_node(
406 &node->children[0], start, middle, left_bounds, thread_allocators_->local(), true);
407 },
408 [&]() {
409 this->build_node(
410 &node->children[1], middle, end, right_bounds, thread_allocators_->local(), true);
411 });
412 }
413 else {
414 this->build_node(&node->children[0], start, middle, left_bounds, allocator, false);
415 this->build_node(&node->children[1], middle, end, right_bounds, allocator, false);
416 }
417
418 node->split.low = left_bounds.max[dim];
419 node->split.high = right_bounds.min[dim];
420 }
421
423
424 /* -------------------------------------------------------------------- */
427
428 static Bounds<BuildPoint> compute_bounds(const Span<BuildPoint> points,
429 const int start,
430 const int end)
431 {
432 /* Straight to the loop rather than through #bounds::min_max: this runs twice per interior
433 * node, and the profiler scope that one opens costs more than the bounds of a small node. */
434 return bounds::detail::min_max_lanes(points.slice(start, end - start));
435 }
436
438 Bounds<BuildPoint> compute_bounds_in_blocks(const int start, const int end)
439 {
440 const int count = end - start;
441 const int blocks = block_num(count);
442 if (blocks < 2) {
443 return compute_bounds(build_points_, start, end);
444 }
445
446 Array<Bounds<BuildPoint>, NODE_MAX_BLOCKS> block_bounds(blocks);
447 threading::parallel_for(IndexRange(blocks), 1, [&](const IndexRange range) {
448 for (const int block : range) {
449 block_bounds[block] = compute_bounds(build_points_,
450 start + block_begin(count, blocks, block),
451 start + block_begin(count, blocks, block + 1));
452 }
453 });
454 return merge_bounds(block_bounds);
455 }
456
457 static Bounds<BuildPoint> merge_bounds(const Span<Bounds<BuildPoint>> block_bounds)
458 {
459 Bounds<BuildPoint> bounds = block_bounds.first();
460 for (const Bounds<BuildPoint> &other : block_bounds.drop_front(1)) {
461 bounds.min = math::min(bounds.min, other.min);
462 bounds.max = math::max(bounds.max, other.max);
463 }
464 return bounds;
465 }
466
468
469 /* -------------------------------------------------------------------- */
472
483 static int partition_points(const MutableSpan<BuildPoint> points,
484 const int start,
485 const int end,
486 const int dim,
487 const value_type split_value)
488 {
489 constexpr int block = PARTITION_BLOCK_SIZE;
490
491 uint8_t offsets_l[block], offsets_r[block];
492 int num_l = 0, num_r = 0, first_l = 0, first_r = 0;
493 int l = start, r = end;
494
495 while (r - l > 2 * block) {
496 /* Offsets of the points of the left block that belong on the right, and the other way
497 * around. The store always happens, only the counter advances conditionally. */
498 if (num_l == 0) {
499 first_l = 0;
500 for (const int i : IndexRange(block)) {
501 offsets_l[num_l] = uint8_t(i);
502 num_l += int(!(points[l + i][dim] < split_value));
503 }
504 }
505 if (num_r == 0) {
506 first_r = 0;
507 for (const int i : IndexRange(block)) {
508 offsets_r[num_r] = uint8_t(i);
509 num_r += int(points[r - 1 - i][dim] < split_value);
510 }
511 }
512
513 const int num = std::min(num_l, num_r);
514 for (const int i : IndexRange(num)) {
515 std::swap(points[l + offsets_l[first_l + i]], points[r - 1 - offsets_r[first_r + i]]);
516 }
517 num_l -= num;
518 num_r -= num;
519 first_l += num;
520 first_r += num;
521
522 /* A block is done once none of its points are misplaced any more. */
523 if (num_l == 0) {
524 l += block;
525 }
526 if (num_r == 0) {
527 r -= block;
528 }
529 }
530
531 return partition_points_small(points, l, r, dim, split_value);
532 }
533
539 static int partition_points_small(const MutableSpan<BuildPoint> points,
540 const int start,
541 const int end,
542 const int dim,
543 const value_type split_value)
544 {
545 const int count = end - start;
546 BLI_assert(count <= 2 * PARTITION_BLOCK_SIZE);
547
548 std::array<BuildPoint, 2 * PARTITION_BLOCK_SIZE> buffer;
549 /* Points below the split fill the buffer from the front, the others from the back. Only the
550 * position depends on the comparison, so there is nothing to mispredict. */
551 int l = 0, r = count;
552 for (const int i : IndexRange(start, count)) {
553 /* Read the coordinate from the array rather than from a copy of the point: indexing a
554 * vector by a value only known at runtime means it has to be in memory, and a copy would
555 * have to be spilled there every iteration. */
556 const bool less = points[i][dim] < split_value;
557 const BuildPoint point = points[i];
558 /* Written to both ends, of which only one is kept. Picking the position instead lets a
559 * compiler turn it back into a branch on the comparison, which is the whole thing this
560 * avoids, and both ends are a few cache lines apart at most. */
561 buffer[l] = point;
562 buffer[r - 1] = point;
563 l += int(less);
564 r -= int(!less);
565 }
566
567 MutableSpan<BuildPoint> range = points.slice(start, count);
568 for (const int i : IndexRange(count)) {
569 range[i] = buffer[i];
570 }
571 return start + l;
572 }
573
585 int partition_points_in_blocks(const int start,
586 const int end,
587 const int dim,
588 const value_type split_value)
589 {
590 const MutableSpan<BuildPoint> points = build_points_;
591 const int count = end - start;
592 const int blocks = block_num(count);
593 if (blocks < 2) {
594 return partition_points(points, start, end, dim, split_value);
595 }
596
597 int begin[NODE_MAX_BLOCKS + 1];
598 int middle[NODE_MAX_BLOCKS];
599 for (const int block : IndexRange(blocks + 1)) {
600 begin[block] = start + block_begin(count, blocks, block);
601 }
602
603 threading::parallel_for(IndexRange(blocks), 1, [&](const IndexRange range) {
604 for (const int block : range) {
605 middle[block] = partition_points(points, begin[block], begin[block + 1], dim, split_value);
606 }
607 });
608
609 /* Where the split ends up once the blocks are put in order. */
610 int split = start;
611 for (const int block : IndexRange(blocks)) {
612 split += middle[block] - begin[block];
613 }
614
615 /* The points that are on the wrong side of it. A block lies either before or after the
616 * split, so it contributes to one of the two lists at most. */
617 IndexRange high[NODE_MAX_BLOCKS], low[NODE_MAX_BLOCKS];
618 int high_num = 0, low_num = 0;
619 for (const int block : IndexRange(blocks)) {
620 if (middle[block] < split) {
621 const int last = std::min(begin[block + 1], split);
622 if (middle[block] < last) {
623 high[high_num++] = IndexRange::from_begin_end(middle[block], last);
624 }
625 }
626 else if (middle[block] > split) {
627 const int first = std::max(begin[block], split);
628 if (first < middle[block]) {
629 low[low_num++] = IndexRange::from_begin_end(first, middle[block]);
630 }
631 }
632 }
633
634 /* Pair the two lists up into chunks that can be swapped independently. Each step finishes a
635 * range on one side or the other, so there are fewer chunks than there are ranges. */
636 struct Swap {
637 int from;
638 int to;
639 int num;
640 };
641 Swap swaps[2 * NODE_MAX_BLOCKS];
642 int swaps_num = 0;
643 for (int h = 0, l = 0, h_done = 0, l_done = 0; h < high_num && l < low_num;) {
644 const int num = std::min(int(high[h].size()) - h_done, int(low[l].size()) - l_done);
645 swaps[swaps_num++] = {int(high[h].start()) + h_done, int(low[l].start()) + l_done, num};
646 h_done += num;
647 l_done += num;
648 if (h_done == int(high[h].size())) {
649 h++;
650 h_done = 0;
651 }
652 if (l_done == int(low[l].size())) {
653 l++;
654 l_done = 0;
655 }
656 }
657
658 threading::parallel_for(IndexRange(swaps_num), 1, [&](const IndexRange range) {
659 for (const int i : range) {
660 const Swap &swap = swaps[i];
661 for (const int offset : IndexRange(swap.num)) {
662 std::swap(points[swap.from + offset], points[swap.to + offset]);
663 }
664 }
665 });
666
667 return split;
668 }
669
670 static int block_num(const int count)
671 {
672 return std::min(count / NODE_BLOCK_SIZE, NODE_MAX_BLOCKS);
673 }
674
675 static int block_begin(const int count, const int blocks, const int block)
676 {
677 return int(int64_t(count) * block / blocks);
678 }
679
681};
682
684
685/* -------------------------------------------------------------------- */
688
689template<typename T>
690void KDTreeNew<T>::build(const Span<T> points,
691 const Span<int> indices,
692 const IndexMask *mask,
693 const int size,
694 const int leaf_size,
695 LinearAllocator<> &allocator)
696{
697 points_ = points.data();
698 if (size == 0) {
699 return;
700 }
701 const MutableSpan<int> tree_indices = allocator.allocate_array<int>(size);
702
703 Span<int> source;
704 if (mask) {
705 mask->to_indices<int>(tree_indices);
706 source = tree_indices;
707 }
708 else {
709 source = indices;
710 }
711
712 TreeBuilder<T> builder(points, tree_indices, leaf_size, allocator);
713 root_ = builder.build(source, bounds_);
714 tree_indices_ = tree_indices.data();
715 size_ = size;
716
717#ifndef NDEBUG
718 /* Only the pointer to the points is kept, so nothing can check a search result against their
719 * number later. Everything the tree can return comes from here. */
720 for (const int index : tree_indices) {
721 BLI_assert(index >= 0 && index < points.size());
722 }
723#endif
724}
725
726template<typename T>
727LinearAllocator<> &KDTreeNew<T>::make_allocator(const int points_num,
728 const int leaf_size,
729 void *&r_owned)
730{
731 /* Allocate enough for the allocator itself, the indices, and the first set of nodes. */
732 const int64_t indices_size = int64_t(points_num) * sizeof(int);
733 const int64_t nodes_size = int64_t(TreeBuilder<T>::node_batch_size(points_num, leaf_size)) *
734 sizeof(Node);
735 /* Room for the allocator to align each of the two allocations it hands out of this. */
736 const int64_t alignment_slack = 2 * alignof(std::max_align_t);
737 const int64_t rest = indices_size + nodes_size + alignment_slack;
738 const int64_t size = sizeof(LinearAllocator<>) + rest;
739
740 void *buffer = MEM_new_uninitialized_aligned(size, alignof(LinearAllocator<>), __func__);
741 r_owned = buffer;
742 LinearAllocator<> *allocator = new (buffer) LinearAllocator<>();
743 allocator->provide_buffer(static_cast<char *>(buffer) + sizeof(LinearAllocator<>), rest);
744 return *allocator;
745}
746
747template<typename T> KDTreeNew<T>::~KDTreeNew()
748{
749 /* An allocator the caller passed is only borrowed, and outlives the tree. The tree's own sits
750 * at the start of the buffer it was built in. */
751 if (owned_buffer_ != nullptr) {
752 std::destroy_at(static_cast<LinearAllocator<> *>(owned_buffer_));
753 MEM_delete_void(owned_buffer_);
754 }
755}
756
757template<typename T>
758KDTreeNew<T>::KDTreeNew(const Span<T> points, LinearAllocator<> &allocator, const int leaf_size)
759{
760 this->build(points, Span<int>(), nullptr, int(points.size()), std::max(leaf_size, 1), allocator);
761}
762
763template<typename T>
765 const IndexMask &mask,
766 LinearAllocator<> &allocator,
767 const int leaf_size)
768{
769 const std::optional<IndexRange> range = mask.to_range();
770 const bool every_point = range && *range == points.index_range();
771 /* Avoid the indirection when the mask contains every point anyway. */
772 this->build(points,
773 Span<int>(),
774 every_point ? nullptr : &mask,
775 int(mask.size()),
776 std::max(leaf_size, 1),
777 allocator);
778}
779
780template<typename T>
782 const Span<int> indices,
783 LinearAllocator<> &allocator,
784 const int leaf_size)
785{
786 this->build(points, indices, nullptr, int(indices.size()), std::max(leaf_size, 1), allocator);
787}
788
789template<typename T> KDTreeNew<T>::KDTreeNew(const Span<T> points, const int leaf_size)
790{
791 this->build(points,
792 Span<int>(),
793 nullptr,
794 int(points.size()),
795 std::max(leaf_size, 1),
796 make_allocator(int(points.size()), std::max(leaf_size, 1), owned_buffer_));
797}
798
799template<typename T>
800KDTreeNew<T>::KDTreeNew(const Span<T> points, const IndexMask &mask, const int leaf_size)
801{
802 const std::optional<IndexRange> range = mask.to_range();
803 const bool every_point = range && *range == points.index_range();
804 this->build(points,
805 Span<int>(),
806 every_point ? nullptr : &mask,
807 int(mask.size()),
808 std::max(leaf_size, 1),
809 make_allocator(int(mask.size()), std::max(leaf_size, 1), owned_buffer_));
810}
811
812template<typename T>
813KDTreeNew<T>::KDTreeNew(const Span<T> points, const Span<int> indices, const int leaf_size)
814{
815 this->build(points,
816 indices,
817 nullptr,
818 int(indices.size()),
819 std::max(leaf_size, 1),
820 make_allocator(int(indices.size()), std::max(leaf_size, 1), owned_buffer_));
821}
822
823template class KDTreeNew<float2>;
824template class KDTreeNew<float3>;
825
827
828/* -------------------------------------------------------------------- */
831
832namespace kdtree {
833
834template<typename T, typename ForeachFn>
835static int calc_duplicates_impl(const KDTreeNew<T> &tree,
836 const typename T::base_type range,
837 const MutableSpan<int> duplicates,
838 const ForeachFn foreach_index)
839{
840 using value_type = typename T::base_type;
841 const T *points = tree.points();
842 int found = 0;
843 foreach_index([&](const int index) {
844 BLI_assert(index < duplicates.size());
845 /* Skip points that are already merged into another point. Points that were preset to their
846 * own index are not merged themselves, but can still be merged into. */
847 if (duplicates[index] != -1 && duplicates[index] != index) {
848 return;
849 }
850 const int found_before = found;
852 points[index], range, [&](const int other, const value_type /*distance_sq*/) {
853 if (other != index && duplicates[other] == -1) {
854 duplicates[other] = index;
855 found++;
856 }
857 });
858 if (found != found_before) {
859 /* Mark as a target so the merged points don't form chains. */
860 duplicates[index] = index;
861 }
862 });
863 return found;
864}
865
866template<typename T>
868 const typename T::base_type range,
869 const Span<int> visit_order,
870 const MutableSpan<int> duplicates)
871{
872 BLI_assert(visit_order.size() == tree.size());
873 return calc_duplicates_impl(tree, range, duplicates, [&](const auto fn) {
874 for (const int index : visit_order) {
875 fn(index);
876 }
877 });
878}
879
880template<typename T>
882 const typename T::base_type range,
883 const IndexMask &visit_order,
884 const MutableSpan<int> duplicates)
885{
886 BLI_assert(visit_order.size() == tree.size());
887 return calc_duplicates_impl(tree, range, duplicates, [&](const auto fn) {
888 visit_order.foreach_index_optimized<int>(fn);
889 });
890}
891
895 float,
896 const IndexMask &,
899 float,
900 const IndexMask &,
902
903} // namespace kdtree
904
906
907} // namespace blender
#define BLI_assert(a)
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr bool is_empty() const
Definition BLI_span.hh:264
static constexpr IndexRange from_begin_end(const int64_t begin, const int64_t end)
constexpr IndexRange()=default
void foreach_in_radius(const T &position, const value_type radius, Fn &&fn) const
const T * points() const
KDTreeNew(Span< T > points, int leaf_size=LEAF_SIZE_DEFAULT)
Definition kdtree.cc:789
void provide_buffer(void *buffer, const int64_t size)
MutableSpan< T > allocate_array(int64_t size)
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr T * data() const
Definition BLI_span.hh:545
constexpr T * end() const
Definition BLI_span.hh:554
constexpr T * begin() const
Definition BLI_span.hh:550
constexpr void copy_from(Span< T > values) const
Definition BLI_span.hh:745
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr bool is_empty() const
Definition BLI_span.hh:264
typename T::base_type value_type
Definition kdtree.cc:93
Node * build(const Span< int > indices, Bounds< T > &r_bounds)
Definition kdtree.cc:191
static int node_batch_size(const int points_num, const int leaf_size)
Definition kdtree.cc:152
static constexpr int dimensions
Definition kdtree.cc:94
TreeBuilder(const Span< T > points, const MutableSpan< int > indices, const int leaf_size, LinearAllocator<> &allocator)
Definition kdtree.cc:183
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
#define index(i)
#define T
Bounds< T > min_max_lanes(const Span< T > values)
Definition BLI_bounds.hh:72
int size(const AssetLibraryReference *library_reference)
BLI_NOINLINE void fill(T *__restrict data, const T &value, const IndexMask &mask)
void split(const std::string &s, const char delim, std::vector< std::string > &tokens)
Definition abc_util.cc:68
int calc_duplicates(const KDTreeNew< T > &tree, typename T::base_type range, Span< int > visit_order, MutableSpan< int > duplicates)
Definition kdtree.cc:867
static int calc_duplicates_impl(const KDTreeNew< T > &tree, const typename T::base_type range, const MutableSpan< int > duplicates, const ForeachFn foreach_index)
Definition kdtree.cc:835
T min(const T &a, const T &b)
void min_max(const T &value, T &min, T &max)
T max(const T &a, const T &b)
void parallel_invoke(Functions &&...functions)
Definition BLI_task.hh:197
void max_threads_task(const int max_threads, const Function &function)
Definition BLI_task.hh:239
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
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static int parallel_build_threads(const int64_t points_num)
Definition kdtree.cc:78
__int64 int64_t
Definition BKE_text.h:90
ATTR_WARN_UNUSED_RESULT const BMLoop * l
static constexpr int PARTITION_BLOCK_SIZE
Definition kdtree.cc:64
static constexpr int PARALLEL_SUBTREE_GRAIN
Definition kdtree.cc:45
static constexpr int NODE_MAX_BLOCKS
Definition kdtree.cc:51
void MEM_delete_void(void *vmemh)
void * MEM_new_uninitialized_aligned(size_t len, size_t alignment, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(3)
int BLI_system_thread_count()
Definition threads.cc:258
static constexpr int PARALLEL_BUILD_THRESHOLD
Definition kdtree.cc:39
unsigned char uint8_t
Definition BKE_text.h:79
ATTR_WARN_UNUSED_RESULT const size_t num
static constexpr int PARALLEL_BUILD_THRESHOLD_THREADS
Definition kdtree.cc:42
iter begin(iter)
static constexpr int NODE_BLOCK_SIZE
Definition kdtree.cc:48
static constexpr int NODE_BLOCK_FRACTION
Definition kdtree.cc:58
#define swap(a, b)
Definition sort.cc:61
Bounds()=default