Metaball math

Introduction to metaballs

Note: bold letters are vectors, normal letters are scalars

Metaballs are described as:

(1)

- m_n = location of metaball number n
- s_n = size of metaball number n
- k = number of balls
- g = "goo"-value, which affects the way how metaballs are drawn
- r = treshold for metaballs
- p = place vector
- |x| = magnitude (length) of vector x

For a more "concrete" example, here's the same formula, written for two 2d metaballs:

You could try to solve y from that equation and draw the metaballs like any normal 1-dimensional function, but as the number of balls increases, solving y becomes impossible.

Normal approach in drawing 2d metaballs is to scan through some grid (for example, every pixel on screen) and evaluate the metaball formula. If the result is true, draw a pixel there. Here's a picture showing some metaballs drawn this way:

Sample 2d metaballs

Small black crosses show the metaball center points m_n, n = {1, 2, 3, 4}

Metaball normals

Metaballs are described by a force field, (1), so normal for any given point is easy to calculate with the help of gradient.

(2)

This leads to

(3)

Very fast method for drawing 2d metaballs

Here I introduce a new way of drawing 2-dimensional metaballs, which should be over 200 times faster than the brute force method described at the beginning of this document. I don't know if it could be implemented in 3 dimensions also, but you could give it a try :)

Tracking the border

First, start at the center of any metaball. Then use the normal information to move towards the border (surface) of the metaball system. Just move towards the normals direction, step by step, until you reach the border. This process can be boosted a little, since we know that metaballs are inversely proportional to the distance from center, raised to power g. Thus, the step size can be calculated better:

(4)

Where f(x) is the force at distance x from origin, and s_min is the size of the smallest ball in the system. (actually you could just use the size of the ball that you're currently using as an origin for tracking, but I haven't tested nor proven that this works in all cases without problems. It would definitely speed up the process though, if you have many balls with highly different sizes)

We need to solve "stepsize" from the following group of equations (in relation to 'r' and 'force' which are both known values).

f(p) = force, f(border) = r, p+stepsize = border

Result:

(5)

where force is the force of metaball field at current point. You shouldn't use this as an exact stepsize though, because this will only reach the border after infinite amount of steps! You should add a small constant value to it, like 0.01. The smaller the constant, the closer you will get of the actual border, but the more steps are needed.

Anton Mikhailov pointed out that just three balls is enough to create a "valley" in which one may get stuck while trying to find the border. The valley is a local minimum which is still greater than r. But since many balls would share the same exterior border in such a situation, you might be able to overcome this problem by simply discarding this metaball's border-finder and rely on the ones that start from other metaballs' centers.

Walking among the path

Now that you have reached the border of the metaball system, use tangential vector of the normal field to start tracking your way around it. Thus you're moving across an iso-line. If normal is calculated as

n = x * i + y * j

(6)

then the tangent is

t = -y * i + x * j

(7)

Now you simply need to move on the surface until you reach your starting place again. Due to numerous inaccuracies, however, you won't reach the starting point exactly. So don't expect the method to be incredibly robust. To improve the accuracy of this method, it is very important to use 2nd or 4th order Runge-Kutta for tracking instead of the simple Euler's method. With Euler's method, you need a ridiculously small step-size for tracking, and even then the results are adequate. 2nd order Runge-Kutta seemed to work best in most cases. Also highly suggested is to use adaptive stepsize so that very curvy areas get more points.

Results

I made an example program [1] in Python that demonstrates everything described here. The source code is throughoutly commented so that it could be useful even for those unfamiliar with Python. If you want to run it, you'll need Python 2.2- and PyGame (both free and recommended).

Here's a small animation showing this method in action. Small white balls indicate the metaball centers, green dots indicate the tracing of the border. As you can see, the green dots jump quite rapidly towards the border, thanks to formula (1) from above.

Step-size is 16 pixels for drawing the border (white line), and 2nd order Runge-Kutta is used.

Fast metaballs in action

Drawing the metaballs in this example demo was over 300 times faster than the brute force method.

My recommended application for this method is Flash demos and games. I doubt any other method would be fast enough to be evaluated with actionscript.

Disadvantages

Two major problems were already mentioned: One might end up in a local minimum when trying to find the border, and when following the edge of the metaball system one might diverge from the iso-line.

But there's yet another flaw which may be more severe. Occasionally there's an isolated empty area inside several balls, but there's no guarantee that you will find it when trying to find the border starting from the center of metaballs. So it's possible for that interior border to disappear when the balls are positioned in certain way.

References

Code highlighting done with this script.