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

[David N. <da...@re...>]

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:and...@gm...] 
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