Marching Cubes

Marching Cubes is an algorithm for computing isosurfaces in 3D computer graphics. He approaches a Voxelgrafik on by a polygon graphics.

• 4.1 octree
• 4.2 Approximation by discretization

Development of the algorithm

Marching Cubes was introduced in 1987 by William E. Lorensen and Harvey E. Cline as a result of research work for the research department of the General Electric Company in the journal Computer Graphics. Lorensen and Cline were concerned with the efficient visualization of image data imaging methods such as computed tomography, magnetic resonance imaging and single photon emission computed tomography.

Importance of the algorithm

In 3D computer graphics, there are various methods to model three-dimensional objects. One is the modeling as a polygonal surface ( " wireframe " ): It adds polygonal surfaces - usually triangles - each other so that they mimic the surface of the object. These models can be implemented very quickly and easily in pictures, the memory requirement of a model is relatively small and numerous refinements are very realistic images possible. On the other hand, it is almost impossible to model in this way a medium such as fog, which has no clear-cut surface.

Another method is to model a voxel dataset: Periodically, the density of the material is read at a single point from the object; the result is a three-dimensional cubic grid of voxels. Imaging systems such as computer tomography inherently produce such models. These voxel models can quite easily be converted into images that also look very realistic and detailed. However, the model requires a lot of memory - in the order of several hundreds of megabytes to several gigabytes - and the visualization takes considerably longer than that of a polygonal surface model of comparable size. In addition, manipulation ( for example, the deformation of an object ) is significantly more difficult, sometimes even impossible.

Marching Cubes is the first time allowed to approach impractical volume models through viable polygonal surface models, in order to subsequently visualize efficiently. The algorithm thus satisfied the desire of Radiology for a procedure, data imaging systems such as computed tomography quickly and meaningfully depict. Even today, Marching cubes is an efficient transformation algorithm in use. Although the volume graphics has made progress in the meantime and found by 3D textures input into the computer graphics field, but currently there is no hardware that accelerates volume rendering in a similar way as do graphics processors with triangles.

The algorithm

The idea of marching cubes is to decompose the given voxel model of an object initially in small cubes ( cubes ) and then from a cube " march " to the next and to determine how the surface of the object to the respective cube cuts. To a user-selected threshold value is used to determine which parts of the individual dice are within and outside of which the final object. By changing this as " density " interpreted limit the user to determine which areas of the object are represented and which are not.

Input

The algorithm processes the following input parameters:

• Voxelgrafik. The volume model of the object.

• Density value ρ. This parameter is used to control which parts of the model as a solid and which are interpreted as transparent.

Data Structures

The following data structures are used or generated by the algorithm, but not passed as input parameters:

• Triangle Lookup Table ( TLT). There are 256 ways in which an arbitrarily shaped surface can split a Marching Cubes cubes in indoor and outdoor areas; because according to combinatorics, there are 28 = 256 ways to divide the eight corners of a Marching Cubes cube in two volumes "inside" and " outside ". The Triangle Lookup Table contains all of these possibilities; while there are actually only 15 distinct entries due to the symmetry of the cases.

• D. The algorithm here a list of all triangles that are required to approximate the input Voxelgrafik by a polygon graphics.
• N. In addition to the triangle list the algorithm creates a list of all unit normal of the nodes of the triangles.

Processing

Output

• D, the list of all triangle nodes generated.
• N, the list of all unit normal to the triangle nodes.

Improvements

The algorithm presented above for Marching Cubes is very rudimentary. He uses, for example, does not exclude that information already computed can be reused: parts two adjacent cubes one edge so it lies node must be interpolated only once; the neighbor can simply take over the already discovered nodes.

Since the running time of the algorithm depends only on the number of observed cubes, is a reduction of this number, the greatest potential for savings. Other optimization approaches therefore attempt away before marching cubes Pass those cubes from the amount of data that already come into contact with the isosurface. These are those cubes that are completely within or completely outside the object.

Octree

A 1992 proposed by Wilhelm / van Gelder method is to store the volume in an octree. In an octree normally each cube of voxels is divided into eight sub-cubes. For each cube, the lowest and the highest value is now stored, which can be found in it. In a cube If both values ​​are equal, so he will not further subdivided. The result is a hierarchy of decreasing dice for each range of values ​​it is well known. By traversing this hierarchy can now be sort out those cubes whose minimum is above or below the maximum of the iso- threshold.

The method has the disadvantages that each time the Isowertes the hierarchy will run through completely new and that in realistic data sets which are normally centered, can usually be ignored only at the lower levels cubes.

Approximation by discretization

This is a simplification of the Marching Cube algorithm referred to in the above description of the algorithm of interpolation Isoflächenschnittpunkte omitted. Vertices of the triangles generated by the algorithm are then only the centers of the twelve edges of the cube and its center. Also, the surface normals must then no longer be interpolated, but can also be stored in a lookup table. An advantage of this approximation is that only integer calculations must be performed. You also get a lot of coplanar triangular faces, which is the number of the resulting triangular faces substantially reduced ..

Software Patents

The MC algorithm is an example of the impact of software patents. Since the algorithm was patented, it could not be used for many years without having to pay fees to the developer. Therefore, it was developed as an alternative of the marching tetrahedron, which divided the voxel cube into tetrahedra, and otherwise work the same. The issued patent U.S. 4,710,876 filed on June 5, 1985 and was in the United States 20 years.