1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
/* SPDX-License-Identifier: GPL-2.0-or-later */
/** \file
* \ingroup bli
* \brief A KD-tree for nearest neighbor search.
*/
#include "BLI_compiler_attrs.h"
#include "BLI_sys_types.h"
#define _BLI_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1##MACRO_ARG2
#define _BLI_CONCAT(MACRO_ARG1, MACRO_ARG2) _BLI_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
#define BLI_kdtree_nd_(id) _BLI_CONCAT(KDTREE_PREFIX_ID, _##id)
#ifdef __cplusplus
extern "C" {
#endif
struct KDTree;
typedef struct KDTree KDTree;
typedef struct KDTreeNearest {
int index;
float dist;
float co[KD_DIMS];
} KDTreeNearest;
KDTree *BLI_kdtree_nd_(new)(unsigned int maxsize);
void BLI_kdtree_nd_(free)(KDTree *tree);
void BLI_kdtree_nd_(balance)(KDTree *tree) ATTR_NONNULL(1);
void BLI_kdtree_nd_(insert)(KDTree *tree, int index, const float co[KD_DIMS]) ATTR_NONNULL(1, 3);
int BLI_kdtree_nd_(find_nearest)(const KDTree *tree,
const float co[KD_DIMS],
KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2);
int BLI_kdtree_nd_(find_nearest_n)(const KDTree *tree,
const float co[KD_DIMS],
KDTreeNearest *r_nearest,
uint nearest_len_capacity) ATTR_NONNULL(1, 2, 3);
int BLI_kdtree_nd_(range_search)(const KDTree *tree,
const float co[KD_DIMS],
KDTreeNearest **r_nearest,
float range) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT;
int BLI_kdtree_nd_(find_nearest_cb)(
const KDTree *tree,
const float co[KD_DIMS],
int (*filter_cb)(void *user_data, int index, const float co[KD_DIMS], float dist_sq),
void *user_data,
KDTreeNearest *r_nearest);
void BLI_kdtree_nd_(range_search_cb)(
const KDTree *tree,
const float co[KD_DIMS],
float range,
bool (*search_cb)(void *user_data, int index, const float co[KD_DIMS], float dist_sq),
void *user_data);
int BLI_kdtree_nd_(calc_duplicates_fast)(const KDTree *tree,
float range,
bool use_index_order,
int *doubles);
int BLI_kdtree_nd_(deduplicate)(KDTree *tree);
/** Versions of find/range search that take a squared distance callback to support bias. */
int BLI_kdtree_nd_(find_nearest_n_with_len_squared_cb)(
const KDTree *tree,
const float co[KD_DIMS],
KDTreeNearest *r_nearest,
uint nearest_len_capacity,
float (*len_sq_fn)(const float co_search[KD_DIMS],
const float co_test[KD_DIMS],
const void *user_data),
const void *user_data) ATTR_NONNULL(1, 2, 3);
int BLI_kdtree_nd_(range_search_with_len_squared_cb)(
const KDTree *tree,
const float co[KD_DIMS],
KDTreeNearest **r_nearest,
float range,
float (*len_sq_fn)(const float co_search[KD_DIMS],
const float co_test[KD_DIMS],
const void *user_data),
const void *user_data) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT;
#ifdef __cplusplus
}
#endif
#ifdef __cplusplus
template<typename Fn>
inline void BLI_kdtree_nd_(range_search_cb_cpp)(const KDTree *tree,
const float co[KD_DIMS],
float distance,
const Fn &fn)
{
BLI_kdtree_nd_(range_search_cb)(
tree,
co,
distance,
[](void *user_data, const int index, const float *co, const float dist_sq) {
const Fn &fn = *static_cast<const Fn *>(user_data);
return fn(index, co, dist_sq);
},
const_cast<Fn *>(&fn));
}
#endif
#undef _BLI_CONCAT_AUX
#undef _BLI_CONCAT
#undef BLI_kdtree_nd_
|
