Overview of Marching Cubes Algorithm

Overview of the Marching Cubes Algorithm

Matthew Ward, WPI CS Department

Summary

Marching Cubes is an algorithm for rendering isosurfaces in volumetric
data. The basic notion is that we can define a voxel(cube) by the pixel
values at the eight corners of the cube. If one or more pixels of a cube
have values less than the user-specified isovalue, and one or more have
values greater than this value, we know the voxel must contribute some
component of the isosurface. By determining which edges of the cube are
intersected by the isosurface, we can create triangular patches which
divide the cube between regions within the isosurface and regions outside.
By connecting the patches from all cubes on the isosurface boundary, we get
a surface representation.

Algorithm Details

There are two major components of this algorithm. The first is deciding how
to define the section or sections of surface which chop up an individual
cube. If we classify each corner as either being below or above the
isovalue, there are 256 possible configurations of corner classifications.
Two of these are trivial; where all points are inside or outside the cube
does not contribute to the isosurface. For all other configurations we need
to determine where, along each cube edge, the isosurface crosses, and use
these edge intersection points to create one or more triangular patches for
the isosurface.

If you account for symmetries, there are really only 14 unique
configurations in the remaining 254 possibilities. When there is only one
corner less than the isovalue, this forms a single triangle which
intersects the edges which meet at this corner, with the patch normal
facing away from the corner. Obviously there are 8 related configurations
of this sort (e.g. for configuration 2 - you may need to tweak the colormap
to see the plane between the spheres/pixels). By reversing the normal we
get 8 configurations which have 7 corners less than the isovalue. We don't
consider these really unique, however. For configurations with 2 corners
less than the isovalue, there are 3 unique configurations (e.g. for
configuration 12), depending on whether the corners belong to the same
edge, belong the same face of the cube, or are diagonally positioned
relative to each other. For configurations with 3 corners less than the
isovalue there are again 3 unique configurations (e.g. for configuration
14), depending on whether there are 0, 1, or 2 shared edges (2 shared edges
gives you an 'L' shape). There are 7 unique configurations when you have 4
corners less than the isovalue, depending on whether there are 0, 2, 3 (3
variants on this one), or 4 shared edges (e.g. for configuration 30 - again
you may need to tweak the colors to see the triangle for the isolated (far)
inside sphere/pixel).

Each of the non-trivial configurations results in between 1 and 4 triangles
being added to the isosurface. The actual vertices themselves can be
computed by interpolation along edges, or, as I did, default their location
to the middle of the edge. The interpolated locations will obviously give
you better shading calculations and smoother surfaces.

Now that we can create surface patches for a single voxel, we can apply
this process to the entire volume. We can process the volume in slabs,
where each slab is comprised of 2 slices of pixels. We can either treat
each cube independently, or we can propogate edge intersections between
cubes which share the edges. This sharing can also be done between adjacent
slabs, which increases storage and complexity a bit, but saves in
computation time. The sharing of edge/vertex information also results in a
more compact model, and one that is more amenable to interpolated shading.

Implementation

Students in CS563 can find my implementation of this algorithm in
/cs/courses/cs563/software/march_cubes [NOTE TO OTHERS: THIS CODE IS NOT
AVAILABLE FOR GENERAL DISTRIBUTION - I WILL IGNORE ALL REQUESTS FOR COPIES
OF THE CODE]. It is loosely based on the description presented in the text
by Watt and Watt (see below). The file cube.new contains 1 row of
information for each of 256 configurations. The first number gives the
configuration ID, which is simply an 8-bit number based on which of 8
corners are inside the isosurface. The numbers after that are triplets,
identifying the edges which contain the vertices for each triangle patch to
be used for that configuration (terminated by a -1). The file hydrogen.dat
is a sample volume file which is distributed with AVS. The first three
bytes give the dimensions, and the rest is just row-major, 1 byte per data
point.

The program mcube.c accepts a data file and an isovalue, reads the
configuration table, and "marches" through the volume, classifying cubes
and outputing triangles as it goes (each row of output is the number 3,
followed by 3 sets of 3-D floating point coordinates). No attempt is made
to share vertices or edges between triangles, which leads to pretty large
output files. The program tri_inventor.c takes this output and creates a
scene graph that can be imported into IRIS Inventor or Open Inventor. This
can make a REALY large file, based on your data set and isovalue (press
here for some sample output).

Problems and Alternatives

One obvious problem with marching cubes is the amount of memory needed to
store the resulting surface. As each boundary cube can generate up to 4
sub-pixel facets, the result is quite large. We can reduce this somewhat by
sharing vertices and edges, or even merging coplanar patches into larger
facets. Another solution might be to try and fit parametric surfaces to
groups of boundary points, though this may be difficult for complex surface
geometries.

Another problem arises when you don't have a filled space of voxels.
Depending on how the volume data was acquired there may be voids which need
to be assigned values or circumnavigated in the surface generation
algorithm. Any interpolated value used may reduce the validity of the
resulting surface.

A final alternate strategy would be to ray trace the original volume data,
which may be the topic of a future presentation.

References

Lorensen, W.E. and Cline, H.E., "Marching Cubes: a high resolution 3D
surface reconstruction algorithm," Computer Graphics, Vol. 21, No. 4, pp
163-169 (Proc. of SIGGRAPH), 1987. Watt, Alan, and Watt, Mark, Advanced
Animation and Rendering Techniques, Addison-Wesley, 1992.

matt@owl.WPI.EDU
Discuss this article in the forums
Date this article was posted to GameDev.net: 7/16/1999
(Note that this date does not necessarily correspond to the date the article was written)
See Also:
Miscellaneous