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