Marching Tetrahedrons
Encyclopedia
Marching tetrahedrons is an algorithm in the field of computer graphics
to render implicit surfaces. It clarifies a minor ambiguity problem of marching cubes
with some cube configurations.
Since more than 20 years have passed from the filing date of the marching cubes
(June 5, 1985), the original algorithm can be used again, adding only the minor modification to circumvent the aforementioned ambiguity in some configurations.
In marching tetrahedrons, each cube is split into six irregular tetrahedron
s by cutting the cube in half three times, cutting diagonally through each of the three pairs of opposing faces. In this way, the tetrahedrons all share one of the main diagonals of the cube. Instead of the twelve edges of the cube, we now have nineteen edges: the original twelve, six face diagonals, and the main diagonal. Just like in marching cubes, the intersections of these edges with the isosurface
are approximated by linearly interpolating the values at the grid points.
Adjacent cubes share all edges in the connecting face, including the same diagonal. This is an important property to prevent cracks in the rendered surface, because interpolation of the two distinct diagonals of a face usually gives slightly different intersection points. An added benefit is that up to five computed intersection points can be reused when handling the neighbor cube. This includes the computed surface normal
s and other graphics attributes at the intersection points.
Each tetrahedron has sixteen possible configurations, falling into three classes: no intersection, intersection in one triangle and intersection in two (adjacent) triangles. It is straightforward to enumerate all sixteen configurations and map them to vertex index lists defining the appropriate triangle strip
s.
The number of configurations, determining the size of the commonly used lookup table
s, is much smaller, since only four rather than eight separate vertices are involved per tetrahedron. There are six tetrahedrons to process instead of one single cube. The process is unambiguous, so no additional ambiguity handling is necessary.
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
to render implicit surfaces. It clarifies a minor ambiguity problem of marching cubes
Marching cubes
Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional scalar field...
with some cube configurations.
Since more than 20 years have passed from the filing date of the marching cubes
Marching cubes
Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional scalar field...
(June 5, 1985), the original algorithm can be used again, adding only the minor modification to circumvent the aforementioned ambiguity in some configurations.
In marching tetrahedrons, each cube is split into six irregular tetrahedron
Tetrahedron
In geometry, a tetrahedron is a polyhedron composed of four triangular faces, three of which meet at each vertex. A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids...
s by cutting the cube in half three times, cutting diagonally through each of the three pairs of opposing faces. In this way, the tetrahedrons all share one of the main diagonals of the cube. Instead of the twelve edges of the cube, we now have nineteen edges: the original twelve, six face diagonals, and the main diagonal. Just like in marching cubes, the intersections of these edges with the isosurface
Isosurface
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 3D-space.Isosurfaces are normally displayed using computer graphics, and are...
are approximated by linearly interpolating the values at the grid points.
Adjacent cubes share all edges in the connecting face, including the same diagonal. This is an important property to prevent cracks in the rendered surface, because interpolation of the two distinct diagonals of a face usually gives slightly different intersection points. An added benefit is that up to five computed intersection points can be reused when handling the neighbor cube. This includes the computed surface normal
Surface normal
A surface normal, or simply normal, to a flat surface is a vector that is perpendicular to that surface. A normal to a non-flat surface at a point P on the surface is a vector perpendicular to the tangent plane to that surface at P. The word "normal" is also used as an adjective: a line normal to a...
s and other graphics attributes at the intersection points.
Each tetrahedron has sixteen possible configurations, falling into three classes: no intersection, intersection in one triangle and intersection in two (adjacent) triangles. It is straightforward to enumerate all sixteen configurations and map them to vertex index lists defining the appropriate triangle strip
Triangle Strip
A triangle strip is a series of connected triangles, sharing vertices, allowing for faster rendering and more efficient memory usage for computer graphics. They are optimized on most graphics cards, making them the most efficient way of describing an object. There are two primary reasons to use...
s.
Comparison
Marching tetrahedrons computes up to nineteen edge intersections per cube, where marching cubes only requires twelve. Only one of these intersections cannot be shared with an adjacent cube (the one on the main diagonal), but sharing on all faces of the cube complicates the algorithm and increases memory requirements considerably. On the other hand, the additional intersections provide for a slightly better sampling resolution.The number of configurations, determining the size of the commonly used lookup table
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
s, is much smaller, since only four rather than eight separate vertices are involved per tetrahedron. There are six tetrahedrons to process instead of one single cube. The process is unambiguous, so no additional ambiguity handling is necessary.