Marching cubes: differenze tra le versioni

Versione delle 21:14, 24 apr 2014

Versione attuale delle 06:22, 13 mar 2025

(19 versioni intermedie di 14 utenti non mostrate)

Riga 1:

'''Marching cubes''' (tradotto letteralmente: cubi marcianti) è un [[algoritmo]] di [[computer grafica]], pubblicato al [[SIGGRAPH]] del [[1987]] da Lorensen e Cline<ref name="Originalpaper">William E. Lorensen, Harvey E. Cline: ''Marching Cubes: A high resolution 3D surface construction algorithm.'' In: ''Computer Graphics'', Vol. 21, Nr. 4, July 1987</ref> per estrarre unala [[mesh poligonale]] di una [[isosuperficie]] da un campo scalare [[Computerdiscreto graficatridimensionale 3D|3D]](gli elementi del quale sono (talvolta chiamati [[voxel]]).

{{F|computer grafica|febbraio 2011}}

L'algoritmo è principalmente utilizzato nel campo della [[radiologia]] attraverso la [[diagnostica per immagini]], ad esempio la [[tomografia computerizzata|CT]] e l'[[imaging a risonanza magnetica|MRI]], nella visualizzazione scientifica per analizzare un dato volumetrico, ma anche nella creazione di effetti speciali nell'amibitoambito della [[modellazione 3D]], con le [[metaball]] o [[metasuperfici]]. Un metodo analogo a due dimensioni è chiamato [[Marchingmarching squares]].

{{C|Controllo richiesto dal traduttore|informatica|febbraio 2007}}

'''Marching cubes''' (tradotto letteralmente: cubi marcianti) è un [[algoritmo]] di [[computer grafica]], pubblicato al [[SIGGRAPH]] del [[1987]] da Lorensen e Cline<ref name="Originalpaper">William E. Lorensen, Harvey E. Cline: ''Marching Cubes: A high resolution 3D surface construction algorithm.'' In: ''Computer Graphics'', Vol. 21, Nr. 4, July 1987</ref> per estrarre una [[mesh poligonale]] di una [[isosuperficie]] da un campo scalare [[Computer grafica 3D|3D]] (talvolta chiamati [[voxel]]).

L'algoritmo è principalmente utilizzato nel campo della [[radiologia]] attraverso la [[diagnostica per immagini]], ad esempio la [[tomografia computerizzata|CT]] e l'[[imaging a risonanza magnetica|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]].

[[File:Marchingcubes-head.png|thumb|Testa e strutture cerebrali (nascoste) estratte da 150 [[Imaging a risonanza magnetica|MRI]] slice usando i marching-cubes (circa 150.000 triangoli)]]

== Storia ==

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 visuallizzarevisualizzare in modo efficenteefficiente dati da dispositivi CT e MRI.

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 efficente dati da dispositivi CT e MRI.

[[File:MarchingCubes.svg|thumb|upright=1.6|15 configurazioni univoche]]

La premessa dell'algoritmo è di dividere il volume di input in un insieme discreto di cubi. Assumendo una conversione lineare, ogni cubo, che contiene una porzione dell'isosuperficie, può essere facilmente identificato, poiché i valori campionati ai vertici del cubo devono coprire il valore dell'isosuperficie in questione. Per ogni cubo viene generata una mesh che approssima il comportamento dell'interpolante trilineare all'interno del cubo. La loro prima versione pubblicata sfruttava una simmetria rotazionale e speculare, e anche cambi di segno, per costruire una tabella con 15 configurazioni univoche. Tuttavia, nell'elaborazione delle facce, si possono presentare casi ambigui dovuti al comportamento dell'interpolante.<ref>{{Cita libro |titolo=The Marching Cubes |url=http://users.polytech.unice.fr/~lingrand/MarchingCubes/algo.html |accesso=24 aprile 2014 |urlarchivio=https://web.archive.org/web/20190818160414/http://users.polytech.unice.fr/~lingrand/MarchingCubes/algo.html |dataarchivio=18 agosto 2019 |urlmorto=sì }}</ref> Questi generavano discontinuità e difetti topologici. Il problema si viene a creare in presenza di segni alterni, dove si riscontrano almeno due scelte corrette per il quale il profilo è valido. La scelta reale non è importante, ma deve essere topologicamente coerente. Un segno diverso agli estremi della diagonale, o ai vertici dei cubi, può comportare diverse configurazioni. Le ambiguità sono state migliorate con lo sviluppo di nuovi algoritmi, come nel 1991 quando venne proposto un test, l'[[asymptotic decider]], di Nielson e Hamann<ref>{{Cita pubblicazione|cognome1=Nielson|nome1=Gregory M.|cognome2=Hamann|nome2=B.|titolo=The asymptotic decider: resolving the ambiguity in marching cubes|rivista=Proceeding VIS '91 Proceedings of the 2nd conference on Visualization '91|anno=1991|url=https://dl.acm.org/citation.cfm?id=949621}}</ref>, il quale corresse solo in parte queste anomalie.<ref name="HansenJohnson2004">{{Cita libro|autore1=Charles D. Hansen|autore2=Chris R. Johnson|titolo=Visualization Handbook|url=http://books.google.com/books?id=ZFrlULckWdAC&pg=PA9|anno=2004|editore=Academic Press|isbn=978-0-12-387582-2|p=9}}</ref><ref name="DykesMacEachren2005">{{Cita libro|autore1=A. Lopes|autore2=K. Bordlie|capitolo=Interactive approaches to contouring and isosurfaces for geovisualization|curatore=Jason Dykes|curatore2=Alan M. MacEachren|curatore3=M. J. Kraak|titolo=Exploring Geovisualization|url=http://books.google.com/books?id=gUza-nsEwioC&pg=PA352|anno=2005|editore=Elsevier|isbn=978-0-08-044531-1|pp=352-353}}</ref> Un ulteriore miglioramento è dovuto a Chernyaev, che portò la tabella delle configurazioni a 33 elementi. Diverse altre problematiche topologiche hanno trovato un parziale soluzione negli anni successivi, fino al lavoro di Custodio & al., del 2019<ref>{{Cita pubblicazione|nome=Lis|cognome=Custodio|nome2=Sinesio|cognome2=Pesco|nome3=Claudio|cognome3=Silva|data=2019-12|titolo=An extended triangulation to the Marching Cubes 33 algorithm|rivista=Journal of the Brazilian Computer Society|volume=25|numero=1|lingua=en|accesso=2024-02-29|doi=10.1186/s13173-019-0086-6|url=https://journal-bcs.springeropen.com/articles/10.1186/s13173-019-0086-6}}</ref>.

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.<ref>{{cite book |title=The Marching Cubes |url=http://users.polytech.unice.fr/~lingrand/MarchingCubes/algo.html}}</ref> Questi casi ambigui possono portare a meshing con fori. Topologicamente parlando, correggere isosuperfici può comportare uno sforzo supplementare.<ref name="citeseerx.ist.psu.edu">{{cite book |title=Marching Cubes 33: Construction of Topologically Correct Isosurfaces |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.7139}}</ref>

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 <ref name="citeseerx.ist.psu.edu"/> mostra 33 configurazioni.

Le ambiguità sono state migliorate con lo sviluppo di nuovi algoritmi come nel 1991 [[asymptotic decider]] di Nielson e Hamann<ref>{{cite journal|last1=Nielson|first1=Gregory M.|last2=Hamann|first2=B.|title=The asymptotic decider: resolving the ambiguity in marching cubes|journal=Proceeding VIS '91 Proceedings of the 2nd conference on Visualization '91|year=1991|url=http://dl.acm.org/citation.cfm?id=949621}}</ref> il quale corresse queste anomalie.<ref name="HansenJohnson2004">{{cite book|author1=Charles D. Hansen|author2=Chris R. Johnson|title=Visualization Handbook|url=http://books.google.com/books?id=ZFrlULckWdAC&pg=PA9|year=2004|publisher=Academic Press|isbn=978-0-12-387582-2|page=9}}</ref><ref name="DykesMacEachren2005">{{cite book|author1=A. Lopes|author2=K. Bordlie|chapter=Interactive approaches to contouring and isosurfaces for geovisualization|editor=Jason Dykes|editor2=Alan M. MacEachren|editor3=M. J. Kraak|title=Exploring Geovisualization|url=http://books.google.com/books?id=gUza-nsEwioC&pg=PA352|year=2005|publisher=Elsevier|isbn=978-0-08-044531-1|pages=352–353}}</ref> Diverse altre analisi di ambiguità e miglioramenti relativi sono stati proposti da allora; vedasi l'indagine del 2005 di Lopes e Bordlie, per esempio.<ref name="DykesMacEachren2005"/>

== Descrizione dell'algoritmo ==

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 (<math>2^8 = 256</math>) 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 allnell'array della configurazione del poligono.

Infine ciascun [[vertice (geometria)|vertice]] didei poligoni generati è messo nella posizione appropriata lungo il verticelato del cubo [[Metodo dell'interpolazione lineare|interpolando linearmente]] i valori dei due scalari che sono connessi da quel verticelato.

L'array precalcolato delle 256 configurazioni può essere ottenuto per [[riflessione (geometria)|riflessione]] e [[rotazione (matematica)|rotazioni]] [[simmetria (matematica)|simmetriche]] degli unicidei 15 casi unici.

Il gradiente del campo scalare ad ogni punto della griglia è anche il vettore normale di una ipotetica isosuperficie passante per 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 un qualche modello di illuminazione.

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==

== Applicazioni ==

{{F|computer grafica|febbraioaprile 20112014}}

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]].

L'algoritmo marching cubes algorithm è ritenuto dai sostenitori del [[software libero]] come un caso principale nel campo della [[computer grafica]] dei mali del [[software proprietario]] {{citazione necessaria}}. Essi sostengono che l'implementazione brevettata (United States Patent 4,710,876<ref name="patent">{{US patent|4710876|Marching Cubes, US Patent Office entry}}</ref>) 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<ref name="patent" />).

== Riferimenti ==

== Note ==

<references/>

== Voci correlate ==

* [[Algoritmo]]

* [[Computer grafica 3D]]

== Altri progetti ==

{{interprogetto}}

[[Categoria:Grafica 3D]]

[[Categoria:Computer grafica]]