Comment by CamperBob2
2 days ago
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...