Raytracing (3e plaats Van Melsen Prijs 2008)

Leerlingen: Gabe Dijkstra en Robert Hensing
Docent: Jan Debets
School: Christiaan Huygens College

Inleiding

Een belangrijk onderdeel van computer graphics is rendering: het bewerken van driedimensionale vormen tot een tweedimensionale afbeelding.
Raytracing, letterlijk het volgen van stralen, is de oudste renderingmethode. De ideeën die hierbij gebruikt worden zijn gedeeltelijk al in de Renaissance bedacht, toen men onderzoek deed naar perspectief (zie Figuur 1).


Figuur 1: Perspectiefonderzoek

Raytracing is de meest gebruikte methode voor niet-realtime toepassingen, zoals bijvoorbeeld in de films van Pixar die uitsluitend met computers zijn gemaakt. Hiermee kunnen natuurgetrouwe beelden gemaakt worden. Het is wel een berekeningsintensieve methode. Daarom zijn er nog geen realtime toepassingen (zoals videospellen) die raytracing gebruiken: de computers zijn er op dit moment nog te langzaam voor.

Vraagstelling

Hoofdvraag:

  • Kunnen we met behulp van ray-tracing een model maken waarbij we een driedimensionale vorm afbeelden als natuurgetrouw tweedimensionaal plaatje?

    • Theorie

    Rendervergelijking
    De gebruikelijke wijze om dit te modelleren is met behulp van de rendervergelijking. Deze vergelijking beschrijft hoe licht een punt op een oppervlak verlaat aan de hand van de eigenschappen van het oppervlak en de hoeveelheden licht die daar binnenkomen (zie Figuur 2).


    Figuur 2: Variabelen in de rendervergelijking

    De hoeveelheid straling Lu(χ, w) die vanuit het punt χ in de richting w het oppervlak verlaat is de som van de straling die dat punt zelf uitzendt Le(χ, w) en de straling die wordt gereflecteerd Lr(χ, w), dus Lu(χ, w) = Le(χ, w) + Lr(χ, w)

    De gereflecteerde straling Lr(χ, w) is de som van de inkomende straling Li vanuit alle mogelijke richtingen, vermenigvuldigd met de reflectie ƒr en de verdunning n•w' (door de hoek van inval). De rendervergelijking kan geschreven worden als:

    Lu(χ, w) = Le(χ, w) +  ∫ ƒr(χ, w', w)Li(χ, w')(n • w')dw'
      Ω
    Omdat de integraal niet kan worden bepaald, passen we numerieke benaderingsmethoden toe.

    Methoden en resultaat

    Ray-tracing werkt als volgt: het raytracing programma ‘schiet’ voor elk punt van het raster van beeldpunten een straal vanuit de camera door het punt. Vervolgens wordt gekeken of deze straal een object uit de scène snijdt. Als dat het geval is, krijgt het beeldpunt de kleur van het gesneden object (zie Figuur 3).


    Figuur 3: Het principe van raytracing

    In pseudocode ziet het programma er als volgt uit:

    voor elk beeldpunt in raster doe
    begin
    bepaal straal vanuit camera richting raster
    bepaal welk object een snijpunt dichtstbij camera heeft
    als object gesneden
    beeldpunt := kleur van gesneden object
    anders
    beeldpunt := achtergrondkleur van scène
    einde
    Het bovenstaande programma houdt alleen rekening met het omgevingslicht; er wordt aangenomen dat elk punt in de scène even veel licht ontvangt (zie Figuur 4). Het is een benadering van het indirecte licht in de scène. Met directe lichtbronnen en de reflectie daarvan op het oppervlak wordt (nog) geen rekening gehouden.


    Figuur 4: Resultaat van simpele raytracing

    Belichtingsmodel van Phong
    Voor directe lichtbronnen maakt Phong onderscheid tussen diffuse en speculatieve reflectie.
    Matte oppervlakten zoals krijt en papier vertonen diffuse reflectie. Ongeacht van welke hoek je naar een punt op een dergelijk oppervlak kijkt, er komt evenveel licht naar het oog. Het licht wordt in alle richtingen weerkaatst. De intensiteit Id kan worden berekend via Id = kd il cos α, waarbij il staat voor de intensiteit van de inkomende lichtstraal, kd voor de diffuse reflectie van het oppervlak en α voor de hoek van inval.

    Een glanzend oppervlak vertoont speculatieve reflectie. Deze reflectie zorgt bijvoorbeeld voor de glimlichten op auto’s die in de zon staan of de felle reflecties van zonlicht op het natte asfalt als de zon al wat lager staat. Voor dit soort weerkaatsing is de richting w tot de waarnemer dus wel relevant (zie Figuur 5). Nat asfalt is bijvoorbeeld alleen hinderlijk als je tegen de zon in rijdt.


    Figuur 5: Speculatieve reflectie

    Wanneer de reflectiehoek (hoek tussen n en r) en de waarnemingshoek (hoek tussen n en w) gelijk zijn, is de speculatieve reflectie volledig. Als de hoeken niet gelijk zijn, wordt de grootte van de lichtreflectie benaderd door een macht g (> 1) te nemen van r • w. Als deze macht hoger is, krijgen we een kleinere lichtreflectie met een duidelijkere overgang (zie Figuur 6). De vergelijking voor de speculatieve reflectie is Is = kd il (r • w)g.


    Figuur 6: Hoe groter g, hoe kleiner de lichtreflectie

    Als we het omgevingslicht, de diffuse reflectie en de speculatieve reflectie hebben berekend, moeten we ze bij elkaar optellen. Het sommatieteken geeft aan dat we de diffuse en speculatieve intensiteit ten opzichte van elke lichtbron moeten berekenen en al deze resultaten moeten optellen.

    I = Ia + Σ (Id + Is)


    Figuur 7: Een voorbeeld met een directe lichtbron

    In Figuur 7 is te zien dat het somresultaat overbelicht is, omdat we een bereik van [0, 1] hadden verwacht. We hebben dit opgelost door dezelfde som met een factor 0,5 te vermenigvuldigen.

    Om een scène in kleur te belichten, dienen bovenstaande berekeningen driemaal uitgevoerd te worden, namelijk voor elk van de kleuren rood, groen en blauw.

    Anti-aliasing
    Aliasing is het verschijnsel dat door bemonstering de bron niet juist wordt weergegeven. Het meest duidelijke voorbeeld hiervan is de vorming van kartelige randjes bij schuine randen als deze in de vorm van een raster worden bemonsterd. Dit wordt veroorzaakt door het feit dat we van een continu veld naar een discreet veld gaan (zie linkerdeel Figuur 8).


    Figuur 8: Aliasing artefacten en antialiasing

    Per beeldpunt nemen we maar één monster c.q. schieten we maar één straal. Het is dan onvermijdelijk dat we een blokkerig beeld krijgen, maar we kunnen het wel minder blokkerig laten lijken. We kunnen bijvoorbeeld meerdere monsters per beeldpunt nemen en dan het gemiddelde gebruiken. Bij een overgang van zwart naar wit, krijgen we grijze beeldpunten op de grens (zie rechterdeel Figuur 8).

    Per beeldpunt nemen we maar één monster c.q. schieten we maar één straal. Het is dan onvermijdelijk dat we een blokkerig beeld krijgen, maar we kunnen het wel minder blokkerig laten lijken. We kunnen bijvoorbeeld meerdere monsters per beeldpunt nemen en dan het gemiddelde gebruiken. Bij een overgang van zwart naar wit, krijgen we grijze beeldpunten op de grens (zie rechterdeel Figuur 8).

    Als we meerdere monsters per beeldpunt willen nemen, ligt het voor de hand dat we deze monsters regelmatig binnen het vierkant van het beeldpunt nemen. Het beeldpunt wordt weer in een nieuw raster verdeeld met n rijen en n kolommen. Van alle n2 monsters per beeldpunt moeten we dan de kleur optellen en delen door n2, oftewel:

    voor elk beeldpunt (x, y) in raster doe
    begin
    kleur := zwart
    voor i in [0, n) doe
    voor j in [0, n) doe
    kleur := kleur + raytrace(x + i / n, y + j / n)
    kleur beeldpunt := kleur / n2
    einde

    Een andere oplossing is om het aantal monsters aan te passen aan de situatie. Er zijn niet altijd evenveel monsters nodig om een goed beeld van de gemiddelde kleur van een beeldpunt te krijgen. Adaptieve bemonsteringsalgoritmen maken gebruik van de kleurwaarden om een inschatting te maken over de hoeveelheid detail in de bron. Ze nemen geen kennis van de eigenlijke details van bron, maar kijken eerst naar het verschil in kleurwaarde van de omliggende monsters voordat ze naar meer detail zoeken. Een dergelijk algoritme blijft bemonsteren totdat het nemen van extra monsters geen zichtbaar effect meer heeft op het eindresultaat (zie Figuur 9).


    Figuur 9: Het raster past zich aan

    Andere raytracing technieken
    Behalve de bovenstaande technieken hebben we nog veel andere raytracing technieken gebruikt, maar daar gaan we in deze samenvatting niet verder op in. Het gaat bijvoorbeeld om technieken als het beperken van recursie, het benaderen van halfschaduwen, het berekenen van snijpunten (algebraïsch en meetkundig) en het parametrisch beschrijven van driehoeken.

    Als aanvulling staat op http://roberthensing.nl/profielwerkstuk onder andere de broncode van de Huygens raytracer, plus beschrijvingen van de gerenderde scènes en de renderingen/ filmpjes in kleur.

    Figuur 10: Gemaakte rendering Figuur 11: Waar gaat het fout?

    Conclusie

    We hebben gezien hoe we met raytracing technieken de rendervergelijking kunnen benaderen. We hebben een eigen raytracer geschreven; het is dus mogelijk om een model te maken waarbij we een driedimensionale vorm afbeelden als natuurgetrouw tweedimensionaal plaatje.

    Discussie

    Uiteraard zijn er verschijnselen die we niet gemodelleerd hebben. Denk hierbij aan breking van licht bij doorzichtige oppervlakken en andere verschijnselen veroorzaakt door het golfkarakter van licht. Het benaderen van indirecte belichting hebben we helaas vrijwel niet kunnen behandelen.

    Van het schrijven van de raytracer hebben we veel geleerd, omdat je de theorie goed moet begrijpen bij het implementeren en bij het wegwerken van fouten. Want als er een fout in de rendering tevoorschijn komt, is het niet altijd eenvoudig om te achterhalen waardoor dat komt. Soms vind je de reden van die fout zelfs niet na vijf pogingen om iets te verbeteren, maar als je hem dan tóch vindt, is het des te leuker!