multiple contacts for SAT collision detection

Question

I have implemented SAT algorithm for obb-obb intersection and I am able to generate a contact for this collision type. My problem is that SAT only generate ONE contact and in many situation I need more than one contact. For example, If I have a big cube and above it I have a small cube I need two contact (two contacts in 2D and 4 contacts in 3D) one for each bottom vertex of small cube.

My question is how can I generate more than one contacts with SAT?

Thanks.

Answer 1

When performing OBB-OBB intersection using SAT, the suggested approach for generating multiple contacts is to find the coincident features and perform clipping - either edge against edge, or face against face, using the sutherland-hodgman clipper, after the SAT returns the intersecting features. This will return one (edge-edge) or more (face/face) contacts.

Dirk Gregorious of Valve covers this really well in his GDC2013 presentation. You can find one here: http://twvideo01.ubm-us.net/o1/vault/gdc2013/slides/822403Gregorius_Dirk_TheSeparatingAxisTest.pdf

I would recommend reading his paper, but essentially he suggests the following steps for face-face (his words not mine)

1. Identify the axis of minimum penetration using the SAT (this defines the reference face)
2. Find the most anti-parallel face on the other shape (this defines the incident face)
3. Clip incident face against the side planes of reference face
4. Keep all vertices below reference face

For edge-v-edge he suggests:

"If the axis of minimum penetration is realized by an edge pair compute the closest points between the two edge segments and are done."

Answer 2

An efficient SAT test is "Exit Early" meaning if you're just testing for collision, you see the collision and end the algorithm. Of course for the situation you've presented exiting early is no good; you need more information. I ran into this problem too.

The solution is fairly simple. You need to test ALL axes during your SAT test and not exit when you find one collision. I end up returning a "Collision" object from my SAT test which stores a vector of points where the objects collided. Of course this can turn out to be a big time waster since there may be some collisions where you care about resolution and some where you don't. There may be some cases where you DO want to exit early and others where you don't so keep that in mind.