Alternative for EPA Penetration depth

[Erwin Coumans]

When using the Hybrid GJK, the penetration depth is either determined by GJK, using margins, or by another algorithm, once the depetration is deeper then the sum of the margins.

EPA is one good approach, but it is fairly complicated to get it 100% robust, and its performance has room for improvement.

A cheap alternative that works in practice is:

1) find a good approximation of the MTD (Minimum Translational Distance)
2) find the points on both objects that give the penetration vector

For (1) you can sample the projection of the origin onto the minkowski sum in a fixed number of directions. For example, in Bullet I use 42 directions, uniformly distributed over the unit sphere. To avoid the cost of 42 virtual function calls, a batch supportingVertex is used. This supportingVertex call can use the non-margin version, and can be optimized using SIMD very well.

For (2), once you found a translational distance, you move the objects out of penetration using the vector, and perform a GJK step to find the closest points. The difference in the distance reported by this GJK query, and the translational distance can be used to correct the estimation error.

This way, the estimated penetration vector exactly puts the objects in touching contact.

It is an approximation that works very well in practice, even tough slighly better directions might exist. Better then failing totally, or spiking in performance. Also, not much accuracy is needed, because deep penetrations should be resolved within a frame, and shallow penetrations are handled using the margins.

You can see implementation details here:
http://www.continuousphysics.com/Bullet ... tml#l00092

Erwin

[dog]

Has any one had any luck implementing the approach described in this paper? They describe why Gino's EPA algorithm has issues (with diagrams!), but I have had no success getting the Gauss mapping robust when trying to emulate their approach.

[Erin Catto]

I implemented some Gauss map stuff, which is essentially an incremental SAT. Unfortunately, it can easily get stuck at local minima, especially in the edge-edge case. However, I'm still hopefully that some other techniques can be combined with Gauss maps to find separating axes that are good enough.

[dog]

Having just got around to implementing my penetration depth calcs the Erwin Coumans way (well roughly), I'm very pleased with how robust and simple it is. Thank you sir.

Now back to playing with Gauss maps...