From 4b3aafd44ffd855f0cdb0d5e368c1abce238e11d Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Mon, 18 Mar 2019 09:28:32 +1100 Subject: BLI_kdtree: refactor boids specific logic into callback Logic to for boids to avoid head-on collisions was in BLI_kdtree. Move this into a callback which is now defined in boids.c so the kdtree code can be kept generic. --- source/blender/blenlib/BLI_kdtree.h | 23 ++++++------ source/blender/blenlib/intern/BLI_kdtree.c | 56 ++++++++++++++++-------------- 2 files changed, 42 insertions(+), 37 deletions(-) (limited to 'source/blender/blenlib') diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/BLI_kdtree.h index 864055127fc..3b21ad76b4d 100644 --- a/source/blender/blenlib/BLI_kdtree.h +++ b/source/blender/blenlib/BLI_kdtree.h @@ -45,9 +45,9 @@ int BLI_kdtree_find_nearest( 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) + BLI_kdtree_find_nearest_n_with_len_squared_cb(tree, co, r_nearest, n, NULL, NULL) #define BLI_kdtree_range_search(tree, co, r_nearest, range) \ - BLI_kdtree_range_search__normal(tree, co, NULL, r_nearest, range) + BLI_kdtree_range_search_with_len_squared_cb(tree, co, r_nearest, range, NULL, NULL) int BLI_kdtree_find_nearest_cb( const KDTree *tree, const float co[3], @@ -61,15 +61,18 @@ int BLI_kdtree_calc_duplicates_fast( const KDTree *tree, const float range, bool use_index_order, int *doubles); -/* Normal use is deprecated */ -/* remove __normal functions when last users drop */ -int BLI_kdtree_find_nearest_n__normal( - const KDTree *tree, const float co[3], const float nor[3], +/* Versions of find/range search that take a squared distance callback to support bias. */ +int BLI_kdtree_find_nearest_n_with_len_squared_cb( + const KDTree *tree, const float co[3], KDTreeNearest *r_nearest, - unsigned int n) ATTR_NONNULL(1, 2, 4); -int BLI_kdtree_range_search__normal( - const KDTree *tree, const float co[3], const float nor[3], + unsigned int n, + float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data), + const void *user_data) ATTR_NONNULL(1, 2, 3); +int BLI_kdtree_range_search_with_len_squared_cb( + const KDTree *tree, const float co[3], KDTreeNearest **r_nearest, - float range) ATTR_NONNULL(1, 2, 4) ATTR_WARN_UNUSED_RESULT; + float range, + float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data), + const void *user_data) ATTR_NONNULL(1, 2) 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 689b9d9720a..92761a5ec7a 100644 --- a/source/blender/blenlib/intern/BLI_kdtree.c +++ b/source/blender/blenlib/intern/BLI_kdtree.c @@ -178,22 +178,9 @@ void BLI_kdtree_balance(KDTree *tree) #endif } -static float squared_distance(const float v2[3], const float v1[3], const float n2[3]) +static float len_squared_v3v3_cb(const float co_kdtree[3], const float co_search[3], const void *UNUSED(user_data)) { - float d[3], dist; - - d[0] = v2[0] - v1[0]; - d[1] = v2[1] - v1[1]; - d[2] = v2[2] - v1[2]; - - dist = len_squared_v3(d); - - /* can someone explain why this is done?*/ - if (n2 && (dot_v3v3(d, n2) < 0.0f)) { - dist *= 10.0f; - } - - return dist; + return len_squared_v3v3(co_kdtree, co_search); } static uint *realloc_nodes(uint *stack, uint *totstack, const bool is_alloc) @@ -422,8 +409,9 @@ finally: } } -static void add_nearest(KDTreeNearest *ptn, uint *found, uint n, int index, - float dist, const float *co) +static void add_nearest( + KDTreeNearest *ptn, uint *found, const uint n, const int index, + const float dist, const float co[3]) { uint i; @@ -451,10 +439,12 @@ static void add_nearest(KDTreeNearest *ptn, uint *found, uint n, int index, * * \param r_nearest: An array of nearest, sized at least \a n. */ -int BLI_kdtree_find_nearest_n__normal( - const KDTree *tree, const float co[3], const float nor[3], +int BLI_kdtree_find_nearest_n_with_len_squared_cb( + const KDTree *tree, const float co[3], KDTreeNearest r_nearest[], - uint n) + uint n, + float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data), + const void *user_data) { const KDTreeNode *nodes = tree->nodes; const KDTreeNode *root; @@ -471,12 +461,17 @@ int BLI_kdtree_find_nearest_n__normal( return 0; } + if (len_sq_fn == NULL) { + len_sq_fn = len_squared_v3v3_cb; + BLI_assert(user_data == NULL); + } + stack = defaultstack; totstack = KD_STACK_INIT; root = &nodes[tree->root]; - cur_dist = squared_distance(root->co, co, nor); + cur_dist = len_sq_fn(co, root->co, user_data); add_nearest(r_nearest, &found, n, root->index, cur_dist, root->co); if (co[root->d] < root->co[root->d]) { @@ -505,7 +500,7 @@ int BLI_kdtree_find_nearest_n__normal( cur_dist = -cur_dist * cur_dist; if (found < n || -cur_dist < r_nearest[found - 1].dist) { - cur_dist = squared_distance(node->co, co, nor); + cur_dist = len_sq_fn(co, node->co, user_data); if (found < n || cur_dist < r_nearest[found - 1].dist) { add_nearest(r_nearest, &found, n, node->index, cur_dist, node->co); @@ -523,7 +518,7 @@ int BLI_kdtree_find_nearest_n__normal( cur_dist = cur_dist * cur_dist; if (found < n || cur_dist < r_nearest[found - 1].dist) { - cur_dist = squared_distance(node->co, co, nor); + cur_dist = len_sq_fn(co, node->co, user_data); if (found < n || cur_dist < r_nearest[found - 1].dist) { add_nearest(r_nearest, &found, n, node->index, cur_dist, node->co); } @@ -594,9 +589,11 @@ static void add_in_range( * 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__normal( - const KDTree *tree, const float co[3], const float nor[3], - KDTreeNearest **r_nearest, float range) +int BLI_kdtree_range_search_with_len_squared_cb( + const KDTree *tree, const float co[3], + KDTreeNearest **r_nearest, float range, + float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data), + const void *user_data) { const KDTreeNode *nodes = tree->nodes; uint *stack, defaultstack[KD_STACK_INIT]; @@ -612,6 +609,11 @@ int BLI_kdtree_range_search__normal( return 0; } + if (len_sq_fn == NULL) { + len_sq_fn = len_squared_v3v3_cb; + BLI_assert(user_data == NULL); + } + stack = defaultstack; totstack = KD_STACK_INIT; @@ -631,7 +633,7 @@ int BLI_kdtree_range_search__normal( } } else { - dist_sq = squared_distance(node->co, co, nor); + dist_sq = len_sq_fn(co, node->co, user_data); if (dist_sq <= range_sq) { add_in_range(&foundstack, &totfoundstack, found++, node->index, dist_sq, node->co); } -- cgit v1.2.3