I'm thinking on using the SAT to do collision detection in 3D. my question is, after detecting a collision, how do i find the exact collision point so that i can respond to the collision? Thanks.

Thanks, the context is a physics simulation so i need to know exaclty were the OBB's touched eachother. Would it be easier to do it by checking all the corners and edges of one of the bodies against the sidesw of the other one? then using the intersection points it would be that hard to get the relevant collision points. Is there a better way?
Thanks.

There are two types of collisions. The first type is when the objects are initially sperated and fly into one another during the next frame. In that case all SAT can tell you is that the objects where separated initially, but won't find any collision features/points. You'll need to do some moving point/plane intersection to do that as well as two moving lines.. SAT is more useful when objects are overlapping initially, in that case there is no impact collision, and you must find a penetration depth or more precisely the shortest vector to separate the two objects. Hope that helps and good luck.

--Bart

I'll just put a list of code samples, and a link to the original thread. Too tired to go through an explanation or format the links but anyway, see if it helps...

original thread
http://www.gamedev.net/community/forums/topic.asp?topic_id=346956

2D
http://members.gamedev.net/oliii/satpost/BoxBoxIntersect.cpp
http://members.gamedev.net/oliii/satpost/BoxBoxCollision2.cpp
http://members.gamedev.net/oliii/satpost/BoxBoxCollisionAndMTD.cpp
http://members.gamedev.net/oliii/satpost/ConvexPolygonCollision.cpp

3D
http://members.gamedev.net/oliii/satpost/OrientatedBoxesCollision.cpp
http://members.gamedev.net/oliii/satpost/3DBoxPolygonCollision.cpp

spheres and polys
http://members.gamedev.net/oliii/satpost/3DSpherePolygonCollision.cpp
http://members.gamedev.net/oliii/satpost/SpherePolygonCollision.cpp

some extra files
http://members.gamedev.net/oliii/satpost/DXInputs.cpp
http://members.gamedev.net/oliii/satpost/DXInputs.h

some more samples (3D cubes and contact point calculations)
http://uk.geocities.com/olivier_rebellion/Cube3D.zip

I'll sort the links out some time later :)

Quote:Original post by jyk

Quote:Original post by bpj1138
There are two types of collisions. The first type is when the objects are initially sperated and fly into one another during the next frame. In that case all SAT can tell you is that the objects where separated initially, but won't find any collision features/points. You'll need to do some moving point/plane intersection to do that as well as two moving lines.. SAT is more useful when objects are overlapping initially, in that case there is no impact collision, and you must find a penetration depth or more precisely the shortest vector to separate the two objects.

You can extend the SAT to return contact information for the continuous test just as with the discrete test; there should never be any need to perform separate swept feature-feature tests as you describe.

Sorry for the delayed response. I remembered reading something to that effect in Eberly's paper, but I couldn't remember why I rejected the idea. Well, I was digging through my garbage today and found the paper, so I took a quick glance. The first sentence in the "extended SAT" section states that the objects are moving with "constant velocity". I took this to mean without rotations. I glanced a little further, and found no mention of angular velocity or individual vertex velocities. Is this correct?

Then while I was reading this thing, I decided to look over the pseudocode for the 2D SAT. It didn't look right to me, and after some thought, it seemed to me Mr. Eberly didn't implement his test right. He's got this function WhichSide() which returns three values -1 for points inside edge, +1 for points outside edge, and 0 for a mix. The thing is, the calling function is only interested in the +1 case (points outside), so why not exit WhichSide() early if 0 or -1, he only seems to do this for 0. Furthermore, he doesn't check for the dot product being zero (this might not be a huge problem, but it bothers me nonetheless).

Oh well, I thought I'd shoot this over here, I'm sure you guys can double check this.

--Bart

I seem to recall he has a paper implementing SAT with rotations in mind, but it's more complicated. Linear SAT is easy enough though. Obviously, you will not be able to prevent intersections (since the objects rotate and that's not taken into account).

BTW, back to the origiinal question,

When the SAT returns, it will provide two things, The normal of collision, and the time or depth of intersection.

The normal can be used to find the features that 'support' the object during the collision.

Example, dropping a box, flat on a table, the normal will be pointing up.

The polygon on the table that will be considered will be the top quad. For the box, it will be the bottom quad.

Those faces can be easily detected, since they will be parallel to the normal of collision.

That provides you with two polygons that literally collide each others. To find the surface of contact, you just use a standard clipping algorithm, estended to 3D, to find the intersection region. That will also be a convex polygon, and you can use the vertices of that polygon as your contact point.

If you drop the box onto an edge, the same thing apply. You are left with the top quad of the table, and the edge on the box. Then you clip the edge with the polygon, to get the contact vertices.

if you drop the box on a corner, then the corner is simply the contact point.

To find what features contact, you just need a bit of logic to find the face / edge / vertex that support the object along the normal of collision.

then you should be left with a few cases.

1) vertex - face contact.
2) edge - edge contact.
3) edge - face contact.
4) face - face contact.

all these are relatively straight forward. The most complex involve some 3D volume clipping, but even that is easy (since the volumes will be convex).