Revision: 15533
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15533
Author: jaguarandi
Date: 2008-07-11 21:46:35 +0200 (Fri, 11 Jul 2008)
Log Message:
-----------
Added sphere cast (tought it doenst seems to solve the intersection problem)
Fixed SweepingSphereIntersectsTriangleUV
Modified Paths:
--------------
branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
branches/soc-2008-jaguarandi/source/blender/blenlib/intern/arithb.c
Modified:
branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
2008-07-11 18:08:25 UTC (rev 15532)
+++ branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
2008-07-11 19:46:35 UTC (rev 15533)
@@ -92,100 +92,35 @@
/* ray - triangle */
-
#define ISECT_EPSILON 1e-6
-float ray_tri_intersection(const BVHTreeRay *ray, const float m_dist, const
float *v0, const float *v1, const float *v2)
+static float ray_tri_intersection(const BVHTreeRay *ray, const float m_dist,
const float *v0, const float *v1, const float *v2)
{
float dist;
+
if(RayIntersectsTriangle(ray->origin, ray->direction, v0, v1, v2,
&dist, NULL))
return dist;
-/*
- float pnormal[3];
- float dist;
+ return FLT_MAX;
+}
- CalcNormFloat(v0, v1, v2, pnormal);
- dist = ray_intersect_plane(ray->origin, ray->direction, v0, pnormal);
-
- if(dist > 0 && dist < m_dist)
- {
- float tmp[3], nearest[3];
- VECADDFAC(tmp, ray->origin, ray->direction, dist);
-
- if(fabs(nearest_point_in_tri_surface(tmp, v0, v1, v2, nearest))
< 0.0001)
- return dist;
- }
-*/
-
-/*
- float x0,x1,x2,t00,t01,t02,t10,t11,t12,r0,r1,r2;
- float m0, m1, m2, divdet, det1;
- float u,v;
- float cros0, cros1, cros2;
- float labda;
-
- float t0[3], t1[3];
-
- VECSUB(t0, v2, v0);
- VECSUB(t1, v2, v1);
-
- Crossf(x, t1, ray->direction);
-
- divdet = INPR( t0, x );
-
- VECSUB( m, ray->origin, v2 );
- det1 = INPR(m, x);
-
- Crossf(cros, m, t0);
-
- if(divdet == 0.0)
- return FLT_MAX;
-
+static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius,
const float m_dist, const float *v0, const float *v1, const float *v2)
+{
+ float dist, idist;
+ float p0[3], p1[3];
+ float plane_normal[3], hit_point[3];
-/ *
- t00= co3[0]-co1[0];
- t01= co3[1]-co1[1];
- t02= co3[2]-co1[2];
- t10= co3[0]-co2[0];
- t11= co3[1]-co2[1];
- t12= co3[2]-co2[2];
-
- r0= ray->direction[0];
- r1= ray->direction[1];
- r2= ray->direction[2];
-
- x0= t12*r1-t11*r2;
- x1= t10*r2-t12*r0;
- x2= t11*r0-t10*r1;
+ CalcNormFloat((float*)v0, (float*)v1, (float*)v2, plane_normal);
- divdet= t00*x0+t01*x1+t02*x2;
+ dist = ray_intersect_plane(ray->origin, ray->direction, v0,
plane_normal);
- m0= ray->origin[0]-co3[0];
- m1= ray->origin[0]-co3[1];
- m2= ray->origin[0]-co3[2];
- det1= m0*x0+m1*x1+m2*x2;
-
- cros0= m1*t02-m2*t01;
- cros1= m2*t00-m0*t02;
- cros2= m0*t01-m1*t00;
-
-
- if(divdet==0.0f)
- return FLT_MAX;
-
- divdet= 1.0f/divdet;
- u= det1*divdet;
- v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
-
- labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
-
- if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)
- && v<ISECT_EPSILON && (u + v) > -(1.0f+ISECT_EPSILON))
+ VECADDFAC( p0, ray->origin, ray->direction, /*dist-radius*/ 0);
+ VECADDFAC( p1, ray->origin, ray->direction, m_dist);
+ if(SweepingSphereIntersectsTriangleUV(p0, p1, radius, v0, v1, v2,
&idist, &hit_point))
{
- return labda;
+ return idist * m_dist;
}
-*/
+
return FLT_MAX;
}
@@ -193,8 +128,29 @@
/*
* BVH tree from mesh vertices
*/
-static BVHTree* bvhtree_from_mesh_verts(DerivedMesh *mesh)
+typedef struct BVHMeshCallbackUserdata
{
+ //Mesh represented on this BVH
+ DerivedMesh *mesh;
+ MVert *vert;
+ MFace *face;
+
+ //radius for sphere cast
+ float sphere_radius;
+
+} BVHMeshCallbackUserdata;
+
+
+static void bvhtree_meshcallbackdata_init(BVHMeshCallbackUserdata *data,
DerivedMesh *mesh, float cast_radius)
+{
+ data->mesh = mesh;
+ data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
+ data->face = mesh->getFaceDataArray(mesh, CD_MFACE);
+ data->sphere_radius = cast_radius;
+}
+
+static BVHTree* bvhtree_from_mesh_verts(DerivedMesh *mesh, float epsilon)
+{
int i;
int numVerts= mesh->getNumVerts(mesh);
MVert *vert = mesh->getVertDataArray(mesh, CD_MVERT);
@@ -211,7 +167,7 @@
return tree;
}
-static BVHTree* bvhtree_from_mesh_tri(DerivedMesh *mesh)
+static BVHTree* bvhtree_from_mesh_tri(DerivedMesh *mesh, float epsilon)
{
int i;
int numFaces= mesh->getNumFaces(mesh), totFaces;
@@ -224,7 +180,7 @@
if(face[i].v4) totFaces++;
/* Create a bvh-tree of the given target */
- tree = BLI_bvhtree_new(totFaces, 0, 2, 6);
+ tree = BLI_bvhtree_new(totFaces, epsilon, 2, 6);
if(tree != NULL)
{
for(i = 0; i < numFaces; i++)
@@ -250,11 +206,12 @@
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;
+ const BVHMeshCallbackUserdata *data = (BVHMeshCallbackUserdata*)
userdata;
+ MVert *vert = data->vert;
+ MFace *face = data->face + 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);
@@ -262,11 +219,13 @@
return nearest_point_in_tri_surface(co, vert[ face->v1 ].co,
vert[ face->v2 ].co, vert[ face->v3 ].co, nearest);
}
+
+
static float mesh_tri_spherecast(void *userdata, int index, const BVHTreeRay
*ray, BVHTreeRayHit *hit)
{
- DerivedMesh *mesh = (DerivedMesh*)(userdata);
- MVert *vert = (MVert*)mesh->getVertDataArray(mesh, CD_MVERT);
- MFace *face = (MFace*)mesh->getFaceDataArray(mesh, CD_MFACE) + index/2;
+ const BVHMeshCallbackUserdata *data = (BVHMeshCallbackUserdata*)
userdata;
+ MVert *vert = data->vert;
+ MFace *face = data->face + index / 2;
const float *t0, *t1, *t2;
float dist;
@@ -276,29 +235,38 @@
else
t0 = &vert[ face->v1 ].co, t1 = &vert[ face->v2 ].co, t2 =
&vert[ face->v3 ].co;
-
- dist = ray_tri_intersection(ray, hit->dist, t0, t1, t2);
- if(dist < hit->dist)
+ dist = sphereray_tri_intersection(ray, data->sphere_radius, hit->dist,
t0, t1, t2);
+ if(dist >= 0 && dist < hit->dist)
{
hit->index = index;
- hit->dist = fabs(dist);
- VECADDFAC(hit->co, ray->origin, ray->direction, hit->dist);
+ hit->dist = dist;
+ VECADDFAC(hit->co, ray->origin, ray->direction, dist);
}
+ return dist;
+}
+static float mesh_tri_raycast(void *userdata, int index, const BVHTreeRay
*ray, BVHTreeRayHit *hit)
+{
+ const BVHMeshCallbackUserdata *data = (BVHMeshCallbackUserdata*)
userdata;
+ MVert *vert = data->vert;
+ MFace *face = data->face + index/2;
+ const float *t0, *t1, *t2;
+ float dist;
-/*
- VECADDFAC(v0, ray->origin, ray->direction, 0);
- VECADDFAC(v1, ray->origin, ray->direction, hit->dist);
+ if(index & 1)
+ t0 = &vert[ face->v1 ].co, t1 = &vert[ face->v3 ].co, t2 =
&vert[ face->v4 ].co;
+ else
+ t0 = &vert[ face->v1 ].co, t1 = &vert[ face->v2 ].co, t2 =
&vert[ face->v3 ].co;
- if(SweepingSphereIntersectsTriangleUV(v0, v1, 0.1f, t0, t1, t2,
&lambda, hit_point))
+ dist = ray_tri_intersection(ray, hit->dist, t0, t1, t2);
+ if(dist >= 0 && dist < hit->dist)
{
hit->index = index;
- hit->dist *= lambda;
- VECADDFAC(hit->co, ray->origin, ray->direction, hit->dist);
- }
-*/
-
+ hit->dist = dist;
+ VECADDFAC(hit->co, ray->origin, ray->direction, dist);
+ }
+ return dist;
}
/*
* Raytree from mesh
@@ -916,6 +884,7 @@
//Ignore a face were not a single vertice moved
if(res == 0) continue;
+
//Only 1 vertice moved.. (if its a quad.. remove the vertice
oposite to it)
if(res == 1 && face[i].v4)
{
@@ -942,7 +911,28 @@
face[i].v4 = 0; //this quad turned on a tri
}
+
+/*
+ if(face[i].v4 && res == 3)
+ {
+ if(!bitset_get(moved_verts, face[i].v1))
+ {
+ face[i].v1 = face[i].v4;
+ }
+ else if(!bitset_get(moved_verts, face[i].v2))
+ {
+ face[i].v2 = face[i].v3;
+ face[i].v3 = face[i].v4;
+ }
+ else if(!bitset_get(moved_verts, face[i].v3))
+ {
+ face[i].v3 = face[i].v4;
+ }
+ face[i].v4 = 0; //this quad turned on a tri
+ }
+*/
+
bitset_set(used_faces, i); //Mark face to maintain
numUsedFaces++;
@@ -1140,12 +1130,13 @@
case MOD_SHRINKWRAP_NORMAL:
if(calc.smd->shrinkOpts &
MOD_SHRINKWRAP_REMOVE_UNPROJECTED_FACES)
- calc.moved = bitset_new(
calc.final->getNumVerts(calc.final), "shrinkwrap bitset data");
+ calc.moved = bitset_new(
calc.final->getNumVerts(calc.final), "shrinkwrap bitset data");
+/*
BENCH(shrinkwrap_calc_normal_projection_raytree(&calc));
calc.final->release( calc.final );
-
- calc.final = CDDM_copy(calc.original);
+*/
+// calc.final = CDDM_copy(calc.original);
BENCH(shrinkwrap_calc_normal_projection(&calc));
// BENCH(shrinkwrap_calc_foreach_vertex(&calc,
bruteforce_shrinkwrap_calc_normal_projection));
@@ -1200,7 +1191,7 @@
BENCH_VAR(query);
- BENCH(tree = bvhtree_from_mesh_verts(calc->target));
+ BENCH(tree = bvhtree_from_mesh_verts(calc->target, 0.0));
if(tree == NULL) return OUT_OF_MEMORY();
//Setup nearest
@@ -1352,6 +1343,8 @@
//setup raytracing
BVHTree *tree = NULL;
BVHTreeRayHit hit;
+ BVHMeshCallbackUserdata userdata;
+ BVHTree_RayCastCallback callback = NULL;
int numVerts;
MVert *vert = NULL;
@@ -1360,10 +1353,11 @@
if( (use_normal & (MOD_SHRINKWRAP_ALLOW_INVERTED_NORMAL |
MOD_SHRINKWRAP_ALLOW_DEFAULT_NORMAL)) == 0)
return; //Nothing todo
- BENCH(tree = bvhtree_from_mesh_tri(calc->target));
+ BENCH(tree = bvhtree_from_mesh_tri(calc->target, calc->keptDist));
if(tree == NULL) return OUT_OF_MEMORY();
+ bvhtree_meshcallbackdata_init(&userdata, calc->target, calc->keptDist);
+ callback = calc->keptDist > 0 ? mesh_tri_spherecast : mesh_tri_raycast;
-
//Project each vertex along normal
numVerts= calc->final->getNumVerts(calc->final);
vert = calc->final->getVertDataArray(calc->final, CD_MVERT);
@@ -1388,13 +1382,13 @@
if(use_normal & MOD_SHRINKWRAP_ALLOW_DEFAULT_NORMAL)
{
- BLI_bvhtree_ray_cast(tree, tmp_co, tmp_no, &hit,
mesh_tri_spherecast, calc->target);
+ BLI_bvhtree_ray_cast(tree, tmp_co, tmp_no, &hit,
callback, &userdata);
}
if(use_normal & MOD_SHRINKWRAP_ALLOW_INVERTED_NORMAL)
{
float inv[3] = { -tmp_no[0], -tmp_no[1], -tmp_no[2] };
- BLI_bvhtree_ray_cast(tree, tmp_co, inv, &hit,
mesh_tri_spherecast, calc->target);
+ BLI_bvhtree_ray_cast(tree, tmp_co, inv, &hit, callback,
&userdata);
}
if(hit.index != -1)
@@ -1424,6 +1418,7 @@
BVHTree *tree = NULL;
BVHTreeNearest nearest;
+ BVHMeshCallbackUserdata userdata;
int numVerts;
MVert *vert = NULL;
@@ -1431,8 +1426,9 @@
//Create a bvh-tree of the given target
- tree = bvhtree_from_mesh_tri(calc->target);
+ tree = bvhtree_from_mesh_tri(calc->target, 0.0);
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
