An Incremental Shaft Subdivision Algorithm for Computing Shadows and Visibility
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
Instructions for the author
Authors
Date
2006
Department
Major/Subject
Vuorovaikutteinen digitaalinen media
Mcode
T-111
Degree programme
Language
en
Pages
12+91
Series
Abstract
Pehmeiden varjojen piirto on tärkeä tehtävä tietokonegrafiikassa. Pehmeitä varjoja muodostuu, kun valonlähdettä ei esitetä pisteenä vaan pintana, jolla on nollasta poikkeava pinta-ala. Fysikaalisesti oikeiden varjojen laskennassa pitää määrittää tarkasteltavan pinnan pisteeseen valonlähteestä saapuvan valon määrä. Tämä on yleisesti laskennallisesti raskasta, ja tehokkaat ratkaisumenetelmät ovat tarpeen, jotta kuvan muodostusaika pysyy siedettävänä. Useimmiten lähekkäisten pisteiden vastaanottamat varjot ovat likimain samanlaisia, ja valon- lähteen lähekkäiset osat myös vaikuttavat kuvaan enimmäkseen samalla tavalla. Modernit varjoalgoritmit perustuvat näiden koherenssin muotojen hyödyntämiseen. Tässä työssä esitellään uusi fysikaalisesti oikeiden pehmeiden varjojen laskenta-algoritmi, joka pyrkii hyödyntämään koherenssia niin paljon kuin mahdollista laskemalla varjorelaatiot suurissa ryhmissä sen sijaan, että tarkasteltaisiin yksittäisiä pisteitä valonlähteellä tai varjostettavalla pinnalla. Varjorelaatioiden laskenta suoritetaan hierarkkisesti, ja tehokasta esitystä varjostavista pinnoista ylläpidetään inkrementaalisesti. Algoritmi on yleiskäyttöinen työkalu näkyvyysrelaatiojoukkojen ratkaisemiseen, ja sillä voi olla muitakin käyttökohteita varjojen laskennan lisäksi. Uuden algoritmin yksityiskohtaisen kuvauksen lisäksi työssä analysoidaan useita olemassa olevia fysikaalisesti oikeiden pehmeiden varjojen laskenta-algoritmeja ja luokitellaan ne algoritmisten kompleksisuusluokkiensa perusteella. Työssä esitetään myös kokeellisia tuloksia, joiden avulla voidaan arvioida algoritmin käyttökelpoisuutta erilaisissa laskentatilanteissa.Description
Supervisor
Savioja, LauriThesis advisor
Aila, TimoKeywords
computer graphics, tietokonegrafiikka, soft shadows, pehmeät varjot, visibility computation, näkyvyyslaskenta