Comment by Animats
3 days ago
Nice. It's definitely an optimization problem. But you have to look at numerical error.
I had to do a lot of work on GJK convex hull distance back in the late 1990s. It's a optimization problem with special cases.
Closest points are vertex vs vertex, vertex vs edge, vertex vs face, edge vs edge, edge vs face, and face vs face. The last three can have non-unique solutions. Finding the closest vertices is easy but not sufficient. When you use this in a physics engine, objects settle into contact, usually into the non-unique solution space. Consider a cube on a cube. Or a small cube sitting on a big cube. That will settle into face vs face, with no unique closest points.
A second problem is what to do about flat polygon surfaces. If you tesselate, a rectangular face becomes two coplanar triangles. This can make GJK loop. If you don't tesselate, no polygon in floating point is truly flat. This can make GJK loop. Polyhedra with a minimum break angle between faces, something most convex hullers can generate, are needed.
Running unit tests of random complex polyhedra will not often hit the hard cases. A physics engine will. The late Prof. Steven Cameron at Oxford figured out solutions to this in the 1990s.[1] I'd discovered that his approach would occasionally loop. A safe termination condition on this is tough. He eventually came up with one. I had a brute force approach that detected a loop.
There's been some recent work on approximate convex decomposition, where some overlap is allowed between the convex hulls whose union represents the original solid. True convex decomposition tends to generate annoying geometry around smaller concave features, like doors and windows. Approximate convex decomposition produces cleaner geometry.[2] But you have to start with clean watertight geometry (a "simplex") or this algorithm runs into trouble.
> But you have to look at numerical error.
Yeah I agree, the error analysis could be many blogs in and of itself. I kinda got tired by the end of this blog. I would like to write a post about this in the future. For global solvers and iterative.
> Finding the closest vertices is easy but not sufficient.
As I'm sure you are aware, most GJK implementations find the closest features and then a one shot contact manifold can be generated by clipping the features against each other. When GJK finds a simplex of the CSO, each vertex of the simplex keeps track of the corresponding points from A and B.
> A second problem is what to do about flat polygon surfaces
Modern physics engines and the demo I uploaded do face clipping which handle this. For GJK you normally ensure the points in your hull are linearly independent.
There's been some recent work on approximate convex decomposition, where some overlap is allowed between the convex hulls whose union represents the original solid.
I wonder if it would be smart to restate the problem in just those terms -- managing bounding-volume overlap rather than interpenetration at the geometric level.
If everything is surrounded by bounding spheres, then obviously collision detection in the majority of cases is trivial. When two bounding spheres do intersect, they will do so at a particular distance and at a unique angle. There would then be a single relevant quantity -- the acceptable overlap depth -- that would depend on the angle between the BV centers, the orientation of the two enclosed objects, and nothing else. Seems like something that would be amenable to offline precomputing... almost like various lighting hacks.
Ultimately I guess you have to deal with concavity, though, and then the problem gets a lot nastier.
The main precomputation needed is the result from the previous frame. Algorithms of this type of convex hull distance are really cheap, because you don't need to examine every vertex, just trace a path to the closest points. That's roughly O(sqrt(n)). If you're doing this over and over as objects move, and start from the previous result, it approaches O(1).
Most physics engines do indeed do this and call it something like "collision margin"[1].
[1]: https://gamedev.stackexchange.com/questions/113774/why-do-ph...
I am consistently amazed at your depth of knowledge. Can we have a meal? My shout. I'm crossing the US a lot for fundraising right now, probably nearby someplace. Email in profile.