Eerste fase implementatie

De eerste fase van de implementatie was het implementeren van een simpele path tracer. Het verschil met een gewone path tracer is echter dat we eerst actief een path construeren, en dat daarna evalueren. Een path is hierbij gelijk aan

• Een punt op de camera lens
• Een aantal diffuse / speculaire botsingen
• Een punt op een lichtbron
  

Dit algoritme is natuurlijk inefficiënter dan een gewone, geoptimaliseerde path tracer, maar het vormt wel de basis voor de rest van het algoritme. Belangrijke zaken die we bij PMC-ER gaan nodig hebben zijn immers

• Path sampling
• Path evaluatie
  

welke nu beide geïmplementeerd en getest zijn.

Het resultaat kan hier worden gezien :


Een aantal andere zaken die we hebben gedaan zijn

• De high-level structuur van het algoritme geïmplementeerd : loopen over iteraties, bepalen hoeveel paden moeten worden geëlimineerd/geregenereerd, ...
• Stratified Sampling over het Image Plane
• Het normaliseren van de afgezette energiewaarden. Bij een gewone path tracer gebeurt dit per pixel. Bij ons algoritme moet dit gebeuren over het hele image plane.

De volgende stappen voor het implementeren van PMC-ER zijn nu :

• Schatten van de gemiddelde energie per path E, en de waarde ed.
• Het afzetten van energie op het Image Plane
  
• Het implementeren en evalueren van mutaties op paden.

Hierna kunnen we een versie van het ERPT algoritme construeren, zodat we opnieuw onze code kunnen testen.

Verslag deze week

Deze week hebben we vooral de papers over MLT (Metropolis Light Transport), ERPT (Energy Redistribution Path Tracing) en PMC-ER (Population Monte-Carlo Energy Redistribution) bekenen.

MLT zal door middel van mutaties paden met een grote bijdrage die moeilijk te vinden zijn grondiger onderzoeken. Voor scenes met lastige belichting (sterke indirecte belichting, (onrechtstreeks waargenomen) caustics, ...) heeft dit een veel betere convergentie tot gevolg.

ERPT tracht een van de zwakke punten van MLT, de startup bias, op te lossen. Concreet betekent startup bias in het geval van MLT dat er veel samples moeten genomen worden vooraleer de verwachte waarde van de schatter de oplossing genoeg benadert. Door een gewone path tracer uit te breiden met mutaties in ERPT, wordt de startup bias geelimineerd, terwijl ze toch het lokaal onderzoeken van interessante lichtpaden blijft ondersteunen. De term Energy Redistribution komt voort uit het feit dat een filter wordt gebruikt om informatie uit pader te verdelen over verschillende pixels (op een unbiased manier).

Bij ERPT worden echter een aantal belangrijke parameters vastgelegd, zoals de grootte van de perturbaties op paden. Dit is niet optimaal. Paden die bijvoorbeeld op schaduwgrenzen uitkomen zouden kleinere mutaties moeten krijgen dan paden die bijvoorbeeld in het midden van een diffuus vlak vallen. PMC-ER gaat er voor zorgen dat het algoritme zelf deze parameters aanpast.

Het algoritme werkt in grote lijnen als volgt : Het algoritme verloopt in verschillende iteraties. Er wordt een populatie van n paden bijgehouden die elk een zeker hoeveelheid energie bevatten. Elke iteratie wordt Energie uit deze paden door middel van mutaties en een ER filter verdeeld over verschillende pixels. Paden die reeds goed onderzocht zijn (die al veel energie op het beeld hebben afgezet) en paden die slechts een kleine bijdrage aan het beeld leveren, hebben een grotere kans om na elke iteratie tijdens een resampling stap te worden vervangen door nieuwe paden. In het begin van elke iteratie worden de parameters op basis van de vorige iteraties ingesteld.

We gaan voor deze thesis proberen PMC-ER te implementeren.

PBRT werkt !

Een aantal dagen geleden is het gelukt om PBRT te compileren op Windows met Visual Studio 2008. Hier is de eerste render met PBRT (simple.pbrt file) :

Nu rest alleen nog de taak om een nieuw algoritme te implementeren. Daarover meer in de volgende post.

Interessante papers

We hebben een aantal papers geselecteerd die ons interessant lijken :

• Metropolis Light Transfer : paper
  Dit is een unbiased techniek die voortbouwt op (bidirectional) path tracing, en Metropolis sampling en path mutaties gebruikt om interessante lichtpaden te selecteren.
  
• ERPT : paper
  Dit algoritme is gelijkaardig aan MLT, maar gebruikt Energy Redistribution sampling om de rendering equation op te lossen. ERPT is ook unbiased.
  
• PMC-ER : paper
  Dit algoritme is gelijkaardig aan ERPT, maar het gebruikt het Population Monte Carlo framework om de render efficientie te verbeteren. Dit is de meest recente techniek (2007) van de drie en lijkt ons dus het interessantst.
  
• Multidimensional Lightcuts : paper
  Dit algoritme is een uitbreiding van het lightcuts algoritme waarbij niet enkel een light tree wordt geconstrueerd, maar per pixel ook een gather tree. Van de combinatie van die twee trees kunnen dan cuts worden genomen.
  
• Re-Using Paths : paper
  Dit algoritme versnelt path tracing door paden te hergebruiken. Op die manier levert elk light path een bijdrage aan verschillende screen pixels.
  

Eerste conclusies van literatuurstudie

Op basis van de papers die we gelezen hebben kunnen we het Global Illumination domein op verschillende manieren indelen. Een van deze manieren is het onderscheid tussen biased en unbiased algoritmen.

• Bij biased algoritmen wordt correctheid opgeofferd aan minimale rekentijd. Bias wil concreet zeggen dat de verwachte waarde van de schatter niet gelijk is aan de oplossing van de rendering equation. Sommige van deze technieken kunnen onder andere gebruikt worden voor interactieve toepassingen.
• Unbiased technieken daarentegen specialiseren zich in het berekenen van de correcte oplossing van de rendering equation (dus waarbij de verwachte waarde van de schatter niet afwijkt van die van de integraal). Dit zijn meestal variaties en uitbreidingen op het klassieke path tracing algoritme. Dit algoritme wordt in recente algoritmen uitgebreid met variantie reductie en path reuse technieken. Voorbeelden van variantie reductie technieken zijn importance sampling en adaptive sampling. Path reuse algoritmes gaan rekentijd uitsparen door bepaalde paden of deelpaden te herbruiken.

Concrete en bekende voorbeelden van unbiased algoritmen zijn 'bidirectional path tracing' en 'Metropolis Light Transport'. Veel van de recentste technieken zijn gelijkaardig aan Metropolis Light Transport, maar brengen aanzienlijke verbeteringen.

Voorlopig zijn we van plan om een recent unbiased algoritme te selecteren voor onze thesis. In een volgende post zullen we een aantal mogelijke kandidaten bespreken.

Welkom

Welkom op onze thesis blog. Hier gaan wij de vooruitgang van onze thesis weergeven.

Het thema van onze thesis is 'Geavanceerde Globale Belichting'. Dit is natuurlijk een ruim vakgebied, dus de eerste stap is het selecteren van een interessant algoritme om te implementeren. Het is de bedoeling om dit algoritme als plug-in in PBRT implementeren. Daarna kunnen we eventueel nog een aantal kleine aanpassingen maken of optimalisaties toevoegen.