|
Figure 1
|
Marching Cubes Algorithm
Marching Cubes Algorithm (MCA) is used to render isosurfaces in volumetric data [1-2]. The basic notion in MCA consists in that one can define a voxel as the sequence of the pixel values at the eight corners of a 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, one knows the voxel must contribute some component of the isosurface. By determining which edges of the cube are intersected by the isosurface, one 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, a surface representation is obtained.
Algorithm Details
There are two major components of MCA. The first consists into decide how to define the section or sections of surface which chop up an individual cube. If each corner is classified as either being below or above the isovalue, there are 256 possible configurations of corner classifications. However if one accounts for symmetry, only 15 configurations remain, see Figure 1. Two of these are trivial: all points are inside or outside the cube and do not contribute to the isosurface. For all configurations it is needed to determine where, along each cube edge, the isosurface crosses, and these edge intersection points can be used to create one or more triangular patches for the isosurface.
|
Figure 1
|
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. There are 8 related configurations of this sort. By reversing the normal one gets 8 configurations which have 7 corners less than the isovalue. However, these are not considered really unique. For configurations with 2 corners less than the isovalue, there are 3 unique configurations, 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, depending on whether there are 0, 1, or 2 shared edges. 2 shared edges gives an 'L' shape. There are 7 unique configurations when 4 corners less than the isovalue are present, depending on whether there are 0, 2, 3 (3 variants on this one), or 4 shared edges.
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, default their location to the middle of the edge. The interpolated locations will obviously provide better shading calculations and smoother surfaces.
When surface patches can be created for a single voxel, this process can be applied to the entire volume. One can process the volume in slabs, where each slab is comprised between 2 slices of pixels. Each cube can be treated either independently, or edge intersections between cubes which share the edges can be propagated. This sharing can also be done between adjacent slabs, increasing storage and complexity a bit, but saving computation time. The sharing of edge/vertex information also results in a more compact model, and one that is more amenable to interpolated shading.
Fortran 90 procedure:
The following F90 procedure, which is ready to compile, needs a file with the proper format it order to perform the surface reconstruction.
This file does not need any proper name, as you will be prompted to write it. The essential parts of the file, which must be in a single line each one are:
Example:
|
125 2.00 2.00 2.00 1.000 quinina1.txt 0.2087D+00 0.1630D+01 ... 0.3110D+00 0.1048D+01 0.1974D+01 |
Another file is also requested to be in the same directory, FULLASAC.TXT, which contains the number of files to create, the set of isovalues and the names of the files.
Example:
|
4 0.10,name1.msh 0.20,name2.msh 0.30,name3.msh 0.40,name4.msh |
The output files, named: name1.msh, name2.msh, name3.msh and name4.msh with the following format, which is the one used by the GiD program [3].
More Information:
Lorensen W.E. and Cline H.E., Computer Graphics, 1987, 21, 163.
Other Web Sites:
