Marching cubes

Model built from 150 layers with MRI using the marching cubes algorithm. Below the surface are about 150,000 polygons and hidden objects. The mesh size is 64 × 64 × 150 voxels encoded with 8 bits. To smooth the surface of the model, pre-processing was applied. The “hole” in the temple area is a consequence of the piercing of the subject.

Marching cubes (from English - “walking cubes”) is an algorithm in computer graphics , first proposed in 1987 at the SIGGRAPH conference by William Lorensen and Harvey Klein ^[1] , for processing a polygonal mesh of a three-dimensional scalar field (often called a voxel mesh).

A similar algorithm on the plane is called marching squares .

Content

Principle of Operation

The algorithm runs through a scalar field, at each iteration it scans 8 adjacent positions (vertices of a cube parallel to the coordinate axes) and determines the polygons necessary to represent the part of the isosurface passing through this cube. Next, polygons forming a given isosurface are displayed.

Since the algorithm selects polygons based only on the position of the vertices of the cube relative to the isosurface, a total of 256 ( $2^{8}=256$ ${\ displaystyle 2 ^ {8} = 256}$ ) possible polygon configurations that can be calculated in advance and stored in an array. Therefore, each cube can be represented by an eight-bit number, assigning to each vertex 1 if the field value at the point is greater than on the isosurface, and 0 otherwise. The resulting number is used as the index of the array element that stores the polygon configurations. Finally, each vertex of the generated polygon is placed in a suitable position on the edge of the cube on which it originally lay. The position is calculated by linear interpolation of the scalar field values at the ends of the edges.

15 different cube configurations.

A pre-calculated array of 256 polygon configurations can be obtained by turning and reflections of 15 different cube configurations. However, using only 15 basic configurations does not guarantee a closed surface. Basic configurations devoid of this drawback can be found in the specialized literature. .

The gradient of the scalar field at each point of the grid is also a normal vector to the assumed isosurface passing through this point. Therefore, it is possible to interpolate these normals along the edges of each cube in order to find the normals of the generated vertices, for the correct display of the model when using lighting.

This algorithm is widely used in medicine, for example, in computer and magnetic resonance imaging , as well as for three-dimensional modeling of metaspheres or other metasurfaces.

Patent

The Marching Cubes algorithm was the first example in the field of computer graphics that provoked a scandal in the field of software patenting . It was patented despite the relative obviousness of solving the problem of surface generation. Later, a similar algorithm was developed, called marching tetrahedrons , which, in order to bypass the patent, uses tetrahedrons instead of cubes. The patent expired in 2005, now the algorithm can be freely used. (Patent of June 5, 1985 ^[2] ).

Sources

↑ William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics , Vol. 21, Nr. July 4, 1987
↑ Marching Cubes, US Patent Office entry

External links

Overview and source code by Paul Bourke
GameDev overview by Matthew Ward of Worcester Polytechnic Institute
Introductory description with additional graphics
Some of the early history of Marching Cubes

[Originalpaper-1] William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics , Vol. 21, Nr. July 4, 1987

[2] Marching Cubes, US Patent Office entry