Contents

Introduction

Walking on Eggshells

Goopy Games

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).

Figure 3a. One vertex inside and
the rest outside create one triangle.

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.

Figure 3b. One vertex outside and the rest inside also make one triangle.

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:

  1. One vertex is inside the surface and the rest outside.
  2. One vertex outside the surface and the rest inside.
  3. Two vertices outside and two inside.

Figure 3c. Two vertices outside and two inside create two triangles.

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.

________________________________________________________

Goopy Games