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
Alternative for EPA Penetration depth
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
-
- Posts: 40
- Joined: Fri Jul 22, 2005 8:00 pm
- Location: Santa Monica
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.
-
- Posts: 316
- Joined: Fri Jul 01, 2005 5:29 am
- Location: Irvine
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.
-
- Posts: 40
- Joined: Fri Jul 22, 2005 8:00 pm
- Location: Santa Monica