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