From 7da21752716a0e9e6e6ad8ccbda20fb1c5e8e123 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Tue, 18 Mar 2014 09:05:07 +1100 Subject: KDTree: deprecate 'normal' argument Normals for each kdtree node were allocated but never used, and search args only use in particles/boids code. --- source/blender/blenlib/BLI_kdtree.h | 32 ++++++++++++++------- source/blender/blenlib/intern/BLI_kdtree.c | 46 ++++++++++++++---------------- 2 files changed, 43 insertions(+), 35 deletions(-) (limited to 'source/blender/blenlib') diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/BLI_kdtree.h index e3c81021351..ebf03b5bc67 100644 --- a/source/blender/blenlib/BLI_kdtree.h +++ b/source/blender/blenlib/BLI_kdtree.h @@ -44,17 +44,29 @@ typedef struct KDTreeNearest { KDTree *BLI_kdtree_new(unsigned int maxsize); void BLI_kdtree_free(KDTree *tree); - -void BLI_kdtree_insert(KDTree *tree, int index, const float co[3], const float nor[3]) ATTR_NONNULL(1, 3); void BLI_kdtree_balance(KDTree *tree) ATTR_NONNULL(1); -int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], - KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2); -int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3], - KDTreeNearest *r_nearest, - unsigned int n) ATTR_NONNULL(1, 2, 4); -int BLI_kdtree_range_search(KDTree *tree, const float co[3], const float nor[3], - KDTreeNearest **r_nearest, - float range) ATTR_NONNULL(1, 2, 4) ATTR_WARN_UNUSED_RESULT; +void BLI_kdtree_insert( + KDTree *tree, int index, + const float co[3]) ATTR_NONNULL(1, 3); +int BLI_kdtree_find_nearest( + KDTree *tree, const float co[3], + KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2); + +#define BLI_kdtree_find_nearest_n(tree, co, r_nearest, n) \ + BLI_kdtree_find_nearest_n__normal(tree, co, NULL, r_nearest, n) +#define BLI_kdtree_range_search(tree, co, r_nearest, range) \ + BLI_kdtree_range_search__normal(tree, co, NULL, r_nearest, range) + +/* Normal use is deprecated */ +/* remove __normal functions when last users drop */ +int BLI_kdtree_find_nearest_n__normal( + KDTree *tree, const float co[3], const float nor[3], + KDTreeNearest *r_nearest, + unsigned int n) ATTR_NONNULL(1, 2, 4); +int BLI_kdtree_range_search__normal( + KDTree *tree, const float co[3], const float nor[3], + KDTreeNearest **r_nearest, + float range) ATTR_NONNULL(1, 2, 4) ATTR_WARN_UNUSED_RESULT; #endif /* __BLI_KDTREE_H__ */ diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c index c8ee0c11fc7..1a4d8bc7f78 100644 --- a/source/blender/blenlib/intern/BLI_kdtree.c +++ b/source/blender/blenlib/intern/BLI_kdtree.c @@ -35,7 +35,7 @@ typedef struct KDTreeNode { struct KDTreeNode *left, *right; - float co[3], nor[3]; + float co[3]; int index; unsigned int d; /* range is only (0-2) */ } KDTreeNode; @@ -85,7 +85,7 @@ void BLI_kdtree_free(KDTree *tree) /** * Construction: first insert points, then call balance. Normal is optional. */ -void BLI_kdtree_insert(KDTree *tree, int index, const float co[3], const float nor[3]) +void BLI_kdtree_insert(KDTree *tree, int index, const float co[3]) { KDTreeNode *node = &tree->nodes[tree->totnode++]; @@ -98,11 +98,6 @@ void BLI_kdtree_insert(KDTree *tree, int index, const float co[3], const float n node->left = node->right = NULL; copy_v3_v3(node->co, co); - if (nor) - copy_v3_v3(node->nor, nor); - else - zero_v3(node->nor); - node->index = index; node->d = 0; @@ -167,7 +162,7 @@ void BLI_kdtree_balance(KDTree *tree) #endif } -static float squared_distance(const float v2[3], const float v1[3], const float UNUSED(n1[3]), const float n2[3]) +static float squared_distance(const float v2[3], const float v1[3], const float n2[3]) { float d[3], dist; @@ -177,8 +172,6 @@ static float squared_distance(const float v2[3], const float v1[3], const float dist = dot_v3v3(d, d); - //if (n1 && n2 && (dot_v3v3(n1, n2) < 0.0f)) - /* can someone explain why this is done?*/ if (n2 && (dot_v3v3(d, n2) < 0.0f)) { dist *= 10.0f; @@ -201,8 +194,9 @@ static KDTreeNode **realloc_nodes(KDTreeNode **stack, unsigned int *totstack, co /** * Find nearest returns index, and -1 if no node is found. */ -int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], - KDTreeNearest *r_nearest) +int BLI_kdtree_find_nearest( + KDTree *tree, const float co[3], + KDTreeNearest *r_nearest) { KDTreeNode *root, *node, *min_node; KDTreeNode **stack, *defaultstack[KD_STACK_INIT]; @@ -221,7 +215,7 @@ int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], root = tree->root; min_node = root; - min_dist = squared_distance(root->co, co, root->nor, nor); + min_dist = len_squared_v3v3(root->co, co); if (co[root->d] < root->co[root->d]) { if (root->right) @@ -245,7 +239,7 @@ int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], cur_dist = -cur_dist * cur_dist; if (-cur_dist < min_dist) { - cur_dist = squared_distance(node->co, co, node->nor, nor); + cur_dist = len_squared_v3v3(node->co, co); if (cur_dist < min_dist) { min_dist = cur_dist; min_node = node; @@ -260,7 +254,7 @@ int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], cur_dist = cur_dist * cur_dist; if (cur_dist < min_dist) { - cur_dist = squared_distance(node->co, co, node->nor, nor); + cur_dist = len_squared_v3v3(node->co, co); if (cur_dist < min_dist) { min_dist = cur_dist; min_node = node; @@ -313,9 +307,10 @@ static void add_nearest(KDTreeNearest *ptn, unsigned int *found, unsigned int n, * * \param r_nearest An array of nearest, sized at least \a n. */ -int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3], - KDTreeNearest r_nearest[], - unsigned int n) +int BLI_kdtree_find_nearest_n__normal( + KDTree *tree, const float co[3], const float nor[3], + KDTreeNearest r_nearest[], + unsigned int n) { KDTreeNode *root, *node = NULL; KDTreeNode **stack, *defaultstack[KD_STACK_INIT]; @@ -335,7 +330,7 @@ int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3 root = tree->root; - cur_dist = squared_distance(root->co, co, root->nor, nor); + cur_dist = squared_distance(root->co, co, nor); add_nearest(r_nearest, &found, n, root->index, cur_dist, root->co); if (co[root->d] < root->co[root->d]) { @@ -360,7 +355,7 @@ int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3 cur_dist = -cur_dist * cur_dist; if (found < n || -cur_dist < r_nearest[found - 1].dist) { - cur_dist = squared_distance(node->co, co, node->nor, nor); + cur_dist = squared_distance(node->co, co, nor); if (found < n || cur_dist < r_nearest[found - 1].dist) add_nearest(r_nearest, &found, n, node->index, cur_dist, node->co); @@ -375,7 +370,7 @@ int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3 cur_dist = cur_dist * cur_dist; if (found < n || cur_dist < r_nearest[found - 1].dist) { - cur_dist = squared_distance(node->co, co, node->nor, nor); + cur_dist = squared_distance(node->co, co, nor); if (found < n || cur_dist < r_nearest[found - 1].dist) add_nearest(r_nearest, &found, n, node->index, cur_dist, node->co); @@ -436,8 +431,9 @@ static void add_in_range(KDTreeNearest **ptn, unsigned int found, unsigned int * * Normal is optional, but if given will limit results to points in normal direction from co. * Remember to free nearest after use! */ -int BLI_kdtree_range_search(KDTree *tree, const float co[3], const float nor[3], - KDTreeNearest **r_nearest, float range) +int BLI_kdtree_range_search__normal( + KDTree *tree, const float co[3], const float nor[3], + KDTreeNearest **r_nearest, float range) { KDTreeNode *root, *node = NULL; KDTreeNode **stack, *defaultstack[KD_STACK_INIT]; @@ -466,7 +462,7 @@ int BLI_kdtree_range_search(KDTree *tree, const float co[3], const float nor[3], stack[cur++] = root->right; } else { - dist2 = squared_distance(root->co, co, root->nor, nor); + dist2 = squared_distance(root->co, co, nor); if (dist2 <= range2) add_in_range(&foundstack, found++, &totfoundstack, root->index, dist2, root->co); @@ -488,7 +484,7 @@ int BLI_kdtree_range_search(KDTree *tree, const float co[3], const float nor[3], stack[cur++] = node->right; } else { - dist2 = squared_distance(node->co, co, node->nor, nor); + dist2 = squared_distance(node->co, co, nor); if (dist2 <= range2) add_in_range(&foundstack, found++, &totfoundstack, node->index, dist2, node->co); -- cgit v1.2.3