#AltDevBlogADay

A large part of a rigid body dynamics engine is collision detection, in particular finding the contact points between objects. In games, non-moving world geometry is often represented by concave triangle meshes. Common collision shape representations for moving objects are basic convex shapes such as spheres, boxes and capsules and convex polyhedral meshes.

There are several efficient ways to generate contact points between convex polyhedral meshes, one method is based on Sutherland Hodgman clipping and another method builds multiple contact points by adding closest points to a persistent contact cache. I implemented both methods in the Bullet physics library, and you can download the source code from Bullet3 github repository, the screenshot above is taken from sample/api_bullet_physics/1_stable_convex.

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:

Sutherland–Hodgman clipping

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.

Contact reduction

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