Gājienu kubi

Gājienu kubi 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, CT un MRT skenēšanas datu attēliem un īpašiem efektiem vai 3-D modelēšanu. Analogisku divdimensiju metodi sauc par maršruta kvadrātu algoritmu.

Vēsture 
Algoritmu izstrādāja William E. Lorensen un 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 Maring 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.
 
 

3D modelēšana