5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The "exit early" scenario is for when you find an axis of separation(hence the term "Separation Axis theorem"). A collision is positive when all axes have been checked and an intersection detected on each one. The question was how to generate multiple contacts for accurate resolution, ie physics. The solution is not actually that simple, and is done via Sutherland-Hodge clipping. This is another phase, carried out following the detection of a collision. \$\endgroup\$ – Ian Young Feb 19 '17 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.