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

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

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