Jump to content
• Advertisement

#### Archived

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

# fast ray/triangle intersection test

This topic is 6796 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

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 this post

##### Share on other sites
Advertisement
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 this post

##### 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 this post

##### 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 this post

##### 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 this post

##### 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 this post

##### 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 this post

##### 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 this post

##### 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 this post

##### 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 this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
3. 3
4. 4
Rutin
13
5. 5
• Advertisement

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633701
• Total Posts
3013433
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!