Head and cerebral structures (hidden) extracted from 150 MRI slices using marching cubes (about 150,000 triangles)
Marching cubes is a computer graphicsalgorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline,[1] for extracting a polygonal mesh of an isosurface from a three-dimensional discrete scalar field (the elements of which are sometimes called voxels). The applications of this algorithm are mainly concerned with medical visualizations such as CT and MRI scan data images, and special effects or 3-D modelling with what is usually called metaballs or other metasurfaces. The marching cubes algorithm is meant to be used for 3-D; the 2-D version of this algorithm is called the marching squares algorithm.
The algorithm was developed by William E. Lorensen (1946-2019) and Harvey E. Cline as a result of their research for General Electric. At General Electric they worked on a way to efficiently visualize data from CT and MRI devices.[2]
The premise of the algorithm is to divide the input volume into a discrete set of cubes. By assuming linear reconstruction filtering, each cube, which contains a piece of a given isosurface, can easily be identified because the sample values at the cube vertices must span the target isosurface value. For each cube containing a section of the isosurface, a triangular mesh that approximates the behavior of the trilinear interpolant in the interior cube is generated.
The first published version of the algorithm exploited rotational and reflective symmetry and also sign changes to build the table with 15 unique cases. However, due to the existence of ambiguities in the trilinear interpolant behavior in the cube faces and interior, the meshes extracted by the Marching Cubes presented discontinuities and topological issues. Given a cube of the grid, a face ambiguity occurs when its face vertices have alternating signs. That is, the vertices of one diagonal on this face are positive and the vertices on the other are negative. Observe that in this case, the signs of the face vertices are insufficient to determine the correct way to triangulate the isosurface. Similarly, an interior ambiguity occurs when the signs of the cube vertices are insufficient to determine the correct surface triangulation, i.e., when multiple triangulations are possible for the same cube configuration.
The popularity of the Marching Cubes and its widespread adoption resulted in several improvements in the algorithm to deal with the ambiguities and to correctly track the behavior of the interpolant. Durst[3] in 1988 was the first to note that the triangulation table proposed by Lorensen and Cline was incomplete, and that certain Marching Cubes cases allow multiple triangulations. Durst's 'additional reference' was to an earlier, more efficient (see de Araujo[4]) isosurface polygonization algorithm by Wyvill, Wyvill and McPheeters.[5] Later, Nielson and Hamann[6] in 1991 observed the existence of ambiguities in the interpolant behavior on the face of the cube. They proposed a test called Asymptotic Decider to correctly track the interpolant on the faces of the cube. In fact, as observed by Natarajan[7] in 1994, this ambiguity problem also occurs inside the cube. In his work, the author proposed a disambiguation test based on the interpolant critical points, and added four new cases to the Marching Cubes triangulation table (subcases of the cases 3, 4, 6 and 7). At this point, even with all the improvements proposed to the algorithm and its triangulation table, the meshes generated by the Marching Cubes still had topological incoherencies.
The Marching Cubes 33, proposed by Chernyaev[8] in 1995, is one of the first isosurface extraction algorithms intended to preserve the topology of the trilinear interpolant. In his work, Chernyaev extends to 33 the number of cases in the triangulation lookup table. He then proposes a different approach to solve the interior ambiguities, which is based on the Asymptotic Decider. Later, in 2003, Nielson[9] proved that Chernyaev's lookup table is complete and can represent all the possible behaviors of the trilinear interpolant, and Lewiner et al.[10] proposed an implementation to the algorithm. Also in 2003 Lopes and Brodlie[11] extended the tests proposed by Natarajan.[7] In 2013, Custodio et al.[12] noted and corrected algorithmic inaccuracies that compromised the topological correctness of the mesh generated by the Marching Cubes 33 algorithm proposed by Chernyaev.[8]
The originally published 15 cube configurations
Algorithm
The algorithm proceeds through the scalar field, taking eight neighbor locations at a time (thus forming an imaginary cube), then determining the polygon(s) needed to represent the part of the isosurface that passes through this cube. The individual polygons are then fused into the desired surface.
This is done by creating an index to a precalculated array of 256 possible polygon configurations (28=256) within the cube, by treating each of the 8 scalar values as a bit in an 8-bit integer. If the scalar's value is higher than the iso-value (i.e., it is inside the surface) then the appropriate bit is set to one, while if it is lower (outside), it is set to zero. The final value, after all eight scalars are checked, is the actual index to the polygon indices array.
Finally each vertex of the generated polygons is placed on the appropriate position along the cube's edge by linearly interpolating the two scalar values that are connected by that edge.
The gradient of the scalar field at each grid point is also the normal vector of a hypothetical isosurface passing from that point. Therefore, these normals may be interpolated along the edges of each cube to find the normals of the generated vertices which are essential for shading the resulting mesh with some illumination model.
Patent issues
An implementation of the marching cubes algorithm was patented as United States Patent 4,710,876.[2] Another similar algorithm was developed, called marching tetrahedra, in order to circumvent the patent as well as solve a minor ambiguity problem of marching cubes with some cube configurations. The patent expired in 2005, and it is now legal for the graphics community to use it without royalties since more than the 20 years have passed from its issue date (December 1, 1987[2]).
Sources
↑ Lorensen, William E.; Cline, Harvey E. (1 August 1987). "Marching cubes: A high resolution 3D surface construction algorithm". ACM SIGGRAPH Computer Graphics. 21 (4): 163–169. CiteSeerX10.1.1.545.613. doi:10.1145/37402.37422.
1 2 3 USgranted US4710876A,Cline, Harvey&Lorensen, William,"System and method for the display of surface structures contained within the interior region of a solid body",issued 1987-12-01
Lorensen, W. E.; Cline, Harvey E. (1987). "Marching cubes: A high resolution 3d surface construction algorithm". ACM Computer Graphics. 21 (4): 163–169. CiteSeerX10.1.1.545.613. doi:10.1145/37402.37422.
In mathematics and computational geometry, a Delaunay triangulation (DT), also known as a Delone triangulation, for a given set {pi} of discrete points pi in general position is a triangulation such that no point pi is inside the circumcircle of any triangle in the DT. Delaunay triangulations maximize the minimum of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.
Gouraud shading, named after Henri Gouraud, is an interpolation method used in computer graphics to produce continuous shading of surfaces represented by polygon meshes. In practice, Gouraud shading is most often used to achieve continuous lighting on triangle meshes by computing the lighting at the corners of each triangle and linearly interpolating the resulting colours for each pixel covered by the triangle. Gouraud first published the technique in 1971.
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.
Solid modeling is a consistent set of principles for mathematical and computer modeling of three-dimensional shapes (solids). Solid modeling is distinguished within the broader related areas of geometric modeling and computer graphics, such as 3D modeling, by its emphasis on physical fidelity. Together, the principles of geometric and solid modeling form the foundation of 3D-computer-aided design and in general support the creation, exchange, visualization, animation, interrogation, and annotation of digital models of physical objects.
Scientific visualization is an interdisciplinary branch of science concerned with the visualization of scientific phenomena. It is also considered a subset of computer graphics, a branch of computer science. The purpose of scientific visualization is to graphically illustrate scientific data to enable scientists to understand, illustrate, and glean insight from their data. Research into how people read and misread various types of visualizations is helping to determine what types and features of visualizations are most understandable and effective in conveying information.
In computational geometry, polygon triangulation is the partition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.
In scientific visualization and computer graphics, volume rendering is a set of techniques used to display a 2D projection of a 3D discretely sampled data set, typically a 3D scalar field.
In computer graphics, metaballs, also known as blobby objects, are organic-looking n-dimensional isosurfaces, characterised by their ability to meld together when in close proximity to create single, contiguous objects.
An isosurface is a three-dimensional analog of an isoline. It is a surface that represents points of a constant value within a volume of space; in other words, it is a level set of a continuous function whose domain is 3-space.
In 3D computer graphics and solid modeling, a polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object. The faces usually consist of triangles, quadrilaterals (quads), or other simple convex polygons (n-gons), since this simplifies rendering, but may also be more generally composed of concave polygons, or even polygons with holes.
In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of these subsets into well-shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams.
The Visualization Toolkit (VTK) is an open-source software system for 3D computer graphics, image processing and scientific visualization.
Marching tetrahedra is an algorithm in the field of computer graphics to render implicit surfaces. It clarifies a minor ambiguity problem of the marching cubes algorithm with some cube configurations. It was originally introduced in 1991.
Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric input domain. Mesh cells are used as discrete local approximations of the larger domain. Meshes are created by computer algorithms, often with human guidance through a GUI, depending on the complexity of the domain and the type of mesh desired. A typical goal is to create a mesh that accurately captures the input domain geometry, with high-quality (well-shaped) cells, and without so many cells as to make subsequent calculations intractable. The mesh should also be fine in areas that are important for the subsequent calculations.
In computer graphics, marching squares is an algorithm that generates contours for a two-dimensional scalar field. A similar method can be used to contour 2D triangle meshes.
In computer graphics, a nonobtuse triangle mesh is a polygon mesh composed of a set of triangles in which no angle is obtuse, i.e. greater than 90°. If each (triangle) face angle is strictly less than 90°, then the triangle mesh is said to be acute. Every polygon with sides has a nonobtuse triangulation with triangles, allowing some triangle vertices to be added to the sides and interior of the polygon. These nonobtuse triangulations can be further refined to produce acute triangulations with triangles.
In 3D computer graphics, 3D modeling is the process of developing a mathematical coordinate-based representation of any surface of an object in three dimensions via specialized software by manipulating edges, vertices, and polygons in a simulated 3D space.
In scientific visualization the asymptotic decider is an algorithm developed by Nielson and Hamann in 1991 that creates isosurfaces from a given scalar field. It was proposed as an improvement to the marching cubes algorithm, which can produce some "bad" topology, but can also be considered an algorithm in its own right.
In computer graphics, tessellation is the dividing of datasets of polygons presenting objects in a scene into suitable structures for rendering. Especially for real-time rendering, data is tessellated into triangles, for example in OpenGL 4.0 and Direct3D 11.
Triangulation of a surface means
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
