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;
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
