Katsaus pinnanmuodostusalgoritmeihin

Abstract

Kolmiulotteisia pintoja käytetään tietokonegrafiikassa esimerkiksi lääketieteessä ja komponenttien suunnittelussa. Pinnanmuodostusalgoritmien avulla on myös mahdollista tehdä reaaliaikaisesti muokattavia pintoja, joita hyödynnetään esimerkiksi simulaatioissa. Pintojen tietokoneellisessa esityksessä tärkeää on esittää pinnat mahdollisimman vähillä resursseilla, kuitenkin säilyttäen piirteet mahdollisimman tarkasti. Tässä työssä tutkitaan kirjallisuuskatsauksen avulla kahta pinnanmuodostusmenetelmää. Nämä ovat Marching Cubes ja Dual Contouring. Tavoitteena on selvittää näiden menetelmien vahvuuksia ja heikkouksia sekä löytää vastaus siihen, millaisiin tilanteisiin kukin menetelmä toimii parhaiten.

Marching Cubes on tutkituista menetelmistä varhaisempi. Sen toiminta perustuu siihen, että mallinnettava alue jaetaan samankokoisiin kuutioihin. Pinta muodostetaan ennalta määritetyt hakutaulukon pohjalta. Tämä hakutaulukko sisältää kaikki mahdolliset pintaelementtiyhdistelmät, jotka pinta voi saada yhden kuution sisäisellä alueella.

Dual Contouring on tutkituista menetelmistä uudempi. Menetelmä perustuu reunojen tarkasteluun, ja etumerkkien muutokseen. Dual Contouring menetelmä ei hyödynnä hakutaulukoita, vaan pintaelementtien asettelu määräytyy ajonaikaisesti. Tämä mahdollistaa sen, että menetelmä voi muodostaa vaihtelevan kokoisia pintaelementtejä.

Kummallekin menetelmälle löydettiin etuja sekä haittoja. Marching Cubes -menetelmä on vahvimmillaan, kun ajonaikaista laskentaa halutaan minimoida. Menetelmän heikkoutena on terävien reunojen tuotto sekä huonosti optimoidun lopputulokset. Dual Contouring -menetelmä soveltuu tilanteisiin, joissa muodostettava pinta sisältää teräviä reunoja. Menetelmällä tuotetut pinnat ovat myös paljon optimoidumpia. Heikkoutena menetelmässä on se, että tuotetut pinnat ovat aina täysin vesitiiviitä, mikä voi aiheuttaa vääristymiä pinnan muotoon ja tuottaa fyysisesti mahdottomia pintoja. Lisäksi menetelmä tarvitsee enemmän ajonaikaista laskentaa.