diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-12-06 07:57:10 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-12-06 07:57:10 +0300 |
commit | 13a578edb40e62a9b9da9b60ac59dc22ce2382ee (patch) | |
tree | d4719835d223e00eca785bae9150b08953e690b5 | |
parent | 8f12dad3093eb4393271d876a9db29b1a0b6dd66 (diff) |
Cleanup: kdtree, redundant root node handling
For range checks we can put the root not in the stack.
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdtree.c | 49 |
1 files changed, 3 insertions, 46 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c index fe822816be4..ae3a1f6ff3d 100644 --- a/source/blender/blenlib/intern/BLI_kdtree.c +++ b/source/blender/blenlib/intern/BLI_kdtree.c @@ -448,7 +448,6 @@ int BLI_kdtree_range_search__normal( KDTreeNearest **r_nearest, float range) { const KDTreeNode *nodes = tree->nodes; - const KDTreeNode *root; unsigned int *stack, defaultstack[KD_STACK_INIT]; KDTreeNearest *foundstack = NULL; float range_sq = range * range, dist_sq; @@ -464,27 +463,7 @@ int BLI_kdtree_range_search__normal( stack = defaultstack; totstack = KD_STACK_INIT; - root = &nodes[tree->root]; - - if (co[root->d] + range < root->co[root->d]) { - if (root->left != KD_NODE_UNSET) - stack[cur++] = root->left; - } - else if (co[root->d] - range > root->co[root->d]) { - if (root->right != KD_NODE_UNSET) - stack[cur++] = root->right; - } - else { - dist_sq = squared_distance(root->co, co, nor); - if (dist_sq <= range_sq) { - add_in_range(&foundstack, &totfoundstack, found++, root->index, dist_sq, root->co); - } - - if (root->left != KD_NODE_UNSET) - stack[cur++] = root->left; - if (root->right != KD_NODE_UNSET) - stack[cur++] = root->right; - } + stack[cur++] = tree->root; while (cur--) { const KDTreeNode *node = &nodes[stack[cur]]; @@ -538,7 +517,7 @@ void BLI_kdtree_range_search_cb( bool (*search_cb)(void *user_data, int index, const float co[3], float dist_sq), void *user_data) { const KDTreeNode *nodes = tree->nodes; - const KDTreeNode *root; + unsigned int *stack, defaultstack[KD_STACK_INIT]; float range_sq = range * range, dist_sq; unsigned int totstack, cur = 0; @@ -553,29 +532,7 @@ void BLI_kdtree_range_search_cb( stack = defaultstack; totstack = KD_STACK_INIT; - root = &nodes[tree->root]; - - if (co[root->d] + range < root->co[root->d]) { - if (root->left != KD_NODE_UNSET) - stack[cur++] = root->left; - } - else if (co[root->d] - range > root->co[root->d]) { - if (root->right != KD_NODE_UNSET) - stack[cur++] = root->right; - } - else { - dist_sq = len_squared_v3v3(root->co, co); - if (dist_sq <= range_sq) { - if (search_cb(user_data, root->index, root->co, dist_sq) == false) { - goto finally; - } - } - - if (root->left != KD_NODE_UNSET) - stack[cur++] = root->left; - if (root->right != KD_NODE_UNSET) - stack[cur++] = root->right; - } + stack[cur++] = tree->root; while (cur--) { const KDTreeNode *node = &nodes[stack[cur]]; |