Archived

This topic is now archived and is closed to further replies.

The fasted ray/triangle collision detection

This topic is 5403 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

It depends.

If the triangles are fixed and you want to test many rays with many triangles, such as in a raytracer, it might be pretty fast to project the triangles to screen space (once before you render the frame) and then instead of testing for intersection just do a quick 2d-(screen space)-point in triangle test!

How about that?

It should be faster than calculating the intersection point with the plane first and then do a point-in-triangle test.

Anyway, you can get the exact 3d intersection location by calculating three coefficients a,b,c which give 1/z at a certain screen point like: depth = 1.0/(a*x + b*y + c).

Just put your pixel x and y in there and you have the depth, your intersection point is p=ray.from+depth*ray.dir;

Share this post


Link to post
Share on other sites
quote:
What is the fastest 100% accurate method of testing if a ray passes through a triangle in 3d space?


That depends on the information you want out of the computation (i.e. just a yes/no answer or you want the intersection point and the surface normal), and if you can afford to store pre-computed info with your vertices.

Here''s one that doesn''t use precomputed data:



#define EPSILON 0.000001

int
intersect_triangle_barycentric(
double orig[3], double dir[3],
double vert0[3], double vert1[3], double vert2[3],
double planeq[4], int i1, int i2,
double *t, double *alpha, double *beta)
{
double dot, dot2;
double point[2];
double u0, v0, u1, v1, u2, v2;

/* is ray parallel to plane? */
dot = dir[0] * planeq[0] + dir[1] * planeq[1] + dir[2] * planeq[2];
if (dot < EPSILON && dot > -EPSILON) /* or use culling check */
return 0;

/* find distance to plane and intersection point */
dot2 = orig[0] * planeq[0] +
orig[1] * planeq[1] + orig[2] * planeq[2];
*t = -(planeq[3] + dot2 ) / dot;
point[0] = orig[i1] + dir[i1] * *t;
point[1] = orig[i2] + dir[i2] * *t;

/* begin barycentric intersection algorithm */
u0 = point[0] - vert0[i1];
v0 = point[1] - vert0[i2];
u1 = vert1[i1] - vert0[i1];
u2 = vert2[i1] - vert0[i1];
v1 = vert1[i2] - vert0[i2];
v2 = vert2[i2] - vert0[i2];

/* calculate and compare barycentric coordinates */
if (u1 == 0) { /* uncommon case */
*beta = u0 / u2;
if (*beta < 0 || *beta > 1)
return 0;
*alpha = (v0 - *beta * v2) / v1;
}
else { /* common case, used for this analysis */
*beta = (v0 * u1 - u0 * v1) / (v2 * u1 - u2 * v1);
if (*beta < 0 || *beta > 1)
return 0;
*alpha = (u0 - *beta * u2) / u1;
}

if (*alpha < 0 || (*alpha + *beta) > 1.0)
return 0;

return 1;
}

/*======================*/

#define EPSILON 0.000001
#define CROSS(dest,v1,v2) \
dest[0]=v1[1]*v2[2]-v1[2]*v2[1]; \
dest[1]=v1[2]*v2[0]-v1[0]*v2[2]; \
dest[2]=v1[0]*v2[1]-v1[1]*v2[0];
#define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])
#define SUB(dest,v1,v2)
dest[0]=v1[0]-v2[0]; \
dest[1]=v1[1]-v2[1]; \
dest[2]=v1[2]-v2[2];

int
intersect_triangle(double orig[3], double dir[3],
double vert0[3], double vert1[3], double vert2[3],
double *t, double *u, double *v)
{
double edge1[3], edge2[3], tvec[3], pvec[3], qvec[3];
double det,inv_det;

/* find vectors for two edges sharing vert0 */
SUB(edge1, vert1, vert0);
SUB(edge2, vert2, vert0);

/* begin calculating determinant - also used to calculate U parameter */
CROSS(pvec, dir, edge2);

/* if determinant is near zero, ray lies in plane of triangle */
det = DOT(edge1, pvec);

#ifdef TEST_CULL /* define TEST_CULL if culling is desired */
if (det < EPSILON)
return 0;

/* calculate distance from vert0 to ray origin */
SUB(tvec, orig, vert0);

/* calculate U parameter and test bounds */
*u = DOT(tvec, pvec);
if (*u < 0.0 || *u > det)
return 0;

/* prepare to test V parameter */
CROSS(qvec, tvec, edge1);

/* calculate V parameter and test bounds */
*v = DOT(dir, qvec);
if (*v < 0.0 || *u + *v > det)
return 0;

/* calculate t, scale parameters, ray intersects triangle */
*t = DOT(edge2, qvec);
inv_det = 1.0 / det;
*t *= inv_det;
*u *= inv_det;
*v *= inv_det;
#else /* the non-culling branch */
if (det > -EPSILON && det < EPSILON)
return 0;
inv_det = 1.0 / det;

/* calculate distance from vert0 to ray origin */
SUB(tvec, orig, vert0);

/* calculate U parameter and test bounds */
*u = DOT(tvec, pvec) * inv_det;
if (*u < 0.0 || *u > 1.0)
return 0;

/* prepare to test V parameter */
CROSS(qvec, tvec, edge1);

/* calculate V parameter and test bounds */
*v = DOT(dir, qvec) * inv_det;
if (*v < 0.0 || *u + *v > 1.0)
return 0;

/* calculate t, ray intersects triangle */
*t = DOT(edge2, qvec) * inv_det;
#endif
return 1;
}











Check out http://www.acm.org/pubs/tog/Software.html for more algos.

-cb

Share this post


Link to post
Share on other sites
I''ve seen this algorithm too, but I probably am going to be storing the triangle plane normals, and I was wondering if there was something faster that used this.

I really only need something that will determine if the intersection exists, as finding where the intersection is will be very easy.

Share this post


Link to post
Share on other sites
quote:
Original post by NickW
I''ve seen this algorithm too, but I probably am going to be storing the triangle plane normals, and I was wondering if there was something faster that used this.

The first version in the listing is from Badouel and the second part is from Thomas Moller. One of the benchmark algo, which can be made to use precomputed information, is from Snyder & Barr:
Snyder, M., Barr, A.H.: "Raytracing complex models containing surface tesselations", Proceedings of the 14th annual conference on Computer Graphics, 1987, Vol.21, No.4, pp.119-128, 1987.

Hope this helps.

-cb

Share this post


Link to post
Share on other sites
when fully optimized for prestoring in funky spaces, you can go for plueckercoordinates. there you get it in very short code, quite fun. but its not useful if the triangle needs to store the standard 3d space vertices, too (using 3*3 + 3*6 floats then, + normal etc..)



"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites