triangle - AABB intersection

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

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.

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.

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.

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.

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!

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).