Piiravad kuubikud

Piiravad kuubikud (ingl marching cubes) on arvutigraafika algoritm, mis koostab kolmemõõtmelise skalaarvälja põhjal ruumilise kolmnurkadest koosneva mudeli, mis järgib skalaarväljas mingit isopinda. Selle töötasid meditsiini valdkonnas kasutamiseks välja Lorensen ja Cline aastal 1987, et aidata visualiseerida magnettomograafia ja muude uuringute tulemusi. Analoogne algoritm kahemõõtmelises ruumis, mis leiab isoliine, on piiravad ruudud (ingl marching squares).

Ajalugu 

Algoritmi töötasid välja William E. Lorensen ja Harvey E. Cline. Esimene avaldatud versioon kasutas peegeldusi ja pöörlemist ning sisaldas vaid 15 juhtu. Kuna antud juhtudega mudeli koostamisel on ebamääraseid juhtumeid, mis võivad auke tekitada, on hilisemad tööd algoritmi edasi arendanud.

Algoritmi on palju edasi arendatud ning sellest on palju variante. Arendatud on jõudlust, et algoritmi käigus tehtaks vähem tööd, kõrgema dimensiooniga andmetel töötavaid variante, ajaga muutuvaid andmeid töötlevaid variante ning variante, mis ei nõua nelinurga kujul olevaid andmeid. Variandid erinevad ka selle poolest, kas nad kasutavad juhtude vähendamiseks ära peegeldumist ja/või pöörlemist. Algoritm on tõenäoliselt kõige populaarsem isopindade visualiseerimise viis.

Algoritm 
Algoritm üritab tekitada kolmnurkadest koosnevat pinda, mille iga punkt on skalaarväljal võimalikult lähedal mingile etteantud väärtusele. Selle tarbeks algoritm läbib skalaarvälja ning kasutab korraga 8 punkti, mis moodustavad mõttelise kuubiku. Nende punktide põhjal otsustab algoritm, kus ja milliseid kolmnurki on pinna loomiseks vaja tekitada. Tervet ruumi läbides tekitatud kolmnurgad pannakse seejärel kokku üheks mudeliks. 

Kuna kasutatakse 8 punkti, millest igaüks võib olla kas väiksema või suurema väärtusega kui etteantud väärtus, tekib 256 kolmnurkade paigutamise võimalust. Algoritmi käigus kasutatakse punkte kui bitte 1 baidises täisarvus, kus väiksemad väärtused teisendatakse nullideks ja suuremad ühtedeks ning tekkiv arv annab käesoleva juhu indeksi. Eelnevalt on koostatud otsingu tabel, mis ütleb milliseid kolmnurki on vaja tekitada antud juhu puhul, ning indeksi kaudu leiab sellest õige paigutuse. Lõpuks paigutatakse iga tekkinud kolmnurga ots mõttelise kuubiku ääre peale, kasutades ääre otstes olevate skalaarväärtuste lineaarset interpoleerimist, et kolmnurga otsa sobiv asukoht määrata, mis parandab mudeli täpsust. 

Mudeli pinnanormaale on võimalik leida, kasutades skalaarvälja gradienti, mis on kasulik mudeli valgustamisel.

Kasutusvõimalused 
Piiravate kuubikute algoritmi algne kasutus oli meditsiiniliste uuringute tulemuste visualiseerimine arstide töö abistamiseks. Algoritmi saab üldisemalt kasutada kõigil juhtudel, kus leidub skalaarväli, näiteks protseduurilise maastiku tekitamisel.

Patent 
Piiravate kuubikute algoritmi patenteeris Ameerikas 1985. aastal General Electric Co, kelle jaoks Lorensen ja Cline töötasid. Praeguseks on patent aegunud ning algoritmi on kõigil võimalik loata kasutada. Et enne aegumist patendist mööda pääseda, arendati sarnane algoritm piirnevad tetraeedrid.

Viited 

Arvutigraafika