Raytracing voor beginners

Zoals eerder beloofd (een paar dagen zijn 2 maanden geworden) zal ik vandaag voor de niet-ingewijden (proberen) uit te leggen wat raytracing is.

Wat is het?
Raytracing is een algoritme om met de computer mooie plaatjes te maken. In computerterminologie wordt dit renderen genoemd. Rasterisation bijvoorbeeld is een ander algoritme dat momenteel gebruikt wordt in computer games en geïmplementeerd is op grafische kaarten.
Het plaatje hieronder is niet echt maar gemaakt met raytracing. Voor meer verbluffende plaatjes gemaakt met raytracing zie de pov-ray hall of fame.

Hoe werkt het?
Het principe is zeer simpel. Om te beginnen hebben we een scène nodig waarvan we een plaatje willen maken, een plaats van waaruit we kijken (het oog, de camera, ...) en het scherm waarop we het plaatje willen tonen.

Om onze scène op het scherm te krijgen "schieten" we een straal (ray) door elke pixel van ons scherm in de scène. We zoeken het dichtsbijzijnde snijpunt met een object uit de scène en geven de pixel de kleur van ons object. We herhalen dit voor alle pixels van het scherm. Nu staat er op het scherm een mooi plaatje van onze scène.

Dit simpel en elegant algoritme is makkelijk te implementeren in computersoftware. Er is echter een zeer fundamenteel probleem, het algoritme is heel traag. Het probleem is het vinden van het snijpunt van de straal en een object uit onze scène. Hiervoor moeten we elk object controleren op snijding met onze straal. In de praktijk zijn alle objecten uit onze scène meestal opgebouwd uit kleine driehoekjes, als je de foto van het konijntje hieronder vergroot dan zie je dat duidelijk. In computer graphics noemen we die modellen meshes (draadmodellen).

Een klein rekenvoorbeeldje om het meer concreet te maken. Stel we willen een plaatje maken van het Stanford Bunny, dit lieve konijntje is opgebouwd uit ongeveer 70.000 driehoekjes. Als we een plaatje willen maken van 1000 x 1000 pixels dan moeten we een straal schieten door 1 miljoen pixels (1000 x 1000 = 1 miljoen). Elke straal moeten we controleren op snijding met elk driehoekje, dit geeft ons 1000 x 1000 x 70.000 = 70 miljoen controles. Als elke controle 1 microseconde (1 miljoenste van een seconde) duurt dan duurt het 70 miljoen * 1 microseconde = 70 seconden = 1.166 minuten voor het hele plaatje. Ter vergelijking in een computer game wordt er gerendered aan 25 beeldjes per seconde dus 0,04 seconden per beeldje.

Conclusie: raytracing is enkel voor geduldige mensen :)

Uiteraard zijn er verschillende technieken ontwikkeld om dit veel sneller te doen maar anno 2008 is dit algoritme nog altijd veel te traag om bijvoorbeeld te gebruiken in computer games. In juni dit jaar hebben enkele Intel werknemers het bekende spel Quake 4 omgebouwd zodat de beeldjes worden gerendered met raytracing. Om 15.2 beeldjes per seconde te renderen zijn er 16 processoren nodig. Voor meer info zie dit artikel.

Mocht het allemaal niet duidelijk zijn laat dan een reactie achter.