Sign in to follow this  
Barguast

Separating Axis (Plane) Theorum, in 3D

Recommended Posts

I'm looking for a good explanation of the Separating Axis Theorum, and how it works in three dimensions. I had successfully learned and implemented the 2D version last year, but unfortunately that is now long gone and I'm having trouble locating the resources I used to learn it. :( Thanks.

Share this post


Link to post
Share on other sites
Thanks, I'd not read those presentations before. :)

While this gives me a good reminder of SAT in 2D, they don't seem to discuss the theory in three dimensions. The major difference I guess would be that I have to determine separating planes rather than axes.

The way I pictured SAT in 2D was that the two objects were being projected into 1D in order to detect intersections. Does SAT in 3D involved projecting the objects to 2D, and then to 1D to do the same? Or am I overthinking this? :p

Sorry about posting in the wrong forum!

Share this post


Link to post
Share on other sites
It's not the wrong forum, you'd get more hit on maths & physics :)

They do talk about the 3D case in the powerpoint presentation. And the 3D algo works the same as the 2D algo. You end up with several 1D tests to perform. The difference as you pointed out is the axes to test against. You need faces and edge directions.

here is a recent discussion on the subject.

here is some code for the 2D example. I'm writing a 3D version based on OBBs, with full physics (so it's gonna take while).

The extra work in 3D is the contact point generation, in particular for face-face and edge-face cases.

Share this post


Link to post
Share on other sites
If you have access to this book http://realtimecollisiondetection.net/ you'll find a good explanation there.

I don't remember if http://www.geometrictools.com/ had an article about it or not. Have a look there if you can't get access to the book.

Share this post


Link to post
Share on other sites
I think I get it for the most part - the only thing that is throwing me at the moment is the necessity to check the axis defined by the cross product of the edges from each volume. I don't think this applies to the 2D version?

Maybe I'm just having trouble visualising it, but I can't envisage a situation where checking this axis would find an intersection where the usual face-normal axes would not.

Share this post


Link to post
Share on other sites
On the X and Y axis, yes. But using the face normals, of which they are four for each shape on your 2D example, the test would correctly say that the objects are NOT intersecting

Share this post


Link to post
Share on other sites
nope, for 2D, you take the perpendicular to the edges. In your example, you are missing the tests considering the edges of the long thin rectangle.

This is also a problem in 3D if you want to test 2 polygons that are coplanar. Because polygons in 3D lack 'depth', you need to revert to a 2D scenario (use the perp of the edges, and not the edge cross products) to test that case. Also, obviously, the two polygons need to be on the same plane (within a tolerance).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this