I've always been a big fan of representing surfaces as a distance field to the surface (e.g. a point cloud over a domain where every point is 1 scalar).
* Distance fields filter very well so you can have a smaller resolution and bilinear filter. For example, check out Valve's vector graphics paper for pictures to convince yourself if it doesn't make sense.
* Compresses very well, you can look into wavelets for a compact representation. I've seen signals compress up to 98% of its data using wavelets.
* Spatially hashed into for O(1) look-up on queries.
* The normal is stored implicitly via calculating the gradient.
* It's a compression and you may not get exact surface representations and with bilinear filtering you will smooth out crevices. Then again triangle representation isn't an exact representation either.
* It typically takes more memory then a triangle representation and much more than an analytical formulation. Though, if you code up a fast wavelet compression/decompression routine you can get huge memory savings over a triangle representation of a surface but not the analytical solution.
* Generating the distance field is kind of a pain for arbitrary convex objects.
The only other gotcha is integrating all your primitive types to collide against it. The basic idea is you take sample points on the surface of your object you are querying with and hash them against the distance field. It's a closet point problem for convex objects and for arbitrary concave objects you can generate sample points over the surface. Then you can take the minimum set of sample points that may collide (e.g. via some broad phase query) and hash them in.
Thanks for all the feedback people, I was hoping that there
would be some kind of simple iterative algorithm (something like GJK) but it
seems like I'm out of luck. I knew that the problem could probably be
formulated as a LCP but unfortunately I don't think this will be feasible given
the number of queries each frame.
Christer, I will look into the analytical solution but I think it will be hard and error prone to extract the intersection curves/points of the capsules.
I'm also toying with the idea of using some kind of Monte Carlo method to find the minimum but perhaps it's faster to just solve the LCP.