41template<
typename CoordT>
47template<
typename CoordT>
55 const float d = a -
b;
87 MEM_delete(tree->
nodes);
95template<
typename CoordT>
120template<
typename CoordT>
125 uint left, right, median, i, j;
127 if (nodes_len <= 0) {
130 if (nodes_len == 1) {
136 right = nodes_len - 1;
137 median = nodes_len / 2;
139 while (right > left) {
176 nodes + median + 1, (nodes_len - (median + 1)), axis, (median + 1) + ofs);
207template<
typename CoordT,
typename Filter>
227 if (dist_sq >= min_dist) {
254 if (cur_dist < 0.0f) {
255 cur_dist = -cur_dist * cur_dist;
257 if (-cur_dist < min_dist) {
258 if (node_test_nearest(
node)) {
271 cur_dist = cur_dist * cur_dist;
273 if (cur_dist < min_dist) {
274 if (node_test_nearest(
node)) {
292 r_nearest->
co = min_node->
co;
295 return min_node->
index;
303template<
typename CoordT>
312 [](
const uint ,
const CoordT & ,
const auto ) {
return 1; });
317template<
typename CoordT>
320 const uint nearest_len_capacity,
327 if (*nearest_len < nearest_len_capacity) {
331 for (i = *nearest_len - 1; i > 0; i--) {
332 if (dist >= nearest[i - 1].dist) {
335 nearest[i] = nearest[i - 1];
339 nearest[i].
dist = dist;
350template<
typename CoordT,
typename Func>
354 const uint nearest_len_capacity,
360 uint i, nearest_len = 0;
372 cur_dist = len_sq_fn(co, root->
co);
374 r_nearest, &nearest_len, nearest_len_capacity, root->
index, cur_dist, root->
co);
399 if (cur_dist < 0.0f) {
400 cur_dist = -cur_dist * cur_dist;
402 if (nearest_len < nearest_len_capacity || -cur_dist < r_nearest[nearest_len - 1].dist) {
403 cur_dist = len_sq_fn(co,
node->co);
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);
419 cur_dist = cur_dist * cur_dist;
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);
438 for (i = 0; i < nearest_len; i++) {
439 r_nearest[i].
dist =
sqrtf(r_nearest[i].dist);
442 return int(nearest_len);
445template<
typename CoordT>
449 uint nearest_len_capacity)
452 tree, co, r_nearest, nearest_len_capacity, [](
const CoordT &a,
const CoordT &
b) {
473template<
typename CoordT>
476 uint *nearest_len_capacity,
483 if (nearest_index >= *nearest_len_capacity) [[unlikely]] {
490 to = (*r_nearest) + nearest_index;
504template<
typename CoordT,
typename Func>
515 uint nearest_len = 0, nearest_len_capacity = 0;
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);
561 *r_nearest = nearest;
563 return int(nearest_len);
566template<
typename CoordT>
573 tree, co, r_nearest, range, [](
const CoordT &a,
const CoordT &
b) {
587template<
typename CoordT,
typename Fn>
623 if (dist_sq <= range_sq) {
624 if (search_cb(
node->index,
node->co, dist_sq) ==
false) {
650 order[
nodes[i].index] = int(i);
672template<
typename CoordT>
722template<
typename CoordT>
725 const bool use_index_order,
738 if (use_index_order) {
741 const int node_index = order[i];
742 if (node_index == -1) {
749 int found_prev = found;
751 if (found != found_prev) {
760 const uint node_index = i;
765 int found_prev = found;
767 if (found != found_prev) {
801template<
typename CoordT,
typename Func>
805 const bool has_self_index,
806 Func &&duplicates_cb)
816 for (
uint i = 0; i < nodes_len; i++) {
817 index_to_node_index[tree->
nodes[i].
index] = int(i);
823 if (has_self_index) {
825 for (
uint i = 0; i < nodes_len; i++) {
827 if (node_index != duplicates[node_index]) {
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](
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;
843 else if (target_index != neighbor_index) {
846 if ((dist_sq < dist_sq_best) ||
848 ((dist_sq == dist_sq_best) && (node_index < target_index)))
850 dist_sq_best = dist_sq;
851 duplicates[neighbor_index] = node_index;
865 for (
uint i = 0; i < nodes_len; i++) {
867 if (duplicates[node_index] != -1) {
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,
877 if (duplicates[neighbor_index] == -1) {
878 cluster.
append(neighbor_index);
887 found += int(cluster.
size());
888 cluster.
append(node_index);
890 const int cluster_index = duplicates_cb(cluster.
data(),
int(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;
A KD-tree for nearest neighbor search.
Read Blender memory allocation and freeing.
#define PRF_scope(category)
void push(const T &value)
void append(const T &value)
KDTreeCoordTraits< CoordT >::ValueType axis_get(const CoordT &co, uint axis)
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
constexpr int kd_stack_init
constexpr int kd_near_alloc_inc
constexpr uint kd_node_root_is_init
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
KDTreeCoordTraits< CoordT >::ValueType distance_squared(const CoordT &a, const CoordT &b)
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
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)
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)
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)
int kdtree_find_nearest(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest)
void kdtree_free(KDTree< CoordT > *tree)
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)
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