Marssivad kuubid

Marssivad kuubid (ingl marching cubes) on arvutigraafika algoritm, mis koostab kolmemõõtmelise skalaarvälja isopinda lähendava kolmnurkadest koosneva võrestiku (mesh). 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 isojooni, on marssivad ruudud (ingl marching squares).

Ingliskeelsel terminil marching on mitu tähendust ja seega on algoritmi nime varem tõlgitud eesti keelde ka piirnevad kuubid või piiravad kuubid. Siiski on Lorensen ja Cline oma esialgses artiklis mõelnud marching all just püsisammulist liikumist ehk marssimist.

 Ajalugu 
pisi|15 originaalset kuubi juhtu.
Algoritmi töötasid välja William E. Lorensen ja Harvey E. Cline. Esimene avaldatud versioon üldistas kõikvõimalikud 256 juhtu kasutades pööramist ja inversiooni (reflection), saades vaid 15 juhtu. Kiiresti pärast algoritmi avaldamist leiti, et kõik juhud siiski ei ole inversiooni suhtes sümmeetrilised. Seda ekslikult eeldades tekkisid ebamääraseid juhud, mis tekitasid võrestikku auke.

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 pööramist, peegeldamist ja/või inversiooni. Algoritm on tõenäoliselt kõige populaarsem isopindade visualiseerimise viis.

Informaatika teaduskirjastaja ACM tõi aastal 1998 Lorenseni ja Cline'i artikli esile ühena arvutigraafika valdkonnas kõrgelt tunnustatud ja valdkonda kujundavatest teadusartiklitest.

 Algoritm 
pisi|Marssivate kuubikute algoritmi poolt loodud pind kahest metapallist ilma skalaarvälja põhjal interpoleerimiseta.
pisi|Marssivate kuubikute algoritmi poolt loodud pind kahest metapallist skalaarvälja põhjal lineaarse interpoleerimisega.

Algoritm loob 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 skalaarvälja sämplimiseks mõttelise kuubi kaheksat tippu. Nende sämplite põhjal otsustab algoritm, kuhu ja milliseid kolmnurki on pinna loomiseks vaja tekitada. Tervet ruumi läbides tekitatud kolmnurgad pannakse seejärel kokku üheks võrestikuks. 

Kuna kasutatakse kaheksat punkti, millest igaüks võib olla kas väiksema või suurema väärtusega kui etteantud isovää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. Seejärel leitakse eelnevalt koostatud otsingutabelist, millised isopinda lähendavad kolmnurgad vastavalt juhul kuubi sisse luuakse. Kolmnurgad luuakse otspunktidega kuubi servadel. Lihtsamal variandil võivad kolmurkade tipud jaotada vastavad servad täpselt pooleks, kuid see põhjustab suhteliselt halva lähendi. Parema isopinna lähendi saab, kui kolmnurkade tipud interpoleeritakse serva peal vastavate skalaavälja väärtuste järgi serva otspunktides. Tüüpiliselt kasutatakse selle lähendamiseks lineaarset interpoleerimist. 

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

 Kasutusvõimalused 
Marssivate kuupide 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 
Marssivate kuupide 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 marssivad tetraeedrid.

 Viited 

Kategooria:Arvutigraafika