An Incremental Shaft Subdivision Algorithm for Computing Shadows and Visibility

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