[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15987] branches/soc-2008-unclezeiv/source /blender/blenlib: Added yet another method to BLI_kdtree: BLI_kdtree_find_callback.

[Davide Vercelli]

Revision: 15987
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15987
Author:   unclezeiv
Date:     2008-08-06 17:24:43 +0200 (Wed, 06 Aug 2008)

Log Message:
-----------
Added yet another method to BLI_kdtree: BLI_kdtree_find_callback. It serves a very specific purpose but I tried hard to give it a general form.

Basically you can use it to find the nearest node where "nearest" is a metric computed by a callback that has also the possibility to reduce the search radius (if it decides that, outside that radius, no node can give a measure smaller than the current one); this way, larger parts of the tree can be pruned, resulting in a faster search.

Works for me but deeper testing, particularly regarding corner/degenerate cases, is welcome.

Modified Paths:
--------------
    branches/soc-2008-unclezeiv/source/blender/blenlib/BLI_kdtree.h
    branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c

Modified: branches/soc-2008-unclezeiv/source/blender/blenlib/BLI_kdtree.h
===================================================================
--- branches/soc-2008-unclezeiv/source/blender/blenlib/BLI_kdtree.h	2008-08-06 13:46:44 UTC (rev 15986)
+++ branches/soc-2008-unclezeiv/source/blender/blenlib/BLI_kdtree.h	2008-08-06 15:24:43 UTC (rev 15987)
@@ -58,6 +58,14 @@
 int	BLI_kdtree_find_n_nearest(KDTree *tree, int n, float *co, float *nor, KDTreeNearest *nearest);
 int	BLI_kdtree_find_in_sphere(KDTree *tree, float dist, float *co, float *nor, KDTreeNearest *nearest);
 
+/* Find element with smallest value and return index, or -1 if no node is found.
+ * The "value" of an element is computed by a callback along with a new radius that can be used
+ * to prune parts of the tree and speed up the search.
+ * If you are looking for the nearest node to a point that is already part of the tree, you can
+ * provide a vetoed_idx in order to avoid getting the node itself as "nearest point". */
+typedef void (*KDTreeValDistFunc)(void *data, int index, float *val, float *dist);
+int	BLI_kdtree_find_callback(KDTree *tree, float *co, float *nor, int vetoed_idx, KDTreeValDistFunc func, void *data, KDTreeNearest *nearest);
+
 /* Builds a correspondence table to convert from user provided indices to internal ones
  * Factor multiplies the amount of space allocated for the table; should normally be "1"
  * Optional; only useful if specifically required by a method */

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-06 13:46:44 UTC (rev 15986)
+++ branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c	2008-08-06 15:24:43 UTC (rev 15987)
@@ -34,6 +34,7 @@
 
 #include "MEM_guardedalloc.h"
 
+#include "blendef.h"
 #include "BLI_arithb.h"
 #include "BLI_kdtree.h"
 #include "BKE_utildefines.h"
@@ -235,6 +236,114 @@
 	return min_node->index;
 }
 
+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 **stack, *defaultstack[100];
+	float min_val, cur_dist, max_dist;
+	float val, dist;
+	int totstack, cur=0;
+
+	if(!tree->root)
+		return -1;
+
+	stack= defaultstack;
+	totstack= 100;
+	
+	root= tree->root;
+	
+	min_node= NULL;
+	min_val= MAXFLOAT;
+	max_dist= MAXFLOAT;
+	
+	if (root->index != veto && !root->invalid) {
+		min_node= root;
+		func(data, root->index, &val, &dist);
+		min_val= val;
+		max_dist= dist;
+	}
+	
+	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];
+
+		cur_dist = node->co[node->d] - co[node->d];
+
+		if(cur_dist<0.0){
+			cur_dist= cur_dist*cur_dist;
+
+			if(cur_dist<max_dist){
+				if (node->index!= veto && !node->invalid) {
+					func(data, node->index, &val, &dist);
+					if (val<min_val) {
+						min_val= val;
+						min_node= node;
+					}
+					if (dist<max_dist)
+						max_dist= dist;
+				}
+				if(node->left)
+					stack[cur++]=node->left;
+			}
+			if(node->right)
+				stack[cur++]=node->right;
+		}
+		else{
+			cur_dist= cur_dist*cur_dist;
+
+			if(cur_dist<max_dist){
+				if (node->index!= veto && !node->invalid) {
+					func(data, node->index, &val, &dist);
+					if (val<min_val && node->index!= veto) {
+						min_val= val;
+						min_node= node;
+					}
+					if (dist<max_dist)
+						max_dist= dist;
+				}
+				if(node->right)
+					stack[cur++]=node->right;
+			}
+			if(node->left)
+				stack[cur++]=node->left;
+		}
+		if(cur+3 > totstack){
+			KDTreeNode **temp=MEM_callocN((totstack+100)*sizeof(KDTreeNode*), "psys_treestack");
+			memcpy(temp,stack,totstack*sizeof(KDTreeNode*));
+			if(stack != defaultstack)
+				MEM_freeN(stack);
+			stack=temp;
+			totstack+=100;
+		}
+	}
+	
+	if (min_node==NULL)
+		return -1;
+
+	if(nearest) {
+		nearest->index= min_node->index;
+		nearest->dist= sqrt(min_val);
+		VecCopyf(nearest->co, min_node->co);
+	}
+
+	if(stack != defaultstack)
+		MEM_freeN(stack);
+
+	return min_node->index;
+}
+
 static void add_nearest(KDTreeNearest *ptn, KDTreeNode *node, int *found, int n, float dist)
 {
 	int i;