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…
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 ma…
Re: A fast 3D collision detection algorithm
#31The 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).