Blender V5.3
BLI_kdtree.hh
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#pragma once
6
11
12#include "MEM_guardedalloc.h"
13
14#include "BLI_array.hh"
15#include "BLI_kdtree_types.hh"
16#include "BLI_math_base_c.hh"
17#include "BLI_math_vector.hh"
18#include "BLI_stack.hh"
19#include "BLI_vector.hh"
20
21#include "PRF_profile.hh"
22
23#include <algorithm>
24
25namespace blender {
26
27namespace detail {
28
29constexpr int kd_stack_init = 100; /* initial size for array (on the stack) */
30constexpr int kd_near_alloc_inc = 100; /* alloc increment for collecting nearest */
31constexpr int kd_found_alloc_inc = 50; /* alloc increment for collecting nearest */
32
33constexpr uint kd_node_unset = (uint(-1));
34
39constexpr uint kd_node_root_is_init = (uint(-2));
40
41template<typename CoordT>
42inline typename KDTreeCoordTraits<CoordT>::ValueType axis_get(const CoordT &co, uint axis)
43{
44 return KDTreeCoordTraits<CoordT>::get(co, axis);
45}
46
47template<typename CoordT>
49 const CoordT &b)
50{
51 return math::distance_squared(a, b);
52}
53template<> inline float distance_squared<float>(const float &a, const float &b)
54{
55 const float d = a - b;
56 return d * d;
57}
58
59} // namespace detail
60
65template<typename CoordT> inline KDTree<CoordT> *kdtree_new(uint nodes_len_capacity)
66{
67 KDTree<CoordT> *tree;
68
69 tree = MEM_new_zeroed<KDTree<CoordT>>("KDTree");
70 tree->nodes = MEM_new_array_uninitialized<KDTreeNode<CoordT>>(nodes_len_capacity,
71 "KDTreeNode<>");
72 tree->nodes_len = 0;
74 tree->max_node_index = -1;
75
76#ifndef NDEBUG
77 tree->is_balanced = false;
78 tree->nodes_len_capacity = nodes_len_capacity;
79#endif
80
81 return tree;
82}
83
84template<typename CoordT> inline void kdtree_free(KDTree<CoordT> *tree)
85{
86 if (tree) {
87 MEM_delete(tree->nodes);
88 MEM_delete(tree);
89 }
90}
91
95template<typename CoordT>
96inline void kdtree_insert(KDTree<CoordT> *tree, int index, const CoordT &co)
97{
98 KDTreeNode<CoordT> *node = &tree->nodes[tree->nodes_len++];
99
100#ifndef NDEBUG
102#endif
103
104 /* NOTE: array isn't calloc'd,
105 * need to initialize all struct members */
106
107 node->left = node->right = detail::kd_node_unset;
108 node->co = co;
109 node->index = index;
110 node->d = 0;
111 tree->max_node_index = std::max(tree->max_node_index, index);
112
113#ifndef NDEBUG
114 tree->is_balanced = false;
115#endif
116}
117
118namespace detail {
119
120template<typename CoordT>
121static uint kdtree_balance(KDTreeNode<CoordT> *nodes, uint nodes_len, uint axis, const uint ofs)
122{
124 typename KDTree<CoordT>::ValueType co;
125 uint left, right, median, i, j;
126
127 if (nodes_len <= 0) {
129 }
130 if (nodes_len == 1) {
131 return 0 + ofs;
132 }
133
134 /* Quick-sort style sorting around median. */
135 left = 0;
136 right = nodes_len - 1;
137 median = nodes_len / 2;
138
139 while (right > left) {
140 co = axis_get(nodes[right].co, axis);
141 i = left - 1;
142 j = right;
143
144 while (true) {
145 while (axis_get(nodes[++i].co, axis) < co) { /* pass */
146 }
147 while (axis_get(nodes[--j].co, axis) > co && j > left) { /* pass */
148 }
149
150 if (i >= j) {
151 break;
152 }
153
157 }
158
161 *(KDTreeNode_head<CoordT> *)&nodes[right]);
162 if (i >= median) {
163 right = i - 1;
164 }
165 if (i <= median) {
166 left = i + 1;
167 }
168 }
169
170 /* Set node and sort sub-nodes. */
171 node = &nodes[median];
172 node->d = axis;
173 axis = (axis + 1) % KDTree<CoordT>::DimsNum;
174 node->left = kdtree_balance(nodes, median, axis, ofs);
175 node->right = kdtree_balance(
176 nodes + median + 1, (nodes_len - (median + 1)), axis, (median + 1) + ofs);
177
178 return median + ofs;
179}
180
181} // namespace detail
182
183template<typename CoordT> inline void kdtree_balance(KDTree<CoordT> *tree)
184{
186 if (tree->root != detail::kd_node_root_is_init) {
187 for (uint i = 0; i < tree->nodes_len; i++) {
190 }
191 }
192
193 tree->root = detail::kdtree_balance<CoordT>(tree->nodes, tree->nodes_len, 0, 0);
194
195#ifndef NDEBUG
196 tree->is_balanced = true;
197#endif
198}
199
207template<typename CoordT, typename Filter>
209 const CoordT &co,
210 KDTreeNearest<CoordT> *r_nearest,
211 Filter &&filter_cb)
212{
213 const KDTreeNode<CoordT> *nodes = tree->nodes;
214 const KDTreeNode<CoordT> *min_node = nullptr;
215 typename KDTree<CoordT>::ValueType min_dist = FLT_MAX, cur_dist;
216
217#ifndef NDEBUG
218 BLI_assert(tree->is_balanced == true);
219#endif
220
221 if (tree->root == detail::kd_node_unset) [[unlikely]] {
222 return -1;
223 }
224
225 const auto node_test_nearest = [&](const KDTreeNode<CoordT> *node) -> bool {
226 const auto dist_sq = detail::distance_squared((node)->co, co);
227 if (dist_sq >= min_dist) {
228 return false;
229 }
230 const int result = filter_cb((node)->index, (node)->co, dist_sq);
231 if (result == 1) {
232 min_dist = dist_sq;
233 min_node = node;
234 return false;
235 }
236
237 if (result == 0) {
238 /* pass */
239 return false;
240 }
241
242 BLI_assert(result == -1);
243 return true;
244 };
245
247 stack.push(tree->root);
248
249 while (!stack.is_empty()) {
250 const KDTreeNode<CoordT> *node = &nodes[stack.pop()];
251
252 cur_dist = detail::axis_get(node->co, node->d) - detail::axis_get(co, node->d);
253
254 if (cur_dist < 0.0f) {
255 cur_dist = -cur_dist * cur_dist;
256
257 if (-cur_dist < min_dist) {
258 if (node_test_nearest(node)) {
259 break;
260 }
261
262 if (node->left != detail::kd_node_unset) {
263 stack.push(node->left);
264 }
265 }
266 if (node->right != detail::kd_node_unset) {
267 stack.push(node->right);
268 }
269 }
270 else {
271 cur_dist = cur_dist * cur_dist;
272
273 if (cur_dist < min_dist) {
274 if (node_test_nearest(node)) {
275 break;
276 }
277
278 if (node->right != detail::kd_node_unset) {
279 stack.push(node->right);
280 }
281 }
282 if (node->left != detail::kd_node_unset) {
283 stack.push(node->left);
284 }
285 }
286 }
287
288 if (min_node) {
289 if (r_nearest) {
290 r_nearest->index = min_node->index;
291 r_nearest->dist = sqrtf(min_dist);
292 r_nearest->co = min_node->co;
293 }
294
295 return min_node->index;
296 }
297 return -1;
298}
299
303template<typename CoordT>
304inline int kdtree_find_nearest(const KDTree<CoordT> *tree,
305 const CoordT &co,
306 KDTreeNearest<CoordT> *r_nearest)
307{
309 tree,
310 co,
311 r_nearest,
312 [](const uint /*index*/, const CoordT & /*coord*/, const auto /*dist*/) { return 1; });
313}
314
315namespace detail {
316
317template<typename CoordT>
319 uint *nearest_len,
320 const uint nearest_len_capacity,
321 const int index,
322 const typename KDTree<CoordT>::ValueType dist,
323 const CoordT &co)
324{
325 uint i;
326
327 if (*nearest_len < nearest_len_capacity) {
328 (*nearest_len)++;
329 }
330
331 for (i = *nearest_len - 1; i > 0; i--) {
332 if (dist >= nearest[i - 1].dist) {
333 break;
334 }
335 nearest[i] = nearest[i - 1];
336 }
337
338 nearest[i].index = index;
339 nearest[i].dist = dist;
340 nearest[i].co = co;
341}
342
343} // namespace detail
344
350template<typename CoordT, typename Func>
352 const CoordT &co,
353 KDTreeNearest<CoordT> r_nearest[],
354 const uint nearest_len_capacity,
355 Func &&len_sq_fn)
356{
357 const KDTreeNode<CoordT> *nodes = tree->nodes;
358 const KDTreeNode<CoordT> *root;
359 typename KDTree<CoordT>::ValueType cur_dist;
360 uint i, nearest_len = 0;
361
362#ifndef NDEBUG
363 BLI_assert(tree->is_balanced == true);
364#endif
365
366 if ((tree->root == detail::kd_node_unset) || nearest_len_capacity == 0) [[unlikely]] {
367 return 0;
368 }
369
370 root = &nodes[tree->root];
371
372 cur_dist = len_sq_fn(co, root->co);
374 r_nearest, &nearest_len, nearest_len_capacity, root->index, cur_dist, root->co);
375
377 if (detail::axis_get(co, root->d) < detail::axis_get(root->co, root->d)) {
378 if (root->right != detail::kd_node_unset) {
379 stack.push(root->right);
380 }
381 if (root->left != detail::kd_node_unset) {
382 stack.push(root->left);
383 }
384 }
385 else {
386 if (root->left != detail::kd_node_unset) {
387 stack.push(root->left);
388 }
389 if (root->right != detail::kd_node_unset) {
390 stack.push(root->right);
391 }
392 }
393
394 while (!stack.is_empty()) {
395 const KDTreeNode<CoordT> *node = &nodes[stack.pop()];
396
397 cur_dist = detail::axis_get(node->co, node->d) - detail::axis_get(co, node->d);
398
399 if (cur_dist < 0.0f) {
400 cur_dist = -cur_dist * cur_dist;
401
402 if (nearest_len < nearest_len_capacity || -cur_dist < r_nearest[nearest_len - 1].dist) {
403 cur_dist = len_sq_fn(co, node->co);
404
405 if (nearest_len < nearest_len_capacity || cur_dist < r_nearest[nearest_len - 1].dist) {
407 r_nearest, &nearest_len, nearest_len_capacity, node->index, cur_dist, node->co);
408 }
409
410 if (node->left != detail::kd_node_unset) {
411 stack.push(node->left);
412 }
413 }
414 if (node->right != detail::kd_node_unset) {
415 stack.push(node->right);
416 }
417 }
418 else {
419 cur_dist = cur_dist * cur_dist;
420
421 if (nearest_len < nearest_len_capacity || cur_dist < r_nearest[nearest_len - 1].dist) {
422 cur_dist = len_sq_fn(co, node->co);
423 if (nearest_len < nearest_len_capacity || cur_dist < r_nearest[nearest_len - 1].dist) {
425 r_nearest, &nearest_len, nearest_len_capacity, node->index, cur_dist, node->co);
426 }
427
428 if (node->right != detail::kd_node_unset) {
429 stack.push(node->right);
430 }
431 }
432 if (node->left != detail::kd_node_unset) {
433 stack.push(node->left);
434 }
435 }
436 }
437
438 for (i = 0; i < nearest_len; i++) {
439 r_nearest[i].dist = sqrtf(r_nearest[i].dist);
440 }
441
442 return int(nearest_len);
443}
444
445template<typename CoordT>
447 const CoordT &co,
448 KDTreeNearest<CoordT> r_nearest[],
449 uint nearest_len_capacity)
450{
452 tree, co, r_nearest, nearest_len_capacity, [](const CoordT &a, const CoordT &b) {
453 return detail::distance_squared(a, b);
454 });
455}
456
457namespace detail {
458
459template<typename CoordT> static int nearest_cmp_dist(const void *a, const void *b)
460{
461 const KDTreeNearest<CoordT> *kda = static_cast<const KDTreeNearest<CoordT> *>(a);
462 const KDTreeNearest<CoordT> *kdb = static_cast<const KDTreeNearest<CoordT> *>(b);
463
464 if (kda->dist < kdb->dist) {
465 return -1;
466 }
467 if (kda->dist > kdb->dist) {
468 return 1;
469 }
470 return 0;
471}
472
473template<typename CoordT>
475 uint nearest_index,
476 uint *nearest_len_capacity,
477 const int index,
478 const typename KDTree<CoordT>::ValueType dist,
479 const CoordT &co)
480{
482
483 if (nearest_index >= *nearest_len_capacity) [[unlikely]] {
484 *r_nearest = static_cast<KDTreeNearest<CoordT> *>(MEM_realloc_uninitialized_id(
485 *r_nearest,
486 (*nearest_len_capacity += detail::kd_found_alloc_inc) * sizeof(KDTreeNode<CoordT>),
487 __func__));
488 }
489
490 to = (*r_nearest) + nearest_index;
491
492 to->index = index;
493 to->dist = sqrtf(dist);
494 to->co = co;
495}
496
497} // namespace detail
498
504template<typename CoordT, typename Func>
506 const CoordT &co,
507 KDTreeNearest<CoordT> **r_nearest,
508 const typename KDTree<CoordT>::ValueType range,
509 Func &&len_sq_fn)
510{
511 const KDTreeNode<CoordT> *nodes = tree->nodes;
512 KDTreeNearest<CoordT> *nearest = nullptr;
513 const typename KDTree<CoordT>::ValueType range_sq = range * range;
514 typename KDTree<CoordT>::ValueType dist_sq;
515 uint nearest_len = 0, nearest_len_capacity = 0;
516
517#ifndef NDEBUG
518 BLI_assert(tree->is_balanced == true);
519#endif
520
521 if (tree->root == detail::kd_node_unset) [[unlikely]] {
522 return 0;
523 }
524
526 stack.push(tree->root);
527
528 while (!stack.is_empty()) {
529 const KDTreeNode<CoordT> *node = &nodes[stack.pop()];
530
531 if (detail::axis_get(co, node->d) + range < detail::axis_get(node->co, node->d)) {
532 if (node->left != detail::kd_node_unset) {
533 stack.push(node->left);
534 }
535 }
536 else if (detail::axis_get(co, node->d) - range > detail::axis_get(node->co, node->d)) {
537 if (node->right != detail::kd_node_unset) {
538 stack.push(node->right);
539 }
540 }
541 else {
542 dist_sq = len_sq_fn(co, node->co);
543 if (dist_sq <= range_sq) {
545 &nearest, nearest_len++, &nearest_len_capacity, node->index, dist_sq, node->co);
546 }
547
548 if (node->left != detail::kd_node_unset) {
549 stack.push(node->left);
550 }
551 if (node->right != detail::kd_node_unset) {
552 stack.push(node->right);
553 }
554 }
555 }
556
557 if (nearest_len) {
558 qsort(nearest, nearest_len, sizeof(KDTreeNearest<CoordT>), detail::nearest_cmp_dist<CoordT>);
559 }
560
561 *r_nearest = nearest;
562
563 return int(nearest_len);
564}
565
566template<typename CoordT>
567inline int kdtree_range_search(const KDTree<CoordT> *tree,
568 const CoordT &co,
569 KDTreeNearest<CoordT> **r_nearest,
570 typename KDTree<CoordT>::ValueType range)
571{
573 tree, co, r_nearest, range, [](const CoordT &a, const CoordT &b) {
574 return detail::distance_squared(a, b);
575 });
576}
577
587template<typename CoordT, typename Fn>
589 const CoordT &co,
590 typename KDTree<CoordT>::ValueType range,
591 Fn &&search_cb)
592{
593 const KDTreeNode<CoordT> *nodes = tree->nodes;
594
595 typename KDTree<CoordT>::ValueType range_sq = range * range, dist_sq;
596
597#ifndef NDEBUG
598 BLI_assert(tree->is_balanced == true);
599#endif
600
601 if (tree->root == detail::kd_node_unset) [[unlikely]] {
602 return;
603 }
604
606 stack.push(tree->root);
607
608 while (!stack.is_empty()) {
609 const KDTreeNode<CoordT> *node = &nodes[stack.pop()];
610
611 if (detail::axis_get(co, node->d) + range < detail::axis_get(node->co, node->d)) {
612 if (node->left != detail::kd_node_unset) {
613 stack.push(node->left);
614 }
615 }
616 else if (detail::axis_get(co, node->d) - range > detail::axis_get(node->co, node->d)) {
617 if (node->right != detail::kd_node_unset) {
618 stack.push(node->right);
619 }
620 }
621 else {
622 dist_sq = detail::distance_squared(node->co, co);
623 if (dist_sq <= range_sq) {
624 if (search_cb(node->index, node->co, dist_sq) == false) {
625 break;
626 }
627 }
628
629 if (node->left != detail::kd_node_unset) {
630 stack.push(node->left);
631 }
632 if (node->right != detail::kd_node_unset) {
633 stack.push(node->right);
634 }
635 }
636 }
637}
638
639namespace detail {
640
645template<typename CoordT> static Vector<int> kdtree_order(const KDTree<CoordT> *tree)
646{
647 const KDTreeNode<CoordT> *nodes = tree->nodes;
648 Vector<int> order(tree->max_node_index + 1, -1);
649 for (uint i = 0; i < tree->nodes_len; i++) {
650 order[nodes[i].index] = int(i);
651 }
652 return order;
653}
654
655/* -------------------------------------------------------------------- */
658
659template<typename CoordT> struct DeDuplicateParams {
660 /* Static */
666
667 /* Per Search */
668 CoordT search_co;
670};
671
672template<typename CoordT>
674{
675 const KDTreeNode<CoordT> *node = &p->nodes[i];
676 if (axis_get(p->search_co, node->d) + p->range <= axis_get(node->co, node->d)) {
677 if (node->left != detail::kd_node_unset) {
678 deduplicate_recursive(p, node->left);
679 }
680 }
681 else if (axis_get(p->search_co, node->d) - p->range >= axis_get(node->co, node->d)) {
682 if (node->right != detail::kd_node_unset) {
683 deduplicate_recursive(p, node->right);
684 }
685 }
686 else {
687 if ((p->search != node->index) && (p->duplicates[node->index] == -1)) {
688 if (distance_squared(node->co, p->search_co) <= p->range_sq) {
689 p->duplicates[node->index] = int(p->search);
690 *p->duplicates_found += 1;
691 }
692 }
693 if (node->left != detail::kd_node_unset) {
694 deduplicate_recursive(p, node->left);
695 }
696 if (node->right != detail::kd_node_unset) {
697 deduplicate_recursive(p, node->right);
698 }
699 }
700}
701
702} // namespace detail
703
722template<typename CoordT>
724 const typename KDTree<CoordT>::ValueType range,
725 const bool use_index_order,
726 int *duplicates)
727{
729 int found = 0;
730
732 p.nodes = tree->nodes;
733 p.range = range;
734 p.range_sq = square_f(range);
735 p.duplicates = duplicates;
736 p.duplicates_found = &found;
737
738 if (use_index_order) {
740 for (int i = 0; i < tree->max_node_index + 1; i++) {
741 const int node_index = order[i];
742 if (node_index == -1) {
743 continue;
744 }
745 const int index = i;
746 if (ELEM(duplicates[index], -1, index)) {
747 p.search = index;
748 p.search_co = tree->nodes[node_index].co;
749 int found_prev = found;
751 if (found != found_prev) {
752 /* Prevent chains of doubles. */
753 duplicates[index] = index;
754 }
755 }
756 }
757 }
758 else {
759 for (uint i = 0; i < tree->nodes_len; i++) {
760 const uint node_index = i;
761 const int index = p.nodes[node_index].index;
762 if (ELEM(duplicates[index], -1, index)) {
763 p.search = index;
764 p.search_co = tree->nodes[node_index].co;
765 int found_prev = found;
767 if (found != found_prev) {
768 /* Prevent chains of doubles. */
769 duplicates[index] = index;
770 }
771 }
772 }
773 }
774 return found;
775}
776
778
779/* -------------------------------------------------------------------- */
782
801template<typename CoordT, typename Func>
803 const typename KDTree<CoordT>::ValueType range,
804 int *duplicates,
805 const bool has_self_index,
806 Func &&duplicates_cb)
807{
808 BLI_assert(tree->is_balanced);
809 if (tree->root == detail::kd_node_unset) [[unlikely]] {
810 return 0;
811 }
812
813 /* Use `index_to_node_index` so coordinates are looked up in order first to last. */
814 const uint nodes_len = tree->nodes_len;
815 Array<int> index_to_node_index(tree->max_node_index + 1);
816 for (uint i = 0; i < nodes_len; i++) {
817 index_to_node_index[tree->nodes[i].index] = int(i);
818 }
819
820 int found = 0;
821
822 /* First pass, handle merging into self-index (if any exist). */
823 if (has_self_index) {
824 Array<typename KDTree<CoordT>::ValueType> duplicates_dist_sq(tree->max_node_index + 1);
825 for (uint i = 0; i < nodes_len; i++) {
826 const int node_index = tree->nodes[i].index;
827 if (node_index != duplicates[node_index]) {
828 continue;
829 }
830 const CoordT &search_co = tree->nodes[index_to_node_index[node_index]].co;
831 auto accumulate_neighbors_fn =
832 [&duplicates, &node_index, &duplicates_dist_sq, &found](
833 int neighbor_index,
834 const CoordT & /*co*/,
835 const typename KDTree<CoordT>::ValueType dist_sq) -> bool {
836 const int target_index = duplicates[neighbor_index];
837 if (target_index == -1) {
838 duplicates[neighbor_index] = node_index;
839 duplicates_dist_sq[neighbor_index] = dist_sq;
840 found += 1;
841 }
842 /* Don't steal from self references. */
843 else if (target_index != neighbor_index) {
844 typename KDTree<CoordT>::ValueType &dist_sq_best = duplicates_dist_sq[neighbor_index];
845 /* Steal the target if it's closer. */
846 if ((dist_sq < dist_sq_best) ||
847 /* Pick the lowest index as a tie breaker for a deterministic result. */
848 ((dist_sq == dist_sq_best) && (node_index < target_index)))
849 {
850 dist_sq_best = dist_sq;
851 duplicates[neighbor_index] = node_index;
852 }
853 }
854 return true;
855 };
856
857 kdtree_range_search_cb<CoordT>(tree, search_co, range, accumulate_neighbors_fn);
858 }
859 }
860
861 /* Second pass, de-duplicate clusters that weren't handled in the first pass. */
862
863 /* Could be inline, declare here to avoid re-allocation. */
864 Vector<int> cluster;
865 for (uint i = 0; i < nodes_len; i++) {
866 const int node_index = tree->nodes[i].index;
867 if (duplicates[node_index] != -1) {
868 continue;
869 }
870
871 BLI_assert(cluster.is_empty());
872 const CoordT &search_co = tree->nodes[index_to_node_index[node_index]].co;
873 auto accumulate_neighbors_fn =
874 [&duplicates, &cluster](int neighbor_index,
875 const CoordT & /*co*/,
876 const typename KDTree<CoordT>::ValueType /*dist_sq*/) -> bool {
877 if (duplicates[neighbor_index] == -1) {
878 cluster.append(neighbor_index);
879 }
880 return true;
881 };
882
883 kdtree_range_search_cb<CoordT>(tree, search_co, range, accumulate_neighbors_fn);
884 if (cluster.is_empty()) {
885 continue;
886 }
887 found += int(cluster.size());
888 cluster.append(node_index);
889
890 const int cluster_index = duplicates_cb(cluster.data(), int(cluster.size()));
891 BLI_assert(uint(cluster_index) < uint(cluster.size()));
892 const int target_index = cluster[cluster_index];
893 for (const int cluster_node_index : cluster) {
894 duplicates[cluster_node_index] = target_index;
895 }
896 cluster.clear();
897 }
898
899 return found;
900}
901
903
904} // namespace blender
A KD-tree for nearest neighbor search.
Read Blender memory allocation and freeing.
#define PRF_scope(category)
#define SWAP(type, a, b)
#define ELEM(...)
bool is_empty() const
Definition BLI_stack.hh:310
void push(const T &value)
Definition BLI_stack.hh:215
int64_t size() const
void append(const T &value)
bool is_empty() const
#define FLT_MAX
KDTreeCoordTraits< CoordT >::ValueType axis_get(const CoordT &co, uint axis)
Definition BLI_kdtree.hh:42
static void deduplicate_recursive(const DeDuplicateParams< CoordT > *p, uint i)
static void nearest_add_in_range(KDTreeNearest< CoordT > **r_nearest, uint nearest_index, uint *nearest_len_capacity, const int index, const typename KDTree< CoordT >::ValueType dist, const CoordT &co)
static uint kdtree_balance(KDTreeNode< CoordT > *nodes, uint nodes_len, uint axis, const uint ofs)
constexpr uint kd_node_unset
Definition BLI_kdtree.hh:33
constexpr int kd_stack_init
Definition BLI_kdtree.hh:29
constexpr int kd_near_alloc_inc
Definition BLI_kdtree.hh:30
constexpr uint kd_node_root_is_init
Definition BLI_kdtree.hh:39
static int nearest_cmp_dist(const void *a, const void *b)
static void nearest_ordered_insert(KDTreeNearest< CoordT > *nearest, uint *nearest_len, const uint nearest_len_capacity, const int index, const typename KDTree< CoordT >::ValueType dist, const CoordT &co)
static Vector< int > kdtree_order(const KDTree< CoordT > *tree)
constexpr int kd_found_alloc_inc
Definition BLI_kdtree.hh:31
KDTreeCoordTraits< CoordT >::ValueType distance_squared(const CoordT &a, const CoordT &b)
Definition BLI_kdtree.hh:48
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
BMesh Iterators.
int kdtree_find_nearest_n_with_len_squared_cb(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > r_nearest[], const uint nearest_len_capacity, Func &&len_sq_fn)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void kdtree_balance(KDTree< CoordT > *tree)
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
int kdtree_find_nearest_cb(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest, Filter &&filter_cb)
int kdtree_range_search_with_len_squared_cb(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > **r_nearest, const typename KDTree< CoordT >::ValueType range, Func &&len_sq_fn)
void kdtree_range_search_cb(const KDTree< CoordT > *tree, const CoordT &co, typename KDTree< CoordT >::ValueType range, Fn &&search_cb)
int kdtree_calc_duplicates_cb(const KDTree< CoordT > *tree, const typename KDTree< CoordT >::ValueType range, int *duplicates, const bool has_self_index, Func &&duplicates_cb)
KDTree< CoordT > * kdtree_new(uint nodes_len_capacity)
Definition BLI_kdtree.hh:65
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
int kdtree_find_nearest_n(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > r_nearest[], uint nearest_len_capacity)
void kdtree_insert(KDTree< CoordT > *tree, int index, const CoordT &co)
Definition BLI_kdtree.hh:96
int kdtree_find_nearest(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest)
void kdtree_free(KDTree< CoordT > *tree)
Definition BLI_kdtree.hh:84
int kdtree_calc_duplicates_fast(const KDTree< CoordT > *tree, const typename KDTree< CoordT >::ValueType range, const bool use_index_order, int *duplicates)
MINLINE float square_f(float a)
int kdtree_range_search(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > **r_nearest, typename KDTree< CoordT >::ValueType range)
void *(*) MEM_realloc_uninitialized_id(void *vmemh, size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(2)
#define sqrtf
static ValueType get(const CoordT &co, const int axis)
typename CoordT::base_type ValueType
uint32_t nodes_len_capacity
static constexpr int DimsNum
typename NodeT::ValueType ValueType
const KDTreeNode< CoordT > * nodes
KDTree< CoordT >::ValueType range_sq
KDTree< CoordT >::ValueType range