Marching cubes
Un algoritmo che trasforma un campo scalare 3D in una mesh poligonale, decidendo cubo per cubo dove la superficie attraversa la griglia.
Il marching cubes, pubblicato da Lorensen e Cline alla GE nel 1987, estrae una superficie (una «isosuperficie») da dati volumetrici. Percorre una griglia 3D un cubo alla volta; ciascuno degli otto vertici è dentro o fuori dalla superficie, il che dà 256 casi (ridotti a 15 per simmetria) che, tramite una tabella di lookup, corrispondono a un insieme di triangoli che attraversano quel cubo. Cuciti insieme, i cubi formano una mesh continua.
Nato per la visualizzazione medica e scientifica (sezioni di TC e risonanza magnetica), è diventato il modo standard con cui i giochi costruiscono mesh da dati voxel o di distanza con segno: terreno distruttibile, mondi voxel lisci, metaball. A differenza di una heightmap gestisce grotte e strapiombi, perché lavora su un volume completo e non su un'altezza per colonna. Gli schemi di LOD variano la dimensione dei cubi in base alla distanza.