[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [16005] branches/soc-2008-unclezeiv/source /blender/blenlib/intern/BLI_kdtree.c: 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.

[Davide Vercelli]

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){