Marching tetrahedrons

Marching tetrahedrons
A cube divided into six tetrahedrons, with one tetrahedron shaded

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 tetrahedrons 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 normals 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 strips.

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 tables, 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.

See also

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Marching Cubes — Tête et structures cérébrales (cachées) obtenues par l application des marching cubes sur 150 tranches provenant d un IRM (env. 150 000 triangles) Les « marching cubes » désignent un algorithme d infographie publié à la conférence… …   Wikipédia en Français

  • Marching cubes — Head and cerebral structures (hidden) extracted from 150 MRI slices using marching cubes (about 150,000 triangles) Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline,[1] …   Wikipedia

  • Marching Cube — Polygonmodell eines Kopfes, der mittels Marching Cube aus 150 MRT Schichten extrahiert wurde ( 150.000 Dreiecke) Marching Cubes ist ein Algorithmus zur Berechnung von Isoflächen in der 3D Computergrafik. Er nähert eine Voxelgrafik durch eine… …   Deutsch Wikipedia

  • Marching Cubes — Polygonmodell eines Kopfes, der mittels Marching Cube aus 150 MRT Schichten extrahiert wurde ( 150.000 Dreiecke) Marching Cubes ist ein Algorithmus zur Berechnung von Isoflächen in der 3D Computergrafik. Er nähert eine Voxelgrafik durch eine… …   Deutsch Wikipedia

  • Marching cubes — Модель, построенная из 150 слоев с МРТ с использованием алгоритма marching cubes. Под поверхностью находятся около 150 000 полигонов и скрытых объектов. Размер сетки составляет 64 × 64 × 150 вокселей, кодированных 8 ю… …   Википедия

  • Marching cubes — Tête et structures cérébrales (cachées) obtenues par l application des marching cubes sur 150 tranches provenant d un IRM (env. 150 000 triangles) Les « marching cubes » désignent un algorithme d infographie publié à la conférence… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”