3D Computer graphics zijn niet meer weg te denken in de media. Computer spelletjes zijn geëvolueerd van de tweedimensionale Pacman tot volledig ruimtelijke spellen die zich in een stad of land afspelen en die je met honderd medespelers tegelijk speelt. In films en televisieseries maakt men veelvuldig gebruik van virtuele decors, virtuele acteurs en speciale effecten. Soms zijn de beelden zelfs volledig met de computer gemaakt.

Veel mensen zijn inmiddels bezig met het maken van 3d-beelden met behulp van 3d-pakketten als Maya, 3dStudio, Cinema 4d, Povray etc. Een enkeling schrijft zijn eigen hi-end render engine in de programmeertaal C(++) of gebruikt Macromedia Flash voor het genereren van 3d-beelden met behulp van de programmeertaal Actionscript.

Dit artikel is bedoeld voor iedereen die geïnteresseerd is in de achterliggende theorie van 3d computer graphics. Hoe komen die 3d-beelden waarmee we overspoeld worden eigenlijk tot stand? Wat zitten daar nou voor berekeningen achter? Welke processen zitten er achter veelgebruikte opties in de 3d-programma’s? En wat bedoelen ze met al die ingewikkelde termen die ik zie in mijn 3d-programma?

De basistheorie van 3d is minder ingewikkeld dan je zou verwachten. Een groot deel van de technieken is bedacht in de jaren zeventig van de vorige eeuw of zelfs eerder, en de basistheorie is ook zonder veel kennis van wiskunde goed te begrijpen. Vuistregel is dat de complexiteit toeneemt naarmate snelheid en beeldkwaliteit/realisme een belangrijke rol gaan spelen.

Natuurlijk kan ik binnen een artikel als dit niet alle onderwerpen die met 3d te maken hebben uitleggen. Ik zal het dan bijvoorbeeld ook niet hebben over onderwerpen als radiosity, texture mappings, particles etc. En om je niet direct te intimideren met wiskunde/algoritmes heb ik de hoeveelheid formules in dit artikel zo minimaal mogelijk gehouden. Bedenk wel dat computer graphics tot stand komen door miljoenen (vaak complexe) berekeningen, dus we zullen er niet onderuit kunnen om af en toe iets moeilijks te behandelen.

Wat gaan we doen?

Ik begin dit artikel met beschrijven wat een polygoon is. Vervolgens ga ik in op hoe een polygoon verwerkt wordt binnen een render engine. Hoe weet je welke polygonen van een object zichtbaar zijn en welke niet? Hoe weet je welke (delen van) een polygoon een andere polygoon overlappen?

De volgende stap is het belichtingsmodel: welke intensiteit heeft een bepaalde polygoon als gevolg van onze lichtbron(nen) en hoe bereken je dat?

Met onze nieuwe kennis over polygonen en het belichtsmodel kijken we naar schaduw en reflecties – allebei natuurlijk heel belangrijk om overtuigende 3d-beelden te maken. Schaduw en reflectie zijn allebei gebaseerd op berekeningen die kijken of lichtstralen snijden met één of meerdere polygonen binnen de virtuele ruimte.

Voor het berekenen van schaduw en reflecties moet je complexe berekeningen maken met grote hoeveelheden data (het zogenaamde numbercrunching) waardoor rendertijden exponentieel toenemen. Door middel van octrees en voxels (hierover later uiteraard meer) kan het aatal berekeningen aanzienlijk gereduceerd worden.

Polygonen

Eerst maar eens beginnen met de basis-bouwstenen van 3d-afbeeldingen: polygonen. Polygonen bestaan uit een oppervlak omsloten door een aantal hoekpunten. In de meeste gevallen worden drie hoekpunten gebruikt, omdat een oppervlak met drie hoekpunten altijd vlak is. Vier hoekpunten zijn direct al veel moeilijker te positioneren voor het verkrijgen van een vlakke polygoon. Een ander voordeel van het gebruik van driezijdige polygonen is uniformiteit: de meeste render engines hebben als input driezijdige polygonen nodig.

Voor standalone projecten (bijv. een Flash-animatie) is het geen vereiste om driezijdige polygonen te gebruiken. Wanneer je binnen een Flash-animatie een kubus wilt renderen is het efficiënter om één vierzijdige polygoon te renderen dan twee keer een driezijdige polygoon.

Een hoekpunt van een polygoon moet minimaal een horizontale (x) en verticale (y) positie bevatten. En als we bezig zijn met een 3d-afbeelding moet elke polygoon ook een positie bevatten voor de diepte (z). Naast deze basale informatie wordt vaak informatie van de normaal (waarover dadelijk meer) opgeslagen en eventueel andere informatie met betrekking tot de polygoon.

Een 3d-model bestaat al gauw uit (tien)duizenden polygonen (zie afbeelding).

De polygonen van een 3d-model worden opgeslagen in bestandsformaten als .DXF (Drawing Interchange Format), .3DS/.MAX (3D-Studio), en .OBJ (Wavefront/Alias Technologies).

Voor elke willekeurige horizontale en verticale positie (x,y) binnen het oppervlak van de polygoon is de exacte z-positie (diepte) te bepalen door middel van interpolatie. Wat is dat?

De informatie van de hoekpunten van een polygoon gebruiken we als basis. We willen de z-positie bepalen van op het kruisje (x,y) in de afbeelding. We beginnen met van dat kruisje de horizontale en verticale positie te bepalen. Vervolgens wordt een denkbeeldige horizontale lijn getrokken door deze posities (zie afbeelding). De volgende stap is het bepalen met welke zijden van de polygoon de denkbeeldige horizontale lijn snijdt. In het voorbeeld is dat aan de linkerzijde het lijnstuk van hoekpunt nul naar hoekpunt een. Rechts snijdt de denkbeeldige lijn met het lijnstuk dat hoekpunt een en twee verbindt.

Met behulp van de verhouding a en b en de verhouding c en d wordt de zogenaamde interpolatie lambda bepaald. Deze interpolatie lambda gebruiken we voor het berekenen van de exacte posities van x en z op de linker- en rechterpositie waar de denkbeeldige horizontale lijn snijdt.

De exacte x- en z-positie zijn nu bekend voor zowel de linker- als rechterpositie. Door de verhouding a en b wederom te gebruiken (dit keer horizontaal) kunnen we met behulp van interpolatie de exacte x- en z-positie bepalen. De x-positie komt overeen met de gekozen horizontale positie en hoeven we in deze laatste fase niet te berekenen, omdat hij al bekend was.

Voilà: we weten de exacte z-positie van op het kruisje! En door deze procedure te herhalen kunnen we de z positie berekenen voor elke positie binnen de polygoon.

Normaal

De normaal is een veel gebruikte en belangrijke eigenschap van een polygoon: je hebt hem nodig om te bepalen of een polygoon zichtbaar is voor de toeschouwer en/of lichtbronnen, voor het bepalen van de lichtintensiteit en voor het berekenen van snijpunten die je weer nodig hebt voor het uitrekenen van schaduwen, reflecties en refracties.

De normaal (ook crossproduct genoemd) berekenen we met behulp van de x, y en z-posities van de hoekpunten van een polygoon. De normaal is een vector (een rechte lijn met een begin positie (x,y,z) en een eind positie (x,y,z)) die loodrecht op het oppervlak van de polygoon staat.

De normaal wordt per polygoon eenmalig berekend en bewaard, net als de x, y en z-posities van de hoekpunten van een specifieke polygoon.

De oriëntatie van de normaal van een polygoon is afhankelijk van de ‘draairichting’ van de hoekpunten van de polygoon (zie afbeelding).

De orientatie van de normaal draait honderdtachtig graden wanneer een polygoon ‘linksdraaiend’ of ‘rechtsdraaiend’ is.

Alle polygonen moeten óf rechtsdraaiend óf linksdraaiend zijn, anders worden ze niet correct verwerkt binnen een render engine.

Gemiddelde normaal

De gemiddelde normaal staat (in tegenstelling tot wat je zou vermoeden door de naam) in veel gevallen niet loodrecht op het oppervlak van een polygoon.

De gemiddelde normaal gebruiken we voor het berekenen van de intensiteit met behulp van phong shading (komen we nog op terug). De normaal loodrecht op het oppervlak van een polygoon wordt binnen de render engine onder andere gebruikt voor het bepalen van de zichtbaarheid van de polygoon en intersectieberekeningen.

De normaal wordt per polygoon eenmalig berekend en opgeslagen bij de x, y en z-positie van elke afzonderlijke hoekpunt. Voor elk afzonderlijk hoekpunt bepalen we vervolgens welke polygonen een hoekpunt hebben met dezelfde positie. De normalen van polygonen met hetzelfde hoekpunt worden opgeteld en gemiddeld, en dat is de gemiddelde normaal.

De gemiddelde normaal kan per hoekpunt binnen een polygoon van orientatie variëren, maar de werkelijke normaal van een polygoon staat uiteraard nog altijd loodrecht op het oppervlak van de polygoon.

Belichting

Afhankelijk van het gebruikte belichtingsmodel (waarover dadelijk meer) wordt de intensiteit/kleur van een polygoon berekenend met behulp van een aantal afzonderlijke componenten. Deze componenten zijn ambient, diffuus en specular. Door de verhouding tussen de afzonderlijke componenten te variëren kun je eigenschappen van fysieke materialen benaderen.

Ambient

De intensiteit van een polygoon als gevolg van indirect licht: licht dat verstrooid wordt door de omgeving. De component ambient is in de drie genoemde belichtingsmodellen een constante.

Diffuus

De intensiteit van de polygoon wordt voor een groot deel bepaald door de hoek tussen de normaal van de polygoon en de lichtbron te berekenen. In computer graphics termen noemen we dat diffuus.

Specular(of hooglicht)

De hoek tussen het oog van de toeschouwer en de op het oppervlak van de polygoon gereflecteerde lichtstraal (afkomstig van de lichtbron).

Belichtingsmodel

Er zijn diverse manieren bedacht om de intensiteit van een polygoon te berekenen als gevolg van belichting met een virtuele lichtbron. De manier waarop de intensiteit van een polygoon berekend wordt, noemen we ook wel het belichtingsmodel. De meest gangbare belichtingsmodellen zijn flat shading, gouraud shading en phong shading.

Flat shading

Flat shading is een eenvoudig en weinig rekenintensief belichtingsmodel.

Bij flat shading berekenen we met behulp van de normaal de component diffuus. Eventueel combineren we dat met de component ambient om de intensiteit van de polygoon te berekenen.

De intensiteit wordt eenmalig per polygoon berekend. Het oppervlak van de polygoon heeft een egale intensiteit waardoor het object er hoekig uitziet. Omdat een polygoon een volledig egale intensiteit heeft wordt flat shading ook wel constant-intensity shading genoemd.

Voor het berekenen van de intensiteit gaan we uit van een lichtbron die zich op een oneindige afstand van de te berekenen polygoon bevindt.

Onderstaande afbeelding laat het 3d model zien waarbij ik per polygoon de normaal zichtbaar gemaakt heb. De normaal is in de afbeelding in het centrum van de polygoon gepositioneerd.

Deze afbeelding heb ik gerenderd met flat shading:

Gouraud shading

Gouraud shading is een iets complexer belichtingsmodel dan flat shading.

Per hoekpunt wordt met behulp van de normaal de component diffuus berekend. Door middel van interpolatie berkenen we daarna (met behulp van de berekende intensiteiten van de hoekpunten) de intensiteit van elke positie van de polygoon. Gouraud shading wordt ook wel intensity-interpolation genoemd.

Bij flat shading heeft het hele oppervlak van de polygoon de zelfde intensiteit. Maar als je Gouraud shading toepast kan het oppervlak een polygoon variënde intensiteiten hebben, afhankelijk van de intensiteiten van de verschillende hoekpunten.

Phong shading

Het meeste gangbare belichtingsmodel is Phong shading, genoemd naar Bui-Tuong Phong. Phong shading levert het beste resultaat tegen een acceptable rekentijd.

Net als bij flat shading en Gouraud shading wordt voor de berekening van de intensiteit van een polygoon gebruik gemaakt van de normaal. Bij Phong shading wordt echter niet de werkelijk normaal van de vlakke polygoon gebruikt, maar de gemiddelde normaal.

Bij Gouraud shading berekenden we per hoekpunt de intensiteit. Vervolgens werd de berekende intensiteit door middel van interpolatie gebruikt voor het bepalen van de intensiteit van het oppervlak van de polygoon.

Bij Phong shading wordt niet de intensiteit van de hoekpunten geïnterpoleerd, maar de gemiddelde normaal. De geïnterpoleerde gemiddelde normaal wordt vervolgens gebruikt voor het berekenen van de intensiteit. Phong shading wordt ook wel normal-vector interpolation shading genoemd.

Per positie op het oppervlak van een polygoon wordt een aparte intensiteitsberekening uitgevoerd met de componenten ambient, diffuus en specular. Door per positie de intensiteit te berekenen kan de component specular nauwkeurig en realistisch berekend worden.

De onderstaande afbeelding toont de gemiddelde normalen van het 3d-object.

Onderstaande afbeelding is gerenderd met Phong shading. Door gebruik te maken van een gemiddelde normaal per hoekpunt vloeien de intensiteiten van de afzonderlijke polygonen naadloos in elkaar over. Het 3d-object is nog steeds even hoekig als het 3d object gerenderd met flat shading, maar het lijkt optisch veel verfijnder te zijn.

Ambient, diffuus, specular

Door de verhouding ambient, diffuus en specular te variëren in combinatie met een eenvoudig herberekening van diffuus en specular, kun je de manier waarop fysieke materialen op licht reageren nabootsen.

Voor het berekenen van diffuus en specular wordt de hoek bepaald, wat resulteert in een getal van -1.0 tot 1.0. Hierbij zijn alleen waarden van 0.0 tot 1.0 van belang. Zodra de hoek tussen de normaal en de lichtbron namelijk groter is dan negentig graden (het resultaat van de hoek berekening is kleiner dan 0.0) kan de polygoon niet meer belicht worden: lichtstralen kunnen geen bocht maken!

De waarde die de berekening van de hoek oplevert bepaalt de intensiteit van de component diffuus en specular. Wanneer de hoek die de normaal maakt met de lichtbron gelijk is aan nul, is het resultaat van de hoekberekening gelijk aan 1.0. Dit is de maximale waarde. Die positie is vergelijkbaar met de positie op de evenaar op aarde: de zon (lees de lichtbron) staat recht boven je. Wanneer het resultaat van de hoek berekening gelijk is aan 0.5, bedraagt de hoek tussen de normaal en de lichtbron zestig graden: de intensiteit is dan gehalveerd.

De volgende grafiek toont de intensiteit (verticaal) uitgezet tegen de hoek (horizontaal).

Door het resultaat van de hoekberekening als basis te gebruiken in een nieuwe berekening, kunnen we het verloop van de intensiteit aanpassen. Als je een exponent gebruikt kan de curve uit de grafiek aangepast worden. En door de waarde van het exponent te wijzigen, wijzigt de oorspronkelijke waarde van de component diffuus en specular.

Door een exponent te gebruiken die kleiner dan 1.0 is, neemt de oorspronkelijk berekende waarde voor een specifieke hoek toe. Door een exponent te gebruiken groter dan 1.0 neemt de oorspronkelijk berekende waarde af. Wanneer de exponent gelijk aan 1.0 is, blijft de oorspronklijk berekende intensiteit gelijk.

Onderstaande afbeelding toont een aantal varianten van dezelfde afbeelding telkens met verschillende herekeningen van diffuus en specular, waardoor het 3d-object steeds anders op licht reageert. De positie van de lichtbron is in alle voorbeelden ongewijzigd, evenals het 3d-object. Alleen de exponent voor de herberekening van de component diffuus en specular is elke keer anders.

Even ademhalen

Zo, we hebben al veel geleerd over 3d-afbeeldingen. Tijd om de armen en de benen even te strekken tijdens een korte pauze en dan verder te gaan met deel twee van dit artikel. Daarin zullen we het hebben over z-buffers, schaduw, weergeven van harde, spiegelende oppervlakten en manieren om efficiëntere berekeningen te maken.

Z-buffer

Het renderen van een polygoon in een programma’s als Flash en Adobe Illustrator levert weinig problemen op. Nadeel van het gebruik van vector graphics is dat polygonen elkaar alleen kunnen overlappen. Polygonen in Flash Illustrator hebben geen diepte: geen z-positie.

Wanneer de uitvoer van een render engine een bitmap graphic is, moet per beeldpunt (pixel) bekend zijn welke polygoon zichtbaar is. De polygoon moet omgezet worden naar een reeks pixels. Dit proces wordt scan conversion genoemd. De software (of hardware) die deze taak uitvoert wordt RIP genoemd: raster image processor.

Het omzetten van een polygoon naar pixels wordt in Flash automatisch door de interne RIP uitgevoerd. Met behulp van actionscript kun je de tweedimensionale hoekpuntposities van een polygoon opgeven en de intensiteit. De verdere verwerking neemt Flash voor zijn rekening.

De z-positie (en de eventuele gemiddelde normaal) wordt opgeslagen in een zogenaamde z-buffer. Een z-buffer is een stuk geheugen waar per schermpositie/pixel (x,y) de gegevens voor het berekenen van de intensiteit (de (gemiddelde) normaal) en de z-positie (diepte) opgeslagen wordt.

De diepte is van belang om te bepalen welke pixel het dichtst bij het oog van de kijker ligt. Deze is namelijk zichtbaar op het scherm. De pixels van de polygonen die zich achter deze z-positie bevinden worden overlapt door de voor de kijker zichtbare pixel, dus je ziet ze niet. Daarom zijn deze pixels verder niet relevant, tenzij de zichtbare polygoon transparant is.

De x-positie wordt afgeleid van de geheugenplaats in de z-buffer, de y positie is gelijk aan de scanline positie. Beide posities worden niet in de z-buffer opgeslagen. In veel gevallen wordt een afbeelding binnen een render engine net als het beeld van een televisie opgebouwd: horizontaal van links boven naar rechts onder. De z-buffer is vaak één pixel hoog en wordt ook wel scanline genoemd.

Je kunt ook het hele scherm als z-buffer gebruiken. Nadeel hiervan is dat bij grote afbeeldingen de hoeveelheid gebruikt geheugen vrij snel toeneemt. Een z-buffer die het hele beeld beslaat voor een afbeelding van 4000 × 3000 pixels resulteert in 12.000.0000 geheugeneenheden, terwijl een scanlijn slecht 4000 (= 0.0003% van 12.000.000) geheugeneenheden nodig heeft.

Het berekenen van de intensiteit is rekenintensief, vandaar dat we eerst alle polygonen die snijden met de scanline omzetten naar pixels met bij behorende z-positie. Zodra bekend is welke pixel van welke polygoon voor de toeschouwer zichtbaar is, berekenen we de intensiteit.

De scan conversie kan aanzienlijk versneld wordt door alleen polygonen naar pixels om te zetten die zich binnen het zichtbare beeld bevinden. De normaal die gebruikt werd voor het bepalen van de intensiteit van een polygoon kan ook gebruikt worden voor het optimaliseren van de scan conversie.

Een polygoon van een gesloten object is alleen voor de toeschouwer zichtbaar wanneer de hoek tussen het oog van de toeschouwer en de normaal minder is dan negentig graden. Wanneer de hoek groter is, is de polygoon niet zichtbaar en niet relevant voor de scanversie. Het bepalen van de zichtbaarheid van de polygoon wordt backface elimination of culling genoemd.

De rode polygonen zijn niet zichtbaar voor de toeschouwer en worden niet verwerkt t.b.v. de scan conversie. In dit specifieke voorbeeld levert de eenvoudige berekening een aanzienlijke besparing van niet-relevante berekeningen op.

De berekening van de hoek met óf het oog van de toeschouwer óf de lichtbron kan eenmalig voor de scan conversie uitgevoerd worden. Het resultaat van de berekening (relevant/niet relevant) kan als extra informatie bij de polygoon opgeslagen worden. Tijdens het renderproces volstaat een eenvoudige controle om te bepalen of scan conversie van een specifieke polygoon zinvol is.

Schaduw

Het gebruik van schaduw voegt meer realisme toe aan een computer graphic. Maar de berekeningen die nodig zijn voor het bepalen of een polygoon wel of niet (gedeeltelijk) schaduw heeft zijn complex en zeer rekenintensief.

Er zijn diverse technieken om schaduw te berekenen. Hier ga ik alleen in op de berekening van schaduw door middel van snijpunt- of intersectieberekening. Deze techniek rekent per polygoonpositie uit of er zich een andere polygoon tussen de lichtbronnen en de betreffende polygoonpositie bevindt, om zo te bepalen of er wel of geen schaduw is.

Een 3d-object bestaat al gauw uit (tien)duizenden polygonen. Per beeldpunt moet per lichtbron berekend worden of één van de overige polygonen eventueel schaduw veroorzaakt.

Een afbeelding op het formaat 400 × 300 pixels bestaat uit 120.000 pixels. Stel dat het gebruikte 3d object uit 10.000 polygonen bestaan en er worden 4 lichtbronnen gebruikt die schaduw kunnen veroorzaken. Dit resulteert in 120.000 × 9.999 × 4 = 479.995.200.000(!) berekeningen, alleen om te bepalen of de polygoon posities wel of geen schaduw hebben. Bij gebruik van anti-aliasing voor een acceptabele beeldkwaliteit worden per pixels meerdere intensiteiten berekend, waardoor het aantal berekeningen nóg groter wordt.

Het berekenen van snijpunten kan uiteraard eenvoudig geoptimaliseerd worden door te stoppen zodra er een polygoon gevonden is die schaduw veroorzaakt. Wanneer deze polygoon niet (gedeeltelijk) transparant is, is verdere berekening niet meer relevant. Bovendien worden de polygonen die niet zichtbaar zijn voor de lichtbron (dus als de hoek van de normaal met de polygoon groter is dan negentig graden) niet meegenomen in de schaduwberekeningen.

In bovenstaande afbeelding zijn de polygonen die niet zichtbaar zijn voor de lichtbron rood weergegeven.

Raytracen

Als je materialen als chroom, glas, of diamant wilt laten zien moet je de techniek van het raytracen toepassen. Raytracen is het berekenen van reflecties en/of refracties van 3d-objecten: het berekenen van de weg die een virtuele lichtstraal door een virtuele ruimte aflegt.

Onderstaande afbeelding is gerenderd met schaduw, reflecties en refracties.

Naast ambient, diffuus en specular kun je reflectie en/of transparantie als extra eigenschappen gebruiken. Door de onderlinge verhoudingen van de afzonderlijke eigenschappen te variëren is het mogelijk veel fysieke materialen zeer realistisch te benaderen.

De gebruikte technieken voor het berekenen van reflectie en refracties zijn overigens afkomstig van militair onderzoek naar het gedrag van nuclaire deeltjes.

Lichtstralen gedragen zich net als nucleaire deeltjes wanneer ze door een (virtuele) ruimte bewegen. Zodra de lichtstraal tijdens zijn weg door de ruimte kruist met een oppervlak vindt er een interactie plaats, afhankelijk van de eigenschappen van het oppervlak.

Wanneer het oppervlak niet reflectief is wordt de energie van de lichtstraal geabsorbeerd en voor een deel in alle richtingen verstrooid door het onregelmatige oppervlak, wat in de virtuele ruimte de eerder besproken component ambient oplevert.

Wanneer het oppervlak zeer vlak is (zoals bijvoorbeeld het oppervlak van een spiegel) wordt de lichtstraal in zijn geheel of gedeeltelijk gereflecteerd en vervolgt zijn weg. Wanneer het oppervlak eveneens transparant is, wordt de lichtstraal niet alleen voor een deel gereflecteerd, maar ook doorgelaten en eventueel iets van richting veranderd als gevolg van de brekingsindex van het materiaal.

Voor de berekening van reflecties en/of refracties wordt als basis een lichtstraal (lees vector) vanuit het oog naar het voor de toeschouwer dichtstbij gelegen punt uit de z-buffer gebruikt. Dit is de initiële lichtstraal. De intensiteit van de beeldpunt wordt berekend en opgeslagen. Wanneer de polygoon reflectief is, wordt een nieuwe lichtstraal berekend op basis van de initiële lichtstraal. De initiële lichtstraal wordt gereflecteerd, waarbij de hoek van inval gelijk is aan de hoek van uitval. De normaal wordt gebruikt voor het bepalen van de te spiegelen hoek. Is de polygoon niet alleen reflectief maar ook nog transparant, dan wordt er ook een afgebroken lichtstraal berekend.

De initiële lichtstraal vanuit het oog deelt zich op in twee afzonderlijke (zwakkere) lichtstralen. Voor beide lichtstralen wordt op dezelfde wijze als de initiële lichtstraal gekeken of de lichtstralen kruisen met de overige polygonen in de virtuele ruimte. Wanneer de lichtstraal polygonen kruist wordt gekeken welke polygoon zich het dichtst bij de startpositie van de lichtstraal bevindt. Het berekende snijpunt wordt gebruikt voor het bepalen van de intensiteit. Deze intensiteit wordt verrekend met de eerder berekende intensiteit.

Op basis van de eigenschappen van de polygoon waar de lichtstraal mee snijdt kijken we dan of de lichtstraal wederom opgedeeld moet worden. Dit proces herhaalt zich net zo vaak totdat de lichtstraal geen polygonen meer snijdt, óf wanneer de eigenschappen van een polygoon die de lichtstraal kruist geen reflectieve en/of transparante eigenschappen heeft.

In veel 3d-programma’s is het mogelijk een maximum op te geven voor het aantal opdelingen van gereflecteerde en/of afgebroken lichtstralen. Hoe groter het aantal opdelingen, hoe meer berekeningen nodig zijn. Wanneer het aantal opdelingen onbegrenst is, is het theoretisch mogelijk dat een lichtstraal oneindig door een ruimte reist. Bedenk wel dat elke keer dat een lichtstraal een oppervlak snijdt er een deel van de lichtenergie verloren gaat, tenzij het oppervlak perfect vlak is. De invloed op de uiteindelijke intensiteit neemt na elke opdeling af en zal na verloop van tijd geen zichtbare bijdrage meer leveren aan de totale intensiteit. Zodra een bepaald minimum bereikt wordt kan verdere berekening gestopt worden.

Het berekenen van reflecties en refracties is nog rekenintensiever dan het berekenen van schaduw. Eén enkele lichtstraal kan zich bij interactie van oppervlakken vele malen opdelen. Voor elke afzonderlijke lichtstraal moet telkens berekend worden of er polygonen zijn die de lichtstraal snijdt, wat resulteert in een enorme hoeveelheid te berekenen snijpunten.

Om rendertijden enigzins acceptabel te houden is het noodzakelijk om technieken toe te passen die ervoor zorgen dat alleen snijpunten met polygonen berekend worden die mogelijk een snijpunt kunnen opleveren. Met behulp van space partitioning wordt een virtuele ruimte opgedeeld. De opdeling maakt het mogelijk het berekenen van snijpunten met polygonen aanzienlijk te optimaliseren.

Space partitioning

Space partitioning is het opdelen van een virtuele ruimte in een aantal kleinere ruimten, ook wel voxels genoemd.

Het doel van space partitioning is het reduceren van intersectieberekeningen die nodig zijn voor onder andere raytracing, schaduwbepaling en bijvoorbeeld collision detectie.

In het voorbeeld gebruik ik een zogenaamde octree. Een octree is een denkbeeldige boom die telkens vertakt in acht nieuwe vertakkingen.

Per polygoon wordt gekeken of het past binnen een van de acht voxels waarin de virtuele ruimte opgedeeld is. Wanneer de polygoon meerdere voxels kruist wordt de polygoon opgeslagen op het eerste niveau van de octree.

Wanneer de polygoon volledig in één van de acht voxels past, wordt de betreffende voxel wederom opgedeeld in acht kleinere voxels en wordt een niveau toegevoegd aan de octree voor zover deze niet aanwezig is.

Wanneer de polygoon meerdere voxels op het tweede niveau kruist wordt de polygoon opgeslagen op het tweede niveau van de octree. Wanneer de polygoon volledig in één van de acht voxels past, wordt de betreffende voxel wederom opgedeeld in acht kleinere voxels etc..

Met behulp van de octree is het mogelijk om op elk niveau te bepalen welke polygonen zich binnen een specifieke voxel bevinden (zie schema).

In onderstaande afbeelding is de virtuele ruimte opgedeeld in acht voxels, waarbij per voxel de inhoud wordt getoond.

De voxel in het centrum van de afbeelding is de basisvoxel. De voxels die rond de basisvoxel geplaatst zijn, zijn de afzondelijke voxels van de basisvoxel. De voxels aan de buitenzijde van de afbeelding zijn de voxels van de afzonderlijke voxels van de basisvoxel. In het schema zijn dit de voxels op niveau 1.

Voor het bepalen van eventuele snijpunten met een lichtstraal worden niet alle aanwezige polygonen gecontroleerd op een eventueel snijpunt, maar wordt eerst bepaald of de lichtstraal snijdt met één van de acht voxels op het eerste niveau van de octree.

Is er geen snijpunt met een voxel op het eerste niveau, dan kan er nooit een snijpunt zijn met een van de polygonen die zich binnen deze voxel bevindt. Alle volgende voxels in volgende niveau’s kunnen in dit geval ook overgeslagen worden.

Wanneer een lichtstraal wél snijdt met een voxel moeten alle polygonen die zich binnen deze voxel bevinden gecontroleerd worden op een eventueel snijpunt. Vervolgens wordt een niveau lager gecontroleerd of de aanwezige voxels ook met de lichtstraal snijden enzovoorts.

Met behulp van een octree kun je met een relatief eenvoudige controle een groot deel van de aanwezig polygonen uitsluiten voor intersectie berekening omdat de lichtstraal ze onmogelijk kan snijden.

Stop het plaatsen van polygonen in voxels wel tijdig, omdat je anders voxels gebruikt waar zich slechts één polygoon in bevindt. Naast de berekening van een snijpunt met de voxel moet je in dat geval ook een snijpuntberekening maken met de enige polygoon binnen de voxel. Het aantal noodzakelijke berekeningen neemt hierdoor juist toe in plaats van af. Door een minimum aantal polygonen per voxel te gebruiken voorkom je dit probleem.

Voxels 2d

De berekening met behulp van octrees en voxels kan met een kleine aanpassing ook gebruikt worden om een 3d-object om te zetten naar blokjes ten behoeve van een 2d-afbeelding.

Met behulp van een grid wordt een 3d object naar snijpunten vertaald. Het eindresultaat van de berekeningen is een aantal snijpunten met een x, y en z-positie die zich (in het geval van het grid) op gelijkmatige afstand van elkaar bevinden.

Op de positie van de berekende snijpunten plaatsen we een blokje, waarbij het centrum gelijk is aan het snijpunt. Het formaat van het blokje is in de afbeelding net iets kleiner dan de afstand tussen twee snijpunten, waardoor je elk afzonderlijk snijpunt als blokje te zien krijgt. Je kunt uiteraard ook een ander 3d-object op de snijpuntpositie plaatsen.

Met behulp van de snijpuntposities is het ook mogelijk een pixel art-afbeelding te maken. De ruimtelijke snijpunten met een x, y en z-positie moeten in dit geval teruggebracht worden tot een tweedimensionale x en y positie.

Als basis neem je de snijpuntpositie die zich in het centrum van alle snijpunten bevindt. Deze positie geef je de index 0,0,0. Vervolgens indexeer je met behulp van de afstand tussen de snijpunten elke positie naar een x, y en z index. Wanneer de afstand tussen de snijpunten gelijk is aan 2.5 levert de positie 0.0,2.5,5.0 de indexen 0,1 en 2 op.

Deze indexen zijn nodig om de pixel art sprite te positioneren naar een tweedimensionale schermpositie.

Het is van belang dat je de sprites van achter naar voren tekent, zodat de posities die zich het dichtst bij de toeschouwer bevinden niet overlapt worden door posities die zich verder van het oog van de toeschouwer af bevinden.

Afhankelijk van het formaat van de gebruikte sprite is met een eenvoudige berekening de exacte positie van de sprite te berekenen. Vervolgens wordt de intensiteit van de pixels van de sprite in het geheugen geplaatst. Zodra alle snijpuntposities verwerkt zijn wordt de afbeelding weggeschreven naar een bitmap graphic en ontstaat onderstaande afbeelding.

Het is uiteraard ook mogelijke de pixel art-afbeelding handmatig te tekenen zonder gebruik te maken van vrij ingewikkelde berekeningen. Dat gaat goed zolang het kleine afbeeldingen betreft. Maar door het proces te automatiseren kun je enorm grote pixel art-afbeeldingen maken die je onmogelijk handmatig zou kunnen produceren.

Ten slotte

Wanneer je de theorie toe wilt gaan passen in de praktijk zul je rekening moeten houden met de (on)mogelijkheden van de taal waarin je gaat programmeren.

De programmeertaal C(++) leent zich erg goed voor het schrijven van een render engine. Programma’s die met C(++) gemaakt worden zijn uiterst snel en bieden veel mogelijkheden voor de opslag van grote hoeveelheden data.

Actionscript leent zich ook prima voor het schrijven van een render engine. Flash voert de scan conversie van polygonen intern uit, waardoor het een goede basis is voor het schrijven van je eigen eenvoudige render engine.

Naast C(++) en Actionscript is de Persistence of Vision Raytracer (afgekort Povray) ook een interessant 3d-programma voor degene die niet gelijk diep in programmeertalen wil duiken.

Povray werkt met een eenvoudige en goed gedocumenteerde scripttaal en is ideaal om begrippen als ambient, diffuus, specular etc. te onderzoeken. Een ander voordeel van Povray is dat het gratis is en er bovendien kwalitatief zeer goede resultaten mee te behalen zijn.

Succes ermee!

Meer lezen

3d programma’s:

• softimage
• Persistence of Vision Raytracer (povray)
• cinema 4d
• maya
• groboto
• 3d studio
• blender

guru’s

• Stephen Wolfram
• Paul Debevec
• Paul Bourke

sites

• Evolutionzone.com
• GroupsC
• maedastudio
• marumushi.com
• the pixel-lab
• marius watz
• bodytag.org
• Leogeo

boeken

• Advanced Animation and Rendering Techniques
  Alan Watt, M. Watt, ADDISON-WESLEY, ISBN 0-201-54412-1
• Computer Graphics: Principles and Practice in C
  James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes, ADDISON-WESLEY, ISBN 0-201-84840-6
• Fundamentals of three-dimensional computer graphics
  Alan Watt, ADDISON-WESLEY, ISBN 0-201-15442-0

De aanleiding voor het schrijven van dit artikel waren twee uitnodigingen om lezingen te komen geven. De eerste was een voordracht met de titel ‘voxels en andere expirimentele webtechonologieën voor het web’ op multi-mania 2005, het grootste Belgische multimedia event, georganiseerd door het Departement PIH van de Hogeschool West-Vlaanderen en Multicoach in België. De tweede was een lezing op Exposure 2005, georganiseerd door de opleiding Communication & Multimedia Design in Leeuwarden, Nederland.

• Home
• Artikelen
• Colofon