Efficient sampling for a visibility preprocessing system

No Thumbnail Available

URL

Journal Title

Journal ISSN

Volume Title

Helsinki University of Technology | Diplomityö
Checking the digitized thesis and permission for publishing
Instructions for the author

Authors

Date

2009

Department

Tietotekniikan laitos

Major/Subject

Vuorovaikutteinen digitaalinen media

Mcode

T-111

Degree programme

Language

en

Pages

65 (+16)

Series

Abstract

The importance of visibility determination in interactive 3D graphics applications is vital. Even the most impressive consumer graphics hardware is not able to deal with arbitrarily large 3D worlds without any visibility algorithms running on the CPUs or GPUs. The visibility calculations are done either for each individual point in space or for a convex region where each point share the same visibility. In the former case typically all the calculations are done runtime and in the latter there often is a pre-processing step and a more lightweight runtime step. The purpose of this thesis is to find a good probability distribution for doing visibility sampling in a from-region visibility pre-processing system. The system is a commercial middleware library used in computer and console games. The visibility sampling is done by generating 3D points on planar surfaces and using the graphics hardware to determine the visibility from these points. The planar surfaces are the borders between the viewing regions, and the surfaces and the region geometry are pre-generated by the system. Two statistical random distributions were implemented and benchmarked against several key metrics. Uniform distribution is a straightforward random distribution of points on the sampling domain. Poisson-disk distribution adds some features to uniform distribution and due to its wide acceptance in the research community it was expected to perform well. The most important metric used to compare the implementations was the pixel error of the sampling process as the function of the number of generated sample points. Even though no optimizations were done to improve the time of generating the Poisson-disk distributed sample points, it still outperformed the regular uniform distribution by a clear margin. In a complex scene it managed to reach an acceptable level of accuracy with approximately 10,000 sample points in a little more than 10 minutes. The corresponding figures for uniform sampling were 630,000 sample points and over 2 hours.

Näkyvyyslaskennan merkitys vuorovaikutteisille kolmiulotteista grafiikkaa käyttäville sovelluksille on olennaisen tärkeää. Edes kaikkein nykyaikaisimmat näytönohjaimet eivät kykene käsittelemään mielivaltaisen kokoisia 3D-maailmoja ilman näkyvyysoptimointia. Näkyvyys lasketaan joko yksittäisille pisteille avaruudessa tai konvekseille alueille, joiden pisteet jakavat saman näkyvyyden. Pistenäkyvyys lasketaan tavallisesti kokonaan ajon aikana ja aluenäkyvyyden määrittelyssä suurin osa laskennasta suoritetaan yleensä esilaskentana. Tämän diplomityön tarkoitus on löytää tehokas algoritmi erään aluenäkyvyyteen perustuvan ohjelmiston näkyvyyden näytteistämiseen. Parannettava ohjelmisto on kaupallinen väliohjelmistokirjasto, joka on kehitetty erityisesti tietokone- ja konsolipelejä varten. Näytteistäminen tehtiin tuottamalla 3D-pisteitä tasopinnoille ja käyttämällä näytönohjainta näkyvyyden määrittelyyn näistä pisteistä. Näytteistämisessä käytetyt alueet ja tasopinnat, jotka ovat käytännössä alueiden välisiä rajapintoja, saadaan automaattisesti ohjelmistolta. Diplomityötä varten toteutettiin kaksi satunnaisuuteen perustuvaa tilastollista jakaumaa, joiden toimivuutta käyttötarkoitukseen arvioitiin muutamalla eri tavalla. Ensimmäinen jakauma on täysin satunnaisesti luotu tasainen jakauma ja toinen noudattaa Poisson-kiekko jakaumaa. Poisson-kiekko jakauma valittiin toteutettavaksi, sillä aikaisempi tutkimus on osoittanut sen toimivuuden tämänkaltaisissa tilanteissa parhaiten. Tärkeimpänä arviointikriteerinä käytettiin uusien näytepisteiden aiheuttamaa pikselivirhettä luotujen näytepisteiden määrän funktiona. Vaikka Poisson-kiekko jakauman tuottamisalgoritmin nopeuden optimointiin ei juurikaan kiinnitetty huomiota, se suoriutui silti huomattavasti tasaista jakaumaa paremmin näkyvyyden määrittämisessä. Esimerkkikentässä, jonka geometria oli huomattavan monimutkaista, se saavutti tyydyttävän näkyvyyden noin 10,000 näytepisteellä hieman yli kymmenessä minuutissa. Käytettäessä tasaista jakaumaa vastaavat luvut olivat 630,000 näytepistettä ja yli kaksi tuntia.

Description

Supervisor

Savioja, Lauri

Thesis advisor

Soininen, Teppo

Keywords

visibility determination, näkyvyyden määrittäminen, visibility sampling, näkyvyyden näytteistäminen, potentially visible set, PVS, Poisson-disk distribution, Poisson-kiekko jakauma

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-2020120555472

Collections

[dipl] Teknillinen korkeakoulu / TKK