[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15970] branches/soc-2008-unclezeiv/source /blender/blenlib: Added a number of features to BLI_kdtree:
Davide Vercelli
davide.vercelli at gmail.com
Tue Aug 5 14:41:54 CEST 2008
Revision: 15970
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15970
Author: unclezeiv
Date: 2008-08-05 14:41:53 +0200 (Tue, 05 Aug 2008)
Log Message:
-----------
Added a number of features to BLI_kdtree:
- BLI_kdtree_find_in_sphere, returns all elements within distance "dist" from "co"
- BLI_kdtree_weak_delete, marks an element as deleted: this means it won't be returned by subsequent queries
In order to have a O(1) BLI_kdtree_weak_delete, we need a conversion table from user defined indices to internal node indices:
- BLI_kdtree_build_correspondence is the function to create such table
Finally, a very specific need:
- BLI_kdtree_change_index, to replace a user defined index with another one (updating the correspondence table as well)
All these features, if unused, shouldn't have a significant impact on existing usage of kd-trees. Still, tests to confirm this are very welcome.
If module maintainers feel that these changes are not appropriate here, I'm ready to move them somewhere else.
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-05 10:48:17 UTC (rev 15969)
+++ branches/soc-2008-unclezeiv/source/blender/blenlib/BLI_kdtree.h 2008-08-05 12:41:53 UTC (rev 15970)
@@ -52,9 +52,28 @@
/* Find nearest returns index, and -1 if no node is found.
* Find n nearest returns number of points found, with results in nearest.
+ * Find all points within a certain distance; returns number of points found, with results in nearest.
* Normal is optional. */
int BLI_kdtree_find_nearest(KDTree *tree, float *co, float *nor, KDTreeNearest *nearest);
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);
+/* 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 */
+void BLI_kdtree_build_correspondence(KDTree *tree, int factor);
+
+/* Marks a node as deleted: it won't be returned in subsequent queries.
+ * Returns 1 if successful, 0 otherwise
+ * Please note: a correspondence table must be built (once) before using this feature
+ * TODO: balance() should remove nodes marked as deleted */
+int BLI_kdtree_weak_delete(KDTree *tree, int index);
+
+/* changes a user provided index into another one, and updates the correspondance table accordingly
+ * Note: it's a O(1) operation, as it doesn't perform a search
+ * Returns 1 if successful, 0 otherwise
+ * Please note: a correspondence table must be built (once) before using this feature */
+int BLI_kdtree_change_index(KDTree *tree, int old_index, int new_index);
+
#endif
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-05 10:48:17 UTC (rev 15969)
+++ branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c 2008-08-05 12:41:53 UTC (rev 15970)
@@ -36,20 +36,21 @@
#include "BLI_arithb.h"
#include "BLI_kdtree.h"
+#include "BKE_utildefines.h"
-#define SWAP(type, a, b) { type sw_ap; sw_ap=(a); (a)=(b); (b)=sw_ap; }
-
typedef struct KDTreeNode {
struct KDTreeNode *left, *right;
float co[3], nor[3];
int index;
- short d;
+ short d, invalid;
} KDTreeNode;
struct KDTree {
KDTreeNode *nodes;
int totnode;
KDTreeNode *root;
+ int totdeleted;
+ int *correspondence;
};
KDTree *BLI_kdtree_new(int maxsize)
@@ -67,6 +68,8 @@
{
if(tree) {
MEM_freeN(tree->nodes);
+ if (tree->correspondence)
+ MEM_freeN(tree->correspondence);
MEM_freeN(tree);
}
}
@@ -80,6 +83,7 @@
if(nor) VecCopyf(node->nor, nor);
}
+/* TODO: would be useful if it removed "weakly deleted" nodes */
static KDTreeNode *kdtree_balance(KDTreeNode *nodes, int totnode, int axis)
{
KDTreeNode *node;
@@ -133,14 +137,12 @@
static float squared_distance(float *v1, float *v2, float *n1, float *n2)
{
float d[3], dist;
+
+ VECSUB(d,v2,v1);
- d[0]= v2[0]-v1[0];
- d[1]= v2[1]-v1[1];
- d[2]= v2[2]-v1[2];
+ dist= INPR(d, d);
- dist= d[0]*d[0] + d[1]*d[1] + d[2]*d[2];
-
- if(n1 && n2 && n1[0]*n2[0] + n1[1]*n2[1] + n1[2]*n2[2] < 0.0f)
+ if(n1 && n2 && INPR(n1, n2) < 0.0f)
dist *= 10.0f;
return dist;
@@ -233,9 +235,12 @@
return min_node->index;
}
-static void add_nearest(KDTreeNearest *ptn, int *found, int n, int index, float dist, float *co)
+static void add_nearest(KDTreeNearest *ptn, KDTreeNode *node, int *found, int n, float dist)
{
int i;
+
+ if (node->invalid)
+ return;
if(*found<n) (*found)++;
@@ -246,9 +251,9 @@
ptn[i]= ptn[i-1];
}
- ptn[i].index= index;
+ ptn[i].index= node->index;
ptn[i].dist= dist;
- VecCopyf(ptn[i].co, co);
+ VecCopyf(ptn[i].co, node->co);
}
/* finds the nearest n entries in tree to specified coordinates */
@@ -268,7 +273,7 @@
root= tree->root;
cur_dist= squared_distance(root->co,co,root->nor,nor);
- add_nearest(nearest,&found,n,root->index,cur_dist,root->co);
+ add_nearest(nearest,root,&found,n,cur_dist);
if(co[root->d] < root->co[root->d]) {
if(root->right)
@@ -295,7 +300,7 @@
cur_dist=squared_distance(node->co,co,node->nor,nor);
if(found<n || cur_dist<nearest[found-1].dist)
- add_nearest(nearest,&found,n,node->index,cur_dist,node->co);
+ add_nearest(nearest,node,&found,n,cur_dist);
if(node->left)
stack[cur++]=node->left;
@@ -308,8 +313,9 @@
if(found<n || cur_dist<nearest[found-1].dist){
cur_dist=squared_distance(node->co,co,node->nor,nor);
+
if(found<n || cur_dist<nearest[found-1].dist)
- add_nearest(nearest,&found,n,node->index,cur_dist,node->co);
+ add_nearest(nearest,node,&found,n,cur_dist);
if(node->right)
stack[cur++]=node->right;
@@ -336,3 +342,126 @@
return found;
}
+/* 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 **stack, *defaultstack[100];
+ float cur_dist;
+ int i, totstack, cur=0, found=0, n;
+
+ if(!tree->root)
+ return 0;
+
+ stack= defaultstack;
+ totstack= 100;
+
+ root= tree->root;
+ n= tree->totnode;
+ dist*= dist;
+
+ cur_dist= squared_distance(root->co,co,root->nor,nor);
+ if (cur_dist <= dist)
+ add_nearest(nearest,root,&found,n,cur_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<dist){
+ cur_dist=squared_distance(node->co,co,node->nor,nor);
+ if(cur_dist<=dist)
+ add_nearest(nearest,node,&found,n,cur_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<dist){
+ cur_dist=squared_distance(node->co,co,node->nor,nor);
+ if(cur_dist<=dist)
+ add_nearest(nearest,node,&found,n,cur_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;
+ }
+ }
+
+ for(i=0; i<found; i++)
+ nearest[i].dist= sqrt(nearest[i].dist);
+
+ if(stack != defaultstack)
+ MEM_freeN(stack);
+
+ return found;
+}
+
+void BLI_kdtree_build_correspondence(KDTree *tree, int factor)
+{
+ int i;
+
+ if (tree->correspondence)
+ MEM_freeN(tree->correspondence);
+
+ tree->correspondence= MEM_callocN(sizeof(int) * tree->totnode * factor, "KDTree correspondence");
+
+ for (i=0; i< tree->totnode; i++) {
+ int idx= tree->nodes[i].index;
+ /* NOTE: this should always be true */
+ if (idx >= 0 && idx < tree->totnode)
+ tree->correspondence[idx]= i;
+ }
+}
+
+int BLI_kdtree_weak_delete(KDTree *tree, int index)
+{
+ if (!tree->correspondence)
+ return 0;
+
+ tree->nodes[tree->correspondence[index]].invalid= 1;
+ tree->totdeleted++;
+ return 1;
+}
+
+int BLI_kdtree_change_index(KDTree *tree, int old_index, int new_index)
+{
+ if (!tree->correspondence)
+ return 0;
+
+ tree->nodes[tree->correspondence[old_index]].index= new_index;
+ tree->correspondence[new_index]= tree->correspondence[old_index];
+ return 1;
+}
More information about the Bf-blender-cvs
mailing list