So after spending a few weeks outside the CSO, I got around to step inside and experiment with a number of different penetration distance algorithms this week. However, I failed to come up with an alteriative to EPA that can actually guarantee a global minimum separation. These are the ones I tried:

1) Use MPR to raycast the inside of the CSO in a direction estimated by the geometric center of the CSO, use the resulting normal and iterate until convergence. This works in 95% of all cases and is really fast. The downside is that there is no way to guarantee or measure if this really is the global minimum.

2) Same method as in 1) but use multiple search directions. I was for a while under the impression that two local minima had to be at least 90 degrees apart, so casting six rays should be safe (of which three can be optimized away). This works in 99% of all cases, but there is still that annoying one percent where it finds a local minima.

3) Same method as in 1) but trace the edges of the last portal. After the initial surface point has been found, tilt the search direction in the direction of each edge, so that it falls outside the last portal, choose the best direction and iterate until convergence. This way we can sample the neighboring triangles and search those directions. Again, there is a 99% success rate. Unfortunately in some cases all neighboring triangles will lean towards the initial triangle, so we will just end up at the same local minima again.

4) Broken EPA. I tried using EPA without tracking connectivity and without keeping the polytope convex. Simply a triangle soup, where the closest triangle is split and valid triangles (the ones that are portals) are kept. It doesn't work.

5) Full EPA. I used the one found in Bullet as inspiration and it works really well in all cases. I'm really impressed by the Bullet implementation by Nathanael Presson. EPA is an awfully complicated algorithm to implement, but it seems very stable and quite fast.

So all this fuzz to come up with the conclusion that EPA is the way to go? I'm still contemplating wether there is a way to combine MPR and EPA to make an early out and just find the surface using MPR. It might not be possible.

I'm still not using EPA for all penetrations. In most cases using MPR with the last known separation axis works excellent, even just sampling and projecting support mappings on the last axis works really well. Physics is surprisingly forgiving about something, for once.

arent you supposed to be busy hugging exotic animals, surfing and generally staying away from computers!! ??

ReplyDeleteHugging a configuration space obstacle is almost as fun, trust me :)

ReplyDeleteLOL! Oddly shaped anyhow.

ReplyDeleteThere is an alternative to EPA if you restrict yourself to polytopes only. In that case the CSO is a polytope itself that can be computed explicitly. The solution is rather brute force. Simply check each face of the CSO and find the one that is closest to the origin. A CSO of polytopes has a complexity of O(m n) for two polytopes having m and n vertices each, so you are looking at a quadratic solution. However, due to the sheer simplicity of the approach, building the Minkowski sum may outperform EPA for lower complexity polytopes.

ReplyDeleteCheck out Efi Fogels's PhD thesis on Minkowski sums of polytopes.

http://www.cs.tau.ac.il/~efif/publications/thesis/thesis.pdf

Gino