accuracy of collision detection: Bullet vs. Solid

[Erin Catto]

You can read about non-convex optimization on this page:

http://www.solver.com/probconvex.htm

If you want to learn more about optimization, I recommend this book:

http://www.amazon.com/Numerical-Optimiz ... 729&sr=8-1

Another way to understand the problem is with the Minkowski sum. Draw a convex polygon with the origin some where inside. Now compute the distance between the origin and the perimeter as your move around the polygon. You will see that in some cases the distance has multiple local minima. It seems that you can overcome this by having a good starting guess and I think this is true in 2D (since I do this in Box2D).

But in 3D with all the edge-edge axes, you quickly run into a situation where there are many local minima. This is something that is difficult to visualize, so if you have doubts, you should try the local search yourself. Just be sure to verify your local search with a global search.

If you get the local search to work in all cases, please let us know since you will have solved one of the most difficult collision detection problems.

[Erwin Coumans]

But in 3D with all the edge-edge axes, you quickly run into a situation where there are many local minima.

Exactly. And this is why EPA, as implemented in Bullet and SOLID has to keep the expanding polytope convex, to avoid getting stuck into a local minimum. So EPA calculates the global minimum. The sampling method I implemented in Bullet, as cheap/simple alternative to EPA approximates the global minimum.

DEEP and XenoCollide don't calculate this global minimum, but just a local minimum. In simulations you might want to use the penetration in the velocity direction, so starting with the velocity direction might give good results.

For more clear picture of local minima in penetration depth, see page 31 of this nice introduction to collision detection, of my former collegue Eric Larsen. From this picture you can also see how the 'sampling' method in Bullet works, by sampling in 42 directions evenly distributed over a sphere.
Erwin

[Erin Catto]

Erwin, thanks for the picture.

It seems that the number of local minima decreases as penetration becomes shallow. Perhaps this be exploited. Also during deep penetration the exit direction may not matter much (it won't be pretty in any case).

It is unclear how these observations carry over to 3D.