Tietorakenteet ja algoritmit näkyvyystarkastelussa
Suopelto, Teemu (2010)
Julkaisun pysyvä osoite on
http://urn.fi/URN:NBN:fi:amk-2010120717266
http://urn.fi/URN:NBN:fi:amk-2010120717266
Tiivistelmä
Nykyaikaisten 3d-pelien grafiikka on äärimmäisen monimutkaista. Nopeasta kehityksestä huolimatta tietokonelaitteisto ei pysty vastaamaan kaikkein vaativimpien reaaliaikaisten sovellusten kuten pelien vaatimuksiin. Pelien 3d-grafiikka sisältää paljon pelaajalle näkymätöntä tietoa, jonka käsittely vie paljon aikaa. Tämän vuoksi pelisovelluksissa hyödynnetään näkyvyydentarkastelualgoritmeja, joiden tarkoituksena on piirtovaiheessa jättää käsittelemättä kuvaruudulla näkymätön data ja siten nopeuttaa kuvan tuottamista kuvaruudulle. Näkyvyystarkastelualgoritmit ovat olennainen osa jokaista nykyaikaista pelimoottoria.
Tämän opinnäytetyön tarkoitus on tutkia näkyvyystarkasteluissa käytettyjen tietorakenteiden ja algoritmien teoriaa. Lähteinä käytettiin akateemisia tutkimuksia ja grafiikkaohjelmointikirjoja. Aiheesta on olemassa erittäin paljon kirjoitettua tietoa, joten vain oleellisimpia asioita on käsitelty tässä opinnäytteessä. Teorian pääpaino on hierarkisissa tietorakenteissa, joiden lisäksi tutkittiin myös näkyvyyysoptimoinnin perusteita ja peittävyystarkastelua.
Taustateoria sovellettiin Kajak3D-pelimoottoriin, johon toteutettiin yleiskäyttöinen ja tehokas octree-lisäosa. Lisäosan vaatimusmäärittelyssä haluttiin tehostaa nimenomaan staattisten objektien piirtoa, ja sen tuli olla riittävän kevyt mobiiliympäristöön. Toteutuksessa haluttiin hyödyntää myös ennustettavuutta, jonka aikaisemmin tapahtuneiden näkyvyystarkasteluiden tutkiminen mahdollisti. Kajaanin amk:n pelilaboratorion henkilökunta osallistui vaatimusmäärittelyn tekemiseen ja auttoi Kajak3D:tä koskevissa teknisissä yksityiskohdissa.
Lisäosa testattiin Android-käyttöjärjestelmällä varustetulla älypuhelimella. Testi koostui Kajak3D:llä suoritettavasta 500-ruudun pituisesta kamera-animaatiosta kolmiuloitteisessa kaupunki-ympäristössä. Jokaisen ruudun prosessointiin ja piirtämiseen käytetty aika mitattiin. Tuloksia verrattiin piirtoon ilman octreeta. Piirto- ja prosessointiajan lisäksi mitattiin myös suoritettavien objektikohtaisten leikkaustestien määrä. Tulokset osoittivat, että octree-lisäosa paransi suorituskykyä huomattavasti. Myös leikkaustestien määrä väheni merkittävästi, koska octreen avulla pystyttiin hylkäämään isoja objektijoukkoja kerrallaan. Octree-lisäosa saavutti asetetut tavoitteet, ja se lisättiin osaksi Kajak3D-pelimoottoria.
Tämän opinnäytetyön tarkoitus on tutkia näkyvyystarkasteluissa käytettyjen tietorakenteiden ja algoritmien teoriaa. Lähteinä käytettiin akateemisia tutkimuksia ja grafiikkaohjelmointikirjoja. Aiheesta on olemassa erittäin paljon kirjoitettua tietoa, joten vain oleellisimpia asioita on käsitelty tässä opinnäytteessä. Teorian pääpaino on hierarkisissa tietorakenteissa, joiden lisäksi tutkittiin myös näkyvyyysoptimoinnin perusteita ja peittävyystarkastelua.
Taustateoria sovellettiin Kajak3D-pelimoottoriin, johon toteutettiin yleiskäyttöinen ja tehokas octree-lisäosa. Lisäosan vaatimusmäärittelyssä haluttiin tehostaa nimenomaan staattisten objektien piirtoa, ja sen tuli olla riittävän kevyt mobiiliympäristöön. Toteutuksessa haluttiin hyödyntää myös ennustettavuutta, jonka aikaisemmin tapahtuneiden näkyvyystarkasteluiden tutkiminen mahdollisti. Kajaanin amk:n pelilaboratorion henkilökunta osallistui vaatimusmäärittelyn tekemiseen ja auttoi Kajak3D:tä koskevissa teknisissä yksityiskohdissa.
Lisäosa testattiin Android-käyttöjärjestelmällä varustetulla älypuhelimella. Testi koostui Kajak3D:llä suoritettavasta 500-ruudun pituisesta kamera-animaatiosta kolmiuloitteisessa kaupunki-ympäristössä. Jokaisen ruudun prosessointiin ja piirtämiseen käytetty aika mitattiin. Tuloksia verrattiin piirtoon ilman octreeta. Piirto- ja prosessointiajan lisäksi mitattiin myös suoritettavien objektikohtaisten leikkaustestien määrä. Tulokset osoittivat, että octree-lisäosa paransi suorituskykyä huomattavasti. Myös leikkaustestien määrä väheni merkittävästi, koska octreen avulla pystyttiin hylkäämään isoja objektijoukkoja kerrallaan. Octree-lisäosa saavutti asetetut tavoitteet, ja se lisättiin osaksi Kajak3D-pelimoottoria.