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).

Benefits,

* 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.

Disadvantages,

* 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.

-= Dave

**From:** Andreas Brinck
[mailto:andreas.brinck@gmail.com]

**Sent:** Monday, February 08, 2010 11:49 PM

**To:** Game Development Algorithms

**Subject:** Re: [Algorithms] Algorithm to return point to surface of
concavevolume

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.

Thanks again

Andreas Brinck