The Blobs Go Marching Two by Two

This may come as a shock to some, but the world is not made up of corridors composed of completely planar surfaces. We live in a wildly organic place. Hills roll, muscles bulge and fountains splash. The world around you is filled with organic shapes which cannot easily be created out of triangles.

In fact, many of these objects are not even just lying around looking all organic. They slop, splash, waddle, and plop about you all the time. Many shapes around you are even in motion. These objects change shape effortlessly as you game artists crumple under the pressure of having to model such phenomena. When was the last time you saw a nice splashing fountain in a game, anyway?

Animators have faced the challenge of visually creating the organic world we live in for some time now. To help them out, commercial modeling packages have provided the artist with tools for creating organic shapes. One of the methods for creating organic objects is through the use of blobby balls that can be combined together to form a clay-like sculpture. The commercial animation package developers have realized the usefulness of this technique and coined all sorts of proprietary terms for their version. You may have seen ads for meta-balls, meta-clay, blob-modeling, and various other ways of combining the term "meta" with some form of goop.

To create an object from this meta-goop, an artist drags around primitive elements, usually spheres, which represent the rough shape of the object. Each of these elements has a center position and several parameters associated with it. These parameters define how the element will interact with the particles and world surrounding it. You can see an example structure for a meta-goop particle in Listing 1.

Listing 1. A Meta-goop Particle.

typedel tMetaGoop
{
Vector position;
float radiusSquared;
float strength;
};

The position describes the center of the element. I also need to keep track of the radius of influence of the element (actually squared so I save some math later) and the strength of the element. This strength parameter defines how the element will affect the space surrounding it.

The elements interact with each other by creating an energy
field around them. This is similar to the way planets create a gravitational field for a solar system. It is possible to evaluate the energy of the system at an arbitrary point in space. The formula to determine the amount of energy that an element contributes to the point is given as:

distance = squaredDistance(&goop-> position,&testPosition);
if (distance < goop->radiusSquared)
{
falloff = 1.0f - (distance/goop-> radiusSquared);
fieldStrength += goop->strength * falloff * falloff;
}

By running this formula over all the elements in your system, you get the exact field strength for that position. The energy field creates some interesting data but is not much of an object. What I want to create are particles that will visually grow together as they get closer. You can see an example in Figure 1. In order to create an object that will show this visual aspect of the energy field, it is necessary to define a value that will represent the outer shell of the object - the threshold.

The energy field varies in strength from zero on up at any position you may evaluate. In fact, there is nothing to keep you from defining negative strength for an element, creating negative regions, or holes, in the energy field. This is useful for effects such as denting and the like. To define the surface of the object in the field, I can set an arbitrary threshold giving the object its final shape.

The threshold value defines the boundary between the area inside and the area outside the shell of the object. Figure 2 shows how an example threshold value creates a boundary in a 2D energy field created by three meta-goop entities.

By adjusting this threshold value for the energy field, as well as adjusting the strength, position, and effective radius of individual entities, a great variety of objects can be created. But I still need to talk about how.

Walking on Eggshells

By creating a few meta-goop particles and setting some values for them, I have created my meta-goop system. Run that goop through a function that evaluates the energy field, apply a surface threshold, and I have the surface shell for the meta-goop object defined. But the problem remains, how do I draw it?

I could step across the entire 3D space defined by entity radii and evaluate the field. Anywhere the returned value is equal to the threshold, I could draw a solid cube the size of the steps taken. This sounds pretty good. Sounds like it would work. Actually, it sounds kind of familiar. It sounds kind of like volume rendering of voxels for applications such as viewing CAT scan data. In fact, that is exactly what I would be doing if I took this approach.

However, rendering the energy field this way can lead to pretty chunky looking images unless the step size is fairly small. This is because the energy field is continuous over the entire range of the model world. However, the steps I took walking across the field are in discrete steps. If the steps are too big, the image can look chunky. This is analogous to drawing a line on a computer graphics screen. If the resolution of the screen is too low, the line can look very jagged. This unfortunate condition is known as "the jaggies" and requires some form of smoothing or antialiasing to make the lines look better.

Unfortunately, decreasing the step size in my energy field will greatly increase the amount of calculations that must be made. Therefore, it is necessary to find a way to smooth out the voxel image - sort of antialias the meta-surface.

CAT Scans and Game Development

Fortunately for me, the graphic visualization and medical imaging industries have been dealing with this issue for quite some time. Wyvill and McPheeters in 1986 and Lorenson and Cline in 1987 independently developed a system called "marching cubes" which enables you to render a polygonal approximation of a voxel field. One possible unfortunate circumstance is that this algorithm may be tainted by a software patent and I am investigating how this will affect the issue (see the section titled The Marching Cubes Patent Question at the end of this article).

That aside, the way marching cubes works is pretty simple. Divide the region you wish to render into a regular 3D grid. Evaluate the energy field at each position on this grid. Now, consider the grid cube by cube. If the energy function at all eight corners of the cube are less than the threshold level, the entire cube is outside the meta-object and the cube can be ignored completely. Likewise, if the corners are all greater than the threshold, the cube is completely inside the object and can also be ignored. The only cubes that need further consideration are those that have corners both inside and outside the meta-object. These cubes are on the object surface and will be part of the final render.

A cube has eight vertices. That means that there are 256 possible combinations of how a surface can intersect with the cube. If you consider symmetry, the number of possibilities reduces to 14. Much of the literature on surface generation using the marching cubes routine deals with optimizing for those 14 special cases.

However, there is an easier way I have seen termed "marching pyramid." If you consider a cube of eight vertices as being composed of five tetrahedrons with four vertices each, the problem is greatly simplified. There are now only three very simple cases to deal with. The cases are the following:

That is all I need to consider. In cases 1 and 2, a single triangle is generated. In case 3, two triangles are generated. You can see the three cases represented in Figures 3a-c.

Once the vertices of the pyramid are classified, the actual vertex positions of the triangles created are obtained by linear interpolation of the corner values along each edge. You can see the code for this in Listing 2. As there are five tetrahedrons making up each cube, the number of triangles generated with the marching pyramid technique is greater than what would be created from simple marching cubes. However, the classification and creation step is much simpler and the resultant surface is a more accurate approximation of the surface. On current 3D graphics hardware, the extra triangles shouldn't affect performance too much.

Listing 2. Finding the Intersection Point.

void FindIntersection( tVector *a, tVector *b,
float aVal, float bVal,
float thresh, tVector *result)
{
/// Local Variables ////////////////////////////////////
tVector diff;
float ratio;
////////////////////////////////////////////////////////
VectorSubtract( a, b, &diff);
ratio = (thresh - aVal) / (bVal - aVal);
VectorMultiply( &diff, ratio);
VectorSubtract(a,&diff,result);
if (aVal > bVal)
}

Goopy Games

I hope it is now clear that these meta-goop techniques can be used to create interesting organic objects suitable for real-time display. However, there are several aspects that actually make them ideal for use in games. For one, they are procedurally created. Complex structures can be generated from simple data structures consisting of the location and attributes of each particle in the system. There is no need to store a complete mesh.

In addition, the meta-object can be tessellated to different levels depending on the initial grid size of the voxel space. This gives the game a dynamic level-of-detail component that is needed in these days of varying hardware performance.

You can attempt generation of the objects in real time through efficient optimization of the surface approximation routine. You could also simply decide to create the objects at load time and display them as traditional polygonal objects during the actual game, or evaluate the mesh only when the state of the goop elements changes. This kind of flexibility makes for easy integration into a variety of applications.

I didn't even discuss how the surfaces could be rendered. One obvious choice would be to apply environment-mapping techniques to create the chrome creature from Terminator 2. Likewise, you could apply bump-mapping techniques to bring a water creature to life. I think an interesting application would be to combine meta-surface techniques to a particle system like the one I described last summer ("Spray in Your Face," Game Developer, July 1998).

For more fun, get my demo application off the Game Developer web site (http://www.gdmag.com). This will allow you to play with the creation of meta-goop and start spreading some slop around your games.

The Marching Cubes Patent Question

As many of you who have met me and heard me rant on the topic know, I believe algorithmic software patents are totally wrong. I feel they completely halt continued development down interesting research pathways by shrouding a topic with legal pitfalls. Graphics researchers create progress by building on the work done by others before them. I like to imagine the state of the industry if Bresenham had patented his method for drawing a line on a graphic display and then charged a licensing fee for every line drawn.

The topic of volume rendering is an interesting case in point. As an obvious next step in the visualization of volume data, it was reported by researchers in several publications. However, General Electric apparently owns a patent on the technique via the Lorenson and Cline implementation (U.S. patent #4,710,876). As an actual apparatus to display medical imaging data, I can understand it. However, the patenting of a "method for displaying three-dimensional surface images" seems pretty broad to me.

I have been told by someone via e-mail that GE aggressively enforces this patent. However, it is not clear to me how this would apply to the rendering of an isosurface in a game. Does this mean that any modeling program using these techniques must pay a license to GE? If I create a game using a derivative of marching cubes and it is a big hit, am I going to receive a stealth patent letter in the mail demanding a percentage? How derivative does it need to be? The prior art on this topic seems limitless, but what can I use as a reference and still be safe?

With the record number of software patents being filed, this is going to become an increasingly difficult issue for game developers in the future. I am actively researching the issue and hope to report on the results in a later column. Anyone with information on the topic, please let me know. In the meantime, always document your research from public journals as best you can. Ignorance is not bliss in this situation.

For Further Info:

Greene, Ned. "Voxel Space Automata: Modeling with Stochastic Growth Processes in Voxel Space (Proceedings of Siggraph 89)." Computer Graphics, Vol. 23, No. 4 (Aug. 1989): pp. 175-184.

Lorensen, William, and Harvey Cline. "Marching Cubes: A High Resolution 3D Surface Construction Algorithm (Proceedings of Siggraph 87)." Computer Graphics Vol. 21, No. 4 (Aug. 1987): pp. 163-169.

Watt, Alan, and Mark Watt. Advanced Animation and Rendering Techniques. Reading, Mass: Addison-Wesley, 1993.

Wyvill, Geoff, Craig McPheeters, and Brian Wyvill. "Data Structure for Soft Objects." The Visual Computer Vol. 2, No. 4 (Aug. 1986): pp. 227-234.

Web Resources

http://www.students.cs.ruu.nl/people/jedik/Methods/Surface_
fitting/Marching_cubes.htm

http://www.swin.edu.au/astronomy/pbourke/modelling

When not splashing gloop around his kitchen floor, Jeff can be found creating real-time graphics applications at Darwin 3D. Fling some bits of your own his way at [email protected].