[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15509] branches/soc-2008-jaguarandi/ source/blender: Add raycast ability for BLI_kdopbvh

André Pinto andresusanopinto at gmail.com
Wed Jul 9 21:43:10 CEST 2008


Revision: 15509
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15509
Author:   jaguarandi
Date:     2008-07-09 21:43:09 +0200 (Wed, 09 Jul 2008)

Log Message:
-----------
Add raycast ability for BLI_kdopbvh

small bvh fixes:
*allow to create any tree type >= 2
*save split axis

changed shrinkwrap to perform normal cast with raytree and bvh tree and print both times:

Shrinkwrap (OBCube)24578 over (OBSuzanne)504482
target = raytree_create_from_mesh(calc->target): 1260.000000ms
shrinkwrap_calc_normal_projection_raytree(&calc): 1850.000000ms
tree = bvhtree_from_mesh_tri(calc->target): 3330.000000ms
shrinkwrap_calc_normal_projection(&calc): 3780.000000ms

On general query time is bit smaller on bvh tree..
but the build time of bvh is pretty big.
(build time can be removed from both if a cache system is added)
But I am still trying to see how fast I can make the bvh build

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-07-09 19:15:26 UTC (rev 15508)
+++ branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c	2008-07-09 19:43:09 UTC (rev 15509)
@@ -59,7 +59,7 @@
 #define OUT_OF_MEMORY()	((void)printf("Shrinkwrap: Out of memory\n"))
 
 /* Benchmark macros */
-#if 0
+#if 1
 
 #define BENCH(a)	\
 	do {			\
@@ -88,14 +88,108 @@
 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 float ray_intersect_plane(const float *point, const float *dir, const float *plane_point, const float *plane_normal);
 
-static void normal_short2float(const short *ns, float *nf)
+
+/* 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)
 {
-	nf[0] = ns[0] / 32767.0f;
-	nf[1] = ns[1] / 32767.0f;
-	nf[2] = ns[2] / 32767.0f;
+	float dist;
+	if(RayIntersectsTriangle(ray->origin, ray->direction, v0, v1, v2, &dist, NULL))
+		return dist;
+
+/*	
+	float pnormal[3];
+	float dist;
+
+	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;
+
+	
+
+/ *
+	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;
+
+	divdet= t00*x0+t01*x1+t02*x2;
+
+	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))
+	{
+		return labda;
+	}
+*/
+	return FLT_MAX;
 }
 
+
 /*
  * BVH tree from mesh vertices
  */
@@ -168,7 +262,45 @@
 		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 float *t0, *t1, *t2;
+	float 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;
+
+
+	dist = ray_tri_intersection(ray, hit->dist, t0, t1, t2);
+	if(dist < hit->dist)
+	{
+		hit->index = index;
+		hit->dist = fabs(dist);
+		VECADDFAC(hit->co, ray->origin, ray->direction, hit->dist);
+	}
+
+
+
 /*
+	VECADDFAC(v0, ray->origin, ray->direction, 0);
+	VECADDFAC(v1, ray->origin, ray->direction, hit->dist);
+
+	if(SweepingSphereIntersectsTriangleUV(v0, v1, 0.1f, t0, t1, t2, &lambda, hit_point))
+	{
+		hit->index = index;
+		hit->dist *= lambda;
+		VECADDFAC(hit->co, ray->origin, ray->direction, hit->dist);
+	}	
+*/
+
+}
+/*
  * Raytree from mesh
  */
 static MVert *raytree_from_mesh_verts = NULL;
@@ -724,7 +856,7 @@
 		//We also need to apply the rotation to normal
 		if(calc->smd->shrinkType == MOD_SHRINKWRAP_NORMAL)
 		{
-			normal_short2float(vert[i].no, normal);
+			NormalShortToFloat(normal, vert[i].no);
 			Mat4Mul3Vecfl(calc->local2target, normal);
 			Normalize(normal);	//Watch out for scaling (TODO: do we really needed a unit-len normal?)
 		}
@@ -991,13 +1123,13 @@
 	//Projecting target defined - lets work!
 	if(calc.target)
 	{
-/*
+
 		printf("Shrinkwrap (%s)%d over (%s)%d\n",
 			calc.ob->id.name,			calc.final->getNumVerts(calc.final),
 			calc.smd->target->id.name,	calc.target->getNumVerts(calc.target)
 		);
-*/
 
+
 		switch(smd->shrinkType)
 		{
 			case MOD_SHRINKWRAP_NEAREST_SURFACE:
@@ -1010,6 +1142,10 @@
 				if(calc.smd->shrinkOpts & MOD_SHRINKWRAP_REMOVE_UNPROJECTED_FACES)
 					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);
 				BENCH(shrinkwrap_calc_normal_projection(&calc));
 //				BENCH(shrinkwrap_calc_foreach_vertex(&calc, bruteforce_shrinkwrap_calc_normal_projection));
 
@@ -1116,7 +1252,7 @@
  * it builds a RayTree from the target mesh and then performs a
  * raycast for each vertex (ray direction = normal)
  */
-void shrinkwrap_calc_normal_projection(ShrinkwrapCalcData *calc)
+void shrinkwrap_calc_normal_projection_raytree(ShrinkwrapCalcData *calc)
 {
 	int i;
 	int vgroup		= get_named_vertexgroup_num(calc->ob, calc->smd->vgroup_name);
@@ -1132,7 +1268,7 @@
 		return;	//Nothing todo
 
 	//setup raytracing
-	target = raytree_create_from_mesh(calc->target);
+	BENCH(target = raytree_create_from_mesh(calc->target));
 	if(target == NULL) return OUT_OF_MEMORY();
 
 
@@ -1152,7 +1288,7 @@
 		//Transform coordinates local->target
 		VecMat4MulVecfl(tmp_co, calc->local2target, vert[i].co);
 
-		normal_short2float(vert[i].no, tmp_no);
+		NormalShortToFloat(tmp_no, vert[i].no);
 		Mat4Mul3Vecfl(calc->local2target, tmp_no);	//Watch out for scaling on normal
 		Normalize(tmp_no);							//(TODO: do we really needed a unit-len normal? and we could know the scale factor before hand?)
 
@@ -1167,10 +1303,6 @@
 				dist = FLT_MAX;
 		}
 
-		normal_short2float(vert[i].no, tmp_no);
-		Mat4Mul3Vecfl(calc->local2target, tmp_no);	//Watch out for scaling on normal
-		Normalize(tmp_no);							//(TODO: do we really needed a unit-len normal? and we could know the scale factor before hand?)
-
 		if(use_normal & MOD_SHRINKWRAP_ALLOW_INVERTED_NORMAL)
 		{
 			float inv[3]; // = {-tmp_no[0], -tmp_no[1], -tmp_no[2]};
@@ -1211,6 +1343,73 @@
 	free_raytree_from_mesh(target);
 }
 
+void shrinkwrap_calc_normal_projection(ShrinkwrapCalcData *calc)
+{
+	int i;
+	int vgroup		= get_named_vertexgroup_num(calc->ob, calc->smd->vgroup_name);
+	char use_normal = calc->smd->shrinkOpts;
+
+	//setup raytracing
+	BVHTree *tree	= NULL;
+	BVHTreeRayHit hit;
+
+	int	numVerts;
+	MVert *vert = NULL;
+	MDeformVert *dvert = NULL;
+
+	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));
+	if(tree == NULL) return OUT_OF_MEMORY();
+
+
+	//Project each vertex along normal
+	numVerts= calc->final->getNumVerts(calc->final);
+	vert	= calc->final->getVertDataArray(calc->final, CD_MVERT);	
+	dvert	= calc->final->getVertDataArray(calc->final, CD_MDEFORMVERT);
+
+	for(i=0; i<numVerts; i++)
+	{
+		float tmp_co[3], tmp_no[3];
+		float weight = vertexgroup_get_vertex_weight(dvert, i, vgroup);
+
+		if(weight == 0.0f) continue;
+
+		//Transform coordinates local->target
+		VecMat4MulVecfl(tmp_co, calc->local2target, vert[i].co);
+
+		NormalShortToFloat(tmp_no, vert[i].no);
+		Mat4Mul3Vecfl(calc->local2target, tmp_no);	//Watch out for scaling on normal
+		Normalize(tmp_no);							//(TODO: do we really needed a unit-len normal? and we could know the scale factor before hand?)
+
+		hit.index = -1;
+		hit.dist = 1000;
+
+		if(use_normal & MOD_SHRINKWRAP_ALLOW_DEFAULT_NORMAL)
+		{
+			BLI_bvhtree_ray_cast(tree, tmp_co, tmp_no, &hit, mesh_tri_spherecast, calc->target);
+		}
+
+		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);
+		}
+
+		if(hit.index != -1)
+		{
+			VecMat4MulVecfl(tmp_co, calc->target2local, hit.co);
+			VecLerpf(vert[i].co, vert[i].co, tmp_co, weight);	//linear interpolation
+
+			if(calc->moved)
+				bitset_set(calc->moved, i);
+		}
+	}
+
+	BLI_bvhtree_free(tree);
+}
+
 /*
  * Shrinkwrap moving vertexs to the nearest surface point on the target
  *

Modified: branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h	2008-07-09 19:15:26 UTC (rev 15508)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h	2008-07-09 19:43:09 UTC (rev 15509)
@@ -47,10 +47,26 @@
 	float dist;			/* squared distance to search arround */
 } BVHTreeNearest;
 
+typedef struct BVHTreeRay
+{
+	float origin[3];	/* ray origin */
+	float direction[3];	/* ray direction */
+} BVHTreeRay;
+
+typedef struct BVHTreeRayHit
+{
+	int index;			/* index of the tree node (untouched if no hit is found) */
+	float co[3];		/* coordinates of the hit point */
+	float dist;			/* distance to the hit point */
+} BVHTreeRayHit;
+
 /* 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);
 
+/* returns the ray distancence from given co to the node, nearest point is stored on nearest */
+typedef float (*BVHTree_RayCastCallback) (void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit);
 
+
 BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis);
 void BLI_bvhtree_free(BVHTree *tree);
 
@@ -70,5 +86,7 @@

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list