This blog posting I discuss the contact clipping method, and I’ll discuss the persistent contact caching method in a future posting.
The basic recipe
1) find the separating axis between the two convex polyhedra A and B
2) search for a face in A and B that support the separating axis
3) generate contact points by clipping one face from A against the convex hull B
Finding the separating axis
Given two convex polyhedra A and B, we need to find the axis with the minimum projected separation. For step 1 in above recipe you can any method to find the separating axis. Two popular methods to find the separating axis are the separating axis test (SAT) and GJK named after its creators Gilbert, Johnson and Keerthi. Note that GJK needs a companion algorithm such as the expanding polytope algorithm (EPA) for the penetration case.
The SAT test is easier to explain and implement than GJK/EPA so here is a brief description. You can check the books by Gino van den Bergen and Christer Ericson for more details.
SAT in a nutshell
The potential separating axis can be either a face normal from A or B, or a cross product using edges from A and B, unless the edges are parallel. We can do an exhaustive search using all potential axis and computing the projection of the convex hull on those axis. We search for the axis with the largest separating distance. If maximum distance of the projection is positive, the object don’t overlap and we can terminate. In my implementation this step is implemented in btPolyhedralContactClipping::findSeparatingAxis.
Projection of the convex hull onto an axis
The projection of a convex hull onto an axis can be computed by taking the vertex with the maximum dot product with the axis. Such search for a extreme vertex given a direction vector is also known as a support mapping.
Reducing the number of separating axis tests
The number of separating axis can grow fast and testing all axis can become a performance bottleneck.
1) Only use unique directions.
For a box-box test this reduces the total number of candidates from 156 to 15 axis.
2) First check against interior objects to cull detailed tests
This was recently discussed by Pierre Terdiman in this blog posting: if the separating distance with a simplified object is already larger than the current smallest distance, then we don’t need to test the distance with the more complex convex hull. This optimization will easily reduce the total number of tests 90%.
3) Once the minimal separating distance for a face goes beyond the current smallest distance, we can discard the remaining vertices for this face.
Even with above optimizations, I found that GJK/EPA test still outperforms the SAT test in many cases. I’m sure there are other optimizations possible, if you know any please leave a comment.
Searching clipping faces
Once we have the separating axis we can search for a face on A and a face on B with a normal that is closest to the separating axis. These are faces with maximum and minimum dot product of its face normal against the separating axis. In the picture those two faces are drawn in red:
To generate multiple contact points, we can clip the face from one object against the hull of the other object. The wikipedia page has a good illustration about this clipping process:
Instead of clipping against the entire hull, we can only clip against the edge planes connected to the incident face in the other object. In the picture those edge planes are drawn in green:
You can choose to perform this clipping in world space, or in the space of object A or B. The resulting contact points can be reported in world space or in one of the object spaces. You can check the implementation in btPolyhedralContactClipping::clipFaceAgainstHull.
The contact generation method can produce a lot of contacts. We can reduce the number of contacts in several ways, for example only keep the following contact points:
1) the deepest point
2) the furthest from the deepest point
3) the furthest point from (2)
4) the supporting point of a direction orthogonal to the edge connecting point (2) and (3)
5) the support point of the negative orthogonal direction to this edge
Convex polyhedral meshes can be created manually using authoring tools, or generated automatically from concave triangle meshes using convex decomposition methods. Khaled Mammou just released a brand new library for Hierarchical Approximate Convex Decomposition of 3D Meshes (HACD) that can be downloaded here https://sourceforge.net/projects/hacd
I plan to try out his convex decomposition method and discuss this in an upcoming blog posting.