Marching cubes

[thumb|250px|Galvas un smadzeņu struktūras (slēptas), kas iegūtas no 150 [magnētiskās rezonanses tomogrāfijas daļām, izmantojot *Marching cubes* algoritmu (aptuveni 150 000 trīsstūri)]]

***Marching cubes*** ir datorgrafikas algoritms, kas publicēts 1987. gadā SIGGRAPH, 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.

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  8  = 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. 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)

## Atsauces

## Ārējās saites

* 
* 
* 
* 
* 
* 
* 
* . Some of the early history of Marching Cubes.
* 
*