Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


triangle - AABB intersection


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 Lode   Members   -  Reputation: 982

Like
0Likes
Like

Posted 08 April 2006 - 10:52 PM

What's a good way to test if a triangle intersects an axis aligned bounding box in 3D? Currently I test if the AABB around the triangle intersects the other AABB, but clearly that solution will generate some false positives. Thanks!

Sponsor:

#2 Tessellator   Members   -  Reputation: 644

Like
0Likes
Like

Posted 09 April 2006 - 02:23 AM

I've used the Tri-AABB code from here in several projects:

http://www.realtimerendering.com/int/

(There are loads of other tests as well). It seems to perform pretty well.

HTH,
T

#3 BlackSheep   Members   -  Reputation: 100

Like
0Likes
Like

Posted 09 April 2006 - 02:43 AM

OTTOMH - Simply checking each vertex of the triangle is inside the AABB will do it. Quite a lot of point-plane distance tests though. Maybe there's a cleverer way than just brute-forcing it.


#4 Lode   Members   -  Reputation: 982

Like
0Likes
Like

Posted 09 April 2006 - 03:07 AM

Quote:
Original post by BlackSheep
OTTOMH - Simply checking each vertex of the triangle is inside the AABB will do it. Quite a lot of point-plane distance tests though. Maybe there's a cleverer way than just brute-forcing it.


Sometimes all vertices of the triangle are outside the AABB, and still a part of the triangle may go through the AABB, I'd like to include those cases too.

#5 BlackSheep   Members   -  Reputation: 100

Like
0Likes
Like

Posted 09 April 2006 - 03:52 AM

Quote:
Original post by Lode
Quote:
Original post by BlackSheep
OTTOMH - Simply checking each vertex of the triangle is inside the AABB will do it. Quite a lot of point-plane distance tests though. Maybe there's a cleverer way than just brute-forcing it.


Sometimes all vertices of the triangle are outside the AABB, and still a part of the triangle may go through the AABB, I'd like to include those cases too.


If you use the hyperplanes of the AABB rather than the absolute rectangular boundaries, you'll catch those too.



#6 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 09 April 2006 - 08:19 AM

This method may have already been mentioned, but the separating axis test is a reasonably efficient way to test for AABB-triangle intersection; it's also accurate, in that it won't miss any cases or return any false positives.

#7 Lode   Members   -  Reputation: 982

Like
0Likes
Like

Posted 09 April 2006 - 09:03 AM

The separating axis test sounds interesting. However, I don't know how it works, and a google search doesn't return any in depth explanation or tutorial. I found an old gamedev.net post about the box triangle test involving 13 axes, but I don't know what it means.

How to perform a separating axis test?

Thanks!

#8 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 09 April 2006 - 09:20 AM

Quote:
Original post by Lode
The separating axis test sounds interesting. However, I don't know how it works, and a google search doesn't return any in depth explanation or tutorial. I found an old gamedev.net post about the box triangle test involving 13 axes, but I don't know what it means.

How to perform a separating axis test?

Thanks!
You're right, this particular test doesn't seem to be documented so much online. Here's some code which might do the trick; I didn't look at it carefully though, so I'm not sure what method is employed.

The SAT itself is well-documented, and once you understand it thoroughly, applying it to different object pairs is fairly trivial. With AABB vs. triangle, the axes to test are:

- 3 AABB axes, which are the global axes
- 1 triangle normal
- 9 cross products, between each edge of the triangle and the three global axes

For a total of 13. A lot of this can of course be nicely optimized due to the axis alignment (watch out for degenerate cross products though).




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS