Separating Axis (Plane) Theorum, in 3D
Author
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.
salvation is at hand
Essential Maths For Games Programming.
Collisions using separating-axis tests.
That should get you going.
It's also probably best to post collision detection related questions in the Maths and Physics forums.
Essential Maths For Games Programming.
Collisions using separating-axis tests.
That should get you going.
It's also probably best to post collision detection related questions in the Maths and Physics forums.
Author
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!
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!
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.
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.
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.
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.
Author
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.
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.
Author
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
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).
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
