diff options
Diffstat (limited to 'source/blender/blenlib/intern/BLI_kdtree.c')
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdtree.c | 34 |
1 files changed, 24 insertions, 10 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c index 03b7561bad5..8e8b2e9f0e9 100644 --- a/source/blender/blenlib/intern/BLI_kdtree.c +++ b/source/blender/blenlib/intern/BLI_kdtree.c @@ -163,11 +163,18 @@ int BLI_kdtree_find_nearest(KDTree *tree, float *co, float *nor, KDTreeNearest * min_node= root; min_dist= squared_distance(root->co,co,root->nor,nor); - if(root->left) - stack[cur++]=root->left; - - if(root->right) - stack[cur++]=root->right; + if(co[root->d] < root->co[root->d]) { + if(root->right) + stack[cur++]=root->right; + if(root->left) + stack[cur++]=root->left; + } + else { + if(root->left) + stack[cur++]=root->left; + if(root->right) + stack[cur++]=root->right; + } while(cur--){ node=stack[cur]; @@ -263,11 +270,18 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, float *co, float *nor, KDTree cur_dist= squared_distance(root->co,co,root->nor,nor); add_nearest(nearest,&found,n,root->index,cur_dist,root->co); - if(root->left) - stack[cur++]=root->left; - - if(root->right) - stack[cur++]=root->right; + if(co[root->d] < root->co[root->d]) { + if(root->right) + stack[cur++]=root->right; + if(root->left) + stack[cur++]=root->left; + } + else { + if(root->left) + stack[cur++]=root->left; + if(root->right) + stack[cur++]=root->right; + } while(cur--){ node=stack[cur]; |