/* Ray-Triangle Intersection Test Routines */
/* Different optimizations of my and Ben Trumbore's */
/* code from journals of graphics tools (JGT) */
/* http://www.acm.org/jgt/ */
/* by Tomas Moller, May 2000 */
#include <math.h>
#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];
/* the original jgt code */
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);
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;
return 1;
}
ray-tri intersection
Author
I hope this isn't a stupid question, but does this code require a particular coordinate system?
I'm assuming the dir[3] parameter is a ray that is visible to the triangle and points into it, but I have to invert the ray just to get this function to work.
it's quite odd.
looking at the cross product, that should be for a right ended coordinate system. Like, a ''normal'' coordinate system. Maybe you are using a left handed coordinate system? Or in other words, use clockwise ordering for front facing?
Are you sure your triangle vertices are listed anti-clockwise? Else, it would explain. Or alternatively, try changing the sign for each components at the CROSS() macro. But that''s not recommended. better change the winding order of the vertices (instead of (v0[3], v1[3], v2[3]), use (v2[3], v1[3], v0[3])).
if I remember correctly, there is a version of that code that does not use culling, works both ways.
Are you sure your triangle vertices are listed anti-clockwise? Else, it would explain. Or alternatively, try changing the sign for each components at the CROSS() macro. But that''s not recommended. better change the winding order of the vertices (instead of (v0[3], v1[3], v2[3]), use (v2[3], v1[3], v0[3])).
if I remember correctly, there is a version of that code that does not use culling, works both ways.
this one? http://www.acm.org/jgt/papers/MollerTrumbore97/code.html
EDIT: got it from here : http://www.realtimerendering.com/int/
[edited by - sBibi on January 22, 2004 4:53:16 AM]
EDIT: got it from here : http://www.realtimerendering.com/int/
[edited by - sBibi on January 22, 2004 4:53:16 AM]
Author
Besides that, I''m having trouble with edges between two planes
or two triangles.
The ray shoots right between them through the edge!
This makes my collision test fails. I thought this code was
good??
I''ve never seen that problem, and I use it. It may require some bits of thresholds. replace the 0.0 and 1.0 with (-0.000001f and 1.0000001f), maybe?
Author
If a ray hits an edge between two triangles, how do you treat this case for collision?
I''m trying to ''illuminate'' one of those triangles, so sometimes
the adjacent triangle gets flagged as causing a collision, sometimes not.
I''m trying to ''illuminate'' one of those triangles, so sometimes
the adjacent triangle gets flagged as causing a collision, sometimes not.
hmmm... I don''t use rays for pure collision detection, I don''t know what you use rays for exactly, but I don''t see where it should make a difference. After all, if the ray hits the edge dead on (and it should occur very rarely, or else something is wrong), tri A as as much right to be used for collision as tri B. What do you do with the ray after you found the triangle?
unless you are doing the tresholding thing, it working, and you forgot to tell me
in most cases involving ray intersection tests, you would be interested mostly on the first triangle intersected, and the distance should be provided by the value t returned by the function. So I''d say, take the smallest t value to get the triangle intersected by the ray.
unless you are doing the tresholding thing, it working, and you forgot to tell me
in most cases involving ray intersection tests, you would be interested mostly on the first triangle intersected, and the distance should be provided by the value t returned by the function. So I''d say, take the smallest t value to get the triangle intersected by the ray.
Author
Yep, adding a small epsilon value seems to be working, I have another problem now.
I''m creating a lightmap for a model and I''m using raytracing for triangle collision detection.
Each triangle has its own lightmap.
Everything seems to be working ok, except when I turn on bilinear filtering, which messes up
the edges.
I tried to be sneaky by adding a 1-pixel border around each lightmap, but this causes
headaches in raytracing.
Not quite sure how people solve this bilinear filtering problem, either during or after
the raytracing process. I tried duplicating the outer lightmap edges, but this doesn''t
work.
I''m creating a lightmap for a model and I''m using raytracing for triangle collision detection.
Each triangle has its own lightmap.
Everything seems to be working ok, except when I turn on bilinear filtering, which messes up
the edges.
I tried to be sneaky by adding a 1-pixel border around each lightmap, but this causes
headaches in raytracing.
Not quite sure how people solve this bilinear filtering problem, either during or after
the raytracing process. I tried duplicating the outer lightmap edges, but this doesn''t
work.
this is a bit beyond the scope of the thread, and it would be best answered by graphics dudes. You''ll probably have more luck with lightmapping, filtering, and mipmapping at the graphics forum.
Share:
This topic is closed to new replies.
Advertisement
Advertisement
