|
'''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]]).
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.svg|thumb|upright=1.6|15 configurazioni univoche]]
La premessa dell'algoritmo è di divedere il volume di input in un inseme 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 triilineare all'interno del cubo. La loro prima versione pubblicata sfruttòsfruttava una simmetria rotazionale e riflettentespeculare, ed anche particolaricambi cambiamentidi nellasegno, costruzioneper dicostruire una tabella con 15 configurazioni univoche. Tuttavia, nell'elaborazione delle facce, cisi sonopossono alcunipresentare 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 casigeneravano ambiguidiscontinuità possonoe portaredifetti topologici. Il problema si viene a meshingcreare conin foripresenza di segno doppio, dove si riscontrano almeno due scelte corrette per il quale il profilo è valido. La Topologicamentescelta parlandoreale non importa, correggerema deve essere topologicamente coerente. Un segno diverso agli estremi della diagonale, o dei vertici dei isosuperficicubi può comportare unodiverse sforzoconfigurazioni. supplementareLe 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="citeseerxHansenJohnson2004">{{Cita libro|autore1=Charles D.ist Hansen|autore2=Chris R.psu Johnson|titolo=Visualization Handbook|url=http://books.edugoogle.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|titoloautore1=MarchingA. CubesLopes|autore2=K. 33:Bordlie|capitolo=Interactive Constructionapproaches ofto Topologicallycontouring Correctand Isosurfacesisosurfaces for geovisualization|curatore=Jason Dykes|curatore2=Alan M. MacEachren|curatore3=M. J. Kraak|titolo=Exploring Geovisualization|url=http://citeseerxbooks.istgoogle.psu.educom/viewdoc/summarybooks?doiid=10.gUza-nsEwioC&pg=PA352|anno=2005|editore=Elsevier|isbn=978-0-08-044531-1.1.56.7139|pp=352–353}}</ref> Un ulteriore miglioramento è dovuto a Chernyaev, che porto la tabella delle configurazione a 33. Diverse altre problematiche topologiche hanno trovato un parziale soluzione negli anni successivi, fino al lavoro di Custodio & al., del 2013.
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>{{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 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> 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 ==
|
