Marching cubes

Da Wikipedia, l'enciclopedia libera.

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 CT e l'MRI, 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.

Testa e strutture cerebrali (nascoste) estratte da 150 MRI slice usando i marching-cubes (circa 150.000 triangoli)

Storia[modifica | modifica wikitesto]

L'algoritmo è stato sviluppato da William E. Lorensen e Harvey E. Cline come risultato della loro ricerca presso la General Electric. Alla General Electric hanno lavorato in modo da visuallizzare in modo efficiente dati da dispositivi CT e MRI.

15 configurazioni univoche

La loro prima versione pubblicata sfruttò una simmetria rotazionale e riflettente ed anche particolari cambiamenti nella costruzione di una tabella con 15 configurazioni univoche. Tuttavia, nell'elaborazione delle facce, ci sono alcuni casi ambigui.[2] Questi casi ambigui possono portare a meshing con fori. Topologicamente parlando, correggere isosuperfici può comportare uno sforzo supplementare.[3]

Il problema si viene a creare per i casi in presenza di segno doppio, dove si riscontrano almeno due scelte corrette per il quale il profilo è valido. La scelta reale non importa, ma deve essere topologicamente coerente. I casi primari portano a scelte coerenti, ma il cambiamento di segno può comportare errori. La tabella estesa in[3] mostra 33 configurazioni.

Le ambiguità sono state migliorate con lo sviluppo di nuovi algoritmi come nel 1991 asymptotic decider di Nielson e Hamann[4] il quale corresse queste anomalie.[5][6] Diverse altre analisi di ambiguità e miglioramenti relativi sono stati proposti da allora; vedasi l'indagine del 2005 di Lopes e Bordlie, per esempio.[6]

Descrizione dell'algoritmo[modifica | modifica wikitesto]

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 (2^8 = 256) 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.

Questioni relative ai brevetti[modifica | modifica wikitesto]

L'algoritmo marching cubes algorithm è ritenuto dai sostenitori del software libero come un caso principale nel campo della computer grafica dei mali delSoftware proprietario [senza fonte]. Essi sostengono che limplementazione brevettata (United States Patent 4,710,876[7]) sia ovvia relativamente al problema della generazione di superfici. È stato sviluppato un algoritmo similare chiamato marching tetrahedra, al fine di aggirare il brevetto, oltre a risolvere alcuni casi di ambiguità con qualche configurazione del cubo. La licenza dell'algoritmo marching cubes è scaduta nel 2005, ed è ora legale per la comunità nel campo della computer grafica usare l'algoritmo senza diritti d'autore da più di 18 anni dalla sua dato di emissione (December 1, 1987[7]).

Riferimenti[modifica | modifica wikitesto]

  1. ^ William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987
  2. ^ The Marching Cubes.
  3. ^ a b Marching Cubes 33: Construction of Topologically Correct Isosurfaces.
  4. ^ Gregory M. Nielson e B. Hamann, The asymptotic decider: resolving the ambiguity in marching cubes in Proceeding VIS '91 Proceedings of the 2nd conference on Visualization '91, 1991.
  5. ^ Charles D. Hansen e Chris R. Johnson, Visualization Handbook, Academic Press, 2004, p. 9, ISBN 978-0-12-387582-2.
  6. ^ a b A. Lopes e K. Bordlie, Interactive approaches to contouring and isosurfaces for geovisualization in Jason Dykes, Alan M. MacEachren e M. J. Kraak (a cura di), Exploring Geovisualization, Elsevier, 2005, pp. 352–353, ISBN 978-0-08-044531-1.
  7. ^ a b (EN) United States Patent 4710876, United States Patent and Trademark Office.