Rotational penetration depth

[Erwin Coumans]

Interesting concept, calculating rotational penetration depth, rather then just translational:

http://www.cs.unc.edu/~geom/PDG/pdg.pdf

Unfortunately this paper, and other UNC papers make some dubious claim about EPA:

Bergen proposes a quick lower bound estimation to PDt between two convex polytopes by iteratively expanding a polyhedral approximation of the Minkowski sum [van den Bergen 2001].

Bergen's expanding polytope algorithms is exact, not just an approximation. Bullet also implements and uses this EPA algorithm by default, and it seems to be a very fast and a reliable penetration depth method for general convex objects (not just polyhedra). The penetration depth calculated by EPA is exact, within a user-defined epsilon.

I'm anxious to learn about the details about this claim that EPA is just a 'quick approximation', rather then a 'very good penetration depth calculation'. When I asked Gino van den Bergen recently, he confirmed that EPA is an exact method.

[youngjkim]

We claimed that the EPA is not exact in the following sense (neither do ours, DEEP):

1) It is not an analytical solution so that it cannot provide all PD solutions; e.g. imagine a sphere overlapped with itself; it has an infinite # of solutions to report, which the EPA cannot.

2) The result of EPA is a lower bound to PD; it approximates the "internal" Minkowski sums. In case of DEEP, it provides an upper bound to PD.

One quick question for those who read this post

Would it be "quite" useful to have a rotational (generalized) PD, PD^g, for physics simulation? If so, how can PD^g help or how the simulation can be improved if you have PD^g?

BTW, recently, we have published another paper on PD^g, which is soon to be available online:

Liangjun Zhang, Young J. Kim, Dinesh Manocha, A fast and practical algorithm for generalized penetration depth, Robotics: Science and Systems, 2007

[gino]

We claimed that the EPA is not exact in the following sense (neither do ours, DEEP):

1) It is not an analytical solution so that it cannot provide all PD solutions; e.g. imagine a sphere overlapped with itself; it has an infinite # of solutions to report, which the EPA cannot.

2) The result of EPA is a lower bound to PD; it approximates the "internal" Minkowski sums. In case of DEEP, it provides an upper bound to PD.

Having a multiple or even an infinte number of solutions does not have an impact on the accuracy. The result of EPA is indeed a lower bound, but one that can be computed arbitrarily close to the actual penetration depth. So, is EPA exact? In theory, yes. In practice, no. Nor is any other algorithm that uses finite-precision arithmetic. Is EPA's accuracy worse than other existing methods for doing penetration depth computations? No. Since you control the tolerance of the relative error in the computed penetration depth, you can set it to any epsilon you require no matter how small. The epsilon is needed since EPA allows arbitrary convex objects as input. When applied to polyhedra, other termination conditions can be used that give "exact" results, since for these cases the expanding polytope will eventually touch the penetration depth in a finite number of steps. Needless to say you need to use a numerical format that has sufficient precision for your epsilon, but this is true for any geometric algorithm. EPA is by no means a quick approximation. Could it be that you are confusing EPA with Cameron's minimal translational distance approximation?

[Erwin Coumans]

EPA should find a global minimal penetration depth.
A correction on the first EPA publication keeps the expanding polytope convex, to avoid getting into a local minimum.

Could that have lead to the confusion?
Thanks,
Erwin

By the way, I think the generalized (including rotational) penetration depth can be useful in physics simulations. I'm curious how to select between the translational (without rotation) and generalized penetration depth recovery. Perhaps it can be chosen by the user on a per-object basis (like a quality/level of detail option)?

[Christer Ericson]

Interesting concept, calculating rotational penetration depth, rather then just translational[...]

Here's another on the same topic: http://www.geometrie.tuwien.ac.at/nawratil/gpdcbokg.pdf

This one is outstanding in the sense that it manages to make the presentation just about unreadable by overloading the paper with technical jargon. A great example of how not to write a paper.

Researchers, it doesn't matter if you have the best idea in the world if no one can read and understand your paper!

[Dirk Gregorius]

Sometimes or maybe often overloading the paper with technical jargon and making the paper unreadable is a sign that the idea is actually not that good.

In this sense: "The first obstacle is the misunderstood word"