Samenvatting werking ERPT

Als voorbereiding voor de presentatie van volgende week, leggen we de werking van ERPT nog eens bondig uit. ERPT staat voor Energy Redistribution Path Tracing. Energy Redistribution is een techniek om gecorelleerde integralen op te lossen. Omdat de waarden in verschillende pixels in een afbeelding het resultaat zijn van gecorelleerde integralen, kunnen we deze techniek gemakkelijk toepassen.

Het algoritme begint met het aanmaken van een pad. Elk pad heeft een bepaalde hoeveelheid energie die overeenkomt met het licht dat door het pad naar de camera vloeit. Door middel van mutaties gaat deze energie worden verdeeld over verschillende pixels. Een pad met hoge energie zal vaker gemuteerd worden, en zal dus meer energie afzetten op het image plane.

Energie verspreid over meerdere pixels

De kost van het vinden van goede paden wordt op deze manier verspreid over meerdere pixels. Globaal gezien gaat er dus minder moeite moeten worden gedaan om goede paden te gebruiken. ERPT steunt dus op het zelfde idee als MLT, waar belangrijke paden beter worden onderzocht.

Als we op deze manier het algoritme uitvoeren krijgen we echter geen correct resultaat. De verkregen afbeelding zal te veel energie krijgen op plaatsen en te weinig op andere, zoals hieronder gedemonstreerd :

Foute verspreiding van energie (links), referentie (rechts)

Het probleem is dat wanneer energie uit een bepaalde pixel gaat afgezet worden in andere pixels, er geen garantie is dat hij ook genoeg energie terugkrijgt van de andere pixels. Om het algoritme correct te houden moet de pixel evenveel energie terugkrijgen als dat hij weggeeft. Dit heet general balance. Een strengere voorwaarde is detailed balance. Hierbij moet de energie die van pixel x naar naar pixel y vloeit gelijk zijn aan de energie die van pixel y naar pixel x vloeit. Detailed balance garandeert general balance en is gemakkelijker af te dwingen.

Afbeelding uit : [CTE 05]

Concreet kan men detailed balance afdwingen door niet alle mutaties te aanvaarden, maar sommige nieuwe paden te verwerpen. Dit gebeurt aan de hand van de 'acceptance probability'. Deze waarde houdt rekening met de kans dat het gemuteerd pad terug gaat bijdragen tot het oorspronkelijk pixel, en steunt dus op detailed balance. Wanneer men deze acceptance probability correct toepast krijgt men betere resultaten :

Juiste verdeling van de energie (links) + referentie (rechts)

In tegenstelling tot MLT is dit algoritme wel goed te stratificeren, doordat de initiele paden op een gestratificeerde manier op het image plane worden gegenereerd. Omdat we veel initiele paden nemen, vermijden we de startup bias van MLT, en bovendien is het niet nodig om een volledige set mutaties te nemen. Dit maakt het algoritme een stuk eenvoudiger dan MLT.

Verslag deze week

Deze week hebben we ons vooral beziggehouden met het maken van onze volgende presentatie. Wegens het drastisch wijzigen van de presentatievorm hebben we er langer aan gewerkt dan voorzien. Ook veel tijd is gestoken in het renderen van prentjes die gebruikt moeten worden in de presentatie :

- Een zelfde scene, maar met verschillende parameters (om de invloed van parameters te bestuderen)
- Een paar goede referenties van onze scenes

Een paar prentjes die we niet willen achterhouden (bedoeld als referenties) :

Rendertijd : ongeveer 66h met een path tracer (512 x 512 samples per pixel)

Rendertijd : ongeveer 16h met een path tracer (256 x 256 samples per pixel)

Nieuwe mutaties vs. Path tracer

Scene gerender met een path tracer
Rendertijd : ongeveer 8min 30s

Scene gerenderd met ERPT (nieuwe mutaties)
Rendertijd : ongeveer 10 min

Bij de gewonde path tracer zien we vooral gelijkmatig verspreidde ruis. Bij de ERPT render is er minder ruis, maar is de belichting meer geclusteerd. Voor de rest is het verschil in kwaliteit vrij klein.

Andere kleine nieuwigheden

Nu we scenes zoals de bunny scene gebruiken om te testen, hadden we nood aan een betere versnellingsstructuur. We hebben de grid accelerator vervangen door een kd-tree (implementatie overgenomen van luxrender en aangepast aan onze raytracer). De bunny scene rendert nu ongeveer een factor 3 sneller.

Een tweede aanpassing is het aanpassen van de BSDF sampling. Een BSDF bestaat uit een lijst van verschillende componenten (BRDF's en BTDF's). Bij het samplen van een BSDF werd vroeger uniform één van de componenten gekozen. Dit is suboptimaal. Het is beter om ook hier importance sampling op toe te passen. Nu krijgt elke component van de BSDF een gewicht mee, afhankelijk van de hoeveelheid licht dat wordt gereflecteerd door de component en de vector waarlangs het licht invalt. Aan de hand van deze gewichten kan een pdf worden geconstrueerd, en gebruik makende van deze pdf wordt een component geselecteerd.

Dit levert vooral voordelen op bij bijvoorbeeld een glazen bol, waar de verhouding tussen de reflectie en de transmissie sterk varieert over het oppervlak (afhankelijk van de fresnel distributie). Het effect is wel moeilijker te illustreren om dat de verschillen redelijk klein zijn in de meeste gevallen, en een geoefend oog nodig hebben om herkend te worden.

Nieuwe mutaties

Omdat we caustic perturbations niet juist hebben gekregen, hebben we besloten om een ander type mutaties te gebruiken in ons algoritme. Deze mutaties staan beschreven in de volgende paper : A Simple and Robust Mutation Strategy for the Metropolis Light Transport Algorithm. Deze mutaties worden niet gedaan in de ruimte van paden, maar in de ruimte van random getallen.

Om dit te kunnen doen wordt een path eerst getransformeerd naar de ruimte van random getallen. Daarna worden de verkregen random getallen gemuteerd. Op het einde wordt de nieuwe reeks random getallen weer getransformeerd naar een path.

Het voordeel van deze nieuwe methode is dat ze zeer robuust en eenvoudig te implementeren is. Een groot bijkomend voordeel is dat de acceptance probability zeer gemakkelijk te bepalen is, wat bij caustic perturbations voor ons zeer moeilijk bleek te zijn. Het nadeel is dat elke mutatie opnieuw een geheel path moet construeren. Er is dus geen sprake van hergebruik van vorige paden, wat wel het geval was bij lens en caustic perturbations. Dit maakt deze methode inherent trager.

We hebben onze ERPT implementatie aangepast om ook dit nieuw type mutatie te gebruiken. Hieronder volgen een aantal resultaten :

Scene op (relatief) lage kwaliteit

De zelfde scene op hogere kwaliteit

De bunny scene met dit keer juiste caustics

Op deze afbeeldingen is ook te zien dat bepaalde nadelen, (zoals de vlekken in de hoeken van de box) grotendeels verdwenen zijn. Dit is te danken aan het feit dat nu de mutaties van dit soort paden ook een hoge acceptance probability krijgen. De paar vlekken die nog te zien zijn, zijn te wijten aan caustics.

Nieuwe scenes

Om ons algoritme verder te testen hebben we een paar nieuwe scenes met lastige belichtingssituaties gemaakt. De eerste bevat een glazen "Stanford Bunny", waarmee we nagaan of ons algoritme met grotere aantallen primitieven (in dit geval ongeveer 70000) kan omgaan. Deze scene kan vooral ook gebruikt om de complexere caustics te evalueren.

Referentie met path tracer

Gerendert met Erpt (vrij lage kwaliteit en foute caustics)

Een tweede scene wordt de lichtbron en een box geplaats die enkel open is aan de bovenkant. De scene wordt hierdoor bijna alleen indirect verlicht.

Referentie met Path tracer

Gerenderd met ERPT in zelfde rekentijd

Voor de laatste scene kunnen we zien dat ERPT duidelijk beter presteert. Enkel de hoeken blijven een pijnpunt.

Debug tijd: Speculaire objecten

We zijn er in geslaagd om voor lens perturbations de acceptance probability op een correcte manier te evalueren. Voor caustic perturbations is dit echter niet gelukt. We hebben de auteurs van de relevante papers gecontacteerd om meer inzicht te krijgen in deze materie, maar hebben tot nu toe geen bevredigend antwoord gekregen. Voorlopig zitten we daar klem. Als alternatief gaan we een ander soort mutatie implementeren (zie een latere blog post).

We geven nog enkele afbeeldingen die gebruik maken van onze verbeterde lens perturbations. We zien enkel de paden van de vorm ESD... en ESSD... Een aantal types paden ontbreken, maar om de correctheid van lens perturbations vast te stellen is dit voldoende.

Referentie door pathtracer

Afbeelding gerendert met Erpt

We zien dat qua belichting de twee beelden nagenoeg identiek zijn op een paar artifacten na. We zien ook dat het beeld gerenderd door Erpt veel minder ruis bevat voor ongeveer de zelfde rekentijd. Gelijkaardige tests voor de caustic perturbations zijn helaas gefaald.

Debug tijd : Diffuse scenes

Na het correct evalueren van de directe belichting bleek het vrij eenvoudig om op een correcte manier diffuse scenes te renderen (inclusief indirecte belichting).

Diffuse scene gerenderd met onze ERPT implementatie.

Diffuse scene gerenderd met een standaard path tracer

Deze scenes zijn nagenoeg gelijk. Bij ERPT zien we in de hoeken nog te heldere pixels. Deze artifacts zijn inherent aan het algoritme, en dus moeilijk te verwijderen op een elegante manier. Ze zijn een gevolg van een zeer grote geometrische term in het oorspronkelijk pad, waardoor de acceptance probability van mutaties zeer laag is. Hierdoor blijft het pad steeds in dezelfde pixel, en zet het daar al zijn energie af.

Op deze moment zijn we nog bezig met het aanpassen van de acceptance probabilities voor paden die speculaire nodes bevatten. To be continued...

Debug tijd : Directe belichting

Bij het vergelijken van de resultaten van ons ERPT algoritme met die van een path tracer, zijn we tot de conclusie gekomen dat de belichting fout was. Om de fout in onze implementatie te vinden hebben we op een systematische manier de mutaties gedebugd. We zijn hiermee begonnen door enkel directe belichting in overweging te nemen. Dit is een van de eerdere resultaten :

Afbeelding gerenderd met foutieve ERPT implementatie.

Hier is te zien dat de belichting geconcentreerd is in het midden van de muren. De sterkte en grootte van de lichtvlekken zijn afhankelijk van de perturbatie grootte. Om dit heel duidelijk te maken hebben we een zeer grote perturbatie gekozen. De volgende afbeelding is een reference image, gerenderd met een standaard path tracer. Dit is hoe de directe belichting er uit zou moeten zien :

Afbeelding gerenderd met een path tracer

Onze conclusie was dat er iets fout was met de waarschijnlijkheid waarmee mutaties aanvaard worden. Mutaties naar het centrum van de muren toe werden meer aanvaard dan zou mogen. Het voorgaande ging enkel over caustic perturbations, maar lens perturbations vertoonden ook gelijkaardige problemen.

Bij het nader bekijken van de formules voor het berekenen van de acceptance probabilities in de relevante papers, bleek dat deze formules niet consistent zijn. Het is ook moeilijk om de oorsprong van deze formules te achterhalen. In een poging om meer duidelijkheid te scheppen hebben we de schrijvers van de ERPT paper gecontacteerd. Op basis van hun advies en onze eigen intuïtie zijn we er in geslaagd om juiste resultaten te verkrijgen in het geval van directe belichting. Deze resultaten zijn nagenoeg gelijk aan dat van de path tracer (op wat ruis na).

Eerste resultaten ERPT

De volgende mijlpaal bij het implementeren van PMC-ER is het maken van een werkende ERPT implementatie. Door dit te doen kunnen we onze mutatie code vroeger debuggen. Deze week hebben we ons daarmee bezig gehouden. Dit zijn de eerste resultaten :

Rendertijd : ongeveer 3 minuten

Op de platte oppervlakken is het te zien dat er over het algemeen minder ruis is, maar dat er wel vlekken en clusters voor in de plaats zijn gekomen. Deze ruis is het sterkst aanwezig in hoeken en grensvlakken.

Rendertijd : ongeveer 35 minuten

In deze afbeelding is nog steeds ruis in de hoeken te zien, maar de oppervlakken zijn wel mooi 'glad'. Verder is de rendering op bepaalde plaatsen nog iets te donker, wat er op wijst dat er nog enkele foutjes in de code zitten. Deze week gaan we ons vooral bezighouden met het debuggen van de mutatiecode.

Rendertijd : ongeveer 45 minuten

In deze rendering zien we dat de caustics aanwezig zijn (al zien ze er niet uit zoals ze moeten). Ook de reflectie en de refractie zijn min of meer geslaagd en bevatten relatief weinig ruis. Toch zijn er nog een aantal fouten te zien : Vlekken op de muren, slecht gevormde caustics, te heldere reflecties, en op sommige plekken is de afbeelding weer te donker.

Zoals reeds vermeld gaan we deze week proberen om de oorzaken van deze fouten te vinden (en op te lossen). Verder gaan we ook nog wat experimenteren met de parameters van het algoritme om te zien wat de beste resultaten geeft.

Updates implementatie

In onze vorige post hebben we het resultaat van een eenvoudige pathtracer (volgens de path integraal formulering) getoond. Bij het vergelijken ervan met reference images gerenderd met een standaard path tracer hebben we echter gemerkt dat het resultaat niet volledig overeen kwam. De randen van de afbeelding bleken onder andere te licht te zijn. We vermoeden dat dit komt doordat de pdf niet altijd juist geevalueerd werd.

De laatste week hebben we onder andere een nieuwe path sampling methode geschreven. Deze werkt ongeveer als volgt :

• Een path wordt geconstrueerd in de scene en beëindigd met russian roulette.
• Vervolgens proberen we elke node in dit path expliciet met een lichtbron te verbinden.
• We checken dan of het resulterende path geldig is : of het licht de camera wel kan bereiken.
• Uit alle geldige paden kiezen we er willekeurig een uit.
  

Deze methode heeft als voordeel dat er met grotere kans een geldig path wordt gekozen, en de pdf's zijn eenvoudig te berekenen. Nadeel is dat er iets te veel werk wordt uitgevoer voor paden die later niet gaan worden gekozen. Dit is echter geen al te groot probleem, omdat slechts een klein deel van de paden die geëvalueerd gaan worden op deze manier worden aangemaakt.

Hier is een rendering die gebruikt maakt van deze sampling methode. Links is de afbeelding gerenderd met onze nieuwe path sampler.

Dit is een afbeelding van ongeveer dezelfde kwaliteit, gerenderd met een standaard geoptimaliseerde path tracer. (implementatie van PBRT)







Verder hebben we ook een aantal andere zaken gedaan deze week zoals het begin van de implementatie van lens perturbaties.

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.