Tietorakenteet ja algoritmit näkyvyystarkastelussa

Abstract

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.

Graphics in modern computer games are increasingly complex. Despite having very effective hardware, they simply cannot keep up with the demands of real-time applications such as games. At the same time 3d-graphics based games contain a lot of redundant information which takes a lot of time to process which is, however, never visible to the player. Some kind of visibility determination is often used to reduce the amount of processed graphical data and to speed up rendering. Visibility determination algorithms are an integral part of every modern game engine.

The purpose of this thesis is to study the theory behind basic data structures and techniques used in the visibility determination literature. The main sources of information are academic research papers and graphics programming books. A large body of research and data about visibility determination exists, thus only the most essential works have been included. The main part of the theory concerns hierarchical data structures, while the other parts consist of the basics of visibility optimization and occlusion culling.

The studied background theory was applied to a mobile game engine called Kajak3D and it was used to implement a practical, generic octree plug-in component including several enhancements. Requirements for the plug-in are specified to boost rendering of static objects in the mobile platforms. It was also required from the implementation that it utilizes temporal coherence data. The staff of the game development laboratory was involved in defining the requirements and they also provided technical support for Kajak3D.

Finally, the plug-in was tested on an Android-based mobile phone. The test scenario consists of a 500-frame long fly-through camera animation in a simplistic 3d-city environment which was rendered in real-time using Kajak3D. The time spent on processing and rendering each frame was saved and compared to the timing results without octree. Besides the processing and rendering time also a number of intersection tests were measured. The results of this work show that rendering with octree significantly increased performance. Also, the number of intersection tests was reduced significantly, because octree helped to reject groups of objects before rendering. The octree-plugin accomplished its objectives, and it was subsequently added to the Kajak3D component library.