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 () 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 data 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.