[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15014] branches/soc-2008-jaguarandi/ source/blender: Added bvh nearest neighbour for nearest surface shrinkwrap
André Pinto
andresusanopinto at gmail.com
Tue May 27 20:32:23 CEST 2008
Revision: 15014
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15014
Author: jaguarandi
Date: 2008-05-27 20:32:23 +0200 (Tue, 27 May 2008)
Log Message:
-----------
Added bvh nearest neighbour for nearest surface shrinkwrap
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-27 15:36:36 UTC (rev 15013)
+++ branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c 2008-05-27 18:32:23 UTC (rev 15014)
@@ -86,6 +86,7 @@
typedef void ( *Shrinkwrap_ForeachVertexCallback) (DerivedMesh *target, float *co, float *normal);
+static float nearest_point_in_tri_surface(const float *point, const float *v0, const float *v1, const float *v2, float *nearest);
static void normal_short2float(const short *ns, float *nf)
{
@@ -145,18 +146,19 @@
{
for(i = 0; i < numFaces; i++)
{
- float co[4][3];
+ float co[3][3];
VECCOPY(co[0], vert[ face[i].v1 ].co);
VECCOPY(co[1], vert[ face[i].v2 ].co);
VECCOPY(co[2], vert[ face[i].v3 ].co);
- if(face[i].v4)
- VECCOPY(co[3], vert[ face[i].v4 ].co);
-
-
BLI_bvhtree_insert(tree, 2*i, co[0], 3);
if(face[i].v4)
- BLI_bvhtree_insert(tree, 2*i+1, co[1], 3);
+ {
+ /* second face is v1,v3,v4 */
+ VECCOPY(co[1], vert[ face[i].v3 ].co);
+ VECCOPY(co[2], vert[ face[i].v4 ].co);
+ BLI_bvhtree_insert(tree, 2*i+1, co[0], 3);
+ }
}
BLI_bvhtree_balance(tree);
@@ -165,7 +167,17 @@
return tree;
}
+static float mesh_tri_nearest_point(void *userdata, int index, const float *co, float *nearest)
+{
+ DerivedMesh *mesh = (DerivedMesh*)(userdata);
+ MVert *vert = (MVert*)mesh->getVertDataArray(mesh, CD_MVERT);
+ MFace *face = (MFace*)mesh->getFaceDataArray(mesh, CD_MFACE) + index/2;
+ if(index & 1)
+ return nearest_point_in_tri_surface(co, vert[ face->v1 ].co, vert[ face->v3 ].co, vert[ face->v4 ].co, nearest);
+ else
+ return nearest_point_in_tri_surface(co, vert[ face->v1 ].co, vert[ face->v2 ].co, vert[ face->v3 ].co, nearest);
+}
/*
* Raytree from mesh
@@ -482,7 +494,7 @@
nearest[2] = du[2]*nearest_2d[0] + dv[2] * nearest_2d[1] + dw[2] * plane_offset;
}
- return sasqrt(plane_sdist + normal_dist*normal_dist);
+ return plane_sdist + normal_dist*normal_dist;
}
@@ -808,8 +820,8 @@
switch(smd->shrinkType)
{
case MOD_SHRINKWRAP_NEAREST_SURFACE:
-// BENCH(shrinkwrap_calc_nearest_surface_point(&calc));
- BENCH(shrinkwrap_calc_foreach_vertex(&calc, bruteforce_shrinkwrap_calc_nearest_surface_point));
+ BENCH(shrinkwrap_calc_nearest_surface_point(&calc));
+// BENCH(shrinkwrap_calc_foreach_vertex(&calc, bruteforce_shrinkwrap_calc_nearest_surface_point));
break;
case MOD_SHRINKWRAP_NORMAL:
@@ -888,7 +900,7 @@
}
else nearest.dist = FLT_MAX;
- index = BLI_bvhtree_find_nearest(tree, tmp_co, &nearest);
+ index = BLI_bvhtree_find_nearest(tree, tmp_co, &nearest, NULL, NULL);
if(index != -1)
{
@@ -1046,7 +1058,7 @@
}
else nearest.dist = FLT_MAX;
- index = BLI_bvhtree_find_nearest(tree, tmp_co, &nearest);
+ index = BLI_bvhtree_find_nearest(tree, tmp_co, &nearest, mesh_tri_nearest_point, calc->target);
if(index != -1)
{
Modified: branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h 2008-05-27 15:36:36 UTC (rev 15013)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h 2008-05-27 18:32:23 UTC (rev 15014)
@@ -47,6 +47,10 @@
float dist; /* squared distance to search arround */
} BVHTreeNearest;
+/* returns square of the minimum distance from given co to the node, nearest point is stored on nearest */
+typedef float (*BVHTree_NearestPointCallback) (void *userdata, int index, const float *co, float *nearest);
+
+
BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis);
void BLI_bvhtree_free(BVHTree *tree);
@@ -64,7 +68,7 @@
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);
+int BLI_bvhtree_find_nearest(BVHTree *tree, float *co, BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata);
#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-27 15:36:36 UTC (rev 15013)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-05-27 18:32:23 UTC (rev 15014)
@@ -117,6 +117,8 @@
{
BVHTree *tree;
float *co;
+ BVHTree_NearestPointCallback callback;
+ void *userdata;
float proj[13]; //coordinates projection over axis
BVHTreeNearest nearest;
} BVHNearestData;
@@ -919,25 +921,32 @@
float nearest[3], sdist;
sdist = calc_nearest_point(data, node, nearest);
-
if(sdist >= data->nearest.dist) return;
if(node->totnode == 0)
{
+ if(data->callback)
+ sdist = data->callback(data->userdata , node->index, data->co, nearest);
+
+ if(sdist >= data->nearest.dist) return;
+
data->nearest.index = node->index;
VECCOPY(data->nearest.nearest, nearest);
data->nearest.dist = sdist;
}
else
{
- for(i=0; i != node->totnode; i++)
+ if(sdist < data->nearest.dist)
{
- dfs_find_nearest(data, node->children[i]);
+ 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 BLI_bvhtree_find_nearest(BVHTree *tree, float *co, BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
{
int i;
@@ -947,6 +956,9 @@
data.tree = tree;
data.co = co;
+ data.callback = callback;
+ data.userdata = userdata;
+
for(i = data.tree->start_axis; i != data.tree->stop_axis; i++)
{
data.proj[i] = INPR(data.co, KDOP_AXES[i]);
More information about the Bf-blender-cvs
mailing list