#### Archived

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

# fast ray/triangle intersection test

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

## Recommended Posts

I want to have a fast ray/triangle intersection test alogrithm. I just have a ray start/end vertex and three triangle vertices and want to know if the ray intersects with the triangle, no uv coords needed. Speed is very important. Any ideas ??? Tim

##### Share on other sites
Hi there,

find the intersection point with the plane the triangle lies in. Then do a point in polygon test. That is the most used method.

For speeds sake precalculate the triangleplane. And if you wanna go really fast then precalculate the edge planes as well (planes that are perpendicular to the triangle going trough the edge, which are often used for point in poly tests).

Jaap Suter

##### Share on other sites
Hi !!

The method described above is ok. I have found another algo which can be found here:

http://www.acm.org/jgt/papers/MollerTrumbore97/

Have fun.

Phillip

##### Share on other sites
just for reference - a ray does not have an end vertex.

-goltrpoat

##### Share on other sites
Yeah I know. But may (light) ray has, it ends on the wall ;-))))

Jaap Suter:

I know the tutorial on flipcode. But the stuff with the anti-planes doesn''t work if you use the alog for lightmap calculation. The start/end point of the light ray may be outside the collision box, but still cross the triangle. To make sure that this don''t happens, the anti-planes of the collsion box must be calculated trough adding the ray''s vector, rather than adding the plane normal. This is slow, you need 3 square roots for each intersection test since you have to recalculate your anti-plane normal....

any idea how to avoid this ????

##### Share on other sites
two words - barycentric coordinates.

-goltrpoat

##### Share on other sites
http://www.acm.org/jgt/papers/MollerTrumbore97/

can''t get this working. The code seems to be somehow wrong !? Just look at the first macro, the author forgot a "\" this code can''t compile, I guess the writer of this document never compiled it !?

##### Share on other sites
Hi Tcs (and others).

The method I mentioned does work but you probably think I mention another method then I did (that must be the worst sentence I ever wrote in a foreign language).

What I always do is calculating the intersection of the ray and the plane (the plane of the polygon I mean). And then I do a point in polygon test. This point in polygontest is done using the edgeplanes (or antiplanes as you call them). This has always worked for me and I couldn''t see why this wouldn''t work.

or.. ?

Jaap

##### Share on other sites
I was under the impression that after finding the intersection point on the plane it''s faster to figure the angles between the vertices and the point, add em, and see if they add to 180 degrees or not. :?

##### Share on other sites
The problem is that calculating the angle takes a squareroot unless your vectors are normalized. And with the point in poly test with angles your vectors are never normalized. And these can''t be precalculated either (edge (or anti-) planes can).

##### Share on other sites
Jaap:

My fault. I always used the start/end point of my camera/light path, and those points could be outside the collsion box, even if a collision has been occured. I tried to avoid the calculation of t, the intersection point. But my method of recalculating anti-planes that are parallel to the ray (3 sq roots) is a lot slower. I think I just calc the intersection point and do the anti-p check. That''s a lot of add''s and mul''s, but it should be faster than three sq''s. I post the code here, please tell me when it gets any faster ;-))

thanks, TIm

##### Share on other sites
Damn, I hate to ask stupid questions all the time...
can''t get my intersection test working.

void CTriangle::CalcIntersectionPoint(const float fRayStart[], const float fRayEnd[], float fIntersectionOut[])
{

float fD = DOT(m_Normal, m_Vertices[0]);
float fRay[3] = { fRayEnd[x] - fRayStart[x], fRayEnd[y] - fRayStart[y], fRayEnd[z] - fRayStart[z] };
float fT = - (DOT(m_Normal, fRayStart) + fD) / DOT(m_Normal, fRay);

fIntersectionOut[x] = fRayStart[x] + (fRay[x] * fT);
fIntersectionOut[y] = fRayStart[y] + (fRay[y] * fT);
fIntersectionOut[z] = fRayStart[z] + (fRay[z] * fT);

}

This works "a bit" but I got many errors on my lightmaps. Some triangles are completely black. Where is the error in
this code ???

##### Share on other sites
Hej there,

I''ll post my intersection code later tonight when I get home. It''s pretty simple.

Catch you later.

Jaap Suter

____________________________
Mmmm, I''ll have to think of one.

##### Share on other sites
Hey, that''s cool, thanks ! I want a good book about all this, but there isn''t a good one out there. Computer Graphics P&P seems to be outdated...

##### Share on other sites
Hi!

I'd like to throw my support in for Jaap's method of doing the intersection test. This is the way that I myself use.

I don't know what you want to use the test for, but since you say speed is important, I would suggest you try not to focus on the actual intersection calculation, but instead try to eliminate as many tests as possible before they are done. One way of doing this would be to see if the triangle's bounding box is inside the bounding box of your start and end points. Then you can group several triangles together and eliminate them all if their combined bounding box doesn't cut it.

Another thing you can do once you have found one intersection point is to exchange your endpoint for it in future testings, thus shrinking the ray's bounding box. Assuming you only want the closest intersection.

For your choice of book I highly recommend Real-Time Rendering by Tomas Möller and Eric Haines. You can find their web site here. You might even find some good articles on intersection testing there.

I myself bought this book because I thought Computer Graphics: P & P to be a bit outdated, and although I haven't read the whole book yet I'm impressed with it so far.

WitchLord

Edited by - WitchLord on 4/21/00 3:01:57 PM

##### Share on other sites
I need it for lightmaps. Want to do shadows. So you''re right, I want to get rid of as much polys as possible. If you hav a 3K poly world ad 32x32 lightmaps, and yu have 10 lightsources... this means 3000x3000x1024x10 (=92160000000)
intersection tests. A lot of ar 3k poyl scene... I guess I just have to sue BSP trees, if I want to get those calcs done in a acceptable time...

ok, I sit around and wait for Jaap to post his code ;-))

BTW: If you want my class for the lightmap calculation, just go to my site http://glvelocity.demonews.com/

I post a early version of my class in a day or two...

Tim

##### Share on other sites
can you *please* post the code ? My weekend is very boring if I don''t know how to continue... ;-))

Thanks ;-)

Tim

##### Share on other sites
quote:
Original post by tcs

void CTriangle::CalcIntersectionPoint(const float fRayStart[], const float fRayEnd[], float fIntersectionOut[])
{

float fD = DOT(m_Normal, m_Vertices[0]);
float fRay[3] = { fRayEnd[x] - fRayStart[x], fRayEnd[y] - fRayStart[y], fRayEnd[z] - fRayStart[z] };
float fT = - (DOT(m_Normal, fRayStart) + fD) / DOT(m_Normal, fRay);

fIntersectionOut[x] = fRayStart[x] + (fRay[x] * fT);
fIntersectionOut[y] = fRayStart[y] + (fRay[y] * fT);
fIntersectionOut[z] = fRayStart[z] + (fRay[z] * fT);

}

You have an error in this code, when you compute fT you should subtract fD and not add it.

float fT = - (DOT(m_Normal, fRayStart) - fD) / DOT(m_Normal, fRay);

WitchLord

Edited by - WitchLord on 4/22/00 9:53:51 AM

##### Share on other sites
Thanks man !

It works, very cool. The new alog is about 150% faster than the old, very cool.

Thanks!

Tim

##### Share on other sites
I''m very very sorry. I was at my parents place this weekend and I didn''t have acces to the internet there. I suppose you got it working now so you don''t need the code anymore. If you still do then just reply.

I''m sorry again.

Jaap Suter.

##### Share on other sites
By the way, you are not checking whether the ray is parrallel to the plane in your code.

Here is my plane/ray intersection code:
(Hoping the messageboard won''t f*k up my code...

// -------------------------------------
// CAPlane::IntersectsWithRay
// Find the intersection point of a ray and a plane;
// Returns false if the ray is parallel;
// -------------------------------------
aBool CAPlane::IntersectsWithRay( CAVector3Df& a_Intersection, const CAVector3Df& a_Origin, const CAVector3Df& a_Ray ) const
{
// Calculate the denominator;
aFloat denominator = (a_Ray.GetX() * static_cast (m_Normal.GetX())) +
(a_Ray.GetY() * static_cast (m_Normal.GetY())) +
(a_Ray.GetZ() * static_cast (m_Normal.GetZ()));

// Check for a_Ray parrallel to plane;
if ( denominator != 0 )
{
// Calculate the t value of the intersection point;
aFloat t = (static_cast (m_D) -
((a_Origin.GetX() * static_cast (m_Normal.GetX())) +
(a_Origin.GetY() * static_cast (m_Normal.GetY())) +
(a_Origin.GetZ() * static_cast (m_Normal.GetZ())) ) )
/
denominator;

// Calculate the intersection point itself;
a_Intersection = CAVector3Df( a_Origin.GetX() + t * a_Ray.GetX(),
a_Origin.GetY() + t * a_Ray.GetY(),
a_Origin.GetZ() + t * a_Ray.GetZ()
);
return true;
}
else
{
// Ray is parrallel;
return false;
}
}

##### Share on other sites
Besides some indention problems and the wrong static_casts everything seems ok.

static_cast should be static_cast(aFloat) where the brackets are actually those sharp ones

(english is not my native language so I don''t know what they are called.)

I''m sorry for posting three times in a row too by the way.
Anyway, see you all later.

Jaap Suter

##### Share on other sites
ok, thank you anyway !

I managed to get everything fast and reliable working. You can get my triangle class for collision detection and lightmap calculation at http://glvelocity.demonews.com/
I don''t need the parallel check cause I first test the intersections with the triangle''s hyperplane...

But now I have another problem (see my new post) ;-))

Tim

##### Share on other sites
As a side note

How do you compute the arccos of a value? I am looking at doing the finding the intersection point of the plane, then summing the angles between each vert. So I have this code:

float fDot = Inter.DotProduct( Verts.Position );
float fLength = Inter.Length() * Verts[i].Position.Length();
float fCos = fDot / fLength;

Now I need to get the angle that fCos belongs to...

Any ideas

Thanks.

##### Share on other sites
try using the function acos() that is declared in math.h

- WitchLord