Metball modelling rests on the polygonization of an isosurface. The isosurface is defined as the set of all points in space where the force function is precisely equal to some chosen constant threshold. The polygonization of the surface is a set of polygons which attempt to aproximate the form of the surface to the best of their resolution. The surface is not guaranteed to be accurate; shapes on the surface that fall below the resolution of the polygon mesh will not be represented accurately. But overall, polygonization is an effective way of displaying the isosurface, and so care must be taken to compute the polygon mesh as quickly and accurately as possible.
In the following discussion, a point is hot if the value of the force function at that point is above the system threshold. A point is cold if the value of the force function at that point is below the threshold. An edge or face is hot if it has one or more hot vertices and one or more cold vertices.
The polygon mesh is generated by refining an Octree over the bounding cube of the model. An Octree is a cube of space. Cubes have eight corners; consider an edge between any two. If the edge is hot, then somewhere in between the two F() must be exactly 0.5. This is because F() is a continuous function, because it is the sum of a set of continuous functions. Interpolation techniques can be used to quickly aproximate where along the edge F()=0.5. An effective function has proven to be
where P is now an interpolation between the two vertices. (Obviously, this fails if both vertices are hot or cold.) P is the vertex of a polyon in the polygon mesh.
If only one corner of the cube is hot then we will interpolate three points in space where F()=0.5; these three points uniquely determine an oriented polygon. If only two neighboring corners were hot, we would find a squareish polygon separating those two vertices from the rest of the cube. Any configuration of hot and cold corners gives rise to one or two polygons. So any cube in space in which one or more corners are different temperatures from the rest of the cube can be used to produce polygons whose vertices are on the surface. Eight corners, each either hot or cold, means that there are 2^8=256 possible combinations of hot and cold corners=256 possible polygon cases. Both implementations currently use pre-calculated arrays of constants to find which vertices are applicable to which cases.
A single Octree produces a single polygon. When we refine an Octree, we break it up into eight smaller Octrees, one for each octant. Several of these will not contain any part of the surface; they will not be refined any further. Those which are crossed by the surface (some corners are hot but some are cold) will produce polygons; they can be queued for refinement at a later date. Thus starting from a single seed Octree, we can produce a smooth, finely faceted surface. Parts of this surface can be removed and updated dynamically as changes occur to the underlying model.
The following sequence demonstrates refinement in action.
These images were taken from meshes exported to Data Explorer:
An important consideration in implementing an octree refinement scheme is that sampling the force function F() may be a very expensive operation. Care should be taken to avoid repeating it more often than necessary. If possible, neighboring octrees should share vertex values between them and parent octrees should share vertex values with their children.
More Information on Surface-Fitting Algorithms
An Overview of Metaballs/Blobby Objects by Matthew Ward, WPI CS Department
Example Dinosaur image.
Example animation by John Isidoro created by using the Marching Pyramids algorithm.
Main Modeling Page
HyperGraph Home page.