Revision: 16005
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=16005
Author: unclezeiv
Date: 2008-08-07 18:31:50 +0200 (Thu, 07 Aug 2008)
Log Message:
-----------
Added an optimization in kdtree search: by performing an additional check on
the father's boundary coordinate, subtrees can be pruned more efficiently when
needed.
This requires one more pointer per node but seems to be consistently
outperforming the unmodified search by around 20%-30%.
Warning: I only tested BLI_kdtree_find_callback and only as used in lightcuts.
Tests to validate this optimization also for the other functions and in other
uses of BLI_kdtree are very welcome, so that this can go safely in trunk (along
with the other BLI_kdtree modifications).
Modified Paths:
--------------
branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c
Modified: branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c
===================================================================
--- branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c
2008-08-07 16:15:10 UTC (rev 16004)
+++ branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c
2008-08-07 16:31:50 UTC (rev 16005)
@@ -40,7 +40,7 @@
#include "BKE_utildefines.h"
typedef struct KDTreeNode {
- struct KDTreeNode *left, *right;
+ struct KDTreeNode *left, *right, *father;
float co[3], nor[3];
int index;
short d, invalid;
@@ -126,6 +126,11 @@
node->d= axis;
node->left= kdtree_balance(nodes, median, (axis+1)%3);
node->right= kdtree_balance(nodes+median+1, (totnode-(median+1)),
(axis+1)%3);
+
+ if (node->left)
+ node->left->father= node;
+ if (node->right)
+ node->right->father= node;
return node;
}
@@ -133,6 +138,7 @@
void BLI_kdtree_balance(KDTree *tree)
{
tree->root= kdtree_balance(tree->nodes, tree->totnode, 0);
+ tree->root->father= NULL;
}
static float squared_distance(float *v1, float *v2, float *n1, float *n2)
@@ -151,7 +157,7 @@
int BLI_kdtree_find_nearest(KDTree *tree, float *co, float *nor,
KDTreeNearest *nearest)
{
- KDTreeNode *root, *node, *min_node;
+ KDTreeNode *root, *node, *min_node, *father;
KDTreeNode **stack, *defaultstack[100];
float min_dist, cur_dist;
int totstack, cur=0;
@@ -181,6 +187,11 @@
while(cur--){
node=stack[cur];
+ father=node->father;
+
+ cur_dist= father->co[father->d] - co[father->d];
+ if (((node == father->right && cur_dist > 0) || (node ==
father->left && cur_dist < 0)) && cur_dist * cur_dist > min_dist)
+ continue;
cur_dist = node->co[node->d] - co[node->d];
@@ -238,7 +249,7 @@
int BLI_kdtree_find_callback(KDTree *tree, float *co, float *nor, int veto,
KDTreeValDistFunc func, void *data, KDTreeNearest *nearest)
{
- KDTreeNode *root, *node, *min_node;
+ KDTreeNode *root, *node, *min_node, *father;
KDTreeNode **stack, *defaultstack[100];
float min_val, cur_dist, max_dist;
float val, dist;
@@ -278,6 +289,11 @@
while(cur--){
node=stack[cur];
+ father=node->father;
+
+ cur_dist= father->co[father->d] - co[father->d];
+ if (((node == father->right && cur_dist > 0) || (node ==
father->left && cur_dist < 0)) && cur_dist * cur_dist > max_dist)
+ continue;
cur_dist = node->co[node->d] - co[node->d];
@@ -368,7 +384,7 @@
/* finds the nearest n entries in tree to specified coordinates */
int BLI_kdtree_find_n_nearest(KDTree *tree, int n, float *co, float *nor,
KDTreeNearest *nearest)
{
- KDTreeNode *root, *node=0;
+ KDTreeNode *root, *node=0, *father;
KDTreeNode **stack, *defaultstack[100];
float cur_dist;
int i, totstack, cur=0, found=0;
@@ -399,6 +415,14 @@
while(cur--){
node=stack[cur];
+
+ if (found==n) {
+ father=node->father;
+
+ cur_dist= father->co[father->d] - co[father->d];
+ if (((node == father->right && cur_dist > 0) || (node
== father->left && cur_dist < 0)) && cur_dist * cur_dist >
nearest[found-1].dist)
+ continue;
+ }
cur_dist = node->co[node->d] - co[node->d];
@@ -454,7 +478,7 @@
/* finds all the entries within distance (dist) from (co) */
int BLI_kdtree_find_in_sphere(KDTree *tree, float dist, float *co, float
*nor, KDTreeNearest *nearest)
{
- KDTreeNode *root, *node=0;
+ KDTreeNode *root, *node=0, *father;
KDTreeNode **stack, *defaultstack[100];
float cur_dist;
int i, totstack, cur=0, found=0, n;
@@ -488,7 +512,12 @@
while(cur--){
node=stack[cur];
+ father=node->father;
+ cur_dist= father->co[father->d] - co[father->d];
+ if (((node == father->right && cur_dist > 0) || (node ==
father->left && cur_dist < 0)) && cur_dist * cur_dist > dist)
+ continue;
+
cur_dist = node->co[node->d] - co[node->d];
if(cur_dist<0.0){
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
