bññáåáøåíé=êéåçéêáåö=çé=ä~~íëíé=öéåéê~íáé=öê~ñáëåüé= Ü~êÇï~êÉ

bÑÑáÅáØåíÉ=êÉåÇÉêáåÖ=çé=ä~~íëíÉ=ÖÉåÉê~íáÉ=Öê~ÑáëÅÜÉ= Ü~êÇï~êÉ

káÉäë=pÅÜêçóÉå éêçãçíçê=W mêçÑK=ÇêK=mÜáäáééÉ=_bh^boq

=

báåÇîÉêÜ~åÇÉäáåÖ=îççêÖÉÇê~ÖÉå=íçí=ÜÉí=ÄÉâçãÉå=î~å=ÇÉ=Öê~~Ç= j~ëíÉê=áå=ÇÉ=áåÑçêã~íáÅ~=ãìäíáãÉÇá~

Inhoudsopgave 1 Inleiding 1.1 Motivatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Doelstellingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Structuur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Graphics Processing Unit 2.1 Render Pipeline . . . . . . . . . . . . . . . . . . 2.1.1 Van Vertex tot Pixel . . . . . . . . . . . 2.1.2 Stream Processing . . . . . . . . . . . . 2.1.3 Transformaties . . . . . . . . . . . . . . 2.2 Graphics Programming Unit . . . . . . . . . . . 2.2.1 Geschiedenis . . . . . . . . . . . . . . . 2.2.2 Systeem Architectuur . . . . . . . . . . 2.2.3 The Past: Parallel Pipelined GPU . . . 2.2.4 Next-Generation: Unified Shading GPU 2.3 Geometrische Complexiteit . . . . . . . . . . .

1 1 2 2

. . . . . . . . . .

3 3 3 5 5 8 10 12 13 14 17

. . . . . . . . . . . . . .

21 21 22 22 23 23 23 24 26 26 28 28 29 29 30

4 Hardware Occlusion Queries 4.1 Occlusion culling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Early-z Culling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36 36 37

3 Geometrische Instanties 3.1 Geometrische Buffers . . . . . . . . . . 3.2 Filosofie . . . . . . . . . . . . . . . . . 3.3 Gevaren en Moeilijkheden . . . . . . . 3.4 Geometrische Instantie Methodes . . . 3.4.1 Statische Instanciëring . . . . . 3.4.2 Dynamische Instanciëring . . . 3.4.3 Vertex Atribuut Instanciëring . 3.4.4 Instanciëring met Render API 3.5 Optimalisaties . . . . . . . . . . . . . . 3.5.1 Vertex Cache . . . . . . . . . . 3.5.2 Segment Buffering . . . . . . . 3.5.3 Segment Instanciëring . . . . . 3.5.4 Textuurarrays . . . . . . . . . . 3.5.5 Level Of Detail . . . . . . . . .

i

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

INHOUDSOPGAVE

4.2 4.3 4.4

ii

4.1.2 Occlusion Queries . . . . . . . . . . . . Stalls, Starvations and Boxes . . . . . . . . . . Kennis van het Verleden . . . . . . . . . . . . . Coherent Hiërachical Culling . . . . . . . . . . 4.4.1 Hiërarchies . . . . . . . . . . . . . . . . 4.4.2 Hiërarchisch Stop en Wacht . . . . . . . 4.4.3 Coherent Hiërachical Culling Algoritme 4.4.4 Minder Queries, Minder Stalls . . . . . 4.4.5 Optimalisaties . . . . . . . . . . . . . .

5 Uitgestelde Shading 5.1 Achtergrond . . . . . . . . . 5.2 Waarom Uitgesteld Shaden? 5.3 De Uitgestelde Shader . . . 5.3.1 Voorbereiding . . . . 5.3.2 Geometrische Stap . 5.3.3 Belichtings Stap . . 5.3.4 Postprocessing Stap

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

37 37 39 39 39 40 41 42 42

. . . . . . .

44 44 45 46 46 46 46 49

6 Implementatie 6.1 Overzicht . . . . . . . . . . . . . . . 6.1.1 Third-party Libraries . . . . 6.2 Geometrische Instanties . . . . . . . 6.2.1 Instantie Framework . . . . . 6.2.2 Vertex Atribuut Instanties . . 6.2.3 Instanciëren met Render API 6.2.4 Render- en Textuurcontext . 6.2.5 Entiteit Tool . . . . . . . . . 6.2.6 Textuur Atlas . . . . . . . . . 6.3 Coherent Hiërarchical Culling . . . . 6.3.1 Hiërarchische Structuur . . . 6.3.2 CHC algoritme . . . . . . . . 6.3.3 Enkele Bedenkingen . . . . . 6.4 Uitgestelde Shading . . . . . . . . . 6.4.1 G-Buffer . . . . . . . . . . . . 6.4.2 Belichting . . . . . . . . . . . 6.4.3 Post-processing . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

52 52 52 53 53 54 55 55 56 56 56 56 57 57 58 58 59 60

7 Resultaten 7.1 Test Systeem en Methode . . . . 7.2 Statische Entiteiten . . . . . . . . 7.3 Dynamische Entiteiten . . . . . . 7.4 Culling Performantie . . . . . . . 7.5 Uitgestelde Shading Performantie 7.6 Screenshots . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

61 61 61 62 63 65 66

8 Besluit

. . . . . .

. . . . . .

70

INHOUDSOPGAVE A Belichtingsvergelijking A.1 Ambient Licht . . . . . . . A.2 Direct Licht . . . . . . . . . A.2.1 Diffuse Lichtterm . . A.2.2 Speculaire Lichtterm A.3 Punt Licht . . . . . . . . . .

iii

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

71 71 71 71 72 72

Lijst van figuren 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16

Algemeen beeld van de render pipeline . . Streamed render pipeline . . . . . . . . . Een kubus in modelruimte . . . . . . . . . Wereldtransformatie van een kubus . . . . Cameratransformatie van een kubus . . . Orthogonale Projectie . . . . . . . . . . . Perspectief Projectie . . . . . . . . . . . . Samenvatting Transformaties . . . . . . . Systeem architectuur . . . . . . . . . . . . nVidia Geforce 6 architectuur . . . . . . . Zicht op één pipeline. . . . . . . . . . . . . GeForce 8 Unified Architectuur. . . . . . . Traditioneel vs Unified concept. . . . . . . Load-balancing in de unified architectuur. CPU batch performance . . . . . . . . . . Batch-size performantie . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

4 6 7 7 8 9 9 10 12 13 14 15 15 16 18 19

3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10

Structuur van een geometrische buffer . . . . . . . . . Twee instanties van een statische batch. . . . . . . . . Geometrische buffer tijdens Vertex Atribuut Instantie Geometrische buffer tijdens API Instantie . . . . . . . Tangentruimte van een vierhoek. . . . . . . . . . . . . Normaalmap voor een gedetailleerde stenen muur. . . Het probleem van ontbrekende parallax. . . . . . . . . Hoogtemap voor een gedetailleerde stenen muur . . . . Offset berekening voor parallaxmapping. . . . . . . . . Vergelijking van parallaxmapping en normaalmapping.

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

22 24 25 27 31 32 33 34 35 35

4.1 4.2 4.3 4.4

Stalls en Starvations. . . . . . . . . . . . . . . . . De boom vormt een occludee voor het karakter. . Guessing van zichtbaarheid. . . . . . . . . . . . . Optrekken van zichtbaarheidsinformatie doorheen

. . . . . . . . . . . . . . . . . . de boom.

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

38 40 42 43

5.1 5.2 5.3 5.4

De G-Buffer. . . . . . . . . . . . . . . Pre-processed belicht beeld resultaat. . Visualisatie van de scissor berekening. Blurring van een beeld. . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

47 48 48 49

iv

. . . .

. . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

LIJST VAN FIGUREN

v

5.5 5.6

Post-processed beeld met blooming. . . . . . . . . . . . . . . . . . . . . . . . Post-processed beeld met blooming en HDR. . . . . . . . . . . . . . . . . . .

50 51

6.1

Render- en Textuurcontext met batches. . . . . . . . . . . . . . . . . . . . . .

55

7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10 7.11

Vergelijking van de statische rendermethodes . . . . . . . . . . . . . Vergelijking van de dynamische rendermethodes . . . . . . . . . . . . Vergelijking van de culling rendermethodes . . . . . . . . . . . . . . Performantie van de deferred shader. . . . . . . . . . . . . . . . . . . Scherm capture van één der entiteit benchmarks. . . . . . . . . . . . Zicht op het terrein via CHC. . . . . . . . . . . . . . . . . . . . . . . Daadwerkelijk gerenderd gebied uit figuur 7.6. . . . . . . . . . . . . . Pre-process belichting van een terrein en enkele spheres. . . . . . . . Stress testing van terrein en instanties. . . . . . . . . . . . . . . . . . Screenshot uit de deferred shader benchmark. . . . . . . . . . . . . . De uitgestelde shader tijdens de nacht met enkele lichtbronnen boven

62 63 64 65 66 67 67 68 68 69 69

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . het water.

A.1 Diffuse reflectie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Speculaire reflectie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72 73

Abstract De laatste jaren is er heel wat veranderd op het vlak van real-time Computer Graphics. De hardware is sneller geworden en de eisen in grafische toepassingen zijn veranderd. Zo verwacht men steeds realistischere werelden met veel meer objecten. Traditioneel waren grafische systemen gelimiteerd in de kracht van de grafische processor. Doordat de videohardware alsmaar sneller is geworden en door de nieuwe eisen die gesteld worden, hebben we een verschuiving kunnen vaststellen in wat nu eigenlijk een grafische toepassing limiteert. Niet meer de video-hardware is de beperkende factor maar veelal stellen we vast dat de central processing unit het systeem nekt. Om deze evoluties op te vangen is het belangrijk om de rendermethodes aan te passen. In deze thesis zullen we de problemen met traditionele rendertechnieken identificeren en stellen we enkele nieuwe technieken voor, speciaal ontworpen met de laatste generatie van grafische hardware in het achterhoofd. We zullen zien hoe geometrie instanties kunnen helpen om de grote hoeveelheid drawcalls, die de hoofdreden vormen van de zware CPU-last, te verminderen. Ook kijken we hoe oudere hiërarchische cullingmethodes omgezet kunnen worden naar een CPU vriendelijke versie. Omdat belichting een grote rol speelt tegenwoordig in Computer Graphics bespreken we ook een nieuwe vorm van lichtrendering, namelijk uitgestelde shading dat perfect inpast met de besproken geometrie instantie methodes.

vi

Dankwoord Ik wil graag mijn promotor, Prof. Dr. Philippe Bekaert, bedanken voor het vertrouwen om mij dit onderwerp te laten onderzoeken. Ook mijn begeleider, Yannick Francken, wil ik in deze weg bedanken voor de discussies, de vele tips en het helpen zoeken naar de juiste focuspunten in het onderwerp, alsook het nalezen en raadgeven. Tot slot wil ik ook nog William Van Haevre bedanken voor de raadgevingen in het beginstadium van deze thesis in verband met de rendering en modellering van boommodellen.

vii

Hoofdstuk 1

Inleiding Rise and shine, Mr. Freeman. Rise and shine. - G-Man, Halflife 2

Voor we beginnen met het echte werk blijven we even stilstaan bij de bedoeling van deze thesis en overlopen we in het kort de verdere opbouw van de tekst.

1.1

Motivatie

De laatste jaren is er een ontzettende evolutie gebeurd op het vlak van real-time computer graphics. Niet alleen is de hardware gegroeid aan een verschroeiend tempo, ook de verwachtingen van de uiteindelijke eindgebruiker zijn ongelooflijk gestegen. Virtuele werelden moeten er zo realistisch mogelijk uitzien. Zowel spectaculaire effecten als grote hoeveelheden mooi gemodelleerde objecten zijn allemaal standaard eisen in de grafische applicaties van vandaag. De dagen van pixelart en kartonnen platen met beschilderde bomen behoren nu wel degelijk tot het verleden. Door deze veranderingen zijn traditionele methodes om 3D omgevingen in real-time te tekenen, hopeloos verouderd. Aangepaste methodes zijn vereist doordat volledig nieuwe verwachtingen gesteld zijn en doordat de gebruikelijke bottlenecks in de render pipeline verschoven zijn naar andere componenten. In feite begon deze thesis als een onderzoek naar enkel en alleen het renderen van botanische scènes, zoals weide landschappen of bossen. Maar in de loop van deze thesis werd het na een tijd duidelijk dat de benodigde algoritmes gebruikt konden worden om ook andere complexe scènes aan te pakken omdat uiteindelijk het probleem steeds lag in de geometrische complexiteit van het te renderen frame. Hierdoor beperken de besproken probleemstellingen en de algoritmes om deze op te lossen, zich niet tot enkel dit soort van scènes. Het komt erop neer dat elke situatie waarin er ontzachelijk veel objecten in een zo realistisch mogelijke omgeving gerenderd moeten worden, baat hebben bij de technieken uit dit onderzoek. Vandaar dat we dus ook geen duidelijk onderscheid zullen maken tussen omgevingen zoals bossen of verstedelijkte metropolen, maar het eerder zullen hebben over geometrische complexiteit. Vaak ligt het verschil tussen botanische scènes en andere omgevingen enkel in de aard van de materialen zoals de gebruikte shaders en in de interactie die nodig is met designers van 1

HOOFDSTUK 1. INLEIDING

2

de wereld. Men zal immers vaak opteren voor een semi-automatische plaatsing van bomen en gras in de scène in plaats van een puur handmatige methode. Deze topics waren eigenlijk van minder belang in de originele doelstellingen van deze thesis.

1.2

Doelstellingen

In deze thesis is het de bedoeling om eerst en vooral te ontdekken wat we vandaag de dag verstaan onder geometrische complexiteit en welke gevolgen dit heeft tot betrekking van huidige hardware en traditionele render methodes. Vervolgens zullen we op zoek gaan naar technieken om complexe scènes in real-time te renderen zonder aan flexibiliteit te verliezen. Verbonden aan deze thesis is ook een implementatie van de onderzochte render methodes in de vorm van de 3D-engine API Natureality. Het doel van deze library was om in de eerste plaats nieuwe methodes te kunnen uit testen en te vergelijken met traditionele methodes alsook het ontwerpen van een intu¨ıtieve programmeer-tool om makkelijk nieuwe 3D applicaties te ontwerpen die gebruik kunnen maken van deze nieuwe render methodes op de allernieuwste video-hardware.

1.3

Structuur

We overlopen nu even in het kort wat men kan verwachten in de rest van deze tekst. Er zal begonnen worden met wat achtergrond informatie die betrekking heeft op de Graphics Processing Unit (GPU). Het is uiteindelijk van groot belang om een goede kennis te hebben van de grafische hardware. In dit hoofdstuk zal ook dieper in gegaan worden op de render pipeline en op de problemen die we verkrijgen wanneer we proberen complexe scènes te renderen. In de drie volgende hoofdstukken zullen we vervolgens drie technieken bespreken die het mogelijk maken om nagenoeg al onze problemen op te lossen. In het eerste van deze hoofdstukken zullen we Geometrische Instanciëring bespreken dat ons in staat stelt grote hoeveelheden objecten met één enkele drawcall uit te tekenen. Het tweede hoofdstuk zal Hardware Occlusion Queries bespreken en een hiërarchisch algoritme op basis hiervan, namelijk Coherente Hiërachische Culling (CHC). Dit is een techniek in de lijn van wel gekende hiërarchishe methodes zoals BSP-trees en Portal Culling, maar volledig geoptimaliseerd voor huidige GPU’s. Het derde hoofdstuk zal een diepere kijk geven in hoe we geometrisch complexe scènes kunnen belichten. We zullen de problemen met Forward Rendering bespreken en onze voorgestelde oplossing op basis van Uitgestelde Shading. Tot slot be¨ındigen we met een hoofdstuk over onze implementatie en de bekomen resultaten waaruit we dan enkele conclusies zullen trekken.

Hoofdstuk 2

Graphics Processing Unit I am Shodan. - Shodan, System Shock 2

Er is een zekere kennis van GPU’s nodig om goed de problemen te begrijpen die ontstaan bij het renderen van complexe geometrie. Vandaar dat we beginnen met een hoofdstuk dat zal trachten om de nodige kennis over grafische hardware bij te brengen. Dit hoofdstuk zal ook al aantonen waar de problemen zitten die we moeten oplossen en zal bepaalde fundamentele begrippen uit de computer graphics wereld verduidelijken.

2.1

Render Pipeline

Voor we echter kunnen praten over video-hardware is het belangrijk om te weten wat deze hardware voor ons doet. We zullen daarom eerst de render pipeline en zijn componenten bespreken. We gaan hier echter niet in detail treden, de ge¨ınteresseerde lezer willen we echter wel doorverwijzen naar het ontwerp van een software 3D engine die van nul af aan wordt opgebouwd en alzo de nodige kennis verschaft over de diepere mysteries die de dag van vandaag allemaal door de GPU en render API’s worden afgehandeld [22].

2.1.1

Van Vertex tot Pixel

Render pipelines verschillen vaak van elkaar in de volgorde en flow doorheen de modules waaruit de pipeline is opgebouwd, maar het onderliggende principe is steeds opnieuw hetzelfde. De pipeline zorgt ervoor dat de binnenkomende vertices van een object omgezet worden naar pixels op een scherm. Figuur 2.1 geeft dit principe weer. Per-Vertex Operaties Geometrische modellen worden op de render pipeline geplaatst in de vorm van vertices. Deze vertices worden in de eerste stap behandeld. Vaak komt het erop neer dat in deze stap een vertex getransformeerd wordt naar een twee dimensionaal scherm-coördinaat, zometeen zien we wat dit inhoudt als we de verschillende transformatieruimtes bespreken in punt 2.1.3. Een tweede geregeld voorkomende operatie is het belichten van de vertex in deze module. Het is dan ook misschien niet zo verwonderlijk dat deze stap ook wel T&L genoemd wordt,

3

HOOFDSTUK 2. GRAPHICS PROCESSING UNIT

4

Figuur 2.1: Algemeen beeld van de render pipeline afgekort van Transformation and Lighting. Doch is het zeer belangrijk op te merken dat per-vertex operaties zich niet hoeven te beperken tot deze twee berekeningen. Primitive Assembly Nadat de vertices behandeld zijn moeten deze gegroepeerd worden voor het vervolg van de pipeline. Dat is wat er in deze stap zal gebeuren. De meest voorkomende groepering van vertices is het maken van driehoeken, dit sluit niet uit dat ook vierhoeken en andere veelhoeken gevormd kunnen worden. Driehoeken hebben echter de handige eigenschap dat ze steeds een vlak vormen en aldus is de kans op artefacten door het trachten te renderen van primitieven die geen vlak vormen, uitgesloten. Verder zijn driehoeken ook makkelijker te interpoleren wat handig zal zijn voor het rasterizerings-process. Per-Primitive Operaties In deze stap worden er enkele operaties op de gegroepeerde vertices uitgevoerd. Meestal houdt dit technieken in als backface culling, het enkel renderen van primitieven die naar ons toe “kijken” en viewport culling, waarbij primitieven geclipt worden tegen het view-frustum [22, 36, 41, 18]. Rasterisatie Tijdens de rasterisatie stap worden de primitieven op het scherm weergegeven door schermcoördinaten te interpoleren zodat we kunnen aangeven welke pixels overlapt worden door de te verwerken primitief. Deze pixels noemen we ook wel de fragmenten.


5

Fragment Processing Voordat we de fragmenten versturen naar de framebuffer zodat ze door het scherm weergegeven kunnen worden, is er nog de mogelijkheid om bepaalde operaties uit te voeren op deze fragmenten. Het uiteindelijke doel van deze stap is meestal om een kleurwaarde te berekenen die vervolgens naar de framebuffer wordt doorgegeven. Te denken valt hier aan het bemonsteren van een textuur om via een textuurmap kleurwaardes te berekenen voor elke pixel. Verder wordt hier ook vaak de diepte van het fragment berekend om te gebruiken in een zichtbaarheidstechniek - zoals Z-Buffering [22].

2.1.2

Stream Processing

Een zeer belangrijk paradigma is het streaming model. Dit heeft de basis gelegd voor alle GPU’s. Het streaming model contrasteert met het sequentieel model van bijvoorbeeld de Central Processing Unit (CPU), doordat er gewerkt wordt met streams en kernels. De laatste jaren zijn er wel technieken ontworpen voor de CPU om ook bepaalde gestreamde instructies uit te voeren zoals MMX en SSE [22]. Ook zijn de laatste generaties van CPU’s uitegerust met verschillende cores die elk een volwaardige CPU genoemd kunnen worden [21, 1]. Maar toch blijft over het algemeen de CPU sequentieel werken doordat er in de hoofdtaken, zoals het uitvoeren van het besturingssyteem, niet zo een grote parallelliteit te bespeuren valt als in bijvoorbeeld Computer Graphics. Verder wordt de overgrote meerderheid van de CPUtransistors gebruikt voor controletaken en blijft er dus weinig plaats over op de CPU voor transistors die belast zijn met effectief berekenen van data [37]. Al de input en output data wordt weergegeven in streams. Kernels voeren bewerkingen uit niet op de individuele elementen van de streams, maar op de volledige stream. In een sequentieel model zal de data element per element verwerkt worden. Het streaming model maakt dus gebruik van de grote localiteit tussen de elementen van een stream. Het grote voordeel in stream processing ligt in het feit dat er hierdoor optimaal gebruik kan worden gemaakt van parallelle uitvoering en dat er slechts een minimum aan cachegeheugen nodig is. Wanneer er bijvoorbeeld een fragment verwerkt moet worden, is er totaal geen data nodig over de andere fragmenten. Men kan elk fragment individueel berekenen zonder een invloed uit te oefenen op de resultaten van de andere fragmenten en aldus kunnen we al de fragmenten in parallel uitvoeren. Doordat de render pipeline bestaat uit individuele modules die elk bepaalde taken uitvoeren op een - meestal - grote hoeveelheid data en doordat de verwerking van één element uit de dataset onafhankelijk is van de resultaten van de andere datasetelementen, is het makkelijk in te zien dat de render pipeline simpel te mappen is naar het streaming model. De verschillende modules worden onze kernels en de data bestaat uit gestreamde vertices, primitieven of fragmenten. Figuur 2.2 geeft dit principe weer waarbij de kernels, voorgesteld door rechthoeken, verbonden zijn met behulp van streams, weergegeven door middel van pijlen.

2.1.3

Transformaties

Eén van de belangrijkste stappen in de render pipeline is de transformatie van de vertices en de daarmee verbonden coördinaatruimtes. Om enkele veelvuldig voorkomende principes


6

Figuur 2.2: Streamed render pipeline. Kernels zijn voorgesteld als rechthoeken. Streams zijn voorgesteld door pijlen in de richting van hun flow. in deze tekst goed te begrijpen is het belangrijk om te weten hoe deze transformaties werken en welke ruimtes ze creëren. We zullen daarom even iets dieper ingaan op dit concept. Vertices worden meestal gedefinieërd in een assenstelsel bepaald door het object waartoe de vertices behoren. We noemen deze ruimte modelruimte of objectruimte. De keuze van de oorsprong kan in principe vrij gekozen worden door de artist die het model ontwerpt in één of ander 3D modelleer pakket (zoals 3ds Max [3] of Maya [4]). Vaak wordt er echter gekozen om de oorsprong te leggen in het zwaartepunt of het middelpunt omdat dit uiteindelijk betere resultaten geeft wanneer we rotaties en krachten gaan uitoefenen op het object. Figuur 2.3 geeft deze ruimte weer aan de hand van een kubus. Natuurlijk willen we onze objecten kunnen plaatsen in een virtuele wereld. Dit houdt in dat we ons object moeten transleren naar zijn positie in de wereld en roteren naar zijn orientatie in de wereld. We kunnen hiervoor een matrix gebruiken opgebouwd uit een translatie en drie rotaties (rond elke as is een rotatie nodig). Deze matrix noemen we de wereldmatrix en wanneer we een vertex vermenigvuldigen met deze matrix wordt de vertex getransformeerd naar wereldruimte. Het komt er dus op neer dat we de vertices van ons object gaan herdefinieëren, deze keer ten opzichte van de oorsprong van de virtuele wereld. Figuur 2.4 geeft dit weer door onze kubus te transformeren naar het punt (100,100,100) in de wereld. Meestal willen we ook doorheen onze virtuele wereld wandelen en deze vanuit verschillende standpunten waarnemen. We kunnen hiervoor een virtuele camera gaan gebruiken die doorheen onze wereld kan vliegen. De volgende transformatie stap bestaat er dus uit de vertices te transformeren naar cameraruimte. Ook dit gebeurt opnieuw aan de hand van een matrix. De transformatie zelf is ook nu weer opgebouwd uit een translatie en drie rotaties. We moeten namelijk de oorsprong van de wereld eerst transleren naar de positie van de camera en vervolgens moeten we de assen van de wereldruimte alligneren met de assen van de camera. Figuur 2.5 geeft de verschillende stappen van de cameratransformatie weer.


7

Figuur 2.3: Een kubus in modelruimte

Figuur 2.4: De wereldtransformatie van de kubus naar het punt (100,100,100) in de wereld


8

Figuur 2.5: De verschillende stappen in de cameratransformatie In feite zit het transformatie werk er op nadat een vertex in cameraruimte staat. Om drie dimensionale coördinaten te kunnen weergeven op het twee dimensionaal vlak van een computer monitor moeten we echter nog een laatste stap uitvoeren. We moeten onze vertices gaan projecteren naar een vlak zodat deze twee dimensionaal worden. Er zijn twee manieren om dit te doen. Enerzijds is er de orthogonale projectie (zie figuur 2.6) waarbij het z-coördinaat geschrapt wordt. Dit is een eenvoudige projectie die tevens ook afstanden behoudt tussen punten en aldus vaak gebruikt wordt in bijvoorbeeld architecturale programma’s. Wij zijn echter meer op zoek naar een esthetisch mooi en realistisch resultaat. Hiervoor kan de tweede methode gebruikt worden, de perspectief projectie, zoals weergegeven in figuur 2.7. Deze projectie behoudt perspectief en geeft aldus een gevoel van diepte mee aan het getransformeerde object. Deze projectie zal vaak de verkozen optie zijn. We besluiten deze bespreking van de transformaties met figuur 2.8 die alles beknopt samenvat. We willen hier ook nog even bij vermelden dat vaak de verschillende matrices worden geconcateneerd tot de modelviewprojectionmatrix omdat dan alle vertices slechts één keer vermenigvuldigd moeten worden met een matrix in plaats van drie keer.

2.2

Graphics Programming Unit

We gaan nu even kijken naar wat er nodig is om een GPU te bevorderen tot een Graphics Programming Unit. Na even de geschiedenis van GPU’s te overlopen, bekijken we twee chiparchitecturen. Eerst de architectuur die voor zowat de laatste twintig jaar gebruikt is en vervolgens de nieuwe unified structuur die ge¨ıntroduceerd is onlangs met de nVidia G80 chip.


Figuur 2.6: Orthogonale Projectie

Figuur 2.7: Perspectief Projectie gezien in het XZ-plane

9


10

Figuur 2.8: Samenvatting Transformaties

2.2.1

Geschiedenis

Hoewel GPU’s nog maar sinds enkele jaren wijd verspreid zijn geraakt op de desktop en homecomputer markt, is het idee van speciale programmeerbare video-hardware zeker geen nieuwigheid. Ruwweg twintig tot dertig jaar geleden waren er al projecten bezig met onderzoek naar programmeerbare hardware met als specifiek doeleinde het efficiënt renderen van 3D omgevingen. Te denken valt hier aan de Pixel-Planes machines en hun opvolger PixelFlow, het allereerste systeem waarin shaders geprogrammeerd konden worden via een high-level taal [41]. Zulke systemen waren natuurlijk ongelooflijk duur en vaak enkel beschikbaar voor universiteiten of grote bedrijven. Toch staan we de dag van vandaag lichtjaren verder met behulp van kleine add-on kaartjes die betaalbaar zijn voor elke eind-gebruiker. De reden van deze evolutie komt uit een wat verrassende hoek: de gaming-industrie. Begin jaren ’90 kwam er een hevige vraag op gang vanuit de gamedevelopers en eindgebruikers, om hardware acceleratie voor 3D bewerkingen. Tot dan toe leverden grafische hardwarevendors enkel chipsets met 2D acceleraties, zoals de misschien wel legendarische bitBLT operatie. Echter games als Quake hadden een revolutie veroorzaakt door full 3D images in real-time op het scherm te toveren. De CPU werd bevonden als een zeer slecht instrument om de nodige bewerkingen uit te voeren. Elke CPU-cycle die gespaard kon worden was zeer belangrijk en moest men dan ook vinden. Waarschijnlijk de allergrootste evolutie in computer graphics werd in 1996 bereikt dankzij 3Dfx dat ons de allereerste Voodoo bracht. Dit was een add-on kaart met als enige doel het accelereren van 3D graphics. Het werd ineens mogelijk om de blokkerige en onduidelijke 8 bit beelden te vervangen door 16 bit hoge kleur beelden met een Z-Buffer voor diepte-informatie aan dertig frames per seconde (FPS). Een ontzettende


11

verandering die de hele computer wereld in zijn greep had. Een hevige strijd barste los tussen verschillende hardwarevendors. Iedereen was erop uit om de koning, 3Dfx, van zijn troon te stoten. Veel bedrijven mislukten en gingen overkop, anderen zochten hun heil in andere markten totdat er slechts drie grote spelers overbleven: 3Dfx, nVidia [28] en ATI [2]. In deze eerste jaren konden we eigenlijk nog helemaal niet spreken over GPU’s, maar slechts over accelerators. Hier kwam dankzij nVidia verandering in toen deze in 1999 op de proppen kwam met de GeForce 256. Voor het eerst was er een betaalbare kaart op de markt met ingebouwde T&L capaciteiten. De accelerator was gepromoveerd tot GPU. Uiteindelijk ging ook 3Dfx onderuit wegens een bij de start al gedoemd modulair design en doordat de Voodoo’s afhankelijk waren van aangepaste API’s (GLIDE en mini-OpenGL). Hierdoor bleven enkel nog nVidia en ATI over, maar de strijd in video-hardware werd er alleen maar bitsiger om. GPU’s evolueerden aan ongelooflijke snelheden en al gauw werd een niewe mijlpaal gezet door nVidia met de Geforce 3: de alleereerste consumer-hardware met programmeerbare shader units. De GPU was eindelijk programmeerbaar geworden, de afkorting GPU kon dan ook vanaf nu begrepen worden als: Graphics “Programming” Unit. In het begin werkte dit op basis van assembler instructies (programs) maar in volgende generaties GPU’s werd er al gauw ondersteuning geboden voor high-level talen (shaders). Developers waren nu niet meer afhankelijk van de vaste functionaliteiten in render API’s (DirectX en OpenGL) maar konden zelf naar genoegen beslissen wat voor berekeningen er gemaakt moesten worden in de vertex en fragment stadia. De jaren die hierop volgden hadden tot dusver niet echt grote vernieuwingen. Het aantal pipelines en geheugen werd elke nieuwe generatie GPU’s verhoogd, de instructiesets werden uitgebreid met nieuwe functionaliteiten, vaak opgelegd door revisies in de DirectX API en vervolgens indirect overgebracht via extensies naar OpenGL en de interne kloksnelheden werden geoptimaliseerd. Deze impasse van vrij veilige innovatie eindigde nog maar zeer recent in november 2006 toen nVidia zijn nieuwe G80 chipset lanceerde, de basis van de GeForce 8 familie [29]. De G80 is de eerste GPU voor desktop PC’s opgebouwd rond de gloed nieuwe unified shading architectuur die is opgelegd door het vernieuwde DirectX 10 framework van Windows Vista. Waar vroeger aparte units zorgden voor het verwerken van vertices, fragmenten, enzovoort, worden nu streamprocessors dynamisch gealloceerd om een bepaalde taak tot zich te nemen. In feite was deze keer ATI nVidia voor maar de eerste ATI chip op deze architectuur is uitsluitend bedoelt voor de Xbox 360 [25], de desktop variant is nog steeds niet gelanceerd op het moment van schrijven. Natuurlijk omvat de geschiedenis van de GPU nog veel meer zaken, dit zijn echter de meest belangrijke mijlpalen. Meer over de geschiedenis van GPU’s is te vinden in [26]. Wat de toekomst ons zal brengen blijft natuurlijk onzeker maar we kunnen nu al enkele opmerkelijke trends zien opduiken her en der. GPU’s beginnen stilaan hun weg te vinden ook buiten het computer graphics gebied als General Purpose Graphics Processing Unit (GPGPU). De enorme parallelle kracht om miljoenen floats per seconde te berekenen is een zeer handige eigenschap die door de wetenschappelijke wereld niet onopgemerkt is gebleven. Ook de recente fusie tussen AMD en ATI is zeer speciaal en hint naar de interesses om CPU’s en GPU’s op


12

Figuur 2.9: Systeem architectuur. Let op de mogelijkheid voor parallelle werking tussen GPU/CPU en de grote verschillen in memory-bandwidth. één enkel stukje silicon te persen. Intel heeft bijvoorbeeld zijn ideeën hieromtrent ook nooit onder stoelen of banken gestoken en nVidia lijkt dankzij de G80, de meest complexe chip ooit gebakken, ook klaar te zijn voor een evolutie naar een CPU/GPU design. Maar uiteindelijk wordt dit afwachten en zal de tijd uitwijzen welke grote evoluties nog gaan gebeuren in de wereld van GPU’s.

2.2.2

Systeem Architectuur

In figuur 2.9 geven we een simpel beeld weer van de architectuur in huidige computers. Sinds het ontstaan van de GPU, was het niet alleen de bedoeling dat de GPU 3D bewerkingen zou accelereren en later berekenen, maar dat het ook in parallel zou werken met de CPU. Dit lijkt een vrij logisch principe waar men niet veel langer bij moet blijven stilstaan. In de praktijk is het echter zo dat er vrij makkelijk door slechte programmacode en een gebrek aan kennis, zeer snel deze parallelliteit doorbroken kan worden. Wanneer de CPU terecht komt in een fase waar hij moet wachten op de GPU, of omgekeerd, zal de performantie van de applicatie met ettelijke factoren gekelderd worden. Een tweede belangrijke opmerking die we hier maken houdt verband met geheugen. GPU’s hebben toegang tot video RAM. Communicatie met dit geheugen kan ontzettend snel plaats vinden, voor de op dit moment krachtigste GPU, de Geforce 8800 GTX, houdt dit een band-


13

Figuur 2.10: Simpele weergave van een Geforce 6. VP=Vertex Processor; FP = Fragment Processor. width in van maar liefst 86,4 GB/s. Dit staat in sterk contrast met de bandwidth snelheid tussen de GPU en het Systeem geheugen. Het is dus ten alle tijde van het hoogste belang dat men ervoor zorgt dat zoveel mogelijk data die de GPU nodig heeft, al reeds gecached zit in het VRAM. PCI-express heeft dankzij zijn grotere bandwidth deze bottleneck wat kunnen verkleinen maar het is bijvoorbeeld nog steeds een zeer slecht idee om geometerische data elke frame opnieuw te versturen naar de GPU of om leesopdrachten door de CPU te laten uitvoeren in het VRAM.

2.2.3

The Past: Parallel Pipelined GPU

Jarenlang is de architecuur van GPU’s gebouwd geweest rond hetzelfde principe. Voor elke kernel in de render pipeline werd een apparte fysische special-purpose processor gebruikt en verschillende van deze pipes werden in parallel opgesteld. Figuur 2.10 geeft dit principe weer aan de hand van een schema gebasseerd op de architectuur van een nVidia GeForce 6. Het ontwerp is vooral gefocust op de vertex en fragment processors, ook wel shaders genoemd. Men kan makkelijk inzien dat deze structuur een letterlijke toepassing is van het streaming model met de vertex en fragment processors als belangrijkste kernels. Wanneer men het schema goed bekijkt kan men zien dat er minder vertex processors aanwezig zijn dan fragment shaders. Dit is zo altijd het geval geweest en vormt ook meteen één van de grootste problemen in deze architectuur. Men gaat er namelijk vanuit dat er ten alle tijden meer fragmentprocessing nodig is dan vertexprocessing. Op het eerste zicht niet zo een gek idee daar er meestal meer fragmenten per frame zijn dan effectieve vertices. Doch ontstaan er ook situaties waarin er meer vertices verwerkt moeten worden of waarin de vertex shader een complexere taak moet uitvoeren dan de fragment shader. In deze gevallen zal de hardware slechts sub-optimaal gaan presteren doordat fragment processors geen werk


14

Figuur 2.11: Zicht op één enkele pipeline. zullen hebben en in een idle-state terecht komen. Dit is een ware nachtmerrie die grafisch programmeurs niet graag tegenkomen omdat men atlijd ten volle gebruik van elke hardware component wil maken. Het omgekeerde probleem is trouwens ook waar. Het kan gebeuren dat een scene geometrisch niet complex is, maar dat de fragment shading ontzettend zware bewerkingen moet uitvoeren. In dit geval zullen vertex processors bijna niet aan het werken zijn, terwijl de fragment shaders overuren draaien. In figuur 2.11 geven we de flow van één enkele pipeline in deze architectuur weer, samen met de programmeerbare kernels. Voor een uitgebreidere bespreking van deze architectuur kan men de diepere details nalezen van een GeForce 6 en zo een zeer duidelijk beeld verkrijgen van de parallelle pipeline architectuur [16]. Deze stof gaat echter te ver buiten het eigenlijke vaarwater van deze thesis maar vormt desalniettemin interessante lectuur.

2.2.4

Next-Generation: Unified Shading GPU

Sinds kort zijn we een nieuw GPU-tijdperk binnengetreden onder leiding van de nVidia G80 en onder de eisen van Microsoft’s DirectX 10. Het unified shading process is de grootste vernieuwing sinds de release van de allereerste 3Dfx Voodoo, omdat het een volledig nieuwe wending heeft gegeven aan de onderliggende processor-architectuur van de GPU. In plaats van aparte special-purpose processors met een specifieke taak achter elkaar te koppelen tot een pipeline, bestaat het unified idee uit een batterij van streamprocessors die in staat zijn om dynamisch gealloceerd te worden met een bepaalde functie. We kunnen vanaf nu dan ook niet meer spreken van een fysisch ge¨ımplementeerde pipelining omdat een streamprocessor zowel de taak van vertex, fragment of geometrie shader op zich kan nemen. Figuur 2.12 toont dit aan met behulp van een schema gebasseerd op de G80 architectuur. In feite is er nog steeds een pipelining maar deze is nu opgebouwd doordat streams (ook wel threads genoemd in de G80) verschillende loops kunnen maken doorheen de architectuur. Figuur 2.13 geeft een vergelijking tussen het traditionele model en unified shading. Men praat al jaren over een unified shading process, maar tegenhangers vonden dat op dit moment zulke hardware helemaal nog niet zou presteren ten opzichte van het zichzelf al


15

Figuur 2.12: Simpele voorstellingen van de belangrijkste principes van de GeForce 8 Unified Architectuur. Let op de flow die verschillende keren doorheen het design kan stromen en de mogelijkheid om na amper één run al feedback te geven. SP = een cluster van 2x acht streamprocessors.

Figuur 2.13: Traditioneel vs Unified concept.


16

Figuur 2.14: Load-balancing in de unified architectuur. Witte vakjes bevinden zich in een idle-state. bewezen parallel pipeline process. Grappig gegeven is dat één der grootste tegenhangers van deze nieuwe architectuur nVidia was, maar misschien waren ze dit enkel om zand in de ogen van de concurrentie te strooien. Het feit is dat de G80 ongelooflijke prestaties neerzet. De redenen om een unified shading process te verkiezen boven het gekende traditionele alternatief zijn immers zeer groot. Zo is het nu zeer makkelijk om functionaliteiten te delen tussen verschillende kernels van de pipeline. In het oude systeem was dit niet zo vanzelfsprekend en was het soms zelfs onmogelijk om bepaalde features te delen. Te denken valt hier bijvoorbeeld aan vertextexturen. Ongeacht een wijd verspreide foutieve gedachte, maakten vertextextures geen onderdeel uit van de door DirectX gespecificeerde Shader Model 3.0 (SM3.0) standaard, die bepaalde eisen oplegt aan GPU’s om DirectX compatibel te zijn. nVidia ondersteunde deze nieuwigheid wel al beginnende vanaf de GeForce 6, hoewel dit gepaard ging met bepaalde performance problemen. Desalnietemin kon men vertextextures al gebruiken, terwijl ATI verklaarde om zolang als vertextextures geen standaard werden, dit niet te gaan ondersteunen wegens moeilijkheden in hun huidige architectuur. Vandaar dus dat zelfs het ATI vlaggenschip van dit moment, de X1950XTX, nog steeds geen vertextextures ondersteund. Het is gewoon te moeilijk om een efficiënte oplossing te vinden binnen hun huidge architectuur. Een tweede, en misschien ook wel de grootste, reden om voor een unified shading architectuur te kiezen ligt in de dynamische load-balancing van shader-units. In het verleden moest


17

men steeds een soort van “sweetspot” vinden tussen het aantal vertex en fragment processors. Nu kan de GPU zelf at-runtime op een per-frame basis uitmaken hoeveel shader units er voor elke type van shading nodig zijn. Figuur 2.14 geeft dit principe weer. Waar er tijdens het oude process bottlenecks konden ontstaan die componenten uit de hardware onbenut lieten, zorgt het unified process ten allentijde dat alle hardware onderdelen effectief benut worden. Ook is dit design veel makkelijker te scalen. Men hoeft enkel wat streamprocessors weg te nemen of bij te voegen om een nieuwe “klasse” van GPU’s te voorzien. Een commerciële handigheid bij het opstellen van de verschillende budget-reeksen in een nieuwe GPU-familie. Los staand van het eigenlijke unified process zijn er ook nog andere vernieuwingen die een onrechtstreeks gevolg zijn: de geometrie shader die de primitive assembly vervangt, 100% efficiënte shaderbranching die branches volgt op een per-pixel niveau ongeacht het codepad van andere fragmenten, krachtigere multisampling om anti-aliasing uit te voeren en vertex feedback één der waar in het pipeline process. Al de technische specificaties van de G80 zijn terug te vinden in de G80 documentatie beschikbaar op de nVidia website [29, 30, 32]. Meer informatie over directX 10 kan men vinden op de Microsoft of de nVidia website [31].

2.3

Geometrische Complexiteit

Men heeft aangetoond dat GPU’s sneller evolueren dan de wet van Moore voorschrijft [37]. Dit is een ontzettende vaststelling en doordat CPU’s wel mooi de curve van de wet van Moore volgen heeft dit een groot gevolg ingehouden voor real-time computer graphics. Tijdens de eerste graphics accelerators en GPU’s waren programma’s steeds gelimiteerd in de capaciteiten van de video-hardware. Geometrische complexiteit was dan ook een vrij simpel concept dat puur de vertex en polygon count inhield. In deze systemen deed men er dan ook alles aan om zoveel mogelijk polygonen uit de render pipeline te krijgen in een zo vroeg mogelijk stadium. Ontzettend veel CPU-budget werd dan ook gescheduled in technieken met deze taak. Populair waren bijvoorbeeld Level of Detail, het versimpelen van geometrie, of opstellen van een Potential Visible Set (PVS) via hiërachische methodes, het berekenen van enkel en alleen die polygonen waarvan men nagenoeg zeker is dat ze uitgetekend zullen worden [22, 11, 12]. Het is ergens verrassend om op te merken dat er nog steeds niet zoveel aandacht wordt geschonken aan het feit dat geometrische complexiteit in nuance verschoven is. Omstreeks de tijd van de eerste DirectX 9.0c hardware kunnen we vaststellen dat de zwakste schakel in een typische computer graphics setup, niet meer de GPU dan wel de CPU is. Men heeft dit al aangetoond [45]. In figuur 2.15A worden verschillende GPU’s getest op twee verschillende CPU’s. In deze grafiek wordt gemeten hoeveel batches - één batch komt overeen met één drawcall in een render API - er maximaal op de render pipeline gezet kunnen worden per seconde met een wisselende hoeveelheid driehoeken per batch. In de figuur 2.15B is het principe van het resultaat wat duidelijker geschetst. We zien namelijk dat ongeacht de GPU het aantal batches gelijk blijft per CPU, ofdat er nu slechts één triangle aanwezig is per batch of er 200 maakt niet uit. Zelfs de invloed van de GPU is nihil, in de test presteerde een GeForce 2 bijna even goed als een GeForce 5, hardware met drie generaties tussen. Het kleine verschil tussen GPU’s is te verklaren door verschillende codepaden in de driver. De enige factor die een duidelijke invloed heeft op de prestatie is de CPU.


Figuur 2.15: CPU batch performance. (bron: [45])

18


19

Figuur 2.16: Batch-size performantie. (bron: [45]) In figuur 2.16 worden de throughputs van enkele GPU’s getest. Er wordt berekend hoeveel driehoeken een GPU in totaal kan uittekenen per seconde waarbij het aantal driehoeken in een batch geleidelijk wordt verhoogd. Het is duidelijk in te zien dat in het begin van de grafiek de applicatie volledig gelimiteerd wordt door de CPU. Er worden zoveel mogelijk batches verzonden maar de uiteindelijke hoeveelheid triangles is te klein om een onderscheid te zien tussen de verschillende video-hardware. Een GeForce 2 presteert hier opnieuw hetzelfde als een GeForce 5. Naarmate het aantal triangles stijgt per batch begint het werk voor de GPU intensiever te worden en na 130 triangles per batch zien we hoe de GeForce 2 het moet laten afweten, zijn performance is gewoon niet sterk genoeg om de hoeveelheid driehoeken te blijven verwerken. We kunnen zien hoe kaart na kaart moet afhaken en hoe de GeForce 5 dapper driehoeken blijft verwerken. Huidige hardware - opnieuw drie generaties verder - heeft zelfs een nog grotere vertexprocessing en fillrate - snelheid van de rasterizer - gekregen. Wat deze grafieken ons leren is dat de grootste bottleneck van het systeem ligt in het verzenden van batches, oftewel de drawcalls die de CPU moet versturen. Ze tonen ook aan dat een traditionele aanpak van geometrische complexiteit zoals Level of Detail totaal geen nut heeft. Ofdat we nu 1000 batches per seconde versturen met 1000 triangles in elke batch of met één enkele, zal nauwelijks invloed hebben door de ontzettend grote rauwe vertex- en fragmentprocessing van huidige GPU’s. In tegendeel, Level of Detail zal er juist voor zorgen dat de GPU niet genoeg werk krijgt en dat hij niets meer te doen heeft, kostbare hardware die verloren gaat aan het uitvoeren van geen enkele instructie. Men kan natuurlijk wanneer men merkt in deze situatie terecht te zijn gekomen, gebruik maken van veel zwaardere belichtingsmodellen - bijvoorbeeld fresneltermen mee inrekenen [33] - zodat de GPU wel degelijk aan het werk blijft en er geen onbenutte hardware overblijft. Dit wordt zelfs aangeraden om


20

te doen zodat tenminste de beeldkwaliteit hoog blijft [45]. Verder wordt het ook duidelijk dat andere traditionele methodes om complexe scènes aan te pakken zoals PVS-gebasseerde algoritmes uitgesloten zijn. Deze algoritmes maken een hevig gebruik van de CPU, maar deze is al overwerkt enkel en alleen door het versturen van drawcalls. Hierdoor zal zo een “optimalisatie” juist gaan tegenwerken en zal meer kosten dan dat het winst maakt. Een ouder onderzoek toonde aan dat voor een 1 Ghz processor ongeveer 10000 tot 40000 batches per seconde konden worden verzonden [45]. Een wat recenter onderzoek toont aan dat op een modernere CPU dit nummer verwacht kan worden te liggen rond de 30000 tot 120000 batches per seconde [10]. Dit is echter niet veel, als we een interactieve framerate van 30 FPS willen behouden betekent dit slechts 1000 tot 4000 batches per seconde. Een bos vol bomen, een leger dat aanvalt en heel snel zit men aan dit aantal batches per seconde zonder dat de CPU nog tijd heeft om onderhoudstaken uit te voeren zoals input processing, game logic, artificiële intelligentie, streaming en caching van data,... De meeste computer graphics applicaties en zeker video-games zouden liever duizenden batches van enkele triangles verzenden in plaats van enkele batches van duizenden driehoeken wegens scenemanagement. Dit zal dus echter niet meer de manier van werken zijn om nextgeneration applicaties te laten voldoen aan de nieuwe gestelde eisen van mooier”, “sneller” en vooral “veel meer”. In de volgende twee hoofdstukken zullen we nu gaan kijken wat er gedaan kan worden om het aantal batches te reduceren zonder hierdoor de CPU te zwaar te belasten.

Hoofdstuk 3

Geometrische Instanties When we get turned on, there’s bound to be flames. - Jeanette, Vampire: The Masquerade - Bloodlines

Zoals reeds is aangehaald, verkiezen zware computer graphics applicaties, zoals games, grote hoeveelheden kleine batches om uit te tekenen. In dit hoofdstuk zullen we opzoek gaan naar een methode die gebruikt kan worden om zulk een grote massa aan batches te transformeren naar zo weinig mogelijk grote batches. Op die manier kan men nog steeds grote hoeveelheden aan objecten renderen maar wordt de last van de CPU sterk afgenomen doordat minder drawcalls verstuurd moeten worden.

3.1

Geometrische Buffers

Voor we beginnen aan de eigenlijke bespreking van geometrische instanties is het belangrijk om even het concept van geometrische buffers aan te halen. In feite is een geometrische buffer de onderliggende structuur voor de opbouw van een renderbatch. Net als geometrische instanciëring nu, heeft het even geduurd voordat geometrische buffers een weg vonden in Computer Graphics maar ze zijn ondertussen wel goed ingeburgerd. Vroeger gebeurde de rendering van objecten via een onmiddellijk modus in de gebruikte render API. Hierbij werd elke primitief met zijn vertices individueel doorgezonden naar de GPU, elk frame opnieuw. Dit geeft een ontzettende overlast aan functiecalls en een hoop data die elk frame over de transportbussen naar de video-hardware moet worden gezonden. Displaylists in OpenGL trachtten het functiecall probleem op te lossen maar ondertussen zijn er de geometrische buffers die beide problemen kunnen aanpakken [36]. In wezen bestaan geometrische buffers uit minstens twee componenten: een vertex buffer en een index buffer. De vertex buffer houdt alle data van de vertices van een object bij, terwijl de index buffer de data van de polygonen bevat. In feite houdt de index buffer in elk element een index bij naar de vertex buffer. Deze buffers kunnen dan vervolgens verzonden worden naar de GPU die deze opslaat in zijn VRAM. Op deze manier hoeft de geometrische data van objecten slechts in een pre-render fase geupload te worden en kan tijdens de renderfase uitgetekend worden via een drawcall. Geometrische buffers kunnen verder ook nog andere data bevatten, meest voorkomende zijn buffers voor normalen en tangentvectoren, textuurcoördinaten, vertexkleuren, enzovoort. 21

HOOFDSTUK 3. GEOMETRISCHE INSTANTIES

22

Figuur 3.1: Structuur van een geometrische buffer met één driehoek aangeduid.

3.2

Filosofie

Vaak worden er aparte batches - en dus geometrische buffers - gebruikt voor elk individueel object in de te renderen virtuele wereld. Tot op een bepaald niveau was dit haalbaar maar doordat applicaties tegenwoordig verondersteld zijn om een complexe wereld te kunnen renderen met duizenden individuele objecten per frame, is het dus niet meer haalbaar voor de CPU om zoveel drawcalls te versturen. Geometrische instanciëring tracht dit probleem op te lossen door batches te mergen met elkaar zodat er in plaats van duizenden kleine batches, enkele grote batches overblijven. Zoals we gezien hebben in het vorige hoofdstuk maakt het voor huidige hardware niet uit hoe groot een batch is, de prestatie blijft hetzelfde ofdat er nu maar één of 1000 triangles in de batch aanwezig zijn. Deze methode is vooral zeer doeltreffend voor het renderen van vele gelijkaardige objecten. Bijvoorbeeld in de situatie waar we een bos willen renderen zal er vaak gebruik gemaakt worden van slechts enkele boommodellen. In plaats van de GPU honderden keren te vragen de boom opnieuw te renderen zal instancing trachten om met één vraag de GPU de boom honderden keren te laten renderen.

3.3

Gevaren en Moeilijkheden

Er zijn enkele belangrijke redenen waarom 3D engines graag werken met grote hoeveelheden kleine batches. Dit heeft alles te maken met de rendercontext waarin een batch en aldus een object, zich bevindt. Bijna elk object zal een bepaalde verandering in renderstate nodig hebben. Objecten hebben een andere textuur nodig, een andere materiaal shader en bijna elk object onderscheidt zich van de rest door de nood aan een andere wereldmatrix. De verschillende soorten van geometrische instanties trachtten deze renderstatechanges te overwinnen waarbij de ene techniek flexibeler dan wel performanter zal zijn dan de andere.


3.4

23

Geometrische Instantie Methodes

We zullen nu beginnen aan de bespreking van Geometrische Instanties. In de volgende puntjes zullen de verschillende soorten van instanciëring aan bod komen die momenteel het populairste zijn zoals aangegeven in [10, 20, 15]. Belangrijk om in te zien is dat de ene methode beter geschikt is voor een bepaalde groep van objecten dan een andere soort. Men moet dus steeds in het praktische gebruik van instancing beslissen hoe flexibel een bepaald object moet zijn en vervolgens een geschikte instantie methode kiezen. Ook kan de factor videogeheugen een zeer grote rol spelen.

3.4.1

Statische Instanci¨ ering

Statische instanciëring is de eenvoudigste en efficiëntste vorm van instanciëren. Hierdoor is het ook de minst flexibele doordat, zoals de naam laat vermoeden, enkel statische geometrie kan genieten van deze methode. Objecten die moeten kunnen bewegen doorheen de wereld kunnen dus geen gebruik maken van deze techniek. Het statisch instanciëren houdt in dat we alle objecten die tot eenzelfde materiaal klasse en texture behoren gaan groeperen in één enkele batch. In een pre-render fase wordt er aldus een grote geometrie buffer aangemaakt waar de meshdata van elke instantie naartoe gekopieërd wordt. De vertices worden echter eerst nog getransformeerd van objectruimte naar wereldruimte. Het renderen van deze grote batch is dus zeer recht toe recht aan, in de render pipeline hoeft nu zelfs geen wereldmatrix meer gespecificeerd te worden. Figuur 3.2 geeft een overzicht van het concept. Ontzettend veel objecten kunnen op deze manier bijeengevoegd worden tot één batch en vervolgens via slechts één drawcall uitgetekend worden. Het is zelfs mogelijk om objecten met een verschillende mesh te groeperen doordat er toch een volledige geometrie buffer aangemaakt moet worden. Door de transformatie van vertices uit objectruimte naar wereldruimte moet men er wel op letten indien er normaaldata en tangentvectoren nodig zijn, dat ook deze data mee getransformeerd moet worden. Dit kan tijdens het aanmaken van de batch door te transformeren met het rotatiegedeelte van het object zijn wereldmatrix. Het zal immers onmogelijk zijn om bijvoorbeeld in een vertexshader de wereldmatrix van het object op te vragen omdat deze data niet meer beschikbaar zal zijn, immers al de objecten zijn reeds getransformeerd en de gehele batch staat in wereldruimte.

3.4.2

Dynamische Instanci¨ ering

Deze instantie methode bouwt verder op statisch instanciëren. In plaats van enkel en alleen de data door te sturen naar de GPU in een pre-render fase, zal er bij dynamische instanciëring elk frame een update plaats vinden van de opgeslagen geometrische buffer. Deze update houdt in dat alle vertices - en eventueel normaal en tangent data - opnieuw getransformeerd worden naar wereldruimte met geupdate wereldmatrices. Deze vorm van instanciëren is de meest flexibele. Er kunnen bewegende entiteiten tot en met GPU geskinde objecten - GPU verwerkte skeletanimatie van het object - worden ondersteund. Dynamische instanciëring is echter ook de traagste vorm door de trage dataoverdracht in elk frame. Er moet inderdaad enkel vertexdata over de transportbussen gezonden worden, doch is en blijft dit een zeer trage opdracht. Verder is het updaten van buffers in het VRAM ook nog


24

Figuur 3.2: Twee instanties van een statische batch. steeds niet zo efficiënt. Render API’s geven mogelijkheden om de buffers in het geheugen te optimaliseren voor snellere data-updates, maar dit gaat dan weer ten koste van performantie tijdens de render fase [36].

3.4.3

Vertex Atribuut Instanci¨ ering

Het grote probleem bij dynamisch instanciëren zit in de overlast aan data-overdracht naar de GPU. Vertex atribuut instanciëring probeert dit op te lossen door in plaats van de getransformeerde vertices elk frame door te sturen, enkel de wereldmatrices te verzenden. De opbouw van de batch is gelijkaardig aan de twee vorige methodes, enkel dat deze keer alle data in objectruimte wordt behouden. Elk frame wordt er dan een nieuwe stream samengesteld die de wereldmatrices bevat van elk object. Men kan hiervoor bijvoorbeeld vier vectoren voor gebruiken die samen de matrix voorstellen. Om geheugen en data-overdracht te besparen zou men ook twee vectoren kunnen gebruiken waarbij er een quaternion gebruikt wordt voor de rotaties [10]. Deze tweede methode zal echter zorgen voor extra overhead in de vertexshader. Om de juiste matrix terug te vinden in deze stream zal er ook een extra ID-buffer aangemaakt moeten worden in de batch, bijvoorbeeld met een één dimensionaal textuurco¨ ordinaat dat aangeeft tot welke instantie de huidige vertex behoord. In de vertexshader kunnen we vervolgens nagaan via de ID welke matrix we nodig hebben, deze matrix samenstellen en vervolgens de vertex transformeren via de samengestelde wereldmatrix en huidge camera en projectie matrices. In figuur 3.3 tonen we de opbouw van de geometrische buffer om deze instantie methode uit te voeren. Deze methode vermindert de data-overdracht elk frame met een aanzienlijke factor, zeker in het geval van complexere modellen, doordat nu niet meer elke vertex doorgestuurd moet worden, maar enkel nog de wereldmatrix. Deze techniek is wel minder flexibel dan dynamisch instanciëren doordat er programmeerbare vertexshaders nodig zijn, echter de hardware van drie generaties terug voldeed al aan deze voorwaarde. Een tweede probleem kan ook het


Figuur 3.3: Geometrische buffer tijdens Vertex Atribuut Instantie.

25


26

aantal variabelen zijn waartoe een shader toegang heeft. Voor een G80 GPU onder OpenGL kunnen we 4096 floats gebruiken, voor elke matrix zijn er 16 floats nodig dus houdt dit in dat we maixmaal 256 objecten in één batch kunnen groeperen. Als men bijvoorbeeld ook objecten heeft zoals geanimeerde karakters die via de GPU geskinned moeten worden zal deze methode niet meer haalbaar zijn wegens een tekort aan variabelen. Skinning heeft immers informatie nodig over de botten van het animatieskelet. Deze informatie moet ook met behulp van attributen doorgestuurd worden waardoor we nog minder instanties kunnen groeperen in een batch. Op de G80 worden onder OpenGL ook bindable uniforms ondersteund zodat de data in een vertex buffer gebonden kan worden aan een uniforme variabele [32]. Op deze manier kan men per variabele 65536 componenten opslaan en vervalt het tekort aan toegangsmogelijkheden in de vertexshader. Deze feature is op dit moment echter enkel en alleen beschikbaar op de GeForce 8 familie en zoals we later zullen zien is deze methode iets kostelijker en minder performant dan het gebruik van gewone uniforme variabelen door de indirecte adressering van de data.

3.4.4

Instanci¨ ering met Render API

In de twee meest populaire render API’s OpenGL en DirectX is de belangrijkheid van instanciëring niet onopgemerkt gebleven. Op vorige generaties GPU’s werd al een eerste poging gedaan naar een standaard voor Instanciëren onder de “instancing API” en in DirectX 10 is instanciëring één van de basisprincipes geworden. Ook OpenGL heeft zich verijkt met Instanciëring via enkele nieuwe extensies die indirect voortkomen uit DirectX 10. Voor beide render API’s is de werkwijze gelijkaardig. Via een speciale drawcall kan men specificeren hoeveel keer de geometrische buffer gerendered moet worden. Via een stream methode zoals bij de vorige techniek worden vervolgens wereldmatrices doorgegeven. Een ingebouwde variabele in de nieuwe shaderinstructies kan vervolgens in de vertexshader gebruikt worden om een ID te verkrijgen van de huidige instantie die verwerkt moet worden om zo de juiste wereldmatrix samen te stellen. Deze methode maakt het eindelijk mogelijk om de hoge geheugenkosten te beperken. In al de vorige instantie methodes moesten kopies bewaard worden van vaak dezelfde meshdata voor elke instantie. Via de API calls moet men slechts één kopie bewaren die vervolgens veelvuldig wordt gerenderd, zie figuur 3.4. In de toekomst kunnen we verwachten dat deze instantie techniek de standaard gaat worden voor dynamische en geanimeerde entiteiten hoewel ze op dit moment wat betreft prestatie iets minder goed is dan de methode uit het vorige punt. Het feit dat er een veel lagere memory-footprint is, maakt deze techniek toch al de meest nuttige op dit moment. Niet al de video-kaarten, nieuw of oud, genieten van dezelfde 768 MB video geheugen als de GeForce 8800 GTX.

3.5

Optimalisaties

Het gebruik van geometrische instanciëring gaat hand in hand met een creatief gebruik. Vaak kunnen kleine weizigingen aangebracht worden in de algemene methodes wanneer men


Figuur 3.4: Geometrische buffer tijdens API Instantie.

27


28

een goed beeld heeft van de 3D engine structuur en de aard van objecten die men wil instanciëren. We stellen alvast enkele handige tips en optimalisatie mogelijkheden voor.

3.5.1

Vertex Cache

We hebben tot nu toe aangenomen dat de grootte van een batch niet uitmaakt. In feite is dit niet helemaal waar. Naargelang de grafische hardware is er een bepaald punt waar de performantie gekelderd wordt. Dit heeft te maken met de vertex cache van een GPU. Er zijn twee caches aanwezig, één voor de vertexprocessor en één na. De cache na de vertexprocessing wordt ook wel de post-T&L cache genoemd en is zeer klein in grootte, slechts enkele vertices. Deze cache is eigenlijk altijd belangrijk omdat ze gebruikt wordt om te controleren ofdat de huidige te verwerken vertex niet al eens is getransformeerd zodat men gewoon de vertex uit de cache kan gebruiken. Om deze eigenschap van GPU’s uit te buiten volstaat het om meshdata zodanig te genereren dat ze bestaat uit trianglestrips, een handige tool hiervoor is nVidia’s NVTriStrip [34]. De cache vóór de vertexprocessing is de cache die voor instanciëring zeer belangrijk is. Deze cache wordt ook wel de pre-T&L cache genoemd en wordt gebruikt om de vertexdata uit het VRAM te bufferen voor verwerking door de vertexprocessors. Hier ligt dan ook de limiet voor instanciëren. Elke batch moet kleiner blijven dan het totaal aantal slots beschikbaar voor vertices in de pre-T&L cache. Gelukkig ligt op huidige GPU’s deze waarde zeer hoog. Voor de GeForce 8 is momenteel nog geen informatie te vinden maar voor de GeForce 6 bedroeg dit reeds ongeveer 64000 vertices.[5]

3.5.2

Segment Buffering

Deze techniek is enkel van toepassing op statische instanties. Via segment buffering kan men view frustum culling - of mogelijke andere vormen van culling - toepassen op de instanties binnen een batch. In feite bestaat de techniek eruit dat men de grote statische batch zal uittekenen in enkele segmenten. Er zullen dus iets meer rendercalls nodig zijn, maar men krijgt hiervoor een gereduceerde vertex en polygonload terug. Segment buffering zal dus zeker handig zijn wanneer er vrij complexe statische objecten gegroepeerd zijn die in hun geheel een te grote overhead teweeg brengen aan transformatie kosten in de vertexshader. [35] Voor men begint aan het samenstellen van de grote statische buffer moet men eerst zorgen dat er een spatiale coherentie onstaat in de volgorde waarin de objecten aan de buffer toegevoegd worden. De auteur van deze techniek raadt een Kd-tree aan, maar in feite is elke hiërachische boomstructuur voldoende. Door vervolgens deze boom te doorlopen in een depth-first wijze kunnen we op deze manier een één dimensionale lijst maken waarbij de buren van elementen in de lijst ook dichtbij elkaar liggen in de wereld. Het aanmaken van deze lijst moet natuurlijk enkel en alleen gebeuren wanneer er nieuwe statische instanties ge¨ıntroduceerd worden, meestal is het dus voldoende om enkel in een pre-renderfase deze lijst te berekenen. Bij het aanmaken van de statische buffer moet men er ook voor zorgen dat de startindex naar de eerste primitief van elke instantie bewaard wordt.


29

Voordat men nu de statische batch rendert moet men eerst een frustum culling uitvoeren op de objecten in deze batch om zo een lijst te verkrijgen met daarin enkel de potentieel zichtbare objecten. Hieruit kan men nu segmenten creëren van instanties die op elkaar aansluiten in de effectief opgeslagen batch en enkel en alleen die segmenten uittekenen. Op deze manier hebben we dus iets meer drawcalls uitgevoerd maar moeten we ook een heel stuk minder geometrie op de render pipeline plaatsen.

3.5.3

Segment Instanci¨ ering

Het probleem van segment buffering is tweevoudig. Het eerste probleem bestaat eruit dat we enkel en alleen statische objecten kunnen laten genieten van deze methode. Het tweede probleem ligt in het feit dat we extra batches herintroduceren. Beide problemen kunnen aangepakt worden dankzij de nieuwe instantie API drawcalls. Wanneer we dynamische objecten instanciëren via de API calls kunnen we een soort van segment buffering gaan toepassen tijdens de update van de batch. In feite is dit een heel simpel principe waar zelfs geen boomstructuur meer bij nodig is, al wordt er aangeraden om frustum culling altijd via een tree uit te voeren [35, 9]. Wanneer we tijdens de updatefase van de batch eerst al de instanties cullen en zo een lijst aanmaken met enkel de potentieel zichtbare objecten, kunnen we de wereldmatrixstream enkel en alleen voorzien van de matrices van de zichtbare entiteiten. In de rendercall kunnen we immers specificeren hoeveel instanties er getekend moeten worden. Doordat de zichtbare hoeveelheid nooit groter kan zijn dan wat er in de gehele buffer opgeslagen is, riskeren we dus niet een te grote stream wereldmatrices te verzenden. Deze optimalisatie is opnieuw een extra reden om dynamische objecten te instanciëren via de nieuwe instantie calls, hoewel vertex attribuut instanciëring iets sneller zou kunnen zijn als volledige batches in rekening worden genomen.

3.5.4

Textuurarrays

Tot nog toe hebben we enkel gesproken over hoe we de renderstatechanges veroorzaakt door wereldmatrices kunnen omzeilen in instancing. Er is ook een manier om texturestatechanges aan te pakken. Hiervoor kunnen textuur-atlassen gebruikt worden waarbij verschillende texturen gegroepeerd worden in één enkele textuurmap. Dit geeft echter problemen en is een vrij omslachtige methode die men bijna als een goedkope hack” zou kunnen omschrijven. Wanneer men een textuur-atlas gebruikt moet men al de textuurcoördinaten van alle instanties herscalen. Men moet hierbij oppassen dat er genoeg ruimte zit tussen de texturen in de atlas omdat anders bleeding artefacten kunnen onstaan door textuurfiltering. Verder is men steeds gelimiteerd door zeer strikte textuurdimensies die de hoeveelheid van gegroepeerde texturen beperkt. Een betere oplossing is er momenteel in de vorm van textuurarrays. Dit is een nieuw soort van buffer dat gebruikt kan worden om texturen op te slaan in het video-geheugen op een manier zoals gewone vertexbuffers. Textuurarrays kunnen opgevat worden als 3D texturen waarbij de lengte van de array gelijk staat met de diepte van de 3D textuur, echter in hardware worden de texturen nog steeds behandeld als gewone 2D texturen en zijn dus niet gelimiteerd


30

tot dieptes die veelvouden van twee zijn. Het is zelfs mogelijk om textuurarrays van 3D texturen aan te maken. Door textuurarrays te gebruiken kan men een zeer handige atlas aanmaken van al de texturen die nodig zijn voor alle objecten in de wereld. Verder moet men in plaats van de textuurcoördinaten te herscalen, ze enkel uitbreiden met een derde component waarin een index wordt bijgehouden naar de juiste textuur in de atlas. Theoretisch gezien wordt het op deze manier nagenoeg mogelijk om via één enkele drawcall alle objecten in de wereld te renderen, mits al deze objecten dezelfde shader gebruiken.

3.5.5

Level Of Detail

We hebben al vermeld dat de grote van een batch niet echt uitmaakt op de grootte van de pre-T&L cache na. Vandaar dat op zich Level of Detail technieken niet meer zo interessant zijn op huidige grafische hardware. Level of Detail is immers een techniek die het aantal vertices en polygonen van een object aanpast, bijvoorbeeld objecten die verder weg liggen zullen veel minder geometriedata bevatten terwijl objecten die dicht bij het waarnemingspunt liggen gebruik maken van veel meer data. Hoewel voor huidige GPU’s de grote van de batch niet veel uitmaakt, kan het echter wel dat men op een bepaald moment zoveel geometrie probeert uit te tekenen dat zelfs de snelste GPU’s de hoge vertex transformatie kosten niet meer aan kunnen. Er is nog altijd ergens een bepaalde limiet ook aan het aantal vertices dat men kan verwerken. Het probleem is dat wanneer men een beroep doet op instanciëring om de CPU te ontladen van de grote hoeveelheid drawcalls, het niet meer vanzelfsprekend of eigenlijk ronduit onmogelijk wordt om Level of Detail te gebruiken. We hebben uiteindelijk slechts één objectrepresentatie die ge¨ınstanced is en die we niet op een instantieniveau kunnen aanpassen. Wanneer men ontdekt gelimiteerd te zijn aan het aantal te verwerken vertices, moet men trachtten het aantal vertices te verminderen. Als dit niet gaat on-the-fly met Level of Detail, bijvoorbeeld doordat de scène gebruik maakt van instanties, zal men van in het begin al moeten werken met modellen die een stuk minder vertices bevatten. In feite is dit tegenwoordig geen probleem meer dankzij nieuwe per-pixel belichtingstechnieken die het mogelijk maken om zeer lage polygonmodellen eruit te doen laten zien als zeer hoge polygonmodellen. Wat er precies zal gebeuren is dat we het aantal vertices verminderen dankzij de lichtere modellen en zo de vertexbottleneck kunnen ontladen. Anderzijds verkrijgen we wel een hogere fragmentshading kost door de gesofisticeerdere belichting die we gebruiken om onze modellen eruit te doen laten zien alsof ze ontworpen zijn met duizenden of zelfs miljoenen aan vertices en polygonen. De twee per-fragment belichtingsmethodes die we zullen bespreken zijn normaalmapping en het gerelateerde parallaxmapping. Normaalmapping Wanneer een scène belicht wordt, gebeurt dit aan de hand van een belichtingsvergelijking. Voor meer informatie over deze vergelijking verwijzen we naar de appendices. Beknopt sa-


31

Figuur 3.5: Tangentruimte van een vierhoek. Rood is de tangent, groen is de bitangent en blauw de normaal. mengevat is één van de belangrijkste parameters in deze vergelijking de normaal die gebruikt wordt. De normaal definieert uiteindelijk de structuur en curvatuur van het oppervlak dat we gaan belichten. Vroeger werd er vaak één normaal per polygoon gebruikt wat een zeer plat resultaat geeft. Hierna begon men normalen te specificeren per-vertex en werd elke vertex belicht, het resultaat werd dan over de polygoon ge¨ınterpoleerd, ook wel Gouraud shading genoemd [22]. Dit geeft een veel zachtere inkleuring. Een nog wat geavanceerdere vorm is zogenaamde Phong shading waarbij de normaal eerst wordt ge¨ınterpoleerd en vervolgens zal men per-fragment het licht berekenen met deze nieuwe normaal[22]. Hoe preciezer de normaal in een fragment hoe beter de belichting zal zijn doordat hierdoor het oppervlak in de fragment beter gedefinieerd is. Wanneer de belichting accurater is, zal men ook een visueel betere representatie van het object krijgen. Dit is dan ook de hoofdgedachte achter normaalmapping. Phong shading zal enkel een goed resultaat geven wanneer het oppervlak van het model lokaal continue blijft. Een stenen muur lijkt bijvoorbeeld op het eerste gezicht lokaal zeer continue, maar dat is niet zo. Tussen lagen stenen zitten groeven cement die vaak iets dieper liggen in de muur. Stenen zelf kunnen ook kleine discontinuiteiten en onregelmatigheden vertonen of er kunnen zelfs stukken uit een steen gebroken zijn. Phong shading kan in al deze gevallen geen nauwkeurige normaal leveren, behalve wanneer al de stenen en groeven zeer precies gemodelleerd zijn wat een ontzettend grote vertex en polycount met zich meebrengt. Ook al wordt een plat oppervlak gebruikt, als we de normalen precies kunnen benaderen zal de belichting op dit oppervlak eruit zien als een veel gedetailleerder oppervlak. Met normaalmapping zal men eerst een zeer hoog polygoonmodel maken in een modelleerpakket als bijvoorbeeld 3ds Max of Maya. Vervolgens wordt dit model versimpeld, in het geval van de muur kan men bijvoorbeeld een simpel vierkant nemen en wordt er een normaalmap opgesteld. Dit is een textuur zoals bijvoorbeeld ook voor kleur gebruikt wordt, maar nu wordt voor elke texel een genormalizeerde en gescalleerde normaal opgeslaan die


32

Figuur 3.6: Normaalmap voor een gedetailleerde stenen muur. de structuur van het hoge polygoonmodel definieert. De normaal moet eerst genormalizeerd zijn en vervolgens gescaleerd zodat we deze in een kleurenformaat kunnen opslaan dat voor texturen gebruikt wordt. De scalering zorgt er gewoon voor dat de normaalcomponenten die tussen [−1, 1] liggen nu in kleurruimte liggen dat gaat van [0, 1]. Hiervoor kan men formule 3.1 gebruiken indien de normaal reeds genormalizeerd is. normalT exel.r = (normal.x + 1) /2 normalT exel.g = (normal.y + 1) /2 normalT exel.b = (normal.z + 1) /2

(3.1)

Een laatste hinderpunt met normaaltexturen is de ruimte waarin de normaal opgeslagen moet worden. Objectruimte lijkt een goede keuze maar net zoals met de wereld of de cameraruimte geeft dit een probleem als het object gemorpht, gescaleerd of geroteerd wordt doordat de normalen niet meer in de juiste richting wijzen en dus zou de normaalmap opnieuw opgebouwd moeten worden [13]. Een betere oplossing is om tangentruimte te gebruiken, ook wel textuurruimte genoemd. Dit is een ruimte die per polygoon gedefinieerd is via de normaal, tangent en bitangent van de vertices van de polygoon, figuur 3.5 geeft deze ruimte weer. Als al de normalen zijn opgeslagen in tangentruimte verkrijgen we een textuur zoals te zien is in figuur 3.6. Typisch voor deze texturen is de blauwachtige kleur doordat de gewone normaal recht naar boven wijst - een waarde in de textuur van (0.5, 0.5, 1.0). Het is verder ook opvallend hoe er een illusie van structuur en curvatuur door deze map gecreërd wordt. We kunnen nu in de fragmentshader de normaalmap sampelen om zo een nieuwe normaal te verkrijgen per-pixel die het oppervlak in het fragment zeer precies weergeeft en alzo een accuratere belichting kan berekenen. Deze gesampelde normaal staat echter in tangentruimte en dus moeten we deze eerst transformeren naar de ruimte waarin de andere vectoren van de lichtvergelijking staan of we moeten ervoor zorgen dat al deze vectoren in tangentruimte


33

Figuur 3.7: Het probleem van ontbrekende parallax doordat er geen rekening wordt gehouden met de kijkhoek. worden omgezet. Alle vectoren moeten immers in dezelfde ruimte staan om de belichting te berekenen. De beste optie hier is om te zorgen dat al de vectoren in tangentruimte staan. We kunnen dit immers al in de vertexshader berekenen wat veel goedkoper zal zijn in plaats van in elke fragment een transformatie te moeten uitvoeren vanuit tangentruimte. Het omzetten van een vector naar tangentruimte is zeer simpel. Men hoeft de vector enkel te vermenigvuldigen met de zogenaamde TBN-matrix, Tangent-Bitangent-Normaal-matrix. Deze matrix is zoals de naam laat vermoeden een drie bij drie matrix met als eerste rij de tangent, op de tweede rij de bitangent en op de derde rij de normaal van de tangentbasis, zie formule 3.2. Deze matrix vormt dus een basis voor de tangentruimte naar waar we willen transformeren. Voor normaalmapping betekent dit dat we in de vertexshader de lichtvector berekenen en vervolgens deze lichtvector vermenigvuldigen met de TBN-matrix waarbij de normaal, tangent en bitangent van de huidige vertex gebruikt worden. Men moet hier wel opletten dat ook al deze vectoren in dezelfde ruimte moeten staan, wereld of objectruimte is hier een populaire keuze doordat vaak in één van deze twee ruimtes de per-vertex normaal al gedefinieerd is en doordat de lichtvector makkelijk in deze ruimtes te berekenen is.   tangent.x tangent.y tangent.z T BN =  bitangent.x bitangent.y bitangent.z  (3.2) normal.x normal.y normal.z Parallaxmapping Normaalmapping geeft degelijke resultaten maar blijft last hebben van verschillende nadelen. Zo gaat de illusie van bumps en structuren gecreërd door de normaalmapping verloren wanneer we een object van vrij dichtbij bekijken. Ook is het voor normaalmapping niet mogelijk om vrij grote discontinu¨ıteiten in normalen goed weer te geven, enkel vrij kleine oneffenheden geven een goed resultaat. Tot slot en waarschijnlijk het meest vervelende probleem dat indirect bijdraagt aan de twee andere nadelen, is het gebrek aan parallax. Hiermee bedoelen we dat er geen rekening wordt gehouden met de kijkhoek op het object, figuur 3.7 illustreert dit.


34

Figuur 3.8: Hoogtemap voor een gedetailleerde stenen muur. Parallaxmapping probeert deze problemen aan te pakken en voegt slechts enkele extra operaties toe aan gewoon normaalmappen. Het idee bestaat eruit om in de fragmentshader eerst een offset te berekenen op basis van een hoogtemap en de kijkvector die de textuurcoördinaten aanpast zodat de eigenlijke zichtbare positie van het oppervlak benaderd wordt [44]. De hoogtemap is een acht bit grijswaardenbeeld waarbij elke waarde een hoogte voorstelt. De hoogtemap definieert zo voor elke texel hoe hoog het oppervlak hier eigenlijk zou moeten zijn, figuur 3.8 geeft een voorbeeld van een hoogtemap voor een stenen muur. Net zoals de lichtvector in tangentruimte moet getransformeerd zijn, moeten we nu ook de viewvector in de vertexshader gaan transformeren naar tangentruimte omdat de textuurcoördinaten en de hoogtemap in tangentruimte gedefinieerd zijn. Als we de kijkvector in de vertexshader berekend hebben laten we deze interpoleren over de fragmenten en in elk fragment wordt deze vector vervolgens genormalizeerd. Met deze informatie kunnen we nu de offset berekenen door na te gaan welke vector, parallel met de polygoon, ons brengt van het eigenlijke oppervlaktepunt uit de hoogtemap naar de kijkvector zoals aangegeven is in figuur 3.9. Deze offset tellen we dan op bij onze oorspronkelijke textuurcoördinaten. De waarde uit de hoogtemap wordt meestal echter eerst nog gescaleerd en verschoven naargelang de waardes waartussen de hoogtes zouden moeten liggen, immers al de hoogtes zijn gecodeerd in de textuur liggende tussen [0, 1]. De formule om de nieuwe accuratere geparallaxte textuurcoördinaten te verkrijgen is weergegeven in 3.3. Tnew = Toriginal + (hsb × V iewxy /V iewz )

(3.3)

Hierbij stelt hsb de gescaleerde en verschoven hoogte weer: hsb = height × scale + bias

(3.4)


35

Figuur 3.9: Offset berekening voor parallaxmapping. Let op het feit dat ook de offset niet het echte samplepunt vindt maar enkel een benadering.

Figuur 3.10: Vergelijking van parallaxmapping en normaalmapping. Op deze manier kunnen we parallax correcte posities benaderen en sampelen uit de rest van onze texturen zoals bijvoorbeeld diffusemaps, normaalmaps en speculairemaps. Het enige extra werk ten opzichte van normaalmappen is de extra textuursampling van de hoogtemap, de berekening van de offset en de transformatie van de kijkvector. De winst in kwaliteit is echter ongelooflijk zoals blijkt uit figuur 3.10. De enige zwakke punten van parallaxmapping zijn self-occlusions en dat het enkel de echte positie kan benaderen. Door afstandsfuncties te gebruiken kan men deze twee problemen wel oplossen. Dit is echter een heel stuk complexer om uit te voeren doordat er rays getraceerd worden in de fragmentshader waardoor deze methode praktisch enkel bruikbaar is op krachtige video-hardware die een optimale shaderbranching ondersteunt [14].

Hoofdstuk 4

Hardware Occlusion Queries Perhaps we are asking the wrong questions. - Agent Brown, The Matrix

In het vorige hoofdstuk hebben we gezien hoe geometrische instanties gebruikt kunnen worden om het aantal renderbatches in een scene te verminderen door zoveel mogelijk van deze batches te groeperen. In dit hoofdstuk gaan we kijken hoe we het aantal rendercalls kunnen verminderen door enkel en alleen de objecten te tekenen die ook daadwerkelijk zichtbaar zullen zijn in het huidige frame. Hiervoor zullen we een beroep doen op hardware occlusion queries om een occlusion culling techniek te creëren. Er bestaan echter heel wat cullingalgoritmes, al dan niet occlusion of een andere culling methode. Deze technieken vereisen echter vaak een zware inspanning van de CPU en zijn soms ook enkel gericht naar het verminderen van de polygonen opzich. Wij zijn meer ge¨ınteresseerd in een techniek die een snelle culling uitvoert op objecten of groepen van objecten met zo min mogelijk interventie van de CPU. We zullen in dit hoofdstuk eerst hardware occlusion queries bespreken, hoe ze werken en wat de nadelen en gevaren zijn. Vervolgens zullen we een algortime behandelen dat deze queries gebruikt om de objecten in een scene te cullen en in welk opzicht dit algoritme te verkiezen valt boven traditionele culling methodes.

4.1

Occlusion culling

Het is misschien handig eerst even stil te staan bij het concept occlusion culling”. Het idee bestaat erin om voor het renderen van een frame eerst te gaan bepalen welke objecten effectief zichtbaar zullen zijn. Hierna worden enkel en alleen deze objecten getekend, wat een bepaalde performantie winst moet opleveren. In een scene zullen er altijd objecten zijn die ervoor zorgen dat andere entiteiten verborgen zijn vanuit het observerende camerastandpunt. Deze objecten kunnen we ook wel occluders noemen. Occlusion culling tracht om deze objecten te vinden en enkel en alleen de niet geocclude objecten te renderen. Er bestaan enkele occlusion technieken die gebruik maken van de CPU, meestal met de bedoeling gebruikt te worden op terrein hoogte data. Ook algoritmes als portal-culling zou men kunnen omvatten als een soort van statische occlusion culling doordat in een pre-renderfase zichtbaarheidsinformatie wordt opgesteld voor verschillende viewpoints. Op de GPU zijn er

36

HOOFDSTUK 4. HARDWARE OCCLUSION QUERIES

37

twee mogelijkheden om occlusion culling te doen. Enerzijds via de hardware queries en anderzijds via early z-culling. Beide methodes kunnen steeds uitgebreid worden naar dynamische scènes en geometrie, ze vereisen dus geen statische levels zoals bijvoorbeeld portal-culling [8, 9].

4.1.1

Early-z Culling

Op moderne hardware worden z-waardes met de dieptebuffer gecontroleerd voordat het fragmentprogramma uitgevoerd wordt. Op deze manier worden pixels enkel belicht wanneer ze de huidige waarde in de framebuffer ook daadwerkelijk gaan overschrijven doordat de pixel dichterbij het waarnemingspunt gelegen is. Vandaar dat z-culling in feite bestaat uit twee renderpasses, eerst wordt er enkel naar de dieptebuffer (Z-Buffer) gerenderd zonder kleurwaardes te gaan berekenen en in een tweede stap wordt er effectief gerenderd maar deze keer worden de z-waardes enkel vergeleken met de dieptebuffer en worden geen waardes meer geschreven. Op deze manier zullen dus enkel fragmentshaders losgelaten worden op pixels die in het uiteindelijke frame ook daadwerkelijk zichtbaar zullen zijn. Deze methode brengt echter wel een dubbele transformatiekost met zich mee en werkt enkel wanneer de hardware early-z rejects ondersteunt.

4.1.2

Occlusion Queries

Deze techniek werkt zeer verschillend van early-z culling. Met de queries kan er aan de GPU gevraagd worden hoeveel pixels zichtbaar zijn van een renderbatch na zijn rendering. Deze informatie kan dus gebruikt worden om te beslissen of een object al dan niet zichtbaar is of geocclude wordt. Early-z culling werkt binnen de rasterizer en zal daar beslissingen maken terwijl occlusion queries op een object of polygoon niveau werken. Occlusion queries maken eigenlijk al lang deel uit van zowel OpenGL als DirectX. Ze dateren terug van de GeForce 3 reeks en waren een echte droom voor elke grafische programmeur. Dit maakt het des te vreemder om op te merken dat occlusion queries tot op de dag van vandaag nog steeds weinig aandacht krijgen en niet volledig naar waarde worden geschat. De grote reden hierachter zal waarschijnlijk het feit zijn dat de queries gepaard gaan met enkele zeer belangrijke gevaren waarvan de grafische programmeur goed op de hoogte moet wezen. Verder is het niet zo simpel om deze gevaren te omzeilen. We zullen in het volgende puntje deze gevaren bespreken. De algemene werking van de occlusion queries is vrij simpel en nagenoeg hetzelfde voor zowel OpenGL als DirectX. Voordat men de geometrie die getest moet worden rendert, specificeert men eerst dat het hier gaat om een occlusion query. Men kan eventueel vervolgens instellen om niets naar de diepte- of de framebuffer te schrijven. Uiteindelijk moet men de geometrie renderen en kan men het resultaat van de query opvragen.

4.2

Stalls, Starvations and Boxes

We gaan nu even stil blijven staan bij de gevaren van occlusion queries omdat startende van hieruit we een veel beter inzicht krijgen in het praktische gebruik van de queries. Een eerste opmerking die we gaan maken is: waarvan moeten we eigenlijk een query maken? Dit is


38

Figuur 4.1: Stalls en Starvations op de CPU en GPU. Q = Query, R = Render, C = Cull. een slimme vraag doordat de GPU ons een resultaat zal geven nadat een object gerenderd is. Vrij logisch want de GPU moet zelf gaan kijken hoeveel pixels er zichtbaar zullen zijn, welke andere optie is er dan resterende van het object te renderen? Dit komt ons echter slecht uit want we willen ons juist de kost besparen om het object onnodig te transformeren en te renderen wanneer het toch niet zichtbaar is. Vandaar dat in de praktijk occlusion queries bijna steeds uitgevoerd zullen worden op de boundingbox van een object, de ruimte die het gehele object omsluit. Op deze manier kunnen we de transformatie kosten sterk reduceren en behouden we toch steeds een vrij goede representatie van ons eigenlijke object en de ruimte die het object inneemt. Een groter probleem komen we echter tegen in het eigenlijke communiceren met de GPU. Wanneer we een query formuleren aan de GPU zal de CPU moeten wachten op een antwoord. Dit leidt tot CPU-stalls en GPU-starvations. Zoals we reeds gezien hebben is één der basisprincipes van de GPU om parallel te werken met de CPU. Bij een verkeerd en onvoorzichtig gebruik van occlusion queries kan men dit basisprincipe de das om doen met zware performantieproblemen als gevolg. Wanneer we een occlusion query versturen en wachten op het resultaat alvorens ander werk te verrichten hebben we effectief de CPU geblokeerd en laten stallen omdat het resultaat dat door de GPU verwerkt en teruggezonden moet worden even op zich kan laten wachten. Dit heeft alles te maken met het volgende gelijkaardige probleem. Een CPU kan heel wat commando’s naar de GPU verzenden. Deze commando’s worden in een First-in-First-out (FIFO) lijst gebufferd op de GPU. Moderne hardware kan soms twee tot drie frames aan commando’s gebufferd hebben, wachtende op uitvoer. Als de CPU een query verstuurd, komt deze in de wachtrij te staan. Uiteindelijk wordt de query uitgevoerd en terug verzonden naar de CPU. Doordat de CPU heeft staan wachten op het resultaat is de volledige FIFO rij uitgeput en aldus verkeerd de GPU nu in een staat van starvation doordat er geen commando’s meer te vinden zijn. Figuur 4.1 duidt dit probleem aan. Het is vrij makkelijk in te zien dat CPU en GPU bijna sequentieel gaan beginnen werken en men zal zien dat op deze manier het gebruik van hardware occlusion queries veel meer kan gaan kosten dan effectief opbrengt. Een allereerste grote regel waardat men zich dus aan moet houden bij het gebruik van occlusion queries is dat men eerst al de queries stelt en later


39

pas de resultaten gaat opzoeken om beslissingen te maken of dat een object nu wel of niet gerenderd moet worden. We moeten er voor zorgen dat steeds genoeg werk aan CPU en GPU gegeven wordt tussen het stellen van een query en het verkrijgen van het resultaat.

4.3

Kennis van het Verleden

Een vrij logische stap die ook gebruikt wordt in early-z culling, is het sorteren van alle objecten op afstand. Zo worden eerst al de occluders getest en getekend, gevolgd door al de geocclude objecten. Dit kan echter problemen veroorzaken wanneer we testen met bounding geometrie zoals een box, figuur 4.2 illustreert dit. De box van het voorste object occlude de box van achterste object maar wanneer we kijken naar de ware geometrie van beide voorwerpen constateren we dat het achterste object toch zichtbaar is. Deze objecten worden geen occluders genoemd maar occludees en er is vastgesteld dat occludees eerst gerenderd moeten worden en dat daarna pas occlusion queries gebruikt kunnen worden voor kleinere objecten. Niet alleen compliceert dit de hele toepassing van occlusion queries, ook de winst in performantie kan weer een groot vraagteken worden. Een simpele, maar ook radicale, oplossing die men vervolgens voorstelt is om occlusion queries te vertragen naar het volgende frame. Bij het renderen van het huidige frame worden voor alle objecten queries geformuleerd zodat voor objecten die in het vorige frame zichtbaar waren, hun geometrie gebruikt wordt en entiteiten die niet zichtbaar waren gebruik maken van hun boundingbox voor de query.[42] Dit is een simpele maar doeltreffende oplossing die het gebruik van queries zeer goed gebruikt om zoveel mogelijk geometrie snel te cullen met een zeer lage kost, de achterstand van één frame is niet zo erg doordat een interactieve applicatie doorgaans toch werkt met een refresh rate van minstens 30 FPS. Echter het aantal rendercalls zal nog steeds hetzelfde blijven en hoewel deze methode goed zal werken voor scènes met een laag aantal complexe objecten, waren we meer ge¨ınteresseerd om ook het aantal batches te verminderen.

4.4

Coherent Hi¨ erachical Culling

Men heeft verder gewerkt aan het gebruik van occlusion queries wat resulteerde in een werkwijze waarbij beslissingen gemaakt worden op een groep van objecten in plaats van op onderlinge objecten [8, 9]. Het idee bestaat erin om net zoals vaak bij view frustum culling gedaan wordt, een spatiale hiërarchische boomstructuur te gebruiken zodat op een hoger niveau nodes geculled kunnen worden zodat volledige groepen van objecten geen test meer vereisen. Verder buit het algoritme ook nog steeds de temporele coherentie van typische Computer Graphics applicaties uit, door zichtbaarheidsinformatie uit het vorige frame te gebruiken bij het renderen van het huidige frame.

4.4.1

Hi¨ erarchies

Spatiale hiërachisch structuren zoals Kd-trees, boundingvolume trees of bsp-trees verdelen de ruimte van de wereld op in steeds kleiner wordende cellen tot een bepaalde diepte bereikt is. Zulke structuren zijn zeer handig om beslissingen te kunnen maken over grote groepen


40

Figuur 4.2: De boom vormt een occludee voor het karakter, doordat enkel de boundingbox van de boom het karakter occlude terwijl de geometrie van de boom dit niet doet. van objecten. Zo kunnen we bijvoorbeeld interior nodes van de boomstructuur gaan testen op occlusion, als een interior node geocclude is weten we dat alle kinderen van deze node ook verscholen zullen zijn en hoeven we deze nodes niet meer te testen wat ons een hele hoop werk uitspaard.

4.4.2

Hi¨ erarchisch Stop en Wacht

In dit algoritme wordt een hiërarchische structuur gebruikt om eerst de wereld te partitioneren. Vervolgens wordt voor de boundingbox van elke node beginnende vanaf de root een occlusion query verstuurd en wacht men op een antwoord. Als de node zichtbaar is worden de kinderen van de node gesorteerd op afstand en vervolgens recursief verwerkt op eenzelfde manier. Wanneer een node niet zichtbaar blijkt te zien worden de gehele subboom vanaf deze node weggeschrapt. Een eerste probleem met deze techniek is dat we stalls en starvations herintroduceren doordat er bij de query van elke node gewacht moet worden op een resultaat. Een tweede probleem zit in de query overhead. In de best case van het algoritme zullen we een grote performantie winst boeken doordat enkele queries genoeg zijn om de scene te cullen, de worst case daarentegen gaat ons heel wat performantie kosten doordat nu niet alleen de objecten (de bladeren van de boom) getest worden maar ook nog eens een hele hoop interior nodes. Deze twee problemen maken dit algoritme praktisch niet zo interessant.


4.4.3

41

Coherent Hi¨ erachical Culling Algoritme

In het “Stop en Wacht” algoritme worden de spatiale eigenschappen van een scène uitgebuit maar niet meer de temporele coherentie die typisch is aan interactieve computer graphics. In het CHC algoritme wordt deze eigenschap wel gebruikt en worden de problemen van het “Stop en Wacht” algoritme opgelost. Temporele coherentie Net zoals we in 4.3 hebben gedaan kunnen we opnieuw informatie uit het vorige frame gaan gebruiken. Deze keer gaan we echter een soort van gok wagen op basis van deze informatie, maar uiteindelijk zorgen we ervoor dat onze gok geverifieerd wordt. Wanneer een node zichtbaar was in het vorige frame gaan we er vanuit dat de node nog steeds zichtbaar is, interior nodes worden verder recursief verwerkt en de bladeren - waar onze geometrie data zit - worden uit getekend samen met het versturen van een query. Nodes die in het vorige frame niet zichtbaar waren, veronderstellen we nog steeds geocclude te zijn. Deze nodes worden dan niet verwerkt. Als we op deze manier zouden werken kunnen er twee foutieve situaties voorkomen. Enerzijds kan het zijn dat we een node tekenen die uiteindelijk geocclude blijkt te zijn. In dit geval hebben we onnodig rekenwerk verricht maar het eindresultaat is correct en vertoont geen artefacten. Anderzijds is er het geval dat we een node niet tekenen terwijl die wel zichtbaar is geworden. In dit geval verkrijgen we een foutief beeld. In 4.3 is dit niet opgelost en wordt er vertrouwd op de snelle refreshrate van de beelden. Dit blijft echter een wat vuile oplossing daarom zullen we in het geval van nodes die niet zichtbaar waren in het vorige frame eerst een query opstellen, eventueel met bounding geometrie. Wanneer we geen nodes meer kunnen oplossen zonder eerst een query te stellen of wanneer we het resultaat van een query verkrijgen, verwerken we dit resultaat. Als blijkt dat de node nog steeds niet zichtbaar zal zijn, kunnen we deze gewoon cullen. Wanneer blijkt dat deze toch zichtbaar is kunnen de kinderen van de node recursief getest worden. In figuur 4.3 tonen we deze uitbreiding. Als uitbreiding hierop zou men in plaats van aan te nemen dat wanneer een node in het vorige frame zichtbaar was het in het volgende frame ook zichtbaar is, ook kunnen aannemen dat de node gedurende verschillende frames zichtbaar is. Op deze manier kan men gedurende enkele frames de queries van deze nodes volledig achterwege laten. Voor een frameduratie van bijvoorbeeld drie frames zou dit de vereiste queries met bijna een factor drie verminderen [9]. Omgekeerde Overerving Het enige probleem dat ons nog rest is de grote hoeveelheid queries. We kunnen dit nu echter ook oplossen. We gaan nodes die zichtbaar waren reeds behandelen alsof ze ook dit frame zichtbaar zijn wat inhoudt dat we de kinderen verwerken en een query opstellen of in het geval van een blad, we de geometrie tekenen en een query versturen. Het is echter mogelijk om voor de interior nodes die zichtbaar waren niet eens een query op te stellen. We kunnen deze zichtbaarheidsinformatie deduceren uit de kinderen van de node. Het komt er dus op neer dat we enkel een query moeten stellen voor de bladeren en voor de grootste interior node die geocclude was in het vorige frame. Andere nodes hebben geen behoefte aan een query omdat we deze informatie naar boven kunnen optrekken in de boom eens deze


42

Figuur 4.3: Guessing van zichtbaarheid. Wit is zichtbaar, grijs niet. Let op de drie occlude bladeren in het paarse gebied die onnodig uitgetekend worden door de onmiddellijke verwerking van deze nodes en de verwachting dat ze zichtbaar zijn. informatie geweten is. Dit klinkt moeilijker dan het is, we proberen het concept hiervan te verduidelijken in figuur 4.4.

4.4.4

Minder Queries, Minder Stalls

Er zijn duidelijk minder tot geen stalls meer aanwezig in CHC vergeleken met het “Stop en Wacht” algoritme. Dit komt doordat we nu tussen queries in de CPU en GPU bezig houden met ander nuttig werk, zoals het verwerken van de volgende nodes en renderen van geometrie waar we al zekerheid over hebben. In feite is er enkel nog een kritiek punt waar een stall zou kunnen voorkomen wanneer al de zichtbare geometrie al getekend is en er gewacht moet worden op nog enkele resultaten van nodes die in het vorige frame geocclude waren. Er zijn ook minder queries nodig doordat we het testen van interior nodes tot een minimum hebben beperkt. Het “Stop en Wacht” algoritme presteert ook goed in situaties waar er veel culling gebeurd maar in bijvoorbeeld een algemeen overzicht van de hele scène waar er weinig occlusion is, zal deze methode ontzettend veel kosten door het testen van al de interior nodes. Men kan inzien dat het aantal queries afhankelijk is van de diepte van de boom en het aantal objecten in de scène. Door in CHC slimmer om te gaan met interior nodes is het opstellen van queries nu slechts afhankelijk van het aantal zichtbare objecten in het frame, op deze manier blijft CHC competitief in alle mogelijke situaties.

4.4.5

Optimalisaties

Er kunnen nog enkele aanpassingen aangebracht worden in het concept van CHC. Deze optimalisaties kunnen in bepaalde situaties een betere prestatie opleveren.


43

Figuur 4.4: Optrekken van zichtbaarheidsinformatie doorheen de boom. Wit is zichtbaar, grijs niet. Let op de rode pijlen die een optrekking van zichtbaarheidsinformatie weergeven maar ook een situatie waar informatie wordt neergetrokken in de boom. Early-z Cull Voor bepaalde toepassingen of situaties kan het voordelig zijn om eerst een depth-only pass uit te voeren met het algoritme. Dit gaat natuurlijk wel ten koste gaan van een hogere transformatiekost en drawcalls. In de eigenlijke render pass hoeft men het CHC algoritme niet meer te gebruiken doordat al de zichtbaarheidsinformatie al beschikbaar is. Een renderengine kan in deze pass zich dan vooral focussen op het sorteren van objecten om zo min mogelijk renderstatechanges te veroorzaken [9]. Zichtbaarheids Treshold Als men bereid is om enkele mogelijke artefacten in het beeld te accepteren in ruil voor een betere performantie, kan men het aantal pixels dat nodig is voor een positief queryresultaat verhogen. In een normale gang van zaken gaan we er vanuit dat een query positief is als er minstens één pixel zichtbaar was. Men kan hier eventueel een andere minimumlimiet opleggen om zo agressiever te cullen. Er wordt echter aangeraden deze treshold niet te hoog te zetten of men loopt het risico om potentiële occluders ook te cullen wat waarschijnlijk ten koste zal gaan van zowel beeldkwaliteit als performantie [9].

Hoofdstuk 5

Uitgestelde Shading Ubiri Oruje! - Random Stalkers, S.T.A.L.K.E.R.: Shadow of Chernobyl

Met de komst van snelle high-end graphics oplossingen is het niet zo abnormaal dat ook belichting een zeer belangrijke factor speelt in huidige Computer Graphics toepassingen. In dit hoofdstuk gaan we kijken hoe we een complexe scène kunnen gaan belichten met een groot aantal lichtbronnen. We zullen zien dat forward rendering te kort zal schieten en vervolgens zullen we een zeer mooi alternatief bespreken, namelijk uitgestelde shading, het scheiden van geometrie rendering en belichting.

5.1

Achtergrond

Het is tegenwoordig niet voldoende om alleen te beschikken over spectaculaire belichtingseffecten zoals bumptechnieken. Het aantal lichtbronnen, liefst dynamisch, is ook een zeer belangrijk gegeven geworden. Er worden op dit moment de eerste stappen gezet om globale belichting toe te passen in real-time applicaties maar in dit meeste gevallen blijkt dit toch nog steeds te hoog gegrepen en onbruikbaar in praktische toepassingen. Vandaar dat er vaak een ontzettende hoeveelheid lichtbronnen gebruikt worden die door artists zo geplaatst worden dat een globale belichtings “look” gesimuleerd kan worden. Om zo een grote hoeveelheid lichtbronnen te kunnen renderen gebruiken forward renderers complexe technieken en datastructuren om voor elk object een set te creëren van de lichten die een invloed hebben op het te renderen voorwerp. Sinds kort bestaat er ook een alternatieve methode in de vorm van uitgestelde shading, ook wel deferred shading genoemd. Hierbij worden eerst al de eigenschappen van de geometrie gerenderd, denk maar aan de diffuse kleur en de normalen van objecten. In een tweede stap wordt de belichting berekend. Geometrie en belichting zijn dus volledig van elkaar gescheiden. Deze techniek is in feite geen nieuw concept maar het is pas sinds zeer recent dat ze ook effectief real-time gebruikt kan worden. We hebben eindelijk de nodige hardware en dankzij de hoge hoeveelheid lichten wordt uitgestelde shading tot een maximum uitgebuit. Commercieel gezien zijn de eerste stappen in de deferred shading wereld nog maar pas gezet. Bij de introductie van de GeForce 6 werd er al een soort van “proof of concept” gecreërd door de mensen van nVidia in de Nalu demo [19] en sinds zeer kort is er ook een eerste commerciële game-title die 44

HOOFDSTUK 5. UITGESTELDE SHADING

45

volledig gebruik maakt van deferred shading: S.T.A.L.K.E.R.: Shadow of Chernobyl. Een artikel over de deferred shader van S.T.A.L.K.E.R. geeft ook interessante details omtrent het process van het omzetten van een traditionele forward renderer naar een uitgestelde shader [43].

5.2

Waarom Uitgesteld Shaden?

Door de grote hoeveelheid aan lichtbronnen in een scène wordt het onmogelijk voor een 3Dengine om in de fragmentshaders over al deze lichten te itereren en de belichtingsresultaten te accumuleren. Neem als praktisch voorbeeld S.T.A.L.K.E.R. waar er per frame niet minder dan 50 lichtbronnen gemiddeld invloed hebben op de scène [43]. Zelfs als lichtbronnen mee geculled zouden worden met geometrie is deze hoeveelheid dus nog steeds te complex voor een fragmentshader. Forwar renderers gaan daarom beslissingen maken omtrent de lichtbronnen die invloed hebben op het object dat gerenderd moet worden. Dit zijn vaak complexe technieken maar hun grootste probleem is dat ze enkel toepasbaar zijn op een per-object niveau. Wanneer een scène volledig gebruik heeft gemaakt van instanties om zoveel mogelijk batches te groeperen wordt het voor een forward renderer ontzettend moeilijk, zoniet onmogelijk, om nog te specificeren welke lichtbronnen invloed hebben op een instantie uit een batch. Uitgestelde shading omzeilt dit probleem door de rendering van de geometrie te ontkoppelen van de belichting. Op deze manier maakt het niet meer uit of dat geometrie ge¨ınstancieërd is of niet. Zelfs in het geval dat we er niet voor kiezen om een scène te instanciëren kan uitgestelde shading een grote winst opleveren. Forward renderers hebben twee opties. Ze kunnen eerst over al de objecten itereren en voor elk object over al de lichtbronnen lopen. Of ze kunnen het omgekeerd aanpakken door voor elk licht een nieuwe pass te gebruiken die al de objecten tekenent. Beide methodes hebben zware nadelen. In het eerste geval kan het zijn dat eerder geshade objecten overtekend worden en dus onnodig belicht zijn geweest. In het tweede geval wordt dit nog eens uitgebreid met de mogelijkheid dat transformatiekosten van objecten herhaald worden. Maar het grootste probleem van beide ligt in de complexiteit, worst-case geldt voor beide gevallen O (objecten × lichten). Door de ontkoppeling van geometrie en belichting in de uitgestelde shader geldt er hier slechts een worst-case scenario O (objecten + lichten). Men verwachtte dat uitgestelde shading enkel een probleem zou kunnen geven bij het renderen van scènes met veel directe lichtbronnen doordat de complexiteit van de belichtingspass gelijk zal zijn aan O (schermresolutie × lichten), doordat elke pixel be¨ınvloed wordt door dit type van bron [19]. Deze claim wordt nu echter gerelativeerd doordat deferred shading wel weer optimaler is dan forward shading wanneer een directe lichtbron ook schaduwen mag casten in de wereld [38]. De keuze om een uitgestelde shader te gebruiken hangt dus af van het soort scène dat men wil gaan renderen maar in vele gevallen zal men toch een winst kunnen ondervinden bij de uitgestelde shader.


5.3

46

De Uitgestelde Shader

We zullen nu bespreken hoe een uitgestelde shader werkt. Eerst en vooral overlopen we de verschillende stadia van de deferred renderer. We beginnen met het renderen van onze geometrie naar een geometrie-buffer, ook wel kortweg de G-Buffer genoemd. Let op dat deze buffer niets te maken heeft met de geometrische buffers die we gezien hebben bij de geometrie instanties. Doordat de gebruikte shaders in deze pass nog al complex kunnen zijn wordt er soms geopteerd eerst een depth-only pass uit te voeren zodat early-z culling gebruikt kan worden tijdens de eigenlijk renderfase. Vervolgens wordt de G-Buffer gebruikt om voor elk licht de belichting uit te voeren. Op dit uiteindelijk verkregen beeld kunnen dan nog post-processing effecten toegepast worden zoals blooming.

5.3.1

Voorbereiding

Voor men kan beginnen moet er beslist worden hoe de G-Buffer eruit zal zien. Meestal worden er voor de G-Buffer vier rendertargets gebruikt. De parameters die naar deze targets worden gerenderd kunnen in principe vrij gekozen worden, maar men moet er natuurlijk rekening mee houden dat tijdens de belichtingsfase al de nodige data beschikbaar is in de G-Buffer. De meest voorkomende verdeling van de G-Buffer bestaat uit een target met de diffuse kleur van de scène, één met de normalen, één met de speculaire component en een dieptebuffer. In plaats van de dieptebuffer wordt ook wel eens de positie van elke pixel in cameraruimte opgeslagen maar dit geeft doorgaans precisieproblemen. Uit de dieptebuffer kan men in de belichtingsfase de eigenlijke positie in cameraruimte herconstrueren.

5.3.2

Geometrische Stap

Indien de shaderberekeningen in deze fase intensief zijn en als men last heeft van te veel overdraw, kan men opteren deze fase op te splitsen in twee passes waarbij eerst de geometrie enkel naar de dieptebuffer wordt geschreven. In een tweede pass rendert men de geometrie naar de G-Buffer en zorgt early-z culling ervoor dat enkel de zichtbare pixels verwerkt zullen worden. Dit gaat natuurlijk wel ten koste van een dubbele transformatiekost. Op moderne hardware ken men nu gebruik maken van Multiple Render Targets (MRT), op deze manier kan men in één pass al de componenten in de G-Buffer vullen. Bij het invullen van de G-Buffer moet men ervoor zorgen dat vectoren, zoals normalen, getransformeerd worden naar de cameraruimte. Dit is zeer belangrijk omdat de belichtingsfase plaats vindt in cameraruimte, alle vectoren moeten dus in deze ruimte getransformeerd zijn. Dit houdt ook in dat wanneer er normaalmapping gebruikt wordt, deze transformatie in de fragmentshader moet gebeuren. Vandaar dat een dieptepass interessant kan worden. Figuur 5.1 geeft het resultaat weer van de G-Buffer na de geometrie stage.

5.3.3

Belichtings Stap

Vanaf dit stadium wordt er niet meer gewerkt in een 3D omgeving maar in 2D. Dit is één van de situaties waarin de orthogonale projectie zeer handig is. We moeten nu voor elk licht een screen-alligned rechthoek gaan teken ter grootte van het uiteindelijk gewilde beeld, dus met andere woorden de schermresolutie. Om een basiskleur te verkrijgen wordt er eerst een rechthoek getekend met de ambiente lichtkleur. Hiervoor wordt de diffuse kleur uit de


47

Figuur 5.1: De G-Buffer. Linksboven: diffuse kleur. Rechtsboven: normalen in cameraruimte. Linksonder: Speculaire kleur en materiaalindex. Rechtsonder: dieptemap (moeilijk zichtbaar wegens de precisie). G-Buffer gemoduleerd met de ambiente lichtterm van de scène. Vervolgens gaan we voor elke lichtbron de belichting berekenen. De resulterende rechthoeken worden allen geblend met de basisquad wat een resultaat geeft als in figuur 5.2. Licht Scissor Test Van directe lichtbronnen weten we dat ze steeds elke pixel be¨ınvloeden. Puntlichtbronnen daarentegen nemen af in sterkte naargelang het licht zich weg beweegt van de oorsprong. Wanneer we dus de belichting berekenen van puntlichten kan het zijn dat we teveel pixels gaan shaden die uiteindelijk zwart blijven doordat ze buiten het bereik van de bron liggen. Dit type van lichtbronnen kunnen we dan ook optimaliseren door eerst de invloed van het licht in schermruimte te berekenen. Via de stencil buffer kan dan enkel het be¨ınvloede gebied van de rechthoek verwerkt worden. Het berekenen van deze rechthoek kunnen we doen door vier vlakken te berekenen, twee parallal met de X-as en twee parallel met de Y-as. De vlakken moeten de camerapositie bevatten en tangentieel op de boundingsphere van het licht staan, zie figuur 5.3. Als we nu de intersectie van deze vlakken berekenen met het projectievlak verkrijgen we het vierkant dat we zoeken en waarbinnen het licht een invloed heeft op de pixels [23]. Cameraruimte Positie Wanneer we niet de cameraruimte positie van elke pixel opslaan maar enkel de diepte, moeten we in de fragment shader van de belichting deze positie herberekenen uit de dieptein-


Figuur 5.2: Pre-processed belicht beeld resultaat.

Figuur 5.3: Visualisatie van de scissor berekening.

48


49

Figuur 5.4: Blurring van een beeld. Eerste stap is horizontaal blurren. Tweede stap is verticaal blurren. Laatste stap geeft het resultaat. formatie. Hiervoor hebben we de kijkvector nodig. Deze vector kunnen we berekenen door deze mee te geven aan de vier hoekpunten van de rechthoek en vervolgens te laten interpoleren. De kijkvector van elk hoekpunt kan berekend worden door eerst de hoekpunten inverse te projecten (bijvoorbeeld met behulp van gluUnProject in OpenGL) en vervolgens deze vector te transformeren naar cameraruimte. In de fragmentshader kan dan de cameraruimte positie berekend worden door middel van 5.1 als de kijkvector genormalizeerd is. positie.xy =

5.3.4

viewvector.xy viewvector.z × positie.z

(5.1)

Postprocessing Stap

Na het berekenen van de belichting bekomen we een degelijk resultaat. Dit beeld kan echter nu makkelijk nog gepostprocessed worden met bepaalde technieken. Eén van de meest populaire postprocessing technieken op dit moment is blooming. Een tweede postprocessing die we bespreken is anti-aliasing doordat dit momenteel niet altijd hardwarematig ondersteund wordt in een uitgestelde shader. Blooming Dit is een simpele techniek die ervoor zorgt dat heldere delen van het beeld een soort glow krijgen terwijl de rest lichtjes gedimd wordt. Het simuleert zo de verstrooing van licht in het oog (of een lens). De methode is zeer eenvoudig. Er moet een blurfilter toegepast worden op het belichte beeld. Vervolgens blenden we dit blurresultaat met dit beeld. Vaak wordt er ook een lagere resolutie gebruikt om de blurring uit te voeren, dit maakt de techniek iets goedkoper en zorgt tevens al voor een lichte blurring. Het blurren kan bekomen worden door een convolutie uit te voeren. Er zijn hier twee opties. Enerzijds kan men in één pass blurren maar dit is zeer rekenintensief en zal enkel haalbaar zijn met een kleine convolutiekernel, wat niet zo een goed resultaat geeft. Anderzijds kan men in twee passes filteren, een horizontale en een verticale pass. Hierbij kan men een veel kleinere kernel gebruiken. Als we een 7 op 7 filter gebruiken hebben we 49 samples per pixel nodig om in één pass te convolueren terwijl we in twee passes slechts 14 samples per pixel nodig hebben. Figuur 5.4 geeft de stappen weer in het blurprocess, figuur 5.5 geeft het resultaat weer. Het gebruik van blooming kan mooie resultaten geven maar doordat de traditionele 32 bits RGBA kleurenopslag (8 bits voor drie basiskleuren en één alphakanaal) uiteindelijk toch vrij


50

Figuur 5.5: Post-processed beeld met blooming. beperkt blijft is het mogelijk om zeer snel een overbelicht beeld te renderen. Een oplossing hiervoor is High Dynamic Range (HDR) en floating point rendertargets [17]. In de echte wereld neemt het menselijke oog verschillen in lichtsterkte weer. Zo kunnen er verschillen waargenomen worden met een factor oplopende tot 100.000 [17]. Door te renderen naar een framebuffer die een float (16 of 32 bits naargelang de nood aan precisie) per kanaal gebruikt kunnen veel meer kleurwaardes gebruikt worden. Vervolgens kan het bekomen beeld via HDR getonemapped worden zodat de heldere elementen echt helder zijn, de donkere elementen echt donker zijn en toch in alle situaties detail behouden kan worden. Een eindresultaat van een gebloomed beeld met HDR vindt men terug in figuur 5.6. Anti-aliasing Anti-aliasing is een welgekend probleem in Computer Graphics. Het aliasing probleem waar we het specifiek over hebben is de trapvormige manier waarin randen van objecten worden weergegeven. Dankzij de evoluties in de GPU-wereld zijn er de dag van vandaag vrij snelle hardwarematige technieken die deze aliasing tegengaan en door het gebruik van steeds hogere resoluties wordt het aliasing probleem ook al vrij goed tegengewerkt. Wanneer er echter een uitgestelde shader gebruikt wordt kan er een probleem ontstaan rond deze anti-aliasing technieken. Heel wat van de huidige GPU’s ondersteunen namelijk niet de multi-sampling methodes om de anti-aliasing uit te voeren wanneer framebuffer objecten of MRT’s gebruikt worden, net zeer kritieke elementen om een efficiënte deferred shader te implementeren. Het is zelfs zo dat op dit moment enkel en alleen de nVidia GeForce 8 reeks beschikt over MRT’s met multi-sampling. Om ook anti-aliasing mogelijk te maken op andere hardware moet men een alternatief gebruiken.


51

Figuur 5.6: Post-processed beeld met blooming en HDR. Op oudere hardware die geen ondersteuning biedt voor multi-sample MRT’s kunnen we zelf een anti-aliasing gaan maken toegepast met een fragmentshader. Doordat we in elke pixel informatie hebben over de normaal en de diepte kunnen we vrij simpel een edge-detection filter maken die zoekt waar er grote discontinuiteiten in normaal en diepte plaatsvinden. Wanneer deze edges gevonden zijn moeten deze enkel nog geblurred worden zoals bij blooming. Deze techniek zal echter kostelijker zijn dan hardware anti-aliasing maar het vormt een goed alternatief om toch lichte aliasing artefacten weg te werken op oudere hardware.

Hoofdstuk 6

Implementatie No. Of course not. I can’t teach you spells. I’m NOT a necromancer. No. Absolutely not. Not a necromancer. - Sharn Gra-Muzgob, The Elder Scrolls III: Morrowind

In dit hoofdstuk worden de sleutelelementen besproken van de 3D-engine Natureality die ge¨ımplementeerd werd als onderdeel van deze thesis. We behandelen hier de door ons gemaakte keuzes om de eerder besproken algoritmes effectief te laten werken.

6.1

Overzicht

De implementatie is aangepakt als een volwaardige 3D-engine API, bevat in een dynamic link library (DLL). Op deze manier is het simpel om applicaties aan te maken die gebruik maken van Natureality. Applicaties communiceren met de 3D-engine DLL via abstracte interfaces in een statische lib. Hierdoor is het enkel nodig om applicaties te hercompilen wanneer er een wijziging gebeurd in de interfaces maar niet wanneer de DLL wordt aangepast [46]. Er is zo min mogelijk gebruik gemaakt van third-party onderdelen maar voor sommige functionaliteiten zijn toch een paar libraries gebruikt, deze overlopen we nu even.

6.1.1

Third-party Libraries

OpenGL vs DirectX Om te communiceren met de GPU bestaan er op dit moment twee populaire render API’s: OpenGL en DirectX. Overal kan men discussies vinden omtrent welke van de twee de betere keuze is. Wij laten in het midden welk van beide nu de beste is en zijn zelf van de opinie dat beide API’s doen wat ze moeten doen, beide met hun voor- en nadelen. In eerste instantie was er dan ook de bedoeling om zowel DirectX als OpenGL te ondersteunen. Door het grote kopieer-werk dat dit zou teweeg brengen is er echter voorlopig enkel OpenGL gebruikt. Dit zou in feite geen probleem mogen geven wat betreft het opbouwen van nieuwe applicaties omdat de volledige render API verholen is voor applicatiecode. Ook wat betreft resultaten van de geteste algoritmes zou dit geen probleem mogen geven door dat de kritieke punten van de rendertechnieken vooral in de algemene principes van de methode liggen en niet in de onderliggende communicatie van de hardware.

52

HOOFDSTUK 6. IMPLEMENTATIE

53

Glut Dit is een toolkit speciaal voor OpenGL die bepaalde extra functionaliteiten toevoegt en enkele functies eenvoudiger maakt om mee te werken. GLEW Om makkelijker te onderzoeken ofdat de video-hardware over de nodige functionaliteiten beschikt wordt GLEW gebruikt. Met deze library kan men OpenGL versies detecteren en extensies (de methode waarmee hardware-vendors GPU-specifieke functionaliteiten kunnen toevoegen aan OpenGL). Freeimage Dit wordt gebruikt om beeldbestanden in te laden voor de texturen. Freeimage ondersteunt nagenoeg elk bestandsformaat voor beeldopslag. TinyXML Een zeer eenvoudige manier om allerhande data op te slaan in files is het XML formaat. Heel wat data in de engine werkt op basis van XML bestanden, zoals de wereld definitie, de entiteiten en 3D texturen. Om deze bestanden makkelijk te parsen wordt TinyXML gebruikt. Ageia PhysX Dit is een physics engine die is gegroeid uit het oudere Novodex. Ageia PhysX wordt ook door speciale GPU-achtige hardware ondersteund in de vorm van een uitbreidingskaart. In de Natureality API vormt Ageia PhysX de onderliggende basis van de physics engine. Deze physics engine is vooral bedoelt om snel en eenvoudig dynamische entities te kunnen creëren om de ge¨ımplementeerde rendertechnieken te testen.

6.2 6.2.1

Geometrische Instanties Instantie Framework

De instantie technieken zijn zo ge¨ımplementeerd dat ze vrijwel onzichtbaar zijn voor de applicatie. Dit is gedaan met behulp van een instancing framework [10]. Als basis dient een abstracte interface waarmee de renderer van de 3D engine communiceert. Voor de renderer maakt het dus niet uit wat voor soort van batch er moet worden uitgetekend. De basis interface ziet er als volgt uit:

class nrIGeometryBatch { public: nrIGeometryBatch(); virtual ~nrIGeometryBatch(); //verwijder alle instances


54

virtual void clearInstances()=0; //voeg een instance toe aan de batch virtual HRESULT addInstance(nrCGeometryInstance* instance)=0; //Dit verzent al de data naar de GPU en moet aldus voor te //renderen minstens eenmaal worden aangeroepen. virtual void commit()=0; //Dit update de batch voor het huidige frame virtual void update()=0; //Dit rendert de batch virtual void render()=0; private: //een vector met al de instances van de batch std::vector m_instances; }; Het implementeren van de verschillende instantie technieken is nu niet meer dan het aanmaken van een nieuwe class afgeleid van deze interface en vervolgens al de functies correct invullen naar de vereisten van de instantie methode. De besproken technieken uit de tekst zijn allemaal ge¨ımplementeerd maar als er bijvoorbeeld de nood ontstaat voor een ietwat aangepaste versie van één der technieken kan dit snel bijgevoegd worden aan de engine. Om een instantie methode te specificeren aan een entiteit volstaat het om aan de entiteit het type van instantie mee te geven. De besproken instantie methodes zijn vrij recht toe recht aan te implementeren.

6.2.2

Vertex Atribuut Instanties

De grootste moeilijkheid in deze techniek is de manier waarop de instantiedata wordt doorgestuurd. We hebben twee verschillende methodes gebruikt. Enerzijds een methode die gewoon een array van vier dimensionale uniforme vector variabelen gebruikt. Vier vectoren worden gebruikt voor het opslaan van de wereldmatrix en één voor een instantie specifieke kleur. Nadeel aan deze methode is dat er slechts een beperkt aantal componenten gebruikt mogen worden afhankelijk van de video-hardware. We hebben dan ook een tweede methode ge¨ımplementeerd die gebruik maakt van de nieuwe EXT bindable uniform extensie op de GeForce 8 [32]. Met deze extensie kunnen we een uniforme variabele array opslaan als een buffer object zoals bijvoorbeeld ook onze vertexdata is opgeslagen in het VRAM. Deze methode kan dan ook de standaard buffer object update functies van OpenGL gebruiken. Het voordeel aan deze methode is dat slechts één uniforme variabele component gebruikt wordt en er toch naargelang de video-hardware een grote hoeveelheid variabelen gestockeerd kunnen worden. Op een GeForce 8 bedraagt dit aantal 65536 variabelen.


55

Figuur 6.1: Render- en Textuurcontext met batches.

6.2.3

Instanci¨ eren met Render API

Deze methode maakt gebruik van de EXT draw instanced extensie [32]. De functies uit deze extensie werken nagenoeg hetzelfde als de gewone rendercalls uit OpenGL, enkel dat het mogelijk is om bij deze functies te specificeren hoeveel keer de batch moet worden gerenderd. Vervolgens maakt het gebruik van deze functies het mogelijk om in een vertexshader de gl InstanceID variabele op te roepen die specificeert welke instantie momenteel verwerkt wordt. Via deze ID kan men dan de juiste wereldmatrix opzoeken in de stream en opnieuw opbouwen. De stream met instantiedata bevat ook hier weer de wereldmatrices en een kleurwaarde. Met de bindable uniforms techniek wordt de stream doorgegeven. Omdat de EXT draw instanced extensie een GPU vereist die ook bindable uniforms ondersteunt en doordat streams op basis van deze techniek meer data kunnen opslaan, is er geen andere extra methode gebruikt om de stream door te sturen zoals wel het geval was bij Vertex Atribuut Instanties.

6.2.4

Render- en Textuurcontext

De engine zal in een pre-render fase zorgen dat al de huidige entiteiten correct ge¨ınstancieërd worden in batches en dat vervolgens deze batches op de GPU geladen worden. Tijdens dit process wordt er ook geanalyseerd welke materialen en texturen nodig zijn voor de batches. Aan de hand van het materiaal wordt een rendercontext opgesteld zodat dezelfde materialen eenzelfde rendercontext hebben. Per rendercontext worden de texturen gecontroleerd en worden er textuurcontexten aangemaakt zodat batches die dezelfde texturen gebruiken in eenzelfde context zijn gegroepeerd. Op deze manier worden al de batches opgedeeld in materiaal en textuur zodat er tijdens het renderen zo min mogelijk statechanges gemaakt moeten worden. In figuur 6.1 wordt dit verduidelijkt.


6.2.5

56

Entiteit Tool

Voor de eenvoudigheid is er ook een kleine grafische gebruikersinterface ontworpen om snel entiteiten aan te maken en op te slaan in een simpele database. Op deze manier kan men gewoon een XML bestand inladen met al de entities en zorgt de engine zelf voor het inladen van al de resources en het specificeren van de correcte instantie methodes op basis van het type van entiteit. Door deze kleine extra tool moeten programmeurs van een nieuwe applicatie niet zelf zorgen dat al de entiteiten correct aangemaakt worden. In de kleine extra tool kan men een model specificeren voor de entiteit, een materiaal en een type dat zich vertaalt naar de gebruikte instantie methode.

6.2.6

Textuur Atlas

In de loop van de implementatie en door de overstap van een oudere GPU naar een nVidia GeForce 8800 GTX is er een alternatieve instantie flow opgesteld. Hierin zijn de textuurcontexts uitgebreid met de ondersteuning van een textuur atlas op basis van de nieuwe EXT texture array extensie. Deze context wordt automatisch gebruikt wanneer er bomen ge¨ınstancieërd worden die een speciaal soort van entiteit voorstellen. Hierdoor werkt voorlopig de textuur atlas ook enkel met statische batches. De engine zorgt er automatische voor dat een derde textuurcoördinaat wordt bijgevoegd met de index naar de juiste textuur in de array. De textuurcontext zorgt voor het juist inladen en activeren van de 3D textuur in de array.

6.3

Coherent Hi¨ erarchical Culling

De implementatie van het CHC algoritme is een “proof of concept” waarbij het gebruikt wordt om een hoog resolutie terrein te renderen. Het terrein bestaat uit een uniforme grid van vertices waarbij er een hoogtemap aangeeft hoe hoog elke vertex ligt. De terreinmesh wordt in een pre-render fase berekend en opgedeeld in kleinere tiles. Deze tiles worden uiteindelijk via CHC getest en geculled om zo min mogelijk van deze tiles te moeten tekenen.

6.3.1

Hi¨ erarchische Structuur

De boomstructuur die we hebben gekozen is vrij simpel en gebasseerd op Kd-Trees [6, 7]. Kd-trees gebruiken echter voor al de nodes, elementen uit de dataset terwijl in ons geval de datasetelementen - de terreintiles - enkel zullen voorkomen in de bladeren. De opbouw van de boom gebeurd door alternerent de terreintiles te sorteren op x waarde dan wel op z waarde. We beginnen met de root en stellen voor de rootnode een boundingbox op bestaande uit de elementen van onze verzameling - in dit geval zijn dit nog al de terreintiles. Het midden van deze boundingbox wordt ook de positie voor de rootnode. Vervolgens nemen we al de elementen in de gesorteerde dataset tot en met de mediaan. Dit wordt de nieuwe dataset voor het linker kind van de rootnode. De resterende elementen vormen de verzameling voor het rechter kind. Nu voeren we recursief dit algoritme verder uit op deze twee nieuwe kinderen. Men moet wel blijven letten op het alternerent sorteren, als de rootnode sorteerde op x-waarde zullen beide kinderen moeten sorteren op z-waarde. Doordat dit alles gebeurt in een pre-render fase wordt er een simpele brute-force sortering gedaan, als snellere laadtijden gewenst zijn zou hier bijvoorbeeld quicksort gebruikt moeten worden.


57

Wanneer we een bladnode creëren stopt de recursie. In een bladnode wordt buiten de boundingbox en positie ook een pointer naar de effectieve terreintile bijgehouden.

6.3.2

CHC algoritme

Sleutel in de implementatie van het algoritme zijn een stack om nodes in te verzamelen die verwerkt moeten worden en een queue die queryresultaten opvolgt. We beginnen steeds door de rootnode op de stack te plaatsen. Vervolgens begint het algoritme te lopen totdat er geen nodes op de stack en geen onverwerkte queryresultaten aanwezig zijn. Eerst checken we of dat er resultaten beschikbaar zijn, dit kan natuurlijk nog niet omdat er nog geen queries zijn verstuurd. We kijken dan ofdat er een node op de stack zit. Dit is wel het geval en nu wordt de eerste node - de root - verwerkt. Om CHC praktisch bruikbaar te maken moeten we ook zorgen dat CHC enkel en alleen voor occlusion culling wordt gebruikt, daarom bestaat de eerste stap in het verwerken van een node erin om een frustum culling to doen. Ligt de node buiten het frustum hoeven we verder geen overbodige tests met queries uit te voeren. Queries zijn nog steeds trager dan een frustum test om te gaan frustum cullen. Als de node in het frustum ligt laten we CHC zijn gang gaan. Interior nodes die in het vorige frame zichtbaar waren zijn triviaal voor ons en nemen we van aan nog steeds zichtbaar te zijn. Voor deze nodes gaan we dan ook gewoon de kinderen op de stack pushen voor verdere verwerking. Nodes die niet zichtbaar waren of voor de bladeren gaan we eerst een query versturen. Uiteindelijk zullen we een resultaat binnen krijgen in de queue met queries. Als het resultaat positief is wordt de node verder verwerkt door zijn kinderen op de stack te pushen of in het geval we een blad hebben kunnen we de terreintile tekenen.

6.3.3

Enkele Bedenkingen

Wanneer we de kinderen van een node recursief verwerken moeten we dit natuurlijk wel doen in zo een manier dat het kind met een positie het dichtst bij de camera, als eerste verwerkt zal worden en dan pas het verder weggelegen kind. Het kan echter toch gebeuren door de aard van het algoritme en door het soms wachten op resultaten van nodes die niet zichtbaar waren dat niet al de nodes op de stack in een juiste volgorde zitten waardoor de performantie iets lager kan liggen dan in de optimale situatie. We hebben dit probleem in de eerste implementatie van het algoritme meegenomen en opgelost door in plaats van een stack een priority queue te gebruiken die de nodes sorteert op afstand van de waarnemer. Hiervoor werd de STL implementatie van de priority queue gebruikt maar om onverklaarbare redenen werkte dit helemaal niet efficiënt, dit maakte het algoritme kostelijker dan frustum culling en zelfs gewone brute-force rendering van de ganse terreinmesh. De implementatie werd vervolgens aangepast door een stack te gebruiken, die dus niet altijd correct is en eigenlijk nog trager zou moeten werken, doch ondervonden we hier een ontzettende snelheidswinst die het gebruik van CHC rechtvaardigt. We kunnen enkel concluderen dat het toevoegen van elementen aan de priority queue te traag is voor dit algoritme. Een tweede opmerking die we willen maken is dat in een CHC implementatie men ten allen tijde goed de flow van het algoritme moet inzien. In een eerste implementatie ontdekken we zo dat in bepaalde gevallen terreintiles twee keer gerenderd werden, één keer met query en één keer zonder, dit zijn natuurlijk gevallen die opgespoord en aangepast moeten worden. Ook


58

ontdekten we zo de gelegenheid om in bepaalde gevallen de geometrie rechtstreeks te renderen met de query zonder eerste een query met enkel bounding geometrie te versturen.

6.4 6.4.1

Uitgestelde Shading G-Buffer

Frame Buffer Object Vroeger was het aanmaken van de G-Buffer één der grootste problemen voor het implementeren van een uitgestelde shader onder OpenGL. Eerst gaan renderen naar de framebuffer en vervolgens de inhoud overkopiëren naar een textuur via bijvoorbeeld glCopyTexSubImage2D is uitgesloten. Dit is niet flexibel en is gevoelig in het veroorzaken van een stall en starvation. Pixel-Buffers of kortweg P-Buffers waren een stap in de goede richting en lieten toe om rechtstreeks naar een textuur of een andere buffer te renderen. Het grote probleem met P-Buffers zit in de contextswitch die gebeurd wanneer er van de framebuffer overgeschakeld wordt naar de P-Buffer of omgekeerd. Deze contextswitch is een heel dure operatie die de performantie naar beneden haalt. Daarom is er in onze implementatie gekozen om Frame Buffer Objects (FBO) te gebruiken. Deze FBO’s zijn gelijkaardig aan P-Buffers maar hebben geen behoefte aan een contextswitch bij overschakeling. Als er al een nadeel is aan FBO’s is dit de hardwaresupport, oudere hardware ondersteunt deze techniek meestal niet. Met een FBO is het zeer simpel om de G-Buffer te creëren. Het is namelijk mogelijk om in één FBO verschillende rendertargets aan te maken, zo bekomen we een effectieve MRT toepassing. Onze G-Buffer bevat vijf van deze rendertargets die allen gekoppeld zijn aan een textuur. Wanneer de FBO geactiveerd wordt, kunnen we renderen naar deze vijf texturen. Parameters Naargelang het type object en het type van materiaal dat hierop gebruikt wordt, zal er een shader gekozen worden die de G-Buffer vult met de parameters van de huidige batch. Het is hier misschien ook belangrijk op te merken dat de berekeningen voor normaalmapping en parallaxmapping hier al zullen gebeuren doordat beide technieken belichtingsparameters berekenen. Tijdens de belichtingsfase hoeven we dus helemaal niet meer na te gaan of een object zo een materiaal gebruikte omdat het grote werk toch al gedaan is tijdens de geometriefase. We overlopen nu de parameters die naar de G-Buffer worden gerenderd. Als eerste is er de diffuse kleur van de scène, deze wordt naar de eerste textuur geschreven. In de tweede textuur slaan we de normalen in cameraruimte op. De derde textuur is een combinatie van een speculaire term, deze is gestokkeerd in het eerste kanaal - het rode kanaal - en een materiaal index in het tweede kanaal - het groene kanaal. In de vierde textuur wordt een refractiemap bijgehouden voor het renderen van water, een reflectiemap is niet nodig omdat deze in de diffuse textuur geschreven kan worden. Tot slot houdt het laatste rendertarget een dieptemap bij, dit is ook de enige textuur die in een luminance mode staat waarbij 24 bits gebruikt worden voor diepte en 8 voor een stencil component.


59

Een vaak vernoemt probleem van een uitgestelde renderer bestaat erin dat al de lichten in de belichtingsfase eenzelfde shader moeten gebruiken wat als gevolg heeft dat de hele scène uit één materiaal moet bestaan. Dit is echter een misleidende gedachte. Door de evolutie van de efficiëntie van branching in shaders is het nu geen probleem meer om via enkele condities een juiste codepad te volgen in de belichtingsfase. Het enige dat de belichtingsshader nodig zal hebben is een parameter om het juiste codepad te kiezen voor de huidige pixel. In S.T.A.L.K.E.R. wordt een ingenieus systeem gebruikt dat een materiaalindex opslaat op basis van een bepaalde parameterisatie [43]. In onze implementatie gebruiken we een gelijkaardige maar ietwat simpelere methode door een materiaalindex te renderen naar het tweede kleurkanaal van ons derde rendertarget. Op dit moment zijn er slechts enkele materiaalindices beschikbaar doordat enkel getallen tussen nul en één gebruikt mogen worden met als interval 0.1. Wegens textuurfiltering in de hardware ontstaat er blijkbaar een kleine afwijking en is er aldus gekozen om materiaalindices op een afstand 0.1 van elkaar te houden. De belichtingsshader controleert de materiaalindex van een fragment en neemt op basis hiervan een juist codepad. Zo zal een fragment met materiaalindex 0.1 gewoon belicht worden en een andere pixel met index 0.2 zal belicht worden aan de hand van een fresnelterm die de refractiemap zal gebruiken. De materiaalindex wordt ook gebruikt in de ambiente belichting omdat het mogelijk is dat bepaalde objecten uitgesloten moeten worden van ambiente verlichting. Om refracterende objecten mogelijk te maken is er een refractiemap vereist. De engine ondersteund de toevoeging van water aan een scène en dus was er nood aan zo een refractiemap. Voor water is er in feite ook nood aan een reflectiemap maar deze wordt ge¨ınterpreteerd als een diffuse kleur en gewoon naar de diffuse textuur gerenderd. In theorie was het niet nodig om een vijfde rendertarget te introduceren aan de FBO om refractie in op te slaan en door dit vijfde rendertarget wordt de G-Buffer van onze implementatie enkel ondersteunt op de GeForce 8 familie doordat dit de enige hardware is op het moment die zoveel verschillende rendertargets in één enkele FBO ondersteunt. In zowel de diffuse als de normaal textuur zijn nog twee kanalen vrij, de alpha kanalen. In de gecombineerde speculaire, materiaalindex textuur zijn er zefls nog twee kanalen vrij, blauw en alpha. De poging om deze kanalen te gebruiken om de refractiemap in op te slaan mislukten echter om tot op heden onverklaarbare wijze. Het zou mogelijk moeten zijn om de alphakanalen te gebruiken van deze texturen omdat de fixedfunction pipeline van OpenGL niet gebruikt wordt en alles verloopt via zelfgeschreven shaders. Toch bleek het onmogelijk om juiste resultaten uit deze alphakanalen te verkrijgen. Onder directX zou dit geen problemen geven [43].

6.4.2

Belichting

In de huidige implementatie is het mogelijk om directe en punt lichtbronnen toe te voegen aan een scène. Ook kan men specificeren om een zon in een dag en nacht cyclus te laten functioneren. De zon is intern ge¨ımplementeerd als een directe lichtbron. De belichtingsfase gebeurd in verschillende aparte renderpasses, één pass voor elk licht. Per licht renderen we een rechthoek op het scherm die orthogonaal geprojecteerd wordt. Voor directe lichtbronnen neemt deze rechthoek de volledige grootte van de viewport in beslag. In het geval van punt lichtbronnen, berekenen we de zone van invloed in schermruimte en wordt via een scissortest enkel deze verkleinde rechthoek getekend. De resultaten van deze rechthoeken worden met elkaar geblend. De basis en eerste stap in de blending is een rechthoek


60

met de ambiente kleurwaardes, de daadwerkelijk belichte rechthoeken kunnen dan vervolgens hiermee geblend worden.

6.4.3

Post-processing

De enige post-process techniek die geactiveerd kan worden is blooming, al dan niet met of zonder HDR. Als er HDR gebruikt wordt zal er een floatingpoint textuurformaat gekozen worden om de belichting in te blenden en de blooming op uit te voeren. Voor een waarschijnlijk kleine winst in nog betere kwaliteit maar een groot verlies aan performantie zou ook de GBuffer omgezet kunnen worden naar een floatingpoint formaat maar dit lijkt niet echt de moeite te lonen doordat er geen HDR bronnen gebruikt worden in de geometrie stage. De blooming zelf maakt gebruik van een twee-pass algoritme waarbij er eerst horizontaal en daarna vertikaal geblurred wordt steeds met een kernel van zeven samples. Er is ook de optie om het blurresultaat van het huidige frame te mixen met het blurresultaat van het vorige frame. Hiermee kan men een subtiele motionblurring verkrijgen wat esthetisch wel een mooi resultaat geeft.

Hoofdstuk 7

Resultaten Double the gun, double the fun! - Serious Sam, Serious Sam II

In dit hoofdstuk bekijken we de resultaten van onze implementatie. We beginnen met enkele grafieken die de voordelen van de besproken technieken aantonen. Tot slot geven we ook nog enkele screenshots mee die een idee geven van de mogelijkheden en beeldkwaliteit van de implementatie.

7.1

Test Systeem en Methode

Alle tests zijn uitgevoerd op een zelfde systeem: Processor: Moederbord: Ram Geheugen: GPU: GPU-driver: Harde Schijf: OS:

AMD Athlon 64 3500+ (Clawhammer core) ASUS A8N-SLI Deluxe 2x512MB Corsair TwinX PC4400C25 (2-2-2-5 latency @ DDR400) ASUS GeForce 8800 GTX ForceWare Release 158.22 WD Raptor 74GB @ 10000RPM Windows XP home

Voor elke test hebben we een camera een traject laten afleggen doorheen de wereld. Alle tests gebruiken hetzelfde traject en worden steeds afgeklokt op 48 secondes. Voor de entiteit benchmarks hebben we gebruik gemaakt van kubussen. Deze objecten zijn geometrisch zeer simpel en snel te renderen waardoor we beter de CPU bottlenecks kunnen blootleggen.

7.2

Statische Entiteiten

Als eerste test bekijken we de performantie van statische rendermethodes. We vergelijking hier het uittekenen van object per object en statische instanciëring van de objecten. Voor elke test werden kubussen gebruikt. Voor beide technieken hebben we vier runs uitgevoerd waarbij telkens het aantal objecten verhoogd werd van 1000 tot uiteindelijk 25000.

61

HOOFDSTUK 7. RESULTATEN

62

Figuur 7.1: Vergelijking van de statische rendermethodes De grafiek in figuur 7.1 geeft het resultaat van de benchmark weer. Het is duidelijk dat de CPU zeer zwaar overbelast wordt in de traditionele methode zonder instanties. De instantie methode blijft zelfs uitermate goed presteren zelfs wanneer we 25000 kubussen renderen. Deze test toont aan dat het steeds de moeite loont om statische objecten te instanciëren doordat hierdoor de CPU-bottleneck vermeden wordt. Naargelang de complexiteit van de te renderen models is het mogelijk dat men op een bepaald punt te hoge vertex-kosten verkrijgt en dat men GPU gelimiteerd is. In zo een situatie zullen de besproken instantie optimalisaties interessant worden.

7.3

Dynamische Entiteiten

In deze test bekijken we de performantie van technieken om dynamische objecten te renderen. Ook deze test voeren we opnieuw uit met kubussen maar deze keer bewegen de kubussen zich. We hebben hiervoor de kubussen in de lucht geplaatst en zwaartekracht laat ze naar beneden vallen. Figuur 7.2 toont de resultaten van de test. We waren eigenlijk wat verrast met dit resultaat. Zoals verwacht presteert de niet ge¨ınstancieërde methode het slechts en zelfs ondermaats. Dynamische en API instanties doen het al een stuk beter, maar echt verbazend is dat de sterkste methode de vertex attribuut instantie is met bindable uniforms als streamingmethode. We verwachtten dat de vertex attribuut methode het sterkste zou zijn maar we dachtten dat de rechtstreekse methode met uniform variabelen sneller zou zijn dan de bindable, wegens de indirecte adressering. Eerdere onofficiele benchmarks ondersteunden onze verwachtingen.


63

Figuur 7.2: Vergelijking van de dynamische rendermethodes We kunnen hier enkel uit concluderen dat nVidia zijn videodrivers voor de GeForce 8 familie heeft geoptimaliseerd. De oudere onofficiele benchmarks waren immers uitgevoerd op oudere ForceWare drivers die zelfs nog niet de volledige featureset implementeerden van de G80. Ongeacht de instantiemethode blijkt dat we op 5000 objecten opnieuw CPU-gelimiteerd zijn, simpelweg door het doorsturen van geometriedata of matrixstreams. Dit is een reden temeer waarom segement instanciëring zeer interessant is doordat we dan enkel de matrices van potentieel zichtbare objecten moeten doorsturen. Dit vereist echter meer onderzoek en een implementatie van de optimalisatie.

7.4

Culling Performantie

In de huidige implementatie wordt CHC enkel toegepast op een terreinmesh. Daarom voeren we deze test uit op enkel en alleen een hoog resolutie terrein van 1025 op 1025 vertices. Drie methodes hebben we uitgetest: brute-force, view frustum culling en CHC. Figuur 7.3 toont de resultaten. We kunnen opmaken dat CHC een vrij delicaat algoritme is. In de benchmark is er niet overal veel occlusie en soms zijn vrij grote delen van het terrein zichtbaar, zoals de eerste twintig seconden. In deze situaties blijkt de brute-force methode zelfs het beste te zijn. Wanneer er echter wel veel occlusie is blijkt CHC heel wat performantie te winnen. Een zeer goed voorbeeld is het tijdsframe vanaf 38 tot 43 seconden: hier volgt de camera de helling van


64

Figuur 7.3: Vergelijking van de culling rendermethodes een vulkaan in het midden van het terrein. In deze situatie is CHC zeer sterk. View frustum culling alleen redt het hier niet zo goed doordat in het view frustum zelf nog heel veel terrein aanwezig is. Met CHC daarentegen wordt ontzettend veel van het terrein weggeculled doordat de vulkaan heel veel van het terrein occludeert. Op secondes 43, 44 kijkt de camera bijna recht omhoog. Hier is CHC weer minder sterk dan view frustum culling door de overhead aan queries. De camera duikt vervolgens recht in de vulkaan waarbij even een groot deel van het terrein zichtbaar is, ook hier wordt de overhead aan queries weer iets te veel voor CHC. Het CHC algoritme heeft zeker heel wat in zijn mars maar moet met grote voorzichtigheid toegepast worden. Scènes moeten een goede occlusie bieden. Interieur omgevingen lijken hier een zeer grote potentiele klant van CHC. Echter buitenomgevingen kunnen ook profiteren van CHC als men zorgt voor strategisch geplaatste dalen en bergen, maar ook voorwerpen als huizen, stenen, bomen, enzovoort. Het huidige CHC algoritme zouden we zo bijvoorbeeld nog kunnen uitbreiden zodat het werkt op objecten. Immers één van de mooie eigenschappen van CHC is dat het dynamisch is, zolang men er maar voor zorgt dat elk frame de bounding geometrie opnieuw berekend wordt. Dit hoeft uiteindelijk slechts een vergelijking te zijn van de extremen in de bladeren en vervolgens kan men deze informatie geleidelijk omhoog werken in de boomstructuur.


65

Figuur 7.4: Performantie van de deferred shader.

7.5

Uitgestelde Shading Performantie

Als laatste grafiek bekijken we de prestaties van de ge¨ımplementeerde deferred shader. We zagen niet echt het nut in van een vergelijking met forward rendering. Ten eerste ondersteunt onze implementatie geen dynamische forward rendering en ten tweede zou dit uiteindelijk een “no-contest” zijn doordat de objecten in de wereld ge¨ınstancieërd zijn en aldus is er geen controle meer over de overdraw en lichtinvloed. Wel handig om te testen waren de verschillende effecten die aan onze uitgestelde shader toegevoegd kunnen worden. In figuur 7.4 worden de resultaten weergegeven. Deze benchmark combineert eigenlijk alle elementen en technieken van deze thesis. De terreinmesh wordt gerenderd met CHC, wat de reflectie en refractie aanzienlijk helpt doordat de zichtbaarheidsinformatie slechts één keer berekend moet worden. Er worden 500 bomen, goed voor 1 miljoen vertices, gerenderd in een statische batch waarbij textuurarrays zorgen voor wat variatie in de bladeren, zo zijn er gezonde en verrotte bomen. Er zijn 6 lichtbronnen aanwezig in de scène waaronder één directe bron - de zon. We zien dat als al de effecten aanstaan de performantie vrij laag ligt rondt de 20 FPS. We vermoeden dat hier de applicatie 100% gelimiteerd wordt door de GPU. De vertexload van de bomen lijkt ons het probleem doordat we de bomen drie keer moeten verwerken: één keer gewoon, één keer voor refractie en één keer voor reflectie. Dit geeft ongeveer een totaal van 3 miljoen vertices per frame. De boommodellen zijn niet geoptimaliseerd en ook een gebruik van segment buffering kan hier dus wel handig zijn.


66

Het gebruik van HDR en blooming blijkt slechts een kleine performantiekost te betalen. Dit is waarschijnlijk zeer te danken aan de grote fillrate en fragmentprocessing kracht, alsook de verbeteringen van floating point framebuffers, op de GeForce 8800.

7.6

Screenshots

We besluiten dit hoofdstuk met nog enkele screenshots van de implementatie.

Figuur 7.5: Scherm capture van één der entiteit benchmarks.


67

Figuur 7.6: Zicht op het terrein via CHC.

Figuur 7.7: Daadwerkelijk gerenderd gebied uit figuur 7.6. De rode balken stellen de nodes voor die geculled werden.


Figuur 7.8: Pre-process belichting van een terrein en enkele spheres.

Figuur 7.9: Stress testing van terrein en instanties.

68


69

Figuur 7.10: Screenshot uit de deferred shader benchmark, alle effecten aanwezig (water, blooming, HDR)

Figuur 7.11: De uitgestelde shader tijdens de nacht met enkele lichtbronnen boven het water.

Hoofdstuk 8

Besluit My information might well be of use to you stalker. - Stalker, S.T.A.L.K.E.R.: Shadow of Chernobyl

Grafische hardware heeft een ontzettende evolutie ondergaan in de laatste paar jaren. Niet alleen is de snelheid verbetert ook zijn er heel wat nieuwe features bijgekomen op GPU’s die alles veel makkelijker moeten maken. We zitten momenteel in een periode die zeer interessant is voor grafische programmeurs met al deze leuke speeltjes die ter beschikking zijn. Toch mogen we niet uit het oog verliezen dat efficiënt programmeren op de laatste GPU’s nog steeds een zeer lastig werk blijft. Men moet op de hoogte zijn van de tools die men ter beschikking heeft en hoe deze tools werken en communiceren met elkaar. Grafisch programmeren is één ding maar dit efficiënt doen is iets heel anders. De technieken besproken in deze thesis vormen een zeer stevige basis om next-generation applicaties te schrijven voor next-generation hardware. Hoofdzaak nummer één zal zeker nog gedurende enkele jaren het ontlasten van de CPU zijn. Al het renderwerk moet zoveel mogelijk met de GPU afgehandeld worden. Tijdens het schrijven van deze thesis is ook duidelijk geworden hoeveel belang erin DirectX 10 gegeven wordt aan instanciëring van objecten, dit geeft aan dat de industrie ook bezig is met het overschakelen naar deze methodes. Toch is en blijft Computer Graphics ook een zeer creatief terrein. Zo kunnen de algoritmes die we hebben voorgesteld aangepast worden - of moeten aangepast worden - aan de noden van de applicatie en de aard van de werelden die men wil renderen. Zolang men steeds de werking van de onderliggende funderingen goed in het achterhoofd houdt, zoals de hardware maar ook de render API’s, zal men in staat zijn verbluffende resultaten te bekomen. Kijken we bijvoorbeeld naar de teasers die de Duitsers van Crytek ons al hebben laten zien van hun binnenkort te releasen nieuwe telg, Crysis, kunnen we eigenlijk alleen maar met verstomming dromen over wat de toekomst ons nog meer te bieden heeft op het vlak van real-time Computer Graphics. Kortom, hoezeer de hardware en eisen ook verandert mogen zijn, we moeten nog steeds veel aandacht steken in efficiënt programmeren en benutten van onze tools. Veelvuldig monitoren en benchmarken van de toepassing en steeds dieper en dieper zoeken naar mogelijkheden om te optimaliseren. Maar natuurlijk mag men hier nooit of te nooit bij vergeten dat er eerst en vooral al een goede basis gelegd moet worden.

70

Bijlage A

Belichtingsvergelijking Realistische belichting uit de echte wereld is vaak te complex om in real-time te berekenen. Daarom valt men vaak terug op versimpelde voorstellingen van belichting. We bespreken hier kort even de berekeningen nodig om belichting uit te voeren van directe lichtbronnen en punt lichtbronnen zoals we die ook in onze implementatie gebruikt hebben en die vrij populair zijn [22, 41, 39].

A.1

Ambient Licht

Eén van de grote vereenvoudigingen in de belichting is de ambiente lichtterm. In de echte wereld weerkaatst licht vaak op verschillende oppervlakken en draagt zo indirect bij tot de belichting van een specifiek punt in de wereld. Deze indirecte belichting is vaak te moeilijk om in real-time te berekenen doordat het vereist om ontzettend veel rays doorheen de wereld te casten om een goed resultaat te verkrijgen. Om toch een vorm van indirect licht te hebben, dus licht dat bijdraagt tot de belichting van elke pixel, gebruiken we de ambiente term. De kleur van deze term is constant voor een scène en geldt voor elke pixel.

A.2

Direct Licht

Directe lichtbronnen zijn lichten die geen positie in de wereld hebben, enkel een orientatie. Deze bronnen bevinden zich op een onneindige afstand. Als men bijvoorbeeld een zon wil toevoegen aan een scène is de directe lichtbron een goede keuze doordat relatief gezien, de zon op een onneindige afstand van de scène staat. Directe lichtbronnen zullen altijd invloed uitoefenen op de gehele wereld. De berekining voor de directe lichtbron kunnen we opsplitsen in twee componenten: diffuse lichtterm en speculaire lichtterm. Optellen van deze twee geeft de uiteindelijke belichting van het licht in een punt op het object.

A.2.1

Diffuse Lichtterm

De diffuse lichtterm is het licht dat met een zelfde intensiteit wordt waargenomen ongeacht de kijkhoek op een object. De intensiteit van de term is afhankelijk van de diffuse parameters van de bron, de diffuse reflectie van het object en de hoek tussen de bron en de normaal op 71

BIJLAGE A. BELICHTINGSVERGELIJKING

72

Figuur A.1: Diffuse reflectie. het object (zie figuur A.1). Dit vertaalt zich naar de formule in A.1 en wordt ook wel de Lambertiaanse reflectie genoemd. Idif = Ldif × Mdif × N · L

(A.1)

Hierin is L de lichtvector, N is de normaal, Ldif de diffuse parameter van het licht en Mdif de diffuse reflectie van het object zijn materiaal.

A.2.2

Speculaire Lichtterm

De speculaire intensiteit hangt af van de kijkhoek op een object. Deze term is afhankelijk van de cosinus tussen de kijkvector en de reflectievector zoals aangegeven in figuur A.2. Deze reflectievector is de spiegeling van de lichtvector rond het te belichten oppervlak en wordt gegeven door: R = 2N × (N · L) − L

(A.2)

De speculaire term wordt dan gegeven door formule ??, dit wordt ook wel het Phong model genoemd. Ispec = (R · Eye)s × Lspec × Mspec

(A.3)

Hierbij zijn s de shininess die de hotspot bepaalt, Lspec de speculaire parameter van het licht en Mspec de speculaire reflectie van het object zijn materiaal.

A.3

Punt Licht

Dit type van lichtbronnen situeerd zich in de wereld en heeft een bepaalde positie en invloedszone. Het licht zal geleidelijk minder sterk in intensiteit worden naargelang het zich verder van de bron bevindt. Dit zijn uiteindelijk de enige verschillen met direct licht. Het

BIJLAGE A. BELICHTINGSVERGELIJKING

73

Figuur A.2: Speculaire reflectie. gevolg hiervan is dat de lichtvector nu niet meer gewoon de orientatie is van de lichtbron - er is trouwens geen orientatie meer - maar het verschil tussen de positie van de bron en het te belichten oppervlak. Vervolgens moet ook de degradatie van lichtintensiteit berekend worden, dit gebeurd aan de hand van een attenuatie. In onze implementatie is deze als volgt: Ldist att = max 0, 1 − (A.4) Lradius Hierbij zijn Ldist de afstand van het te belichten punt tot de lichtbron en Lradius is de radius waarin het licht invloed heeft.

Bibliografie [1] Advanced Micro Devices, Inc.: http://www.amd.com [2] Advanced Micro Devices, Inc.: ATI Solutions, http://ati.amd.com [3] Autodesk: Autodesk 3ds Max, http://usa.autodesk.com/adsk/servlet/index?siteID=123112&id=5659302 [4] Autodesk: Autodesk Maya, http://usa.autodesk.com/adsk/servlet/index?siteID=123112&id=7635018 [5] Bavoil, L.: Rendering Huge Triangle Meshes with OpenGL, University of Utah, 2005 [6] Bentley, J. L.: Multidimensional binary search trees used for associative searching, 1975 [7] Bentley, J. L.: K-d Trees for Semidynamic Point Sets, 1990 [8] Bittner, Wimmer, Piringer, Purgathofer: Coherent Hierarchical Culling: Hardware Occlusion Queries Made Useful, 2004 [9] Bittner, Wimmer: GPU Gems 2: Hardware Occlusion Queries Made Useful, AddisonWesley, 2005 [10] Carucci, F.: GPU Gems 2: Inside Geometry Instancing, Addison-Wesley, 2005 [11] DeLoura, M.: Game Programming Gems, Charles River Media, 2000 [12] DeLoura, M.: Game Programming Gems 2, Charles River Media, 2001 [13] Dietrich, S.: Texture Space Bump Maps, 2004 [14] Donnelly, W.: GPU Gems 2: Per-Pixel Displacement Mapping with Distance Functions, Addison-Wesley, 2005 [15] Dudash, B.: DX10, Batching, and Performance Considerations, Presentation at Game Developers Conference, 2006 [16] Emmet, Randima: GPU Gems 2: The Geforce 6 Series GPU Architecture, AddisonWesley, 2005 [17] Green, Cebenoyan: High Dynamic Range Rendering on the GeForce 6800, Presentation at 6800 Leagues under the Sea, 2004 [18] Gribb, Hartmann: Fast Extraction of Viewing Frustum Planes from the World-ViewProjection Matrix, Ravensoft, 2001

74

BIBLIOGRAFIE

75

[19] Hargreaves, Harris: Deferred Shading, Presentation at 6800 Leagues under the Sea, 2004 [20] Hart, E.: GeForce8800 OpenGL Extensions, Presentation at Game Developers Conference, 2007 [21] Intel Corporation: http://www.intel.com [22] LaMothe, A.: Tricks of the 3D Game Programming Gurus, Sams, 2003 [23] Lengyel, E.: The Mechanics of Robust Stencil Shadows: Scissor Optimization, 2002 [24] Kirmse, A.: Game Programming Gems 4, Charles River Media, 2004 [25] Microsoft Corporation: Xbox 360, http://www.xbox.com/en-US/ [26] Monk, T.: 7 Years of Graphics, http://accelenation.com/?ac.id.123.1, 2006 [27] Myers, K.: Using D3D10 Now, Presentation at Game Developers Conference, 2007 [28] NVIDIA Corporation: http://www.nvidia.com [29] NVIDIA Corporation: Technical Brief: NVIDIA Geforce 8800 GPU, Architecture Overview, NVIDIA Corporation, 2006 [30] NVIDIA Corporation: Technical Brief: Lumenex Engine: The New Standard in GPU Image Quality, NVIDIA Corporation, 2006 [31] NVIDIA Corporation: D3D10: Prepping your Engine for a smooth start, Presentation at Game Developers Conference, 2006 [32] NVIDIA Corporation: NVIDIA OpenGL Extension Specifications for the GeForce 8 Series Architecture (G8x), NVIDIA Corporation, 2007 [33] NVIDIA Corporation: Technical Report: Fresnel Reflection, NVIDIA Corporation, 2002

[34] NVIDIA Corporation: NVIDIA NVTriStrip, http://developer.nvidia.com/object/nvtristrip library.html, 2004 [35] Olick, J.: GPU Gems 2: Segment Buffering, Addison-Wesley, 2005 [36] OpenGL ARB: OpenGL Programming Guide version 2, Addison-Wesley, 2005 [37] Owens, J.: GPU Gems 2: Streaming Architectures and Technology Trends, AddisonWesley, 2005 [38] Pharr, M.: GPU Gems 2, Addison-Wesley, 2005 [39] Policarpo, Fonseca: Deferred Shading Tutorial, Pontifical Catholic University of Rio de Janeiro, 2005 [40] Randima, F.: GPU Gems, Addison-Wesley, 2005 [41] Rost, R.: OpenGL Shading Language, Addison-Wesley, 2004 [42] Sekulic, D.: GPU Gems: Efficient Occlusion Culling, Addison-Wesley, 2005

BIBLIOGRAFIE

76

[43] Shishkovtsov, O.: GPU Gems 2: Deferred Shading in S.T.A.L.K.E.R., Addison-Wesley, 2005 [44] Welsh, T.: Parallax Mapping with Offset Limiting: A PerPixel Approximation of Uneven Surfaces, 2004 [45] Wloka, M.: Batch, batch, batch: what does it really mean? Presentation at Game Developers Conference, 2003 [46] Zerbst, S.: 3D Game Engine Programming, Thomson Course Technology PTR, 2004

Auteursrechterlijke overeenkomst Opdat de Universiteit Hasselt uw eindverhandeling wereldwijd kan reproduceren, vertalen en distribueren is uw akkoord voor deze overeenkomst noodzakelijk. Gelieve de tijd te nemen om deze overeenkomst door te nemen, de gevraagde informatie in te vullen (en de overeenkomst te ondertekenen en af te geven).

Ik/wij verlenen het wereldwijde auteursrecht voor de ingediende eindverhandeling: Efficiënte rendering op laatste generatie grafische hardware Richting: Master in de informatica Jaar: 2007 in alle mogelijke mediaformaten, - bestaande en in de toekomst te ontwikkelen - , aan de Universiteit Hasselt. Niet tegenstaand deze toekenning van het auteursrecht aan de Universiteit Hasselt behoud ik als auteur het recht om de eindverhandeling, - in zijn geheel of gedeeltelijk -, vrij te reproduceren, (her)publiceren of distribueren zonder de toelating te moeten verkrijgen van de Universiteit Hasselt. Ik bevestig dat de eindverhandeling mijn origineel werk is, en dat ik het recht heb om de rechten te verlenen die in deze overeenkomst worden beschreven. Ik verklaar tevens dat de eindverhandeling, naar mijn weten, het auteursrecht van anderen niet overtreedt. Ik verklaar tevens dat ik voor het materiaal in de eindverhandeling dat beschermd wordt door het auteursrecht, de nodige toelatingen heb verkregen zodat ik deze ook aan de Universiteit Hasselt kan overdragen en dat dit duidelijk in de tekst en inhoud van de eindverhandeling werd genotificeerd. Universiteit Hasselt zal mij als auteur(s) van de eindverhandeling identificeren en zal geen wijzigingen aanbrengen aan de eindverhandeling, uitgezonderd deze toegelaten door deze overeenkomst.

Ik ga akkoord,

Niels Schroyen Datum: 23.05.2007

Lsarev_autr

bññáåáøåíé=êéåçéêáåö=çé=ä~~íëíé=öéåéê~íáé=öê~ñáëåüé= Ü~êÇï~êÉ

Recommend Documents