14 #define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1##MACRO_ARG2
15 #define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
16 #define BLI_kdtree_nd_(id) _CONCAT(KDTREE_PREFIX_ID, _##id)
37 uint nodes_len_capacity;
41 #define KD_STACK_INIT 100
42 #define KD_NEAR_ALLOC_INC 100
43 #define KD_FOUND_ALLOC_INC 50
45 #define KD_NODE_UNSET ((uint)-1)
51 #define KD_NODE_ROOT_IS_INIT ((uint)-2)
95 tree->is_balanced =
false;
96 tree->nodes_len_capacity = nodes_len_capacity;
130 tree->is_balanced =
false;
140 if (nodes_len <= 0) {
143 else if (nodes_len == 1) {
149 right = nodes_len - 1;
150 median = nodes_len / 2;
158 while (nodes[++i].co[axis] < co) {
160 while (nodes[--j].co[axis] > co && j >
left) {
180 node = &nodes[median];
185 nodes + median + 1, (nodes_len - (median + 1)), axis, (median + 1) + ofs);
193 for (
uint i = 0; i <
tree->nodes_len; i++) {
202 tree->is_balanced =
true;
210 memcpy(stack_new, stack, *stack_len_capacity *
sizeof(
uint));
229 float min_dist, cur_dist;
230 uint stack_len_capacity, cur = 0;
240 stack = stack_default;
243 root = &nodes[
tree->root];
247 if (co[root->
d] < root->
co[root->
d]) {
249 stack[cur++] = root->
right;
252 stack[cur++] = root->
left;
257 stack[cur++] = root->
left;
260 stack[cur++] = root->
right;
269 if (cur_dist < 0.0f) {
270 cur_dist = -cur_dist * cur_dist;
272 if (-cur_dist < min_dist) {
274 if (cur_dist < min_dist) {
279 stack[cur++] =
node->left;
283 stack[cur++] =
node->right;
287 cur_dist = cur_dist * cur_dist;
289 if (cur_dist < min_dist) {
291 if (cur_dist < min_dist) {
296 stack[cur++] =
node->right;
300 stack[cur++] =
node->left;
304 stack =
realloc_nodes(stack, &stack_len_capacity, stack_default != stack);
309 r_nearest->index = min_node->
index;
310 r_nearest->dist =
sqrtf(min_dist);
314 if (stack != stack_default) {
318 return min_node->
index;
331 int (*filter_cb)(
void *
user_data,
int index,
const float co[
KD_DIMS],
float dist_sq),
339 float min_dist = FLT_MAX, cur_dist;
340 uint stack_len_capacity, cur = 0;
350 stack = stack_default;
351 stack_len_capacity =
ARRAY_SIZE(stack_default);
353 #define NODE_TEST_NEAREST(node) \
355 const float dist_sq = len_squared_vnvn((node)->co, co); \
356 if (dist_sq < min_dist) { \
357 const int result = filter_cb(user_data, (node)->index, (node)->co, dist_sq); \
359 min_dist = dist_sq; \
362 else if (result == 0) { \
366 BLI_assert(result == -1); \
373 stack[cur++] =
tree->root;
380 if (cur_dist < 0.0f) {
381 cur_dist = -cur_dist * cur_dist;
383 if (-cur_dist < min_dist) {
387 stack[cur++] =
node->left;
391 stack[cur++] =
node->right;
395 cur_dist = cur_dist * cur_dist;
397 if (cur_dist < min_dist) {
401 stack[cur++] =
node->right;
405 stack[cur++] =
node->left;
409 stack =
realloc_nodes(stack, &stack_len_capacity, stack_default != stack);
413 #undef NODE_TEST_NEAREST
416 if (stack != stack_default) {
427 return min_node->
index;
436 const uint nearest_len_capacity,
443 if (*nearest_len < nearest_len_capacity) {
447 for (i = *nearest_len - 1; i > 0; i--) {
448 if (dist >= nearest[i - 1].dist) {
452 nearest[i] = nearest[i - 1];
456 nearest[i].
index = index;
457 nearest[i].
dist = dist;
470 const uint nearest_len_capacity,
480 uint stack_len_capacity, cur = 0;
481 uint i, nearest_len = 0;
491 if (len_sq_fn ==
NULL) {
496 stack = stack_default;
497 stack_len_capacity =
ARRAY_SIZE(stack_default);
499 root = &nodes[
tree->root];
503 r_nearest, &nearest_len, nearest_len_capacity, root->
index, cur_dist, root->
co);
505 if (co[root->
d] < root->
co[root->
d]) {
507 stack[cur++] = root->
right;
510 stack[cur++] = root->
left;
515 stack[cur++] = root->
left;
518 stack[cur++] = root->
right;
527 if (cur_dist < 0.0f) {
528 cur_dist = -cur_dist * cur_dist;
530 if (nearest_len < nearest_len_capacity || -cur_dist < r_nearest[nearest_len - 1].dist) {
533 if (nearest_len < nearest_len_capacity || cur_dist < r_nearest[nearest_len - 1].dist) {
535 r_nearest, &nearest_len, nearest_len_capacity,
node->index, cur_dist,
node->co);
539 stack[cur++] =
node->left;
543 stack[cur++] =
node->right;
547 cur_dist = cur_dist * cur_dist;
549 if (nearest_len < nearest_len_capacity || cur_dist < r_nearest[nearest_len - 1].dist) {
551 if (nearest_len < nearest_len_capacity || cur_dist < r_nearest[nearest_len - 1].dist) {
553 r_nearest, &nearest_len, nearest_len_capacity,
node->index, cur_dist,
node->co);
557 stack[cur++] =
node->right;
561 stack[cur++] =
node->left;
565 stack =
realloc_nodes(stack, &stack_len_capacity, stack_default != stack);
569 for (i = 0; i < nearest_len; i++) {
570 r_nearest[i].
dist =
sqrtf(r_nearest[i].dist);
573 if (stack != stack_default) {
577 return (
int)nearest_len;
583 uint nearest_len_capacity)
606 uint *nearest_len_capacity,
613 if (
UNLIKELY(nearest_index >= *nearest_len_capacity)) {
618 to = (*r_nearest) + nearest_index;
643 const float range_sq = range * range;
645 uint stack_len_capacity, cur = 0;
646 uint nearest_len = 0, nearest_len_capacity = 0;
656 if (len_sq_fn ==
NULL) {
661 stack = stack_default;
662 stack_len_capacity =
ARRAY_SIZE(stack_default);
664 stack[cur++] =
tree->root;
669 if (co[
node->d] + range < node->co[
node->d]) {
671 stack[cur++] =
node->left;
676 stack[cur++] =
node->right;
681 if (dist_sq <= range_sq) {
683 &nearest, nearest_len++, &nearest_len_capacity,
node->index, dist_sq,
node->co);
687 stack[cur++] =
node->left;
690 stack[cur++] =
node->right;
695 stack =
realloc_nodes(stack, &stack_len_capacity, stack_default != stack);
699 if (stack != stack_default) {
707 *r_nearest = nearest;
709 return (
int)nearest_len;
739 float range_sq = range * range, dist_sq;
740 uint stack_len_capacity, cur = 0;
750 stack = stack_default;
751 stack_len_capacity =
ARRAY_SIZE(stack_default);
753 stack[cur++] =
tree->root;
758 if (co[
node->d] + range < node->co[
node->d]) {
760 stack[cur++] =
node->left;
765 stack[cur++] =
node->right;
770 if (dist_sq <= range_sq) {
777 stack[cur++] =
node->left;
780 stack[cur++] =
node->right;
785 stack =
realloc_nodes(stack, &stack_len_capacity, stack_default != stack);
790 if (stack != stack_default) {
803 for (
uint i = 0; i <
tree->nodes_len; i++) {
875 bool use_index_order,
884 .duplicates_found = &found,
887 if (use_index_order) {
889 for (
uint i = 0; i <
tree->nodes_len; i++) {
891 const int index = (int)i;
895 int found_prev = found;
897 if (found != found_prev) {
906 for (
uint i = 0; i <
tree->nodes_len; i++) {
907 const uint node_index = i;
912 int found_prev = found;
914 if (found != found_prev) {
943 if (n0->
co[j] < n1->
co[j]) {
946 else if (n0->
co[j] > n1->
co[j]) {
970 tree->is_balanced =
false;
974 for (
uint i = 0; i <
tree->nodes_len; i++) {
983 return (
int)
tree->nodes_len;
typedef float(TangentPoint)[2]
A KD-tree for nearest neighbor search.
MINLINE float square_f(float a)
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble right
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint order
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
static int kdtree_cmp_bool(const bool a, const bool b)
int BLI_kdtree_nd_() range_search(const KDTree *tree, const float co[KD_DIMS], KDTreeNearest **r_nearest, float range)
static void deduplicate_recursive(const struct DeDuplicateParams *p, uint i)
int BLI_kdtree_nd_() calc_duplicates_fast(const KDTree *tree, const float range, bool use_index_order, int *duplicates)
int BLI_kdtree_nd_() find_nearest_n_with_len_squared_cb(const KDTree *tree, const float co[KD_DIMS], KDTreeNearest r_nearest[], const 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)
#define KD_NEAR_ALLOC_INC
#define KD_NODE_ROOT_IS_INIT
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_() find_nearest(const KDTree *tree, const float co[KD_DIMS], KDTreeNearest *r_nearest)
void BLI_kdtree_nd_() balance(KDTree *tree)
static uint * kdtree_order(const KDTree *tree)
static uint kdtree_balance(KDTreeNode *nodes, uint nodes_len, uint axis, const uint ofs)
#define NODE_TEST_NEAREST(node)
static uint * realloc_nodes(uint *stack, uint *stack_len_capacity, const bool is_alloc)
int BLI_kdtree_nd_() deduplicate(KDTree *tree)
void BLI_kdtree_nd_() insert(KDTree *tree, int index, const float co[KD_DIMS])
static int kdtree_node_cmp_deduplicate(const void *n0_p, const void *n1_p)
static void copy_vn_vn(float v0[KD_DIMS], const float v1[KD_DIMS])
struct KDTreeNode KDTreeNode
static void nearest_ordered_insert(KDTreeNearest *nearest, uint *nearest_len, const uint nearest_len_capacity, const int index, const float dist, const float co[KD_DIMS])
struct KDTreeNode_head KDTreeNode_head
void BLI_kdtree_nd_() free(KDTree *tree)
static float len_squared_vnvn_cb(const float co_kdtree[KD_DIMS], const float co_search[KD_DIMS], const void *UNUSED(user_data))
int BLI_kdtree_nd_() range_search_with_len_squared_cb(const KDTree *tree, const float co[KD_DIMS], KDTreeNearest **r_nearest, const 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)
static int nearest_cmp_dist(const void *a, const void *b)
#define KD_FOUND_ALLOC_INC
static void nearest_add_in_range(KDTreeNearest **r_nearest, uint nearest_index, uint *nearest_len_capacity, const int index, const float dist, const float co[KD_DIMS])
int BLI_kdtree_nd_() find_nearest_n(const KDTree *tree, const float co[KD_DIMS], KDTreeNearest r_nearest[], uint nearest_len_capacity)
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)
static float len_squared_vnvn(const float v0[KD_DIMS], const float v1[KD_DIMS])
#define BLI_kdtree_nd_(id)
void(* MEM_freeN)(void *vmemh)
void *(* MEM_reallocN_id)(void *vmemh, size_t len, const char *str)
void *(* MEM_mallocN)(size_t len, const char *str)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)