Metaballs are organic looking n-dimensional objects that are really popular for creating smooth and dynamic shapes. Each metaball is defined as a function having n-dimensions (in this case 3 dimensions). A threshold, also known as the iso-level is chosen to define the iso-surface formed from the combined influence of all the metaballs which defines the resulting shape.
Since the resulting iso-surface is defined by a density or influence function, the naive approach would be to evaluate that function for every point in space, where the resolution of the space would define the smoothness of the surface. This as one might expect is ridiculously expensive computationally speaking, but there are better techniques we can leverage:
To ease the computation involved, we voxelize the space up to a desired resolution and then for every voxel query the density function and use the reulting values to draw a 3D polygonal approximation of the surface. There are 256 (2^8) configurations for a voxel sampled at its 8 corners, however only 15 different configurations can be used to represent all 256 due to symmetry and with the help of rotations; and all of these configurations can be represented with upto 5 triangles/voxel.
A 2D example showing how varying densities can effect the edge (isoline) that is formed.
The polygonal configurations above can be made a more accurate representation of the isosurface even at low resolutions by using the density values at the corners to find new points on the bounding box of the voxel to define the lines that make the triangles of the isosurface.
The eight corners of the voxel can be represented by an 8-bit number, where 1 means the isovalue is above or below the isolevel based on some predefined threshold.And the twelve edges of the voxel can be represented as a 12-bit number, where 1 means that the isosurface intersects with this edge.
This table returns a 12-bit number that represents the edges intersected by the isosurface. For each intersected edge, we can compute the linearly interpolated vertex position on the edge according to the isovalue at each end corner of the edge.
This table stores the triangle indices corresponding to the vertex positions on the edges identified above. Every 16 elements in the table represents a possible polygonizing configuration. Within each configuration, every three consecutive elements represents the indices of a triangle that should be created from the edges above.
Having implemented all of the above, our metaballs would look quite low poly at lower resolutions. An easy fix for this is to calculate the normal for all the points that makes the polygonal configuration of the voxel. This gives us per-vertex data for normals which when passed through a fragment shader results in a much smoother surface than before (it is the equivalent of the switch from having normals per face to having normals per vertex of the mesh).
Calculating the normal at an arbitrary point involves finding the gradient at that point. This can be expensive so a good approximation for the same is to sample neighboring points along the n-dimensions, and use their difference to approximate the slope.
A 1D representation would be:
For 3D density functions the normal would be represented as:
Defined as the sum of the influences of all the metaballs within its vicinity, which have a inverse square fall-off in terms of intensity
The Marching cubes algorithm can achieve a effect similar to ray marching for rendering implicit surfaces, but in addition to the rendered image, you also retain geometry.
Common Use Cases:
- In MRI scanning, to generate geometry for the scans.
- To generate complex terrain for games. The resulting geometrical information can handily support collision and other physical calculation for game engines. For example, their bounding boxes can then be computed to construct the acceleration data structure for collisions.
- Generating complex terrain from GPU Gems 3.
- Polygonising a scalar field by Paul Bourke.
- Marching squares by Jamie Wong.