QB ON ACID
ISSUE #4 December 21st, 1999
_________________________________________________________________
Implicit Surface Polygonization
This article, originally an e-mail to tek_hed and some others, will
describe a method for polygonizing implicit surfaces. Metaballs are an
example of these: the surface is not defined explicitly (as in
polygons), or parametrically (as in spline grids), but rather, well,
implicitly. Basically, you have a function f(x,y,z) which is 0 for any
point on a closed surface, negative on the "inside" of that surface,
and positive on the "outside".
Now, to polygonize it, you create an array of points at an arbitrary
resolution (100x100x25 would do fine in most situations), and evaluate
the function for every point.
Then, you connect all the points with the ones exactly 1 unit away,
creating a gridwork between these points. Every one of those
connections that crosses through the texture (ie, one endpoint has a
different sign than the other), you do a binary search (or just
approximate by averaging) to find a much closer point to the surface,
and you "attach" that point to the two endpoints.
Then, you go through all the points again, and for every one that has
3 attached points that are NOT coaxial (ie, one is offset only by X,
one only by Y and one only by Z), you generate a poly connecting those
points.
You cover all combinations of 3 points that are not coaxial that are
connected to the same grid point, and when you're done, you have a
polygonal representation of the implicitly defined surface (which
could be a metaball system or whatever).
To refine the surface, look at every edge of the polys and find the
angle between the polys on each side of the edge. Sort the edges by
this angle, and resample the ones with angles exceeding a given
threshold using a finer grid (ie, the same grid over a smaller
volume).
There ya go =D
By logiclrd at http://logiclrd.cx