Metaballs, everyone’s favorite computer-generated globby blobs , have been around for a while. They’re the product of a rush of innovation in computer graphics during the 1980′s by the likes of Ken Perlin, Bui Tuong Phong, and Jim Blinn, when computer graphics began recognizing the need for organic shapes and shaders. The algorithm has been implemented countless times and can be astoundingly efficient and simple; the hardest part is finding something useful for them. Here is our take on it.

Download the source for all of these demos here.

There are several parts to this demo, and I’m going to give credit where its due right now. The first part is the vector rendering of the metaballs; the real innovator here is Hannu Kankaanpää, who has a great write up on a clever rendering algorthim, which I’ve adapted from Python to ActionScript. The second part is the eye-candy, the pixel shader. The folks over at omino made this spiffy distortion/chromatic aberration filter for AfterEffects, which I then adapted to run in Flash’s crippled PixelBender environment. I’m not totally satisfied with my conversion, but it does the job. I won’t be going over the details of the refraction, but the PixelBender source file is included.

Pro-tip: Right click on any of these demos for an option to turn on a profiler, so you can watch the performance.

Fields of Metaballs

So what is a metaball really? The mathematical terms for a metaball are either an isoline (two dimensional) or an isosurface (three dimensional). This demo only explores the two dimensional aspects. Isolines are analogous to a contour map; the center of each metaball is like the peak of a mountain, and the line formed by them is the contour of an elevation on that mountain. As those peaks get closer together, they begin to merge and a bridge emerges. If they sit on top of each other, they form one extra large mountain. In this demo, the graph on the top is like a side-view of the system; the metaballs on the bottom can be thought of as a cross-section of that system.

Mathematically, each metaball in the system has a position ( ) and a strength ( ), and the system as a whole has a “gooiness” constant ( ). We can find the strength (or elevation, in our analogy) of a particular point ( ) by plugging everything in to a fall-off function for each metaball in the system, and summing the results. In our implementation, the fall-off function is

This formula might look familiar; when it is an inverse square relationship, or basically Newtonian attraction. Really any fall-off function could be used, as long as it is smooth and has a domain of , and there are some that are more efficient by leaving out the division. But, with some tricks in the code, this one does just fine.

/**
 * Check the strength of this metaball on a point in space.
 * @param	v	The point to check against.
 * @param	c	The exponential constant of the field.
 * @return	The strength of this metaball's field at the point.
 */
public function strengthAt(v:Vector2D, c:Number):Number
{
    var div:Number = Math.pow( Vector2D.subtract(_position, v).lengthSq, c * 0.5 );
    return (div != 0) ? (_strength / div) : 10000;
}

Rendering with Vectors

A regular brute-force metaball renderer would operate by taking this formula and solving it for each pixel or voxel in the system. People have also cheated the effect in Flash using a variety of BitmapData tricks; generally something like drawing circles, applying a strong blur filter and then using BitmapData.threshold(). This can work really well; just look at this awesome demo. Hannu’s approach is a little more complex, but very optimized for the CPU. It also has the unique benefit of having a vector output, which can come in handy given that most of Flash is vector based.

To explain how it works, lets return to our contour map analogy. Suppose you were in a mountain range and wanted to find the contour at around 500 feet elevation. One approach would involve standing on each square foot of dirt and measuring the elevation and then plotting those elevations on some kind of grid. This would be easy and fast if you had thousands of people with you to simultaneously measure each of those square foot plots. But if you’re all alone, like the CPU is, you need a more straightforward approach. Instead, you start at the top of one of the mountains, and descend in any direction until you reach 500 feet elevation. Then you start walking in either direction, never going up or down, only around. When you return to the spot you started at, you’ve successfully plotted the 500 foot elevation contour for that mountain (and any other mountain peaks you walked around). Instead of evaluating every square foot in the mountain range, you only make one evaluation per step you take.

This introduces some unique complexity issues; a GPU solution has a fixed complexity for a certain resolution and number of metaballs, whereas Hannu’s algorithm changes in complexity based on the position of the metaballs. There are also additional problems, such as how far each step should be, how many steps to take before you “give up,” and how to tell when you’re done. I’m not going to post the whole rendering algorithm here; it is messy, a bit long, and not particularly insightful. There are two loops; in the first loop, the algorithm locates a point on the edge of each metaball. The second loop traces the field normal (using second order Runge-Kutta) between the edge points found in the first loop, like a set of dominoes falling into each other. At every step, we write a coordinate to a graphics object, and end with a tidy, convenient GraphicsPath object. What’s the point? Well, that’s up to you, but here is something you could never do with a pixel-based renderer:

There’s Always a Downside

The biggest issue is the stability. Just like dominoes, sometimes things don’t line up quite right. Its a natural problem with a less rigorous approach, and there isn’t much to do about except adding additional error-checking and more generous tolerances. I developed the system for an application that would use four or five metaballs at most, and for that, the system is relatively stable. But…add enough metaballs to the stress test below, and things will start to go haywire; spiraling edges, inversions, the works. Another downside is recognized by Hannu; in certain configurations, a set of three or more metaballs can form a donut-like shape. A rigorous evaluation would show a hole in the middle, but this edge tracing technique may miss it some frames and pick it up in others. I think it could be addressed if it was a huge issue for a certain application, but in general it seems pretty unlikely.

The performance is decent on Flash Player 10, and I’m sure some keen eyes could find plenty of room for optimization. Turn on the profiler on the stress test below (its in the right click menu) and see how much you can break it!

Download the source for all of these demos here.