Simple 3D collision detection for general polyhedra

Question

I have correctly set up a SAT system. I now need to determine a simple, fast, and general purpose collision detection mechanism to identify the collision points. These points will then be used to determine the constraints for Catto's algorithm.

Unfortunately there seems to be a huge set of candidate algorithms, hence my confusion.

My first take would be, given that SAT tells me the candidate triangle-vertex or triangle-triangle for the collision, to perform the following: - if SAT results in a T-V collision, we are done; collision is at V - if SAT results in a T-T collision, then the collision points are found by intersecting the vertices of triangle1 with triangle2 and the edges of triangle1 with triangle2

Am I missing something big?

Answer 1

Are you sure you set up your SAT correctly? You have cross product edge checks to cover, not only face axes. Assuming you have it setup correctly, move on:

Lucky for you manifold generation (finding points of contact + penetration depth + collision normal) is really simple with the SAT. There are two major cases of collisions for general convex polyhedra when dealing with the SAT: something-face and edge-edge. Lets start with something face:

Something has hit a face. This can be multiple edges, or just one vertex. It really doesn't matter which of these two cases you are dealing with, as both use the same exact code to generate contact information, hence calling it the "something hit a face" case. First, the face that contributed the axis of least separation will be called the reference face. The most anti-normal face on the opposing object will be called the incident face. Clip the incident face against the reference face side planes.

Image from Dirk Gregorius's GDC 2013 lecture

Above is a picture of the side planes of one of the faces in contact. These side planes are what you must clip the incident face against.

Here is a 2D representation of the side planes of a face:

After clipping, all resulting contact points need to be tested against the reference face. Discard all contacts in front of the reference plane. You are now left with contact points below the reference face. The deepest point will represent the penetration depth for the collision, though with Sequential Impulses you will want each contact to be aware of its own penetration depth, in order to solve each point of contact iteratively, thus allowing convergence to a global solution.

For the edge-edge case life is a little simpler. Just compute the closest points on the two offending edges, average the points together, and use this single point as the only point of contact.

For clipping I recommend Sutherland-Hodgman. See Real-Time Collision Detection by Ericson for a wonderful and robust implementation of this clipping routine.

Each point of contact's collision normal should just be the reference face's normal for the something-face case. For edge-edge the cross product between the two faces defines the collision normal. There is a small gotcha with cross products: there is no guaranteed orientation. By convention the normal should point in a defined direction from the reference object to the incident object. You'll need to come up with a way to ensure your normal direction is consistent (hint: see Dirk's GDC 2013 slides).