[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [14963] branches/soc-2008-jaguarandi/ source/blender: Added BVH nearest neighbour code, for now only works in 6-dop and finds the node with the nearest bounding volume .
André Pinto
andresusanopinto at gmail.com
Sun May 25 17:43:18 CEST 2008
Revision: 14963
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=14963
Author: jaguarandi
Date: 2008-05-25 17:43:18 +0200 (Sun, 25 May 2008)
Log Message:
-----------
Added BVH nearest neighbour code, for now only works in 6-dop and finds the node with the nearest bounding volume.
I'll work on making it more generic.
So far it querys faster than kdtree, but building the tree is slower.
And bvhtree NN uses an heuristic based on the last match.
Shrinkwrap (OBCube)24578 over (OBSuzanne)31658
kdtree
build: 30.000000ms
query: 1360.000000ms
bvhtree
build: 140.000000ms
query: 490.000000ms
Shrinkwrap now uses bvhtree (binary tree, 6dop) for nearest vertex.
Modified Paths:
--------------
branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h
branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c
Modified: branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c 2008-05-25 15:10:18 UTC (rev 14962)
+++ branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c 2008-05-25 15:43:18 UTC (rev 14963)
@@ -235,6 +235,16 @@
}
/*
+ * Returns the squared distance between two given points
+ */
+static float squared_dist(const float *a, const float *b)
+{
+ float tmp[3];
+ VECSUB(tmp, a, b);
+ return INPR(tmp, tmp);
+}
+
+/*
* This calculates the distance (in dir units) that the ray must travel to intersect plane
* It can return negative values
*
@@ -782,11 +792,14 @@
int i;
int vgroup = get_named_vertexgroup_num(calc->ob, calc->smd->vgroup_name);
+/*
KDTree* target = NULL;
- KDTreeNearest nearest;
+ KDTreeNearest knearest;
+*/
float tmp_co[3];
BVHTree *tree = NULL;
+ BVHTreeNearest nearest;
BENCH_VAR(build);
BENCH_VAR(query);
@@ -798,19 +811,26 @@
numVerts= calc->target->getNumVerts(calc->target);
vert = tvert = calc->target->getVertDataArray(calc->target, CD_MVERT);
+
BENCH_RESET(build);
BENCH_BEGIN(build);
- tree = BLI_bvhtree_new(numVerts, 0, 8, 6);
+ //Create a bvh-tree of the given target
+ tree = BLI_bvhtree_new(numVerts, 0, 2, 6);
if(tree == NULL) return OUT_OF_MEMORY();
for(i = 0; i < numVerts; i++)
BLI_bvhtree_insert(tree, i, vert[i].co, 1);
+
BLI_bvhtree_balance(tree);
+
+ nearest.index = -1;
+ nearest.dist = FLT_MAX;
BENCH_END(build);
BENCH_REPORT(build);
+/*
//Generate kd-tree with target vertexs
BENCH_RESET(build);
BENCH_BEGIN(build);
@@ -825,8 +845,8 @@
BENCH_END(build);
BENCH_REPORT(build);
+*/
-
//Find the nearest vertex
numVerts= calc->final->getNumVerts(calc->final);
vert = calc->final->getVertDataArray(calc->final, CD_MVERT);
@@ -835,40 +855,55 @@
BENCH_BEGIN(query);
for(i=0; i<numVerts; i++)
{
- int t, index;
+ int index;
float weight = vertexgroup_get_weight(dvert, i, vgroup);
if(weight == 0.0f) continue;
-/* VecMat4MulVecfl(tmp_co, calc->local2target, vert[i].co);
+ VecMat4MulVecfl(tmp_co, calc->local2target, vert[i].co);
- index = BLI_bvhtree_find_nearest(tree, tmp_co);
+ if(nearest.index != -1)
+ {
+ nearest.dist = squared_dist(tmp_co, tvert[nearest.index].co);
+ }
+ else nearest.dist = FLT_MAX;
+
+ index = BLI_bvhtree_find_nearest(tree, tmp_co, &nearest);
+
+/*
+ t = BLI_kdtree_find_nearest(target, tmp_co, 0, &knearest);
+
+
+ if(VecLenf(knearest.co, tvert[index].co) > 1e-5)
+ {
+ printf("Nearest failed: {%f,%f,%f} - ", knearest.co[0], knearest.co[1], knearest.co[2]);
+ printf("{%f,%f,%f}\n", tvert[index].co[0], tvert[index].co[1], tvert[index].co[2]);
+ }
+*/
if(index != -1)
{
float dist;
+
VecMat4MulVecfl(tmp_co, calc->target2local, tvert[index].co);
dist = VecLenf(vert[i].co, tmp_co);
if(dist > 1e-5) weight *= (dist - calc->keptDist)/dist;
- VecLerpf(vert[i].co, vert[i].co, nearest.co, weight); //linear interpolation
+ VecLerpf(vert[i].co, vert[i].co, tmp_co, weight); //linear interpolation
}
- */
- t = BLI_kdtree_find_nearest(target, tmp_co, 0, &nearest);
-
- if(t != -1)
+/* if(t != -1)
{
float dist;
- VecMat4MulVecfl(nearest.co, calc->target2local, nearest.co);
- dist = VecLenf(vert[i].co, tmp_co);
+ VecMat4MulVecfl(knearest.co, calc->target2local, knearest.co);
+ dist = VecLenf(vert[i].co, knearest.co);
if(dist > 1e-5) weight *= (dist - calc->keptDist)/dist;
- VecLerpf(vert[i].co, vert[i].co, nearest.co, weight); //linear interpolation
+ VecLerpf(vert[i].co, vert[i].co, knearest.co, weight); //linear interpolation
}
-
+*/
}
BENCH_END(query);
BENCH_REPORT(query);
- BLI_kdtree_free(target);
+// BLI_kdtree_free(target);
BLI_bvhtree_free(tree);
}
Modified: branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h 2008-05-25 15:10:18 UTC (rev 14962)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h 2008-05-25 15:43:18 UTC (rev 14963)
@@ -40,6 +40,12 @@
int indexB;
} BVHTreeOverlap;
+typedef struct BVHTreeNearest
+{
+ int index; /* the index of the nearest found (untouched if none is found within a dist radius from the given coordinates) */
+ float dist; /* squared distance to search arround */
+} BVHTreeNearest;
+
BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis);
void BLI_bvhtree_free(BVHTree *tree);
@@ -56,6 +62,9 @@
float BLI_bvhtree_getepsilon(BVHTree *tree);
+/* find nearest node to the given coordinates (if nearest is given it will only search nodes where square distance is smaller than nearest->dist) */
+int BLI_bvhtree_find_nearest(BVHTree *tree, float *co, BVHTreeNearest *nearest);
+
#endif // BLI_KDOPBVH_H
Modified: branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-05-25 15:10:18 UTC (rev 14962)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-05-25 15:43:18 UTC (rev 14963)
@@ -112,6 +112,14 @@
BVHTreeOverlap *overlap;
int i, max_overlap; /* i is number of overlaps */
} BVHOverlapData;
+
+typedef struct BVHNearestData
+{
+ BVHTree *tree;
+ float *co;
+ float proj[13]; //coordinates projection over axis
+ BVHTreeNearest nearest;
+} BVHNearestData;
////////////////////////////////////////
@@ -340,12 +348,12 @@
tree->start_axis = 0;
tree->stop_axis = 7;
}
- else if(axis == 8) // AABB
+ else if(axis == 8)
{
tree->start_axis = 0;
tree->stop_axis = 4;
}
- else if(axis == 6) // OBB
+ else if(axis == 6) // AABB
{
tree->start_axis = 0;
tree->stop_axis = 3;
@@ -857,3 +865,111 @@
return tree->epsilon;
}
+
+//Nearest neighbour
+static float squared_dist(const float *a, const float *b)
+{
+ float tmp[3];
+ VECSUB(tmp, a, b);
+ return INPR(tmp, tmp);
+}
+
+static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *nearest)
+{
+ int i;
+ const float *bv = node_get_bv(data->tree, node);
+
+ //nearest on AABB hull
+ for(i=0; i != 3; i++, bv += 2)
+ {
+ if(bv[0] > data->proj[i])
+ nearest[i] = bv[0];
+ else if(bv[1] < data->proj[i])
+ nearest[i] = bv[1];
+ else
+ nearest[i] = data->proj[i];
+ }
+
+/*
+ //nearest on a general hull
+ VECCOPY(nearest, data->co);
+ for(i = data->tree->start_axis; i != data->tree->stop_axis; i++, bv+=2)
+ {
+ float proj = INPR( nearest, KDOP_AXES[i]);
+ float dl = bv[0] - proj;
+ float du = bv[1] - proj;
+
+ if(dl > 0)
+ {
+ VECADDFAC(nearest, nearest, KDOP_AXES[i], dl);
+ }
+ else if(du < 0)
+ {
+ VECADDFAC(nearest, nearest, KDOP_AXES[i], du);
+ }
+ }
+*/
+ return squared_dist(data->co, nearest);
+}
+
+
+static void dfs_find_nearest(BVHNearestData *data, BVHNode *node)
+{
+ int i;
+ float nearest[3], sdist;
+
+ sdist = calc_nearest_point(data, node, nearest);
+
+ if(sdist >= data->nearest.dist) return;
+
+ if(node->totnode == 0)
+ {
+ data->nearest.dist = sdist;
+ data->nearest.index = node->index;
+ }
+ else
+ {
+ for(i=0; i != node->totnode; i++)
+ {
+ dfs_find_nearest(data, node->children[i]);
+ }
+ }
+}
+
+int BLI_bvhtree_find_nearest(BVHTree *tree, float *co, BVHTreeNearest *nearest)
+{
+ int i;
+
+ BVHNearestData data;
+
+ //init data to search
+ data.tree = tree;
+ data.co = co;
+
+ for(i = data.tree->start_axis; i != data.tree->stop_axis; i++)
+ {
+ data.proj[i] = INPR(data.co, KDOP_AXES[i]);
+ }
+
+ if(nearest)
+ {
+ memcpy( &data.nearest , nearest, sizeof(*nearest) );
+ }
+ else
+ {
+ data.nearest.index = -1;
+ data.nearest.dist = FLT_MAX;
+ }
+
+ //dfs search
+ dfs_find_nearest(&data, tree->nodes[tree->totleaf] );
+
+ //copy back results
+ if(nearest)
+ {
+ memcpy(nearest, &data.nearest, sizeof(*nearest));
+ }
+
+ return data.nearest.index;
+}
+
More information about the Bf-blender-cvs
mailing list