Skip to main content
gamedev.net
🔒 Locked

ray-tri intersection

Started by raydog 9 replies 2.6k views
Original Post
raydog
raydog
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. 

/* 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;
}
[edited by - raydog on January 21, 2004 6:18:45 PM]
oliii
oliii
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.
Everything is better with Metal.
oliii
oliii
that''s the one. It''s got #defines for enabling culling or not.
Everything is better with Metal.
raydog
raydog

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??
oliii
oliii
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?

Everything is better with Metal.
raydog
raydog
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.
oliii
oliii
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.
Everything is better with Metal.
raydog
raydog
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.
oliii
oliii
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.
Everything is better with Metal.
Charles B
Charles B
When a ray hits an edge straight on.

I presume that you use ray/triangle for col det and that the flashing triangle stuff matters when you apply a response to a collision. For instance a bullet, hits the decor and you need the triangle normal to compute the deflection. If discontinuity is a problem then you can treat edge/ray collision as a separate case.

- You can detect it''s an edge/ray collision when u or v is 0 or 1.
- You can compute the contact point normal by considering the edge is a small cylinder. Thus any annoying discontinuous collision effect will disappear.


Off topic :

For lightmaps per poly and bilinear filtering the solution is by adding extra rows of texels. See GL_TEXTURE_BORDER if my memory serves me well. But trilinear filtering makes it even more difficult to handle. You have to really understand how the GPU handles filtering and also see the particular context of your 3D rendering, specially the range of mip mapping lods. Personnally I rescale the texture image and the model coordinates. I also control the minimum mip LODs to get rid of visible edges. Too hard to explain it here in details.
"Coding math tricks in asm is more fun than Java"

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.