Marching cubes

Marching cubes ir datorgrafikas algoritms, kas publicēts 1987. gadā SIGGRAPH,^[1] lai izdalītu poligonālo sietu no trīsdimensiju diskrēta skalāra lauka (dažreiz to sauc par vokseli). Šī algoritma pielietojumi galvenokārt attiecas uz medicīnisku vajadzību vizualizāciju, piemēram, datortomogrāfijas un magnētiskās rezonanses tomogrāfijas attēliem un īpašiem efektiem vai 3-D modelēšanu. Analogisku divdimensiju metodi sauc par Marching squares algoritmu.

Vēsture

Algoritmu izstrādāja Viljams E. Lorensens (William E. Lorensen) un Hārvijs E. Klains (Harvey E. Cline), veicot pētījumus General Electric. General Electric viņi strādāja, lai efektīvi vizualizētu datus no CT un MRI ierīcēm.^[2]

Algoritma priekšnoteikums ir ieejas tilpuma sadalīšana atsevišķā kubu komplektā. Pieņemot lineāro rekonstrukcijas filtrēšanu, katru kubu, kas satur kādu no konkrētās izovirsmas daļas, var viegli identificēt, jo parauga vērtībām kubu virsotnēs jāatbilst mērķa izovirsmas vērtībai.

Pirmā publicētā algoritma versija izmantoja rotācijas un atstarojošo simetriju, kā arī parakstīja izmaiņas, lai izveidotu tabulu ar 15 unikāliem gadījumiem. Tomēr, ņemot vērā neskaidrības attiecībā uz interpolanta trilīro uzvedību kubu virsotnēs un interjerā, no Marching cubes iegūtās acis parādīja pārtraukumus un topoloģiskus jautājumus. Ņemot vērā režģa kubu, rodas sejas neskaidrības, kad tā virsotnes virsotnēm ir mainīgas zīmes. Tas nozīmē, ka viena diagonālā virsotne šajā sejā ir pozitīva un otrās virsotnes ir negatīvas. Šajā gadījumā sejas virsotņu pazīmes ir nepietiekamas, lai noteiktu pareizo veidu, kā izlīdzināt izovirsmu. Līdzīgi rodas arī iekšējās neskaidrības, kad kubu virsotņu pazīmes nav pietiekamas, lai noteiktu pareizo virsmas trijstūri, t.i., kad vairākas triangulācijas ir iespējamas vienai un tai pašai kuba konfigurācijai.

Algoritms

Algoritms iziet caur skalāra lauku, tajā pašā laikā ņemot astoņas kaimiņu vietas (tādējādi veidojot iedomātu kubu), pēc tam nosakot poligonu (-us), kas vajadzīgs, lai attēlotu to izoskopas daļu, kas iet caur šo kubu. Pēc tam atsevišķi poligoni tiek sapludināti vēlamajā virsmā.

Tas tiek darīts, izveidojot indeksu iepriekš aprēķinātam masīvam 256 iespējamās daudzstūra konfigurācijās (2 ⁸ = 256) kubā, apstrādājot katru no 8 skalārām vērtībām. Ja skalārā vērtība ir lielāka par izo vērtību (t.i., tā ir virsmas iekšpusē), tad atbilstošais bits tiek iestatīts uz vienu, bet, ja tas ir zemāks (ārpus), tas tiek iestatīts uz nulli. Galīgā vērtība pēc visu astoņu skalāru pārbaudīšanas ir faktiskais daudzstūra indeksu masas indekss.

Visbeidzot, katra radīto poligonu virsotne tiek novietota atbilstošajā pozīcijā pa kuba malu, lineāri interpolējot divas skalas vērtības, kas ir savienotas ar šo malu.

Patenta jautājumi

Algoritma ieviešana tika patentēta kā ASV patents Nr. 4 710 876.^[2] Patents savu darbību beidza 2005. gadā un šobrīd šo algoritmu bez jabkdās atlīdzībs viņa veidotājiem, ir iespējams izmantot visiem cilvēkiem. (December 1, 1987^[2])

Atsauces

↑ Lorensen, William E.; Cline, Harvey E. (1 August 1987). "Marching cubes: A high resolution 3D surface construction algorithm". ACM SIGGRAPH Computer Graphics 21 (4): 163–169. doi:10.1145/37402.37422.
↑ ^2,0 ^2,1 ^2,2 System and method for the display of surface structures contained within the interior region of a solid body. 5 June 1985.

Ārējās saites

Vikikrātuvē par šo tēmu ir pieejami multivides faili. Skatīt: Marching cubes

Lorensen, W. E.; Cline, Harvey E. (1987). "Marching cubes: A high resolution 3d surface construction algorithm". ACM Computer Graphics 21 (4): 163–169. doi:10.1145/37402.37422.
G. M. Nielson, Bernd Hamann. The asymptotic decider: resolving the ambiguity in marching cubes. Proc. 2nd Conference on Visualization (VIS' 91). Vis '91, 1991. 83–91. lpp. ISBN 9780818622458. doi:10.1109/VISUAL.1991.175782.
Montani, Claudio; Scateni, Riccardo; Scopigno, Roberto (1994). "A modified look-up table for implicit disambiguation of Marching cubes". The Visual Computer 10 (6): 353–355. doi:10.1007/BF01900830.
G. M. Nielson, Junwon Sung. Interval volume tetrahedrization. 8th IEEE Visualization (VIS'97), 1997. 221–228. lpp. ISBN 978-0-8186-8262-9. doi:10.1109/VISUAL.1997.663886.
Paul Bourke. «Overview and source code».
Matthew Ward. «GameDev overview».^{[novecojusi saite]}
«Introductory description with additional graphics». Arhivēts no oriģināla, laiks: 2019. gada 18. augustā. Skatīts: 2019. gada 27. maijā.
«Marching Cubes». Arhivēts no oriģināla, laiks: 2019. gada 27. maijā. Skatīts: 2019. gada 27. maijā.. Some of the early history of Marching Cubes.
Newman, Timothy S.; Yi, Hong (2006). "A survey of the marching cubes algorithm". Computers and Graphics 30 (5): 854–879. doi:10.1016/j.cag.2006.07.021.
Stephan Diehl. «Specializing visualization algorithms». Arhivēts no oriģināla, laiks: 2017. gada 24. oktobrī. Skatīts: 2019. gada 27. maijā.

[journalarticle-1] Lorensen, William E.; Cline, Harvey E. (1 August 1987). "Marching cubes: A high resolution 3D surface construction algorithm". ACM SIGGRAPH Computer Graphics 21 (4): 163–169. doi:10.1145/37402.37422.

[US_Patent-2] 2,0 ^2,1 ^2,2 System and method for the display of surface structures contained within the interior region of a solid body. 5 June 1985.

[1]

[2]