Marching cubes: differenze tra le versioni

Versione delle 19:42, 24 apr 2014

Versione delle 21:13, 24 apr 2014

Riga 2:

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

[[File:MarchingCubes.svg|thumb|upright=1.6|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.<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'agoritmo ==

Riga 13 ⟶ 25:

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

[[File:MarchingCubes.svg|thumb|upright=1.6|15 configurazioni univoche]] L'array precalcolato delle 256 configurazioni può essere ottenuto per [[riflessione (geometria)|riflessione]] e [[rotazione (matematica)|rotazioni]] [[simmetria (matematica)|simmetriche]] degli unici 15 casi.

Il gradiente del campo scalare ad ogni punto della griglia è anche il vettore normale di una ipotetica isosuperficie