Introduction

Posing the Question

In the history of game development, there has always been a "standard" means to represent data in the game world.

During the 2D era the world and its components were shown by using sprites -- collections of pixels to form an image. As the industry moved into 3 dimensions, this standard-format became the 3D model. Models representing the world, characters, and objects as collections of vertices in 3D space.

Both (arguably) represent the most basic element that can be used in the given number of dimensions, but still allow for the greatest amount of speed. Making things run as fast as possible has always been a critical element in the game industry.

But what about other data representations? Aren't there other means of storing information about a given "thing" in the game world aside from sprites and models? They exist, but generally just don't succeed in quite reaching into the industry of game development. What if some of these representations aren't quite as infeasible as people think?

Overview

The goals of this article are three-fold:

• To discuss the history, concept, and implementation of metaballs and isosurfaces.
• To examine the current applications of isosurfaces in the game- and graphics industries, and their possible future.
• To investigate the performance issues involved with isosurfaces, and some existing optimizations/approximations.

What are Metaballs?

Metaballs largely made their introduction in the 1990's through the demoscene: groups of enthusiastic programmers and artists that aimed to create graphical/musical effects that pushed the known limits of older hardware, such as the Commodore 64 and Amiga. The goal of demosceners was to create audio-visual effects in real-time that would impress viewers and confound other demoscene programmers with how the effect was implemented.

One such effect that gained popularity was metaballs: squishy circular objects that had an organic look and feel to them.

(Metaballs. Note how they have a tendency to "merge" with nearby metaballs.)

The main allure to metaballs is their tendency to 'meld' into other metaballs that are nearby, thus creating smoothly formed shapes. Well, how are these objects represented, and why aren't they being used in real-time more often? To discuss this, we will have to talk about the subset of which metaballs is a member: isosurfaces.

What is an Isosurface?

This article will focus entirely on 2D metaballs and isosurfaces. Although an isosurface generally refers to 3D space, it will be seen that it is very easily adapted to 2 dimensions.

Simply put for our purposes, an isosurface is a surface created by applying one or more functions -- whose domain is the entire real 2D plane – onto the screen (or game map). An isosurface is a level set of this function. For those of you who are not already familiar with the subject, just what does this mean?

Pretend we had a function over the 2D plane (read: a function that has a certain resulting value, given any X and Y) that looked like this:

F(x,y) = (x - x0)^2 + (y - y0)^2

(An image whereas pixel brightness corresponds to distance from the centre of the screen.)

From this it is clear that any given X and Y coordinate will have a value corresponding to it, with said value being larger and larger as it gets farther from the centre (x0,y0). It's sort of pretty, but how is this useful? It's not really an isosurface after all.

Like we said above, an isosurface is a level set of this function. What the heck does that mean?

What it means is that the surface is composed of all points on our screen/world that are equal to a certain constant value. To make that a little more clear, let's look at a modification to our previous function:

F(x,y) = (x - x0)^2 + (y - y0)^2 = R^2

(Circle generated by a metaball-like function.)

A plain circle, nothing more. We said that an isosurface is made up of all of the points that are equal to a certain value, across the 2D plane. Our circle is a simple isosurface which is composed of just that: every single point in the 2D plane has a distance of exactly R units from the centre of the circle. After all of that talk of 'level sets', it turns out that these isosurfaces really aren't that complicated after all.

In fact, breaking down the word "isosurface" you see "iso", meaning "the same", and "surface", referring to something that is solid and flat. By taking the set of all points in the 2D plane that exactly meet the radius of the circle, we see just that: a surface created by all of the values in the X and Y that meet the same value required by the function. Hardly rocket science!

But surely you're now saying, "If an isosurface is just something simple like a circle, then how do we use this information to make something that looks neat, like that 3D image was shown?".

Let's take a look at a simple implementation for Metaballs.

Creating Meta-Things