Optimizations and Improvements

With all of this practical uses existing for clearly high-demand areas like medicine and engineering, why is it that they aren't particularly prominent in the world of game development? If you've taken a try at implementing the algorithm above, you'll know the answer in a heartbeat: they're slow.

Or rather, rendering isosurfaces is slow in the naive implementation of performing a summation of each Meta-Shape on every pixel. There are several immediately noticeable optimizations that we can apply to speed up our Metaballs, depending on what result exactly we want to end up with. Below are several optimizations that one can implement that are not too challenging to add into your own Metaballs rendering routine, or may find generally useful.

Uniform Box Division

As you may have noticed in many of the images shown in this article, only a small amount of the screen is actually being drawn. The majority of the pixels (in most situations) remain black and unaffected by the metaballs.

A fairly easy to implement optimization is thusly to compute only the portions of the screen that will actually be drawn. Imagine the screen as divided into uniformly-sized grid boxes. The idea is to sample one or more points within that box to determine if it is worth drawing the contents of it.

Recall that the equation for a metaball is much like the equation of an electrical field, whereas the "charge" of the metaball gets gradually smaller and smaller the farther from the centre of the metaball that you go. This means that you can check for another threshold value every time you sample from the grid to determine whether the grid box is worth drawing. If it is above the threshold, than there must be a metaball nearby.

To make it easier to visualize, the end-result should look something like this:

(Filling the map with fixed-size boxes which are sampled to determine their viability to be drawn.)

In terms of how useful the optimization is, I receive a speed increase of between 200% and 300% on my machine, but your mileage may vary. The increase you receive is proportional to the size of the grid boxes, how large most metaballs are, and how many metaballs are in the game world. This requires a bit of experimentation to find values that ‘fit’ nicely for your purposes.

A possible further improvement to this would be to implement something like a quadtree, which would allow for quicker sampling and culling of unneeded areas.

Equation Simplification (Square-Root)

The original equation for a metaball was given as follows:

M(x,y) = R / sqrt( (x-x0)^2 + (y-y0)^2 )

The result is metaballs that are processed much faster, at the cost of using radius values for the metaballs which are much larger -- and so less intuitive to work with -- than before. A small trade-off for a significant speed gain.

More Optimizations and Techniques

The two above optimizations only scratch the surface of what is possible. There really is a lot that can be done from the original naive equation of a metaball to something that allows dozens of metaballs to be rendered quickly and efficiently.

In the References section are links to other resources/papers on metaballs and isosurfaces which explore other techniques and optimizations in regard to metaballs.

Conclusion