Dalībnieks:Eddmunds/Smilšu kaste
Gājienu kubi 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īniskām 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
[labot šo sadaļu | labot pirmkodu]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.[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 izovirsma daļas, var viegli identificēt, jo parauga vērtības kubu virsotnēs jāatbilst mērķa izo virsmas 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. Ņemiet vērā, ka šajā gadījumā sejas virsotņu pazīmes ir nepietiekamas, lai noteiktu pareizo veidu, kā izlīdzināt izosu virsmu. 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
[labot šo sadaļu | labot pirmkodu]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
[labot šo sadaļu | labot pirmkodu]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])
Avoti
[labot šo sadaļu | labot pirmkodu]- ↑ 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.
Apskatīt
[labot šo sadaļu | labot pirmkodu]Linki
[labot šo sadaļu | labot pirmkodu] |
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».
- «Introductory description with additional graphics».
- «Marching Cubes».. 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».