Marching cubes
Marching cubes (tradotto letteralmente: cubi marcianti) è un algoritmo di computer grafica, pubblicato al SIGGRAPH del 1987 da Lorensen e Cline[1] per estrarre una mesh poligonale di una isosuperficie da un campo scalare 3D (talvolta chiamati voxel). L'algoritmo è principalmente utilizzato nel campo della radiologia attraverso la diagnostica per immagini, ad esempio la tomografia computerizzata e l'imaging a risonanza magnetica, ma anche nella creazione di effetti speciali nell'amibito della modellazione 3D, con le metaball o metasuperfici. Un metodo analogo a due dimensioni è chiamato Marching squares.
Descrizione dell'agoritmo
L'algoritmo procede attraverso il campo scalare, prendendo otto locazioni vicine per volta (formando così un cubo immaginario), determinando quindi il poligono o i poligoni necessari per rappresentare la parte della isosuperficie che passa attraverso questo cubo. I poligoni individuali sono quindi fusi nella superficie desiderata.
Questo viene fatto creando un indice in un array precalcolato di 256 configurazioni di poligoni possibili ( ) all'interno del cubo, trattando ciascuno degli 8 valori scalari come un bit in un intero di 8-bit. Se il valore dello scalare è più alto dell'iso-valore (cioè è all'interno della superficie) allora il bit appropriato viene posto a uno, mentre se è più basso (esterno) è impostato a zero. Il valore finale dopo che tutti gli 8 scalari sono controllati, è l'indice all'array della configurazione del poligono.
Infine ciascun vertice di poligoni generati è messo nella posizione appropriata lungo il vertice del cubo interpolando linearmente i valori dei due scalari che sono connessi da quel vertice.
L'array precalcolato delle 256 configurazioni può essere ottenuto per riflessione e rotazioni simmetriche degli unici 15 casi.
Il gradiente del campo scalare ad ogni punto della griglia è anche il vettore normale di una ipotetica isosuperficie da quel punto. Quindi, dovremmo interpolare queste normali lungo i cardini di ciascun cubo per trovare le normali dei vertici generati che sono essenziali per ombreggiare la mesh risultante con qualche modello di illuminazione.
Applicazioni
Le applicazioni di questo algoritmo sono principalmente nel campo della visualizzazione medica come la scansione di dati di immagini CT e MRI, ed effetti speciali per modellazione 3-D con quello che di solito viene indicato in metaball o altre metasurface.
Riferimenti
- ^ William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987