Generating Stable Contact Information from EPA/GJK

[Carl Schissler]

I've taken the plunge and implemented SAT GJK and EPA for my physics engine. Both seem to work correctly. The problem that I'm now facing is determining better contact information from the results of EPA.

My implementation of EPA terminates when the increase in maximum penetration depth falls below some epsilon. This leaves me with a triangle farthest from the origin (in minkowski configuration space). When I reduce this triangle into two sets of points in world space I get 1 to 3 points per object.

From this, I observe several types of contact (vertex-face, edge-edge, edge-face, face-face) which correspond to the configuration of the two colliding objects. I can then generate contact information: one point for vertex-face, one point for edge-edge, contact segment for edge-face, contact polygon for face-face.

This works fine while objects are in motion but once they settle, I get jittery behavior, especially when face-face or edge-face contact is involved. I have figured out that the stability of these configurations is dependent on the epsilon I use for EPA termination - too small an epsilon and all terminations are vertex-face or edge-edge, resulting in jitter - too large an epsilon and the terminating element might not be on the surface of the object, resulting in unacceptable penetration.

I've tried caching contacts from the last frame and it improved stability somewhat, but I wasn't sure how I should determine which contacts are stale (I just reused them all).

Does anyone have any ideas how I might generate better contact information in these situations?

[Erwin Coumans]

You could use persistent contact caching, and maintain a few points in local space. The world position and distance projected along the contact normal are updated each frame for all cached points. Once the projected distance along the normal, or tangential exceeds a threshold, contacts are removed. In Bullet, up to 4 contact points are cached: the deepest contact point and a triangle that approximates the convex hull of the contact area.

Some explanation is in this topic:
http://bulletphysics.com/Bullet/phpBB3/ ... p?f=4&t=39

Or you can check out the Bullet physics sdk, and the implementation in btPersistentManifold class.
Hope this helps,
Erwin

[Carl Schissler]

I implemented your suggestion for contact caching and it dramatically improved the stability of face-face contact. Thanks for the tips!

I don't even have to treat different contact configurations separately, I just use barycentric coordinates on the output of EPA to find a single contact per shape pair per timestep.

My implementation is limited - it removes any contacts where the recalculated penetration depth is less than zero and then if necessary, removes the point with the most shallow penetration depth. I'm not sure if it's worth the extra effort to favor contact manifolds with larger areas, as the performance is already stable enough for my purposes (even with a fairly large timestep).

[Carl Schissler]

I've figured out that it is indeed better to prioritize the triangle with the largest area. If this isn't done, it is much less likely that points are chosen that lead to stable contact.