déçãéíêó=`äáéã~éë káéäë=pìäéàã~åá éêçãçíçê=w mêçñk=çêk=táã=i^jlqqb

dÉçãÉíêó=`äáéã~éë

káÉäë=pìäÉàã~åá éêçãçíçê=W mêçÑK=ÇêK=táã=i^jlqqb

=

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

Dankwoord Een thesis maken is een belangrijk onderdeel van een academische opleiding. Het is een product van veel zelfstandig werk en ontelbare uren zwoegen. Ik wil daarom via deze weg een aantal mensen bedanken die me geholpen hebben bij het maken van deze thesis. Om te beginnen bedank ik het onderwijzend team van Prof. dr. Wim Lamotte en Tom Jehaes. Zonder hun steun en richtlijnen was het nooit gelukt. Verder wil ik hen ook danken voor de extra inspanningen die zij geleverd hebben zodat deze thesis toch afgewerkt kon worden. Ook dank ik Jeroen Dierckx voor de nuttige tips tijdens het maken van de implementatie. Ten slotte wil ik ook mijn vriendin en mijn familie bedanken voor de continue steun en begrip tijdens de drukke maanden. Zonder jullie was het nooit gelukt. Bedankt, Niels

Inhoudsopgave 1 Terrein Rendering 1.1 Inleiding tot Level Of Detail . . . . . . . . . . . . . . . 1.2 Introductie tot Terrein Level Of Detail . . . . . . . . . 1.2.1 Terrein rendering . . . . . . . . . . . . . . . . . 1.2.2 Evolutie . . . . . . . . . . . . . . . . . . . . . . 1.3 Evaluatie van terrein level-of-detail algoritmen . . . . 1.3.1 Visuele correctheid . . . . . . . . . . . . . . . . 1.3.2 Processortijd . . . . . . . . . . . . . . . . . . . 1.3.3 Geheugengebruik . . . . . . . . . . . . . . . . . 1.3.4 Real-time vervormbaarheid . . . . . . . . . . . 1.4 Problemen . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Gaps . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Popping artefacten en morphing . . . . . . . . 1.4.3 Omvang van datasets en out-of-core technieken 1.4.4 Hangovers . . . . . . . . . . . . . . . . . . . . . 1.5 Klassieke algoritmen . . . . . . . . . . . . . . . . . . . 1.5.1 Progressive meshes . . . . . . . . . . . . . . . . 1.5.2 Real-time Optimally Adapting Meshes . . . . . 1.5.3 Chunked Level-of-Detail . . . . . . . . . . . . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 1 2 2 7 8 8 10 10 11 11 11 12 14 15 15 16 18 19

2 Geometry Clipmaps 2.1 Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Overzicht . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 De Clipmap . . . . . . . . . . . . . . . . . . . . . 2.2.2 De Geometry Clipmap . . . . . . . . . . . . . . . 2.3 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Clipmap datastructuur en updates . . . . . . . . 2.3.2 Schalering van de datastructuur . . . . . . . . . 2.3.3 Rendering . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Texture mapping . . . . . . . . . . . . . . . . . . 2.3.5 Normal mapping . . . . . . . . . . . . . . . . . . 2.4 Evaluatie . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Visuele correctheid . . . . . . . . . . . . . . . . . 2.4.2 Processortijd . . . . . . . . . . . . . . . . . . . . 2.4.3 Geheugengebruik . . . . . . . . . . . . . . . . . . 2.4.4 Real-time vervormbaarheid . . . . . . . . . . . . 2.5 Problemen . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Transities tussen verschillende niveaus van detail 2.5.2 Selectie van actieve clipmaps . . . . . . . . . . . 2.5.3 View Frustum Culling . . . . . . . . . . . . . . . 2.6 Synthese voor extra detail . . . . . . . . . . . . . . . . . 2.7 Samenvatting . . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23 23 23 24 25 27 27 28 31 32 33 35 35 35 35 36 36 37 39 43 48 48

iii

3 Geometry Clipmaps op de GPU 3.1 Algoritme . . . . . . . . . . . . . . . . . . . . 3.1.1 Datastructuur . . . . . . . . . . . . . . 3.1.2 Gaps en popping . . . . . . . . . . . . 3.1.3 Clipmap grootte . . . . . . . . . . . . 3.1.4 L-shape fixup en view frustum culling 3.1.5 Clipmap updates . . . . . . . . . . . . 3.2 Discussie . . . . . . . . . . . . . . . . . . . . . 3.3 Samenvatting . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

49 49 49 50 51 51 53 53 54

4 Implementatie 4.1 Data structuur . . . . 4.2 Rendering . . . . . . . 4.3 Real-time vervorming 4.4 Resultaten . . . . . . . 4.4.1 Testsysteem . . 4.4.2 Metingen . . . 4.4.3 Discussie . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

55 55 56 57 58 64 65 67

5 Conclusie

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

71

Samenvatting Deze thesis handelt over geometry clipmaps, een level-of-detail techniek voor het renderen van 3D terreinen in computer graphics. Terrein rendering is de laatste jaren een belangrijker onderdeel geworden in 3D applicaties. Grafische kaarten veranderen steeds, waardoor terrein rendering algoritmen aangepast moeten worden aan de nieuwe architecturen. Het aantal triangles dat per seconde gerenderd kan worden is niet langer de grootste bottleneck. Hierdoor presteren de oude algoritmen slecht en moet men op zoek gaan naar alternatieven. Om een betere kijk te hebben op terrein rendering algoritmen wordt er eerst een literatuurstudie uitgevoerd. Hierbij wordt er gekeken naar de belangrijke eigenschappen van level-of-detail technieken voor 3D objecten. Ook worden de belangrijkste eigenschappen van terrein level-of-detail behandeld die nodig zijn om een goede analyse te maken van geometry clipmaps. De literatuurstudie sluit af met een bespreking van drie oudere algoritmen, zodat de verschillende eigenschappen beter begrepen kunnen worden. De kennis uit de literatuurstudie wordt nadien gebruikt om het geometry clipmap algoritme te analyseren. De werking van geometry clipmaps wordt in detail uitgelegd en vergeleken met andere algoritmen. Problemen van het algoritme worden behandeld en indien mogelijk wordt er een oplossing gegeven. Tijdens het bespreken wordt er gekeken naar de sterke en de zwakke punten om een zo goed mogelijk beeld te vormen van de kwaliteiten van geometry clipmaps. Het geometry clipmap algoritme verdeelt het terrein in een aantal niveaus, waarbij het detail van elk niveau afneemt naarmate de afstand tot de kijker vergroot. Via programmeerbare shaders wordt het terrein snel en realistisch weergegeven. Het originele geometry clipmap algoritme blijkt echter te traag te zijn om als onderdeel gebruikt te worden in grotere applicaties. Door het algoritme aan te passen is het mogelijk om een groot deel van het algoritme te verplaatsen naar de grafische kaart. Het verbeterde algoritme maakt optimaal gebruik van de recentste functionaliteit van grafische kaarten waardoor de processor minimaal belast wordt. De technieken die nodig zijn voor de verplaatsing van CPU naar GPU worden onderzocht en ook hier weer worden enkele zwakke punten blootgelegd. Na de aanpassingen is het algoritme een goede kandidaat voor terrein rendering in 3D applicaties. De thesis sluit af met een eigen implementatie van het geometry clipmap algoritme, die geholpen heeft bij het begrijpen van het geometry clipmap algoritme. Ook heeft de implementatie enkele zwakke punten aan het licht gebracht. Een oplossing wordt voorgesteld en ge¨ımplementeerd voor één van deze problemen.

v

Inleiding Al jaren wordt er intensief onderzoek gevoerd naar real-time terrein rendering algoritmen. Door de continu veranderende hardware is het moeilijk om een bestaand algoritme te herbruiken. In de beginjaren was het vooral de beperkte (of ontbrekende) grafische hardware die de grootste bottleneck vormde bij terrein rendering algoritmen. De hardware kon maar een beperkt aantal triangles per seconde verwerken. Naarmate de grafische hardware verbetert, kan men steeds losser omspringen met het aantal triangles dat door de rendering pipeline gestuurd wordt. De huidige generatie grafische hardware bezit voldoende rekenkracht om tientallen miljoenen triangles per seconde te renderen. Maar niet enkel de brute rekenkracht vraagt voor een nieuwe aanpak. Grafische kaarten worden steeds flexibeler, waarbij steeds meer onderdelen van de grafische pipeline geprogrammeerd kunnen worden. Het is dus nuttig om algoritmen te ontwikkelen die hiervan optimaal gebruik maken. Deze thesis behandelt één van deze nieuwe algoritmen. Het doel van deze thesis is het analyseren van het geometry clipmap terrein rendering algoritme [LH04] en de GPU implementatie van dit algoritme [AH05]. Verder wordt het algoritme ge¨ımplementeerd om de efficiëntie te controleren. Per hoofdstuk zullen volgende onderwerpen behandeld worden : In hoofdstuk 1 worden de principes van level-of-detail behandeld. Er wordt onderzocht hoe men level-of-detail algoritmen met elkaar kan vergelijken door te kijken naar een aantal eigenschappen. Verder wordt er in dit hoofdstuk onderzocht wat de eigenschappen zijn van terrein level-of-detail, een onderdeel van het algemene level-of-detail probleem. Het hoofdstuk sluit af met drie analyses van verschillende terrein rendering algoritmen. Hoofdstuk 2 bespreekt het geometry clipmap algoritme. De specifieke werking van het algoritme wordt besproken en vergeleken met andere terrein rendering algoritmen. De eigenschappen van terrein rendering algoritmen uit het vorige hoofdstuk worden gebruikt om sterke en zwakke punten te zoeken. Ten slotte sluit het hoofdstuk af met een aantal problemen van geometry clipmaps en de mogelijke oplossingen. Het geometry clipmap algoritme blijkt te traag te zijn om effectief gebruikt te worden in serieuze applicaties. In hoofdstuk 3 wordt een verbetering van het geometry clipmap algoritme bestudeerd waarbij een groot deel van de CPU taken verplaatst worden naar de GPU. In het laatste hoofdstuk, hoofdstuk 4, wordt er gerapporteerd over de implementatie van het geometry clipmap algoritme. De problemen van het algoritme komen hier opnieuw aan bod, maar dan vanuit een technisch standpunt. Dit hoofdstuk sluit af met een aantal testen die de sterke en zwakke punten van het algoritme aantonen.

vii

Hoofdstuk 1

Terrein Rendering Dit hoofdstuk handelt over het algemeen probleem van terrein rendering, de evolutie en de meest voorkomende problemen.

1.1

Inleiding tot Level Of Detail

Al tientallen jaren wordt er onderzoek gedaan naar efficiënte methoden om het aantal polygonen van 3D modellen te reduceren zonder zichtbaar kwaliteitsverlies (Level Of Detail). Binnen dit domein kan men volgens [LWC+ 02] drie groepen onderscheiden: • Discrete Level Of Detail : Discrete algoritmen berekenen offline verschillende niveaus van detail. Afhankelijk van de afstand tot het object wordt een andere versie van het object gekozen en gerenderd. De methode is zeer CPU vriendelijk omdat enkel de afstand in rekening gebracht wordt, maar gebruikt veel extra geheugen door de verschillende versies van het model op te slaan. Het grote voordeel van deze methode is de mogelijkheid tot handmatige verbetering per niveau voor het beste resultaat. • Continuous Level Of Detail : Bij deze methoden wordt aan het model continu triangles toegevoegd of verwijderd zodat precies het juiste aantal triangles gerenderd wordt. Dit vereist veel rekenkracht door de vele kleine updates. Toch is deze methode interessant omdat er nooit te veel triangles getekend worden. Ook is het mogelijk via intelligente opslag, om de data te streamen over een netwerk, beginnende met weinig detail en nadien incrementeel detail toe te voegen. • View-Dependent Level Of Detail : Dit is een uitbreiding van Continuous LoD waarbij niet enkel de afstand, maar ook de kijkrichting in rekening gebracht wordt om te bepalen welke triangles gerenderd moeten worden. View-dependent algoritmen behalen gelijkwaardige resultaten als continue algoritmen, maar met een kleiner aantal triangles. De kijkrichting in rekening nemen gaat ten koste van iets meer rekenkracht. Wanneer men het detail nog verder wil verlagen is er de mogelijkheid om platte (geanimeerde) texture te gebruiken, billboards genaamd. Billboards zijn de laagste graad van level-of-detail. Meestal worden een aantal textures in een kruis geplaatst zodat er te allen tijde wel één van de textures zichtbaar is. Dit is een zeer snelle methode, maar biedt zeer weinig realisme. Billboards worden vooral gebruik voor het renderen van vegetatie (Figuur 1.1) of om vuur en rook voor te stellen. 1

HOOFDSTUK 1. TERREIN RENDERING

2

Figuur 1.1: Billboard van een boom. Twee dezelfde textures staan in een kruisvorm zodat er altijd iets zichtbaar is vanuit elke hoek. Ten slotte wordt een object dat te ver van de camera verwijderd is gewoon niet meer getekend. ‘Mist’ zorgt ervoor dat het object niet plotseling in de verte verschijnt. Applicaties gebruiken dikwijls een combinatie van deze methoden. Voor objecten die dicht bij de camera zijn, gebruikt men één van de drie level-of-detail technieken (Discrete, Continuous, View-Dependent). Billboards en mist wordt gebruikt voor objecten in de verte.

1.2

Introductie tot Terrein Level Of Detail

Het renderen van realistische terreinen is een belangrijk onderdeel binnen een groot aantal multimedia projecten, zoals virtuele omgevingen of trainingssimulatoren. Vooral bij buitenomgevingen wordt de gebruiker geconfronteerd met de visualisatie van het terrein. Hier moet dus de nodige aandacht aan besteed worden indien men de gebruiker het gevoel van immersie wil geven.

1.2.1

Terrein rendering

In 3D applicaties gericht op buitenomgevingen, zoals bijvoorbeeld een flight simulator, is het terrein het grootste object dat gerenderd wordt. Dit betekent dat verschillende gebieden te zien zijn van op verschillende afstanden en dus niet alle delen met het zelfde niveau van detail gerenderd moeten worden. Het probleem van level-of-detail dat zonet is uitgelegd is dus ook toepasbaar op terreinen, maar door de specifieke aard van terreinen, zoals grootte en vlakheid, is het nuttig om specifieke level-of-detail technieken te ontwikkelen. Terrein level-of-detail heeft niet enkel de verwachte snelheidswinst als voordeel, het is ook belangrijk wanneer om aliasing te vermijden. Bij het renderen van ver afgelegen regio’s waar de triangle/pixel verhouding te groot is, gaan pixels verkeerd gerenderd worden (Figuur 1.2). Terrein structuur Er is een grote hoeveelheid data nodig om terreinen voor te stellen. Een voordehand liggende methode behandelt terreinen net als alle andere 3D modellen, waarbij de verschillende punten opgeslagen worden als individuele vertices. Een efficiëntere opslagmethode is echter mogelijk door een terrein voor te stellen als een plat oppervlak met variatie in hoogtewaarde (Formule 1.1). Hierdoor is er een 1:1 mapping tussen de coördinaten van het grondvlak XY en de hoogtewaarde Z. De X en Y co¨ ordinaten moeten niet opgeslagen worden, ze worden indirect berekent aan de hand van de positie in het geheugen. Deze manier van data opslag verbruikt een derde van het geheugen en is zeer simpel en effic¨ıent te implementeren.


3

Figuur 1.2: Aliasing Distorsie treedt op door een overvloed aan informatie die met een beperkt aantal samples weergegeven wordt.

H(x, y) = z

(1.1)

met x ∈ [xmin , xmax ] en y ∈ [ymin , ymax ] Een terrein voorstellen als een plat vlak is natuurlijk een sterke vereenvoudiging van de realiteit, waar een terrein benadert kan worden door een bol. Maar terrein rendering algoritmen zijn meestal gericht op een hoge graad van detail en hier heeft men nu eenmaal veel data voor nodig. Een terrein kan opgeslagen worden als een texture (Figuur 1.3b), een populaire techniek bij veel algoritmen.

Figuur 1.3: Terrein generatie door een hoogtemap texture. (a) Triangle grid met Z = 0 (b) Hoogtewaarden opgeslagen in de vorm van een texture (c) Hoogtewaarden toegepast op de triangle grid – Afbeelding uit [Bre05] In figuur 1.4 is een voorbeeld te zien van een gedetailleerd model dat aangepast is om snel gerenderd te worden. Naargelang lokale hoogteverschillen en afstand tot de camera wordt het terrein met meer of minder triangles gerenderd. Er zijn ook algoritmen die het mogelijk maken om volledige planeten te visualiseren [CGG+ 03, CH06]. Door de gigantische omvang is het detail dichtbij de oppervlakte meestal beperkt en door de ordinaten zijn de algoritmen trager [CH06]. Sommige planet-sized terrein parametrisatie van bolco¨ rendering algoritmen vermijden bolco¨ ordianten door de bol op te splitsen in een aantal delen die elk voorgesteld worden door een hoogtemap (Figuur 1.5). Het P-BDAM algoritmen [CGG+ 03] maakt hier bijvoorbeeld gebruik van. Hierdoor wordt het probleem herleid tot 6 verschillende hoogtemappen. 3D model voorstellingen Om het aantal triangles van een terrein model te verlagen zijn er twee mogelijkheden. De eerste methode construeert een irreguliere mesh van triangles. Dit wil zeggen dat het model op eerste zicht geen structuur bevat en dat triangles van verschillende grootte doorheen over de gehele mesh verspreid zijn. De triangles zijn echter zo gekozen dat er lokaal meer of minder detail mogelijk


4

Figuur 1.4: Terrein level-of-detail voorbeeld. Links het versimpelde model met verschillende vierkantige stukken die elk een eigen graad van detail hebben. Rechts het volledige model waar het aantal triangles vooral in de verte veel te hoog zijn.

Figuur 1.5: Opsplitsing van een planeet in verschillende hoogtemappen. Het gebruik van bolco¨ ordinaten wordt omzeild door de planeet op te delen in verschillende hoogtemappen met elk een eigen parametrisatie (u, v). – Afbeelding uit [CGG+ 03]


5

is naargelang het hoogteverschil. De tweede methode construeert een regulier grid, zodat binnen een lokaal gebied triangles volgens een vast patroon gepositioneerd worden. In figuren 1.6 en 1.7 zien we twee irreguliere grids: een bovenaanzicht en een perspectief aanzicht. In figuur 1.6 is te zien dat de triangles geen vast patroon hebben en dat triangles binnen een regio ongeveer dezelfde grootte hebben. Figuur 1.7 is een 3D voorstelling van een irregulier grid. Hier zien we dat de kleine triangles gebruikt worden in de gebieden waar veel reliëf is en de grote triangles voor de vlakke gebieden. Modellen van deze vorm noemt men ook Triangulated Irregular Networks, voor het eerst gedefiniëerd in [PTJ78].

Figuur 1.6: Irregulier grid van triangles, ROAM algoritme. Het ROAM algoritme heeft aan de rechterzijde meer triangles samengevoegd. De camera is links gepositioneerd en kijkt naar rechts.

Figuur 1.7: Irregulier grid van triangles, met perspectief gerenderd. De rechtse helling is opgebouwd uit kleinere triangles dan het vlakke dal. – Afbeelding uit [Paj98] De tweede methode gebruikt reguliere grids om het terrein voor te stellen. Hier zijn de triangles vastgelegd volgens een vast patroon. Meestal is dit een rechthoekig gebied waar de hoogtepunten op vaste afstand van elkaar verwijderd zijn. Figuur 1.8 toont een terrein model dat is opgebouwd uit verschillende rechthoekige gebieden waarin elk gebied de triangles gepositioneerd zijn volgens een vast patroon. In dit geval liggen de triangles op vaste horizontale en verticale afstanden. De reguliere vorm kan ook volgens een andere structuur vast liggen. Zo zien we in figuur 1.9 dat de gebieden als cirkels rond de camera gecentreerd zijn en dat de triangles geen rechthoekig patroon vormen. Het lijkt onlogisch dat reguliere grids, die simpeler zijn, na irreguliere grids besproken worden. Dit komt omdat reguliere grids nog niet zo lang gebruikt worden. Reguliere grids verbruiken veel meer resources, waardoor ze pas de laatste jaren populair aan het worden zijn [LH04, LES07]. Met irreguliere grids kan men het terrein voorstellen met een kleiner aantal triangles dan met de reguliere methode. Door te kijken naar lokale hoogtewaarden kunnen irreguliere grids vlakke stukken met een kleiner aantal triangles voorstellen. Reguliere grids kiezen een niveau van


6

Figuur 1.8: Bovenaanzicht van een regulier grid. Elke rechthoekige regio bevat triangles van dezelfde grootte. De camera is gepositioneerd in het zwarte gebied waar de triangles het kleinst zijn. – Afbeelding uit [Lar03]

Figuur 1.9: Regulier grid met bolco¨ ordinaten. Een regulier grid met een bol parametrisatie geeft een goede verdeling van de triangles afhankelijk van de afstand tot de camera. – Afbeelding uit [CH06]


7

detail per regio, waardoor het aantal triangles veel groter is. Vooral oudere algoritmen maken gebruik van irreguliere grids [LKR+ 96, DWS+ 97, Hop98b, Ulr04], maar ze blijven nog altijd de aandacht trekken van onderzoekers [SW06]. Tegenwoordig kan men losser omspringen met het aantal triangles door verbeterde hardware. Daarom heeft men een aantal algoritmen ontwikkeld die gebruik maken van reguliere grids [LH04, AH05, CH06]. Reguliere grids zijn interessant omdat ze gemakkelijker real-time aan te passen zijn.

Real-time terrein updates Terrein redenring algoritmen zijn meestal speciale vormen van view-dependent level-of-detail algoritmen. Afhankelijk van de positie en de kijkrichting van de camera, wordt een stuk van het terrein gerenderd met meer of minder detail. Dit gebeurt door het terrein model real-time aan te passen. Wanneer de camera navigeert, verandert het 3D model geleidelijk aan zodat er meer detail aanwezig is in de regio’s die zichtbaar worden. Bij irreguliere grids gaat men triangles van minder interessante gebieden samenvoegen of splitst men triangles op voor de gebieden die meer detail nodig hebben. Het aanpassen van een reguliere grid is meestal simpeler omdat de datastructuur niet zo complex is. Niet alle algoritmen veranderen 3D modellen in real-time. Sommige algoritmen genereren een aantal statische modellen die tijdens rendering wel of niet getoond worden [Ulr04]. Deze algoritmen zijn meestal simpeler dan algoritmen die in real-time het terrein aanpassen. Verder hebben ze het voordeel dat statische modellen zeer snel te renderen zijn, omdat alle data wordt opgeslagen op de grafische kaart.

1.2.2

Evolutie

Zoals gezegd worden alle level-of-detail algoritmen gedreven door de technologische vooruitgang. De eerste paper over level of detail is geschreven in 1976 [Cla76]. Tijdens die periode was het de normaalste zaak dat het renderen van complexe scenes gemakkelijk enkele minuten in beslag namen. Door de zeer beperkte rekenkracht en het gebrek aan geavanceerde grafische hardware steunde men toen al op het versimpelen van 3D modellen. Ideeën zoals view frustum culling (Sectie 2.5.3) zijn ook in deze periode ontstaan en worden tot op heden nog altijd intensief gebruikt. Een 15-tal jaren later werden de eerste interactieve virtuele realiteiten ontwikkeld waarin grote terreinen ‘real-time’ gevisualiseerd werden. Het systeem ontwikkeld door [HM93] bijvoorbeeld, maakte gebruik van 3 criteria om te bepalen met hoeveel detail een object gerenderd werd. Hiermee werd een framerate gehaald van ongeveer 10 beelden per seconde waarbij de dataset uit 150.000 polygonen bestond. Factoren zoals globale afstand tot camera, schermafstand tot het centrum van het beeld en door de gebruiker gespecifiëerde interessen bepaalde het niveau van detail voor elk object. De laatste jaren zijn er een aantal algoritmen gevonden die succesvol zijn toegepast in commerciële toepassingen [VTP]. Tot enkele jaren terug was het gebruik van geavanceerde terrein rendering echter een grote CPU bottleneck en koos men al snel voor simpelere versies of zelfs voor één grote statische mesh. Echte duidelijkheid bestaat er hier niet over omdat de meeste producten closed source zijn en er weinig informatie vrij gegeven wordt. Recente ontwikkelingen tonen aan dat realistische terreinen populair zijn. In de game industrie zijn er verschillende titels te vinden waar schitterende resultaten behaald worden. Momenteel bestaan 3D modellen in games uit tienduizenden polygonen en is het hoekige uitzicht van de modellen niet meer aanwezig. Hierdoor kan men ook meer rekenkracht spenderen aan het renderen van visueel aantrekkelijke terreinen. Flight simulators waren al veel eerder bezig was met state of the art terrein rendering. Een korte samenvatting van terrein rendering engines in games is beschikbaar in [VTP]. In twee screenshots van Falcon 4.0, een flight simulator van Microprose uit


8

1998, is te zien dat het terrein zeer realistisch was voor zijn tijd (Figuur 1.10 en 1.11). Merk op dat in figuur 1.11 het vliegtuig zelf uit een zeer klein aantal polygonen bestaat en dat de wolken billboards zijn, terwijl het terrein visueel zeer aantrekkelijk is.

Figuur 1.10: Screenshot 1 van Falcon 4.0. De straaljager is net opgestegen van het vliegveld. Let op de golven aan de rand van het eiland en op de kwaliteit van de texture mapping op de grond. Het vliegtuig is een simpel model, maar er is wel een piloot gerenderd. Terrein rendering algoritmen kan men opdelen in twee verschillende categoriën : de algoritmen ontwikkelt voor de intrede van grafische hardware [HM93, LKR+ 96, Hop98b, DWS+ 97] en algoritmen na de intrede van grafische hardware [LH04, D.04, Ulr04, AH05, SW06]. De algoritmen die ontwikkeld zijn om optimaal gebruik te maken van grafische hardware zijn veel efficiënter, omdat ze gericht zijn op het minimaliseren van CPU verbruik en het verlagen van interactie tussen CPU en GPU. De oudere algoritmen blijven echter nuttig om te bestuderen omdat veel ideeën hergebruikt kunnen worden.

1.3

Evaluatie van terrein level-of-detail algoritmen

Elk terrein level-of-detail algoritme heeft specifieke karakteristieken die sterk kunnen verschillen ten opzichte van andere algoritmen. Natuurlijk is het resultaat één van de belangrijkste criteria, maar ook vele andere eigenschappen spelen een rol in het succes van een algoritme. Het is belangrijk om te weten wat de sterke en zwakke punten zijn, om zo een juiste keuze te maken voor een applicatie. Hieronder volgen de belangrijkste kenmerken van deze algoritmen.

1.3.1

Visuele correctheid

Visuele correctheid is ongetwijfeld de belangrijkste factor in het correct en realistisch weergeven van het terrein. Evaluatie kan gebeuren door te kijken naar de afwijkingen van de polygonen ten opzichte van het basismodel via een error-metric. Deze error-metric methoden komen van het algemeen level-of-detail domein en kunnen dus rechtstreeks toegepast worden op terreinen. Als basisregel geld dat de beste evaluatie gebeurt door het menselijk visueel systeem. Wiskun-


9

Figuur 1.11: Screenshot 2 van Falcon 4.0. Het gebied rond het ravijn is redelijk realistisch gerenderd. Dichtbij is het terrein geblokt, verder weg is er geen enkel detail en is het terrein wazig. Let op de kwaliteit van het water in de ravijn en op de billboard wolken die allemaal het zelfde zijn. De lucht is een zeer simpele kleurovergang. dige methoden geven een statistische analyse van de meetfout, maar is dit wel altijd even nuttig? Een kort voorbeeld: een terrein algoritme kan geanalyseerd worden door een persoon en als ‘goed’ beschouwd worden, terwijl de wiskundige methode aangeeft dat er veel grote afwijkingen zijn. Een berg in de verte zou misschien te veel afwijken van het correcte model, maar indien het algoritme dit verstopt door de berg traag te laten ‘groeien’, zonder dat de gebruiker dit merkt, is dit geen enkel probleem. Het is dus belangrijk dat een statistische methode rekening houdt met de afstand tot camera. Maar omdat de gebruiker dikwijls van locatie veranderd is het onmogelijk om alle posities in rekening te brengen. Dit wil echter niet zeggen dat statistische methoden totaal nutteloos zijn. Integendeel, ze zijn belangrijk omdat ze de vergelijking tussen verschillende algoritmen objectief houden. Laten we even kijken naar de verschillende methoden die gebruikt kunnen worden om afwijkingen te meten. Hieronder volgt een korte samenvatting uit [LWC+ 02]. • Geometrische afwijking De meest logische methode is het meten van het verschil tussen het gerenderd punt in de ruimte en de correcte waarde zonder enige vorm van level-of-detail. Met andere woorden, de hoogtewaarden van het versimpelde model vergelijken met het grondmodel. Hierbij wordt de afstand berekend tussen twee punten en daarvan de maximum of gemiddelde afwijking gebruikt om de fout aan te geven. Er kan gekozen worden uit verschillende afstandsmethoden zoals de Euclidische- of de Hausdorff afstand. De Hausdorff afstand tussen twee sets van punten(= het gerenderde en het grondmodel) is het maximum van de afstanden tussen elk punt in de eerste set, met het dichtstbijzijnde punt in de tweede set. In het geval van terrein analyse zou men kunnen kiezen om te vergelijken met het dichtste punt dat hoger of lager ligt. Dit is precies wat gebruikt wordt in [dB00]. Per niveau van detail wordt het maximum genomen van alle afwijkingen op de Z-as, die ontstaan door verwijdering van vertices tussen opeenvolgende niveaus. In [Ulr04] wordt dit ook toegepast, maar wordt de afwijking gemeten ten opzichte van het grondmodel en niet tussen opeenvolgende niveaus. • Schermafwijking Omdat het laagste niveau van detail meestal het verst verwijderd is van de kijker, kan een grote geometrische afwijking slechts enkele pixels verschillen in het beeld.


10

Vergelijken hoeveel een hoogtepunt afwijkt ten opzichte van de correcte waarde kan daarom ook door te kijken naar de pixelafwijking op het scherm. Dit noemt men de screen-space error en kan gemeten worden door een punt te projecteren op het scherm en vervolgens te vergelijken met de projectie van de correcte waarde. Kennis over screen-space error wordt dikwijls gebruikt om het juiste niveau van detail te selecteren. Het ROAM algoritme [DWS+ 97] en het verouderde algoritme van Lindstrom [LKR+ 96] maken hier gebruik van. Bij het ROAMing terrein algoritme bijvoorbeeld stuurt een gekozen maximaal toegelaten afwijking het splitsen of samenvoegen van triangles. Meer detail over ROAM in sectie 1.5.2. • Attribuutafwijking Vele papers over level-of-detail rapporteren over de screen-space error om aan te tonen hoe goed het algoritme werkt. Zelden hoor je echter iets over de afwijking van andere attributen. Normalen voor belichting, kleur en texture coördinaten kunnen ook veranderen door detailreductie. Het Progressive Meshes algoritme van Hoppe brengt verschillende attributen in rekening (Sectie 1.5.1). Enkele algoritmen gebruiken een combinatie van de drie bovenstaande methoden. Zo gebruiken [DWS+ 97, Hop98b] de geometrische error om te bepalen welke triangles het best gesplitst/samengevoegd worden, maar gebruikt de screen-space error als stopconditie voor het algoritme. Vooral de schermafwijking is een interessante manier om correctheid te meten. Door de grote verschillende in afstand kan een sterke geometrische afwijking verwaarloosbaar zijn.

1.3.2

Processortijd

Behalve visuele schoonheid moet een algoritme ook snel zijn. Renderen van een 3D terrein is meestal slechts een klein onderdeel van een groter systeem dat nog vele andere aspecten moet afhandelen: renderen van objecten, networking, physics en artificiële intelligentie. Een correcte balans tussen CPU en GPU verbruik is dan ook cruciaal. Andere factoren zoals de bandbreedte tussen CPU en GPU hebben ook een belangrijke invloed op de snelheid van een systeem. De laatste jaren is er vooral een trend om het renderen van terreinen zoveel mogelijk te verplaatsen naar de grafische processor. Updates van het 3D model gebeuren zo veel mogelijk op de GPU om de druk op de CPU te verlagen. Algoritmen zoals [AH05, CH06, SW06] zijn hier voorbeelden van. Afhankelijk van de positie en kijkrichting moet het model dat gerenderd wordt aangepast worden (Continuous LoD). Algoritmen verschillen van elkaar in complexiteit van updates. Zo zal [DWS+ 97] een aantal ingewikkelde splits en/of merges uitvoeren met behulp van 2 queues en hierdoor de CPU continu belasten, terwijl [LH04] enkel buffers aanpast met nieuwe waarden.

1.3.3

Geheugengebruik

Wanneer we geheugengebruik van verschillende algoritmen bekijken, zien we dat er gevarieerde methoden toegepast worden. Sommige algoritmen samplen textures waar de kleur een hoogtewaarde aangeeft [AH05]. Andere bouwen een quadtree op van rechthoekige blokken [D.04] en gebruiken geomorphing om de overgangen naadloos te renderen. En nog andere gebruiken een triangle bintree [DWS+ 97], waarbij triangles verschillen in grootte naargelang de lokale hoogteverschillen. Er zijn dus een aantal verschillende methoden onderzocht met elk hun voor- en nadelen. Als vuistregel kan gesteld worden dat de complexiteit negatieve invloed heeft op de real-time aanpasbaarheid. In het algemeen kijkt men naar het aantal bytes per hoogtewaarde en de structuur van geheugenopslag. Het aantal bytes per hoogtewaarde bepaalt hoeveel terrein er opgeslagen kan worden in main memory. Wanneer de data verplaatst wordt naar het grafische geheugen zal de data natuurlijk meer plaats innemen omdat de X en Y coördinaten toegevoegd worden. Dit is echter geen probleem omdat slechts een klein deel van de data is gelijktijdig nodig is in het grafische geheugen.


11

De structuur van geheugenopslag bepaalt hoe gemakkelijk een terrein te cachen is naar de harde schijf. In geometry clipmaps [LH04] gebruikt men bijvoorbeeld een compressie piramide waarbij een initiële schets van het laagste detail ingelezen kan worden en nadien verbeterd wordt als er voldoende tijd beschikbaar is. Meestal hebben de hoogtewaarden een zeer lage variantie in een kleine omgeving, met andere woorden, aangrenzende hoogtepunten verschillen weinig van elkaar. Dit maakt hoogtewaarden ideaal voor compressietechnieken. Sommige methoden gebruiken procedurele methoden om hoogtewaarden te berekenen. Hiermee vermijdt men het caching probleem, omdat er geen data bijgehouden wordt in main memory. In dit geval zou een zeer kleine heightmap, ook gekend als sketch atlas [CD04], het algoritme kunnen sturen. Procedurele methoden worden soms ook gebruikt om extra niveaus van detail toe te voegen zonder dat hiervoor hoogtedata beschikbaar is [LH04, SW06]. Dit verhoogt het detail van een bestaand algoritme zonder geheugengebruik. Synthese van extra detail is bovendien zeer efficiënt uit te voeren op de GPU.

1.3.4

Real-time vervormbaarheid

Een laatste eigenschap van een terrein rendering algoritme is de mogelijkheid tot vervorming in real-time. Dit kan nuttig zijn voor artiesten die fictieve terreinen willen scheppen en niet telkens de omzetting van hoogtemap naar 3D model willen uitvoeren (Figuur 1.3). Ook is het interessant wanneer een applicatie de gebruiker de mogelijkheid bied om met verschillende acties het terrein te veranderen. Denk bijvoorbeeld aan computergames waarbij een inslag het landschap wijzigt. Onderzoek over terrein rendering gaat zelden diep in op dit onderdeel, omdat de nadruk ligt op snelheid en visuele correctheid. Vermoedelijk gaat dit aspect van terrein rendering belangrijker worden in de toekomst naarmate applicaties complexer worden.

1.4

Problemen

De meeste terrein rendering algoritmen krijgen te maken met een aantal problemen die opgelost moeten worden vooraleer het algoritme als ‘goed’ beschouwd kan worden. Onderzoekers spenderen daarom typisch een groot deel van hun aandacht om deze problemen (met succes) op te lossen.

1.4.1

Gaps

Binnen een terrein zijn er dikwijls gebieden met verschillende niveaus van detail. De grens tussen die gebieden is dikwijls zichtbaar door te grote verschillen in resolutie. Wanneer een niveau van een model minder triangles bevat komen de hoogtewaarden niet overeen en is het model onderbroken. Delen die onderbroken zijn vormen dan gaten in het model (gaps). Dit is echter niet toegelaten bij een realistische weergave en moet opgelost worden. Klassieke level-of-detail algoritmen hebben ook dikwijls last van gaps. Gaps bij terrein rendering zijn meestal het gevolg van T-junctions: splitsingen tussen twee verschillende modellen in de vorm van een hoofdletter T. Een deel van het terrein met een hoger detailniveau laat meer variatie toe in hoogtewaarden. In figuur 1.12 is te zien dat het linkse niveau minder gedetailleerd is dan het rechtse niveau. Als de tussenliggende hoogtepunten variëren onstaan er gaten in de mesh. Gaps opvullen Een voordehand liggende methode gebruikt extra triangles die de gaten opvullen. In figuur 1.12 is te zien dat de gaten een vorm aannemen van een triangle. Door juist die triangle aan te maken


12

Figuur 1.12: T-junction probleem (a) Grens tussen twee niveaus van detail. De T splitsingen, aangeduid met de cirkels, kunnen gaten veroorzaken. (b) Perspectief van (a). Er ontstaan 2 gaten omdat de hoogtewaarden niet het zelfde zijn als de hoogtewaarden van het niveau met lager detail. wordt het gat opgevuld (Figuur 1.13).

Figuur 1.13: Triangle insertion.De driehoekige opening wordt opgevuld met een triangle. Triangles toevoegen vult de gaps op zodat de mesh gesloten is, maar het zijaanzicht toont een mogelijk probleem. De mesh wordt plotseling zeer onrealistisch door een verticale sprong. Een betere methode, die onder andere gebruikt wordt in [D.04], voert een overgangszone in, zodat de gaten opgevuld worden en tegelijkertijd de overgang geleidelijk aan gebeurt. Er zijn twee mogelijkheden om dit te bekomen. Zo kan men het niveau met de grootste triangles aan de rand opsplitsen en de T-junctions vermijden (Figuur 1.14b). Maar het is gemakkelijker en sneller om het niveau met de kleinste triangles aan te passen (Figuur 1.14c), waardoor er geen extra triangles nodig zijn [D.04, LH04]. Skirts Een andere manier om gaten in 3D modellen op te vullen komt uit het domein van terrein rendering, namelijk het gebruik van skirts [Ulr04]. Skirts zijn overhangende triangles tussen verschillende delen van het model die ervoor zorgen dat de gaps opgevuld worden met valse pixels. In figuur 1.15 is te zien hoe de rand van een model uitgebreid wordt met een skirt. Als er een gap ontstaat, door het verschil in detail, zal men door de gap heen een aantal triangles zien zodat de gaten opgevuld lijken. Deze methode is echter niet aan te raden omdat er meer triangles nodig zijn en er visuele afwijkingen ontstaan bij translatie/rotatie (foute kleuren en onrealistisch gedrag).

1.4.2

Popping artefacten en morphing

Wanneer een object of een stuk van het terrein dichterbij of verder weg van de camera beweegt, dan zal het aantal triangles door het level-of-detail algoritme worden aangepast. Veranderen van het aantal triangles resulteert in popping artefacten. Als een object plotseling met een ander aantal


13

Figuur 1.14: Twee methoden om gaps op te vullen. (a) De driehoekige opening uit figuur 1.13. (b) De grotere triangle wordt opgesplitst en verplaatst zodat de mesh aaneengesloten is. (c) Zelfde als in (b) maar deze keer wordt de vertex van de kleinere triangles verplaatst.

Figuur 1.15: Skirt voor het gap-probleem. Een rand van hangende triangles vult de gaten tussen verschillende niveaus van detail. – Afbeelding uit [NL03].


14

triangles gerenderd wordt, lijkt het alsof er plotseling vertices verdwijnen of tevoorschijn komen. Zo zou een huis van op grote afstand voorgesteld kunnen worden als een kubus, maar dichterbij met een puntdak en een schoorsteen. Op de grens tussen kubus en puntdak/schoorsteen springen een aantal vertices in beeld die storend zijn voor de gebruiker. Dit kan opgelost worden door een overgangsfase in te lassen waarin het model transformeert van de ene vorm naar de andere, morphing genaamd. Morphing gebeurt in twee richtingen. Als het aantal triangles verhoogt, gaat het algoritme eerst het aantal triangles verhogen met een aantal opsplitsingen, maar de vertices worden nog niet verplaatst. Vervolgens worden de toegevoegde triangles in verschillende tussenstappen verplaatst naar hun doelpositie. Het morphing principe is ge¨ıllustreerd in figuur 1.16, waar een vijfhoek opgesplitst wordt en met een tussenstap de doelvorm wordt aangenomen. Om de overgang vlot te laten verlopen is er meer dan één tussenstap nodig. Ook moet het algoritme op tijd beginnen met morphen omdat de gebruiker anders het model ziet ‘groeien’.

Figuur 1.16: Progressive aanpassing van een vijfhoek. De vijfhoek links wordt aangepast zodat er een extra vertex V ontstaat. Hierdoor verhoogt het aantal triangles van 3 naar 5 en is er dus meer detail mogelijk. Vertex V verplaatst vervolgens in tussenstappen naar de doelpositie, aangegeven in de rechter tekening. Door de morphing is de overgang niet zichtbaar. Wanneer een level-of-detail algoritme beslist dat er minder triangles nodig zijn, kan men de morph operatie omkeren. De nodige triangles worden in de omgekeerde richting verplaatst zodat de vorm overeenkomt met de minder gedetailleerde vorm. Nadien worden de overtollige triangles verwijderd zonder dat de gebruiker hier iets van merkt.

1.4.3

Omvang van datasets en out-of-core technieken

Terreinen zijn bijna altijd de grootste modellen die gerenderd moeten worden. Het probleem hierbij is dat de gebruiker dikwijls rechtstreeks in contact staat met het terrein. 3D modellen van personages of voertuigen steunen op het terrein waardoor er een hoge graad van detail nodig is in de nabije omgeving. Een terrein rendering algoritme moet dus voor een enorme oppervlakte zeer gedetailleerd zijn, wat al snel leidt tot dataset van verschillende gigabytes groot. De data moet daarom compact opgeslagen worden en tegelijkertijd flexibel genoeg zijn om snel een specifiek gebied gedetailleerd weer te geven. Gelukkig is terreindata meestal coherent binnen een lokaal gebied: de hoogtewaarden stijgen of dalen meestal traag, waardoor compressie efficiënt uit te voeren is. Puget Sound Dikwijls worden terrein rendering algoritmen getest met de Puget Sound dataset1 . Door altijd het zelfde terrein te gebruiken kan de vergelijking tussen verschillende algoritmen zo objectief mogelijk gehouden worden. Deze dataset bevat 16385 × 16385 = ±268 miljoen hoogtepunten, opgeslagen in een beeldbestand. De eigenlijke afstand tussen twee pixels is 1 meter en dus is de totale oppervlakte ongeveer gelijk aan 16 × 16 kilometer. Per hoogtewaarde verbruikt men 16 bits, 1 Puget

dataset : http://www.cc.gatech.edu/projects/large models/ps.html


15

oftewel 65536 mogelijke hoogtewaarden. In totaal is de Puget Sound dataset ongecompresseerd ±4Gb groot en dat is enkel voor de hoogtewaarden, niet voor de texturing van het terrein. Het is dus duidelijk dat we moeten werken met een gigantische hoeveelheid data om terreinen te renderen met hoog detail en tegelijkertijd een groot gebied. Out-of-core Er bestaan algoritmen die het terrein opdelen in een aantal blokken, zoals dat van Ulrich [Ulr04]. Deze blokken kunnen gemakkelijk verplaatst worden naar externe opslagmogelijkheden, zoals harde schijven en netwerk servers. Deze algoritmen laten het dus toe om ongebruikte stukken tijdelijk uit het geheugen te halen en zo het geheugengebruik te beperken. Meestal wordt de data bijgehouden in main memory, in-core genaamd. Wanneer de data echter te groot is om in main memory te passen, spreekt men van out-of-core algoritmen. Out-of-core algoritmen verdelen de mesh niet in verschillende blokken, maar gebruiken compressie met goede lokaliteit. Deze technieken bewaren een gecompresseerde vorm van het terrein. Maar door een compressie techniek te gebruiken, die zeer snel specifieke delen van het terrein kan decompresseren, is het mogelijk om de buffers constant gevuld te houden. Out-of-core technieken lossen typisch twee problemen op: snel uitlezen van specifieke data en voorspellen welke stukken binnenkort nodig zijn. Voor achtergrondinformatie over out-of-core terrein rendering wordt verwezen naar [LP02].

1.4.4

Hangovers

Ten slotte zijn er ook enkele struikelblokken door de manier van data opslag. Dikwijls wordt er gekozen voor een hoogtemap waarbij enkel de hoogtewaarde opgeslagen wordt (Figuur 1.3). Dit heeft als voordeel dat er slechts een derde aan geheugen nodig is. Maar deze methode laat spijtig genoeg geen overhangende gebieden toe. Overhangende gebieden zoals in figuur 1.17 hebben tot nu toe nog maar weinig aandacht gekregen. Hoewel sommige papers naar dit probleem refereren, wordt het meestal genegeerd en zijn er weinig algoritmen die hiermee overweg kunnen. Indien er een overhangend gebied nodig is, zoals bij een grot, kan met gebruik maken van een tweede object dat bovenop het terrein wordt geplaatst. Op deze manier wordt het een artistiek probleem en kan men de terreindata compact houden.

Figuur 1.17: Overhangend terrein vormt een grot. (a) Een doorsnede van een terrein zonder overhang. De projecties tussen XY co¨ ordinaten en hoogtewaarde Z zijn uniek. (b) Een doorsnede van een terrein met overhang. In het aangeduide gebied is er geen unieke mapping tussen XY co¨ ordinaten en de hoogtewaarde Z.

1.5

Klassieke algoritmen

In deze sectie worden drie klassieke algoritmen besproken. De eerste twee algoritmen maken gebruik van samenvoegingen en opsplitsingen om modellen in kleine stapjes aan te passen gedurende


16

de uitvoering van het algoritme. Het eerste algoritme, Progressive Meshes [Hop96], is ontwikkeld om gebruikt te worden voor allerlei 3D modellen. Het tweede algoritme, ROAM [DWS+ 97], is specifiek ontwikkeld voor het renderen van terreinen. Deze twee algoritmen zijn ontwikkeld in een periode waarin het aantal triangles de grootste bottleneck was voor een algoritme. Het laatste algoritme, Chunked LOD [Ulr04], is een recent terrein rendering algoritme dat optimaal gebruik maakt van de huidige generatie grafische hardware.

1.5.1

Progressive meshes

In 1996 ontwikkelde Hoppe een methode om 3D modellen progressief aan te passen [Hop96]. Dit wil zeggen dat een mesh, beginnend met een grondmodel, geleidelijk aan uitgebreid wordt met extra vertices, zodat het detail verbetert. De elegantie van kleine toevoegingen maakt het mogelijk om de meshes te streamen en zelfs specifieke delen meer prioriteit te geven dan andere. Om dit principe van progressieve meshes uit te kunnen leggen moeten we eerst 2 operaties definiëren, namelijk edge collapse en vertex split. In figuur 1.18 is te zien hoe een zevenhoek, voorgesteld met 8 vertices en 7 triangles, aangepast wordt tot een zevenhoek met 9 vertices en 9 triangles. Vertex Vs wordt via de vertex split operatie opgesplitst in 2 vertices. De omgekeerde operatie, edge collapse, vervangt de edge tussen 2 vertices door één enkele vertex. Zoals aangegeven in [LWC+ 02] zijn er 3 logische posities voor vertex Vs . Men kan kiezen uit één van de posities van Vu of Vt , waardoor er slechts 1 vertex last heeft van popping effecten. Of men kan kiezen om een interpolatie uit te voeren tussen de 2 vertices Vu en Vt , zoals bijvoorbeeld het gemiddelde van de twee vertices. Het progressive meshes algoritme van Hoppe gaat herhaaldelijk op zoek naar de meest optimale collapse. Een traag offline proces lost een minimalisatieprobleem op.

Figuur 1.18: Edge collapse en vertex split operatie. Van links naar rechts wordt een vertex Vs opgesplitst in 2 vertices, Vu en Vt . De omgekeerde operatie, de samenvoeging, combineert Vu en Vt tot vertex Vs . – Afbeelding uit [Hop98b] Eerst begint het algoritme een aantal edge collapse operaties uit te voeren die het model stapsgewijs versimpelen. Dit traag offline proces minimaliseert de afwijkingen per collapse, om zo te voldoen aan een aantal eigenschappen en zoveel mogelijk de originele vorm van de mesh te behouden. Zoals reeds gezegd, wordt hierbij de optimale nieuwe positie berekend ergens tussen de 2 vertices Vu en Vt . Het is ook belangrijk dat andere parameters, zoals de normalen en kleur, niet te veel veranderen. Als de normalen te sterk veranderen, kan het model misschien een goede benadering zijn voor de vorm, maar zal het verschil tussen de verschillende niveaus zichtbaar zijn door een totaal andere belichting. Behalve vormen attributenbehouding (normalen, kleur, . . . ), is het ook belangrijk om gecurvde stukken te bewaren, omdat die veel bijdragen tot de vorm van het object. De minimalisatiefunctie houdt dus rekening met 3 factoren, om zo de meest optimale sequentie collapses te bepalen. Het algoritme heeft een grondmodel en een aantal vertex split operaties als resultaat. Hiermee is het mogelijk maken om het model terug op te bouwen. Eenmaal dat een grondmodel gekend is, kan men de nodige vertex splits of edge collapses uitvoeren, naargelang er meer of minder detail nodig is. Progressive meshes van Hoppe zijn interessant omdat ze arbitraire meshes toelaten waar lokaal meer of minder detail mogelijk is. De verschillende edge collapses zijn namelijk in een boom gestructureerd, waardoor een aantal


17

collapses parallel uitgevoerd kunnen worden. Met andere woorden, te allen tijde kan het algoritme kiezen uit een kleine set van vertex splits of edge collapses. In figuur 1.19 is een boomstructuur te zien van een aantal operaties. Grondmodel M 0 bestaat uit 3 vertices, V1 , V2 en V3 . Elk van deze vertices kan opgesplitst worden in 2 nieuwe vertices. Afhankelijk van de camera kan men bijvoorbeeld kiezen om V1 en V3 één keer op te splitsen. Men zou ook kunnen kiezen om V2 volledig op te splitsen tot aan de leafs van de boom terwijl V1 en V3 onveranderd blijven. Op deze manier is M i in figuur 1.19 een variërend front van actieve vertices en is M n het front met alle opsplitsingen. Door meer splitsingen uit te voeren op een deelboom kan men lokaal meer of minder detail weergeven. In figuur 1.20 is een alternatief front te zien, aangeduid in het grijs, waarbij vertex V1 gedeeltelijk is opgesplitst en vertex V3 volledig.

Figuur 1.19: Variabel front Mn van actieve vertices. Een front Mn is helemaal uitgewerkt tot het hoogste niveau van detail. Alle vertices uit het grondmodel M0 zijn volledig opgesplitst. – Afbeelding uit [Hop98b]

Figuur 1.20: Alternatief variabel front van actieve vertices. Het grijze front is een voorstelling van het object waarbij slechts een deel van de triangles opgesplitst zijn. – Aangepaste afbeelding uit [Hop98b] Tijdens het renderen van de progressive mesh verandert het front naargelang de camera positie en richting. Wanneer een vertex opsplitst of wanneer twee vertices samengevoegd worden, kan men een interpolatie uitvoeren gedurende een korte periode, zodat er geen popping optreed. Een split van vertex Vs uit figuur 1.18 begint met het aanmaken van een tweede vertex op dezelfde positie als Vs . Laten we de originele vertex Vs1 noemen en de nieuwe vertex Vs2 . Vervolgens beweegt vertex Vs1 naar de doelpositie Vu en beweegt Vs2 naar Vt gedurende een korte morphing periode. Op analoge wijze kan men morphing uitvoeren voor de collapse operatie. Progressive meshes zijn uitstekend voor streaming van 3D models. In veel multimedia systemen is het nuttig dat men eerst een grondmodel rendert en daarna details toevoegt. Denk hierbij aan een object dat vanuit de verte naar de camera beweegt. In het begin kan de server een grondmodel inladen en als het object dichter komt, wordt er extra data opgevraagd. De terreindata kan verstuurd worden door een streaming server of uitgelezen worden van de harde schijf. Volgens Hoppe is het mogelijk om de mesh real-time te vervormen [Hop96], maar hoe dit precies


18

werkt wordt niet uitgelegd. Ook niet in de vervolgpaper [Hop98a] waarin meer implementatie details staan. Pas in 2005 heeft Hoppe een patent aangevraagd voor zijn Regional progressive meshes 2 . Dit zijn progressive meshes die grote oppervlakken toelaten waarbij lokale vervorming mogelijk is. Volgens Hoppe is dit mogelijk door de mesh op te delen in meerdere submeshes, maar hoe dit precies gebeurt wordt verder niet vermeld.

1.5.2

Real-time Optimally Adapting Meshes

Het ROAMing [DWS+ 97] algoritme uit 1997 is een zeer populair algoritme dat de terreinmesh at runtime aanpast, zodat het model met een optimaal aantal triangles gerenderd wordt. Het is een view-dependent algoritme dat afhankelijk van de camerapositie en kijkrichting triangles samenvoegt (merge) of terug opdeelt in kleinere triangles (split). Zoals altijd is het de bedoeling om het aantal triangles minimaal te houden zonder verlies van visueel detail. Daarom worden aangrenzende triangles met weinig hoogteverschillen samengevoegd als ze ver verwijderd zijn en gesplitst als de camera dichter bij komt. In figuur 1.6 en 1.7 zijn twee voorbeelden te zien van irreguliere grids. De split en merge operaties worden ge¨ıllustreerd in figuur 1.21, waarbij het vierkant in de eerste rij 4 keer gesplitst wordt en in de tweede rij 2 triangles van het vierkant worden samengevoegd.

Figuur 1.21: Merge en split operaties. Een irregulier grid wordt vier keer opgesplitst in de bovenste rij. Hierbij staat de camera linksboven en wordt er gekeken naar de rechtsonder. In de tweede rij is de camera verplaatst waardoor twee triangles in 2a minder detail nodig hebben en samengevoegd worden. Dit veroorzaakt een recursieve samenvoeging in 2c. De structuur van een ROAM terrein bestaat uit geneste triangles waarvan de ene triangle meer opgesplitst is dan de andere. Merk op dat alle zijden van de triangles in figuren 1.6 en 1.21 grenzen aan volledige zijden van andere triangles. Dit is nodig om T-junctions te vermijden (Sectie 1.4.1) In figuur 1.21 is de verandering van camera positie te zien die er toe leid dat de verticale gestippelde lijn in 2a (linksonder) minder detail nodig heeft. Door de twee aangrenzende triangles te mergen ontstaat er echter een T-junction, zichtbaar in 2b. Het algoritme moet daarom recursief de gestippelde lijn in 2c verwijderen om de T-junction te vermijden. Het recursief samenvoegen of opsplitsen is verplicht om ten alle tijde een gesloten mesh te behouden. Deze merge en split operaties zijn niet hetzelfde als de edge collapse en vertex split van progressive meshes [Hop96] uit sectie 1.5.1. Een triangle merge bij ROAM verwijdert altijd de gedeelde vertex die de rechte hoeken vormt. Hierbij worden de twee triangles (opgebouwd uit vier vertices) vervangen door één 2 Regional

progressive meshes (US Patent 6879324)


19

grotere triangle. De split operatie is net het omgekeerde, namelijk een opsplitsing in het midden van de langste zijde. Welke triangles er precies samengevoegd worden is afhankelijk van de afstand tot de camera en van het lokale reliëf. Om te bepalen welke triangle men het eerst moet mergen, houdt men voor elke triangle bij hoeveel de afwijking is in wereldcoördinaten ten opzichte van het grondmodel. De triangles met de kleinste geometrische afwijkingen zullen het eerste samengevoegd worden. Zo zullen triangles in vlakke gebieden sneller samengevoegd worden, omdat ze weinig afwijken van hun buren en dus de afwijking minimaal blijft. Volgens de auteurs van het ROAM algoritme kan men ook andere parameters in rekening brengen, zoals normalen en texture coördinaten. Het ROAM algoritme gebruikt de schermafwijking (Sectie 1.3.1) als stopconditie voor de merge operatie. Als de totale afwijking onder een vaste waarde ligt, stopt het mergen voor de huidige camerapositie. Als de camera naar het terrein toe beweegt, dan zullen de triangles op het scherm groter worden en de schermafwijking zal dan stijgen. Om te voldoen aan een maximum schermafwijking moet het algoritme een aantal triangles terug opsplitsen. Hiervoor wordt er opnieuw gekeken naar de meest invloedrijke triangle. Door een zeer kleine schermafwijking te kiezen kan het algoritme ervoor zorgen dat de visuele correctheid bijna perfect is, maar zal er veel rekenkracht nodig zijn. Berekenen van de meest invloedrijke triangle at run-time is een dure operatie. Daarom wordt er gebruik gemaakt van een gesorteerde lijst waarin de meest optimale volgorde wordt bijgehouden. Er zijn 2 lijsten: 1 voor de volgorde van optimale splitsing en 1 voor de volgorde van optimale samenvoeging. De lijsten worden op voorhand berekend zodat enkel de schermafwijking gecontroleerd moet worden tijdens de uitvoering. Net als progressive meshes laat het ROAM algoritme morphing toe. Bij een splitsing of samenvoeging gaat men met kleine stapjes de aanpassing verbergen door een interpolatie uit te voeren tussen de beginpositie en de eindpositie van de vertices, zodat men geen last heeft van popping artefacten. De vele updates en de extra morphing kosten maken het ROAMing algoritme traag. Het is een CPU gebonden algoritme dat onefficiënt werkt op hedendaagse hardware, omdat er veel verkeer is tussen CPU en GPU. Op oudere hardware was het ROAM algoritme wel snel omdat die systemen vooral op de CPU vertrouwde. Een ROAM terrein is real-time vervormbaar, omdat de geometrische afwijking lokaal berekend wordt. Dit wil zeggen dat de meest optimale volgorde voor de split- en mergelijst berekend wordt om te voldoen aan een lokaal minimum en niet aan het globale minimum. Een lokale aanpassing heeft dus geen invloed op de afwijking in andere gebieden, waardoor het mogelijk is om de herberekening at run-time uit te voeren.

1.5.3

Chunked Level-of-Detail

Met de komst van krachtige grafische kaarten was het mogelijk om de centrale processor te verlichten. Door de data te verplaatsen naar grafisch geheugen is het mogelijk om met minimale CPU verbruik duizenden triangles te tekenen. Met technieken zoals displaylists en vertex buffers kan men geometrische data verplaatsen naar de grafische kaart waar een processor, gespecialiseerd in vector berekeningen, deze data snel kan uittekenen. Chunked level-of-detail algoritmen verdelen het terrein in verschillende blokken die opgeslagen worden in een quad-tree [dB00, Ulr04]. Elke node van de quad-tree bevat opnieuw 4 nodes met daarin geometrische data met meer detail. Deze chunks worden op voorhand berekend en als statische data opgeslagen op de grafische kaart. Een voorbeeld van deze chunks is te zien in figuur 1.22. Merk op dat de grid in elk van deze chunks irregulier is. De CPU wordt enkel gebruikt om te bepalen met welk detail elke chunk gerenderd wordt. Wanneer twee aangrenzende chunks een ander niveau hebben, ontstaat er een zichtbare rand omdat de vertices niet volledig overeenkomen. Elk niveau heeft ook een andere hoeveelheid vertices zodat er popping optreedt als een chunk vervangen wordt. Popping wordt opgelost door de mesh


20

Figuur 1.22: Quad-tree gevuld met chunks. Opgesplitste chunks hebben telkens meer detail. – Afbeelding uit [Ulr04] te morphen van het ene niveau naar het andere, zodat de verschillen geleidelijk in elkaar overgaan (Sectie 1.4.2). Omdat er gewerkt wordt met een irregulier grid is het moeilijker om te bepalen waar de vertices naar toe moeten morphen dan bij reguliere grids. Men kan de nieuwe hoogtewaarde echter samplen uit het model waarnaar men toe morpht. De nieuwe hoogtewaarde ligt op dezelfde positie in het grondvlak, maar wordt uitgelezen van één niveau hoger of lager (Figuur 1.23). Als het punt waarop men samplet niet overeenkomt met een hoogtewaarde van een aangrenzend niveau, bekomt men de hoogtewaarde door interpolatie van de hoekpunten van de driehoek.

Figuur 1.23: Interpolatie van hoogtewaarden bij reguliere grids. Omdat de posities in het grondvlak onveranderd blijven, is het gemakkelijk om de nieuwe hoogtewaarden te bepalen. – Afbeelding uit [Ulr04] Chunked level-of-detail algoritmes maken optimaal gebruik van het snelle grafische geheugen. Blokken met hoog detail kunnen bijgehouden worden in main memory en, indien nodig, verplaatst worden naar het grafisch geheugen als de camera naar de oppervlakte beweegt. [Ulr04] stelt voor om vertex buffers te gebruiken voor elke chunk. Als een chunk moet morphen wordt er op de CPU in verschillende stappen de interpolatie berekend en de nodige vertex buffers aangepast. Hiervoor moet de CPU echter voor elke tussenstap van de interpolatie een aantal hoogtewaarden herberekenen, wat onefficiënt kan zijn. Een snellere en simpelere methode is voorgesteld in [LH04]. Als een chunk te veel of onvoldoende detail bevat, morphen we eerst naar een hoger of lager niveau vooraleer een andere chunk gerenderd wordt. We kunnen via de vierde vertex coördinaat W de hoogtewaarde aangeven waar we naar toe willen morphen. Hiervoor moeten we enkel een klein deel van de vertex buffer aanpassen, namelijk de W co¨ ordinaat. Dit is mogelijk omdat populaire systemen zoals OpenGL en Direct3D het toelaten om een vertex voor te stellen door een vier-tuppel (X, Y, Z, W ). Er rest dan enkel een lineaire interpolatie uit te voeren tussen Z en W in de vertex shader, net voor men een chunk gaat vervangen door een andere chunk. De interpolatie factor α = [0; 1] kan dan gestuurd worden door het algoritme. Chunked level-of-detail is een zeer geschikte oplossing voor het renderen van grote terreinen. Verschillende chunks kunnen gemakkelijk in en uit het geheugen geplaatst worden naarmate dit


21

nodig is en het renderen gebeurd zeer snel omdat er gebruik wordt gemaakt van statische data die opgeslagen wordt op de GPU. Het grootste probleem van dit algoritme zijn de gaten tussen aangrenzende chunks. Door verschillende irreguliere grids zijn deze niet naadloos en heeft men dus last van gaps. [Ulr04] stelt voor om skirts te gebruiken om de gaten op te vullen, zoals in sectie 1.4, maar dit blijft voor visuele artefacten zorgen. Vooral wanneer de camera dicht bij de grens is tussen twee verschillende chunks, heeft men hier last van omdat de chunks gedefiniëerd zijn en world-space en de camera dus over de grenzen heen beweegt [LH04]. Een andere oplossing zorgt er voor dat de grenzen tussen alle chunks perfect overeen komen met de aangrenzende chunks. Het algoritme dat de irreguliere grids genereert moet dan aangepast worden, maar dit is volgens Ulrich zeer moeilijk. Ten slotte is het ook niet mogelijk om het terrein real-time te vervormen. De efficiëntie van het algoritme is afhankelijk van de statische chunks en deze zijn niet aanpasbaar. Men zou wel een aantal vaste vervormingen op voorhand kunnen berekenen en deze inladen wanneer ze nodig zijn. Dit beperkt de vrijheid van de vervorming en laat enkel voorspelde aanpassingen toe. Zo kan men een chunk opbouwen voor een vastgelegde explosie en op het juiste moment de actieve chunk vervangen door de vervormde chunk.


22

Hoofdstuk 2

Geometry Clipmaps In het vorige hoofdstuk zijn de belangrijkste eigenschappen van een terrein rendering algoritme behandeld. In dit hoofdstuk wordt eerst het idee achter geometry clipmaps [LH04] uitgelegd en daarna wordt het algoritme volledig geanalyseerd.

2.1

Inleiding

De belangrijkste limitaties van moderne grafische kaarten zijn niet het aantal triangles die per seconde getekend kunnen worden, maar de snelheid van de vertex en pixel shaders. Software ontwikkelaars zijn volop bezig met veel van de CPU taken te verplaatsen naar de GPU waardoor de druk op de grafische kaart wordt verhoogd. Shaders zijn korte programma’s die in sequentie uitgevoerd worden op een set van vertices of pixels. Het is dus minder van belang hoeveel triangles er gerenderd worden, maar echter hoeveel tijd er nodig is per triangle. Er moet dus minder aandacht besteedt worden aan het minimaliseren van het aantal triangles in een object, terwijl meer aandacht gaat naar het efficiënt gebruik van shaders. Let op, dit wil niet zeggen dat levelof-detail nutteloos is, enkel dat het interessanter is geworden om minder CPU cycles te gebruiken om level-of-detail toe te passen. Dit idee wordt gebruikt in geometry clipmaps en is de reden waarom dit algoritme eenvoudig van aard is. Het doel is simpel: render veel triangles kort bij de camera, minder triangles voor verafgelegen gebieden en minimaliseer de CPU cycles. Dit is natuurlijk het idee van alle level-of-detail technieken, maar bij geometry clipmaps wordt de CPU niet gebruikt om lokaal detail te verlagen zoals het geval is bij de oudere algoritmen (Sectie 1.5). De CPU is alleen bezig met het vullen van buffers, view frustum culling en met het beheren van actieve clipmaps.

2.2

Overzicht

We willen een grote hoeveelheid terrein data renderen zodat er ver weg weinig detail is en dichtbij net zeer veel detail. Daarom is in het ideale geval de verhouding tussen de grootte van de triangles en de afstand tot de camera constant. Dit zou leiden tot concentrische cirkels waarbij elke cirkel net iets minder detail bevat. Geheugen is echter veel efficiënter in het opslaan van rechthoekige gebieden, dus wordt er gekozen voor concentrische vierkanten. De concentrische vierkanten worden elk met een ander niveau van detail gerenderd, zodat het detail evenredig afneemt met de afstand (Figuur 2.1). In deze sectie bekijken we waar het idee van geometry clipmaps vandaag komt en waarom we deze vorm kiezen. Verder worden de verschillende niveaus van detail binnen de geometry clipmap geanalyseerd. 23

HOOFDSTUK 2. GEOMETRY CLIPMAPS

24

Figuur 2.1: De ideale graad van detail is afhankelijk van de afstand. (a) De ideale structuur is een cirkel met aflopend detail. (b) Een versoepeling laat het toe om de concentrische aard op te slaan in het geheugen.

2.2.1

De Clipmap

De concentrische vierkanten bij geometry clipmaps zijn ge¨ınspireerd door de Clipmap van Tanner [TMJ98]. Deze Clipmap maakt het mogelijk om textures te gebruiken van arbitraire grootte. De Clipmap wordt door de auteurs omschreven als een virtuele mipmap van een arbitrair grote texture met efficiënte caching. Hun algoritme toont aan hoe een texture van 170 Gb gevisualiseerd kan worden met een snelheid van 60 beelden per seconde1 . De Clipmap gebruikt geneste vierkanten rond een focuspunt, waarbij elk opeenvolgend vierkant minder texture detail heeft dan het vorige vierkant. Als het point of interest verplaatst wordt, past het algoritme de nodige buffers aan. In figuur 2.2 is te zien hoe enkel de nodige texture data ingeladen is. Delen van de texture die dicht bij de camera liggen, de grootste vierkanten, worden slechts gedeeltelijk ingeladen omdat er teveel data is. De kleinste vierkantjes worden volledig in het geheugen bijgehouden. Deze textures worden gebruikt voor de punten die ver verwijderd zijn van de point of interest.

Figuur 2.2: Texture clipmap. De data is gedeeltelijk ingelezen rond een point-of-interest. Enkel een kleine set is volledig ingeladen, de rest wordt tijdens de uitvoering ingelezen. – Afbeelding uit [glp00] 1 NVIDIA

heeft een White Paper te beschikking voor de implementatie van Clipmaps met DirectX 10.


2.2.2

25

De Geometry Clipmap

Een geometry clipmap is een geometrische variant van de Clipmap en wordt gevormd door een geneste piramide van vierkante oppervlakken, clipmaps genaamd. Elke clipmap bevat evenveel triangles, maar is wel dubbel zo breed en dubbel zo lang als het vierkant dat net een niveau dichter bij de camera ligt. Renderen gebeurt door alle triangles van een vierkant te renderen op zo’n manier dat in het midden een opening blijft voor het vierkant van groter detail/kleinere oppervlakte. In figuur 2.3 is een piramide te zien die platgedrukt gerenderd wordt. Er is een goede reden waarom de breedte en hoogte van elk vierkant verdubbelt per stap. Wanneer men zou kiezen om de vierkanten lineair te laten groeien, gaan de verafgelegen clipmaps veel te dun gerenderd worden en ontstaan er kleine banden met te veel triangles. Door kwadratisch te groeien blijft de schermgrootte van elke clipmap ongeveer gelijk. De grootte van elke clipmap wordt berekend met behulp van formules 2.1 en 2.2, die respectievelijk het aantal triangles/vertices in de lengte en breedte bepalen. #4 = 2n

(2.1)

#vertices = 2n + 1

(2.2)

Figuur 2.3: Geometry clipmap piramide structuur. (a) Elk vierkant bevat evenveel triangles, maar afhankelijk van de afstand zal een vierkant een grotere XY schaal hebben. (b) De geometry clipmap gerenderd en van boven bekeken. Merk op dat enkel alle triangles van het binnenste vierkant, de finest clipmap, volledige getekend zijn. – Originele afbeelding uit [CH06] Voor eenduidigheid definiëren, we net als in [LH04], enkele termen. Namelijk de finer en coarser clipmap (Figuur 2.4). Een finer clipmap is een clipmap met meer detail en dus een kleinere oppervlakte dan de huidige clipmap. Een coarser clipmap is net het omgekeerde van een finer clipmap, minder detail, meer oppervlakte. Minder detail betekent niet dat er minder triangles zijn, maar dat de triangles groter zijn en er dus lokaal minder geometrische precisie aanwezig is. Soms wordt er ook verwezen naar een next finer clipmap of een next coarser clipmap. Hiermee worden de net aangrenzende finer en coarser clipmaps aangeduid. De finest clipmap en de coarsest clipmap zijn de clipmaps met het meeste en het minste detail. Ook wordt er soms gesproken over triangle size. Hiermee wordt niet de oppervlakte bedoelt van de triangle, maar wel de horizontale/verticale lengte van de gelijkbenige triangles (Figuur 2.4). Geometry clipmaps kan men ook vergelijken met mipmapping van textures [Wil83], maar dan voor hoogtewaarden. Bij mipmapping worden herhaaldelijk verkleinde textures gemaakt van de originele texture. Wanneer een triangle getextured wordt, selecteert men de juiste texture uit de


26

Figuur 2.4: Clipmap render gebied. (a) De finest clipmap (b) De next coarser clipmap. Alle volgende coarser clipmaps zijn van deze vorm. – De lengte en de breedte van (b) zijn het dubbele van (a), maar (b) bevat evenveel triangles. Niet alle triangles van (b) worden gerenderd. verschillende textures, afhankelijk van de grootte van de triangle in screen-space. Hierdoor is er een betere mapping tussen het aantal mogelijke texture coördinaten en pixels op het scherm, waardoor men minder last heeft van aliasing. Voor meer informatie over mipmapping wordt er verwezen naar [Wil83]. Bij geometry clipmaps gebeurt er iets gelijkaardigs. Verschillende versies worden aangemaakt van de hoogtewaarden met telkens een power-of-two verschil in afstand. Naargelang de afstand tot de camera wordt er een andere versie gebruikt, zodat de screen-space triangle size ongeveer constant blijft. Meer over de screen-space triangle size in sectie 2.5.2.


2.3

27

Analyse

In de vorige sectie is uitgelegd hoe een geometry clipmap in elkaar zit. Hier worden de details verder bestudeerd, zoals de overgangen tussen verschillende clipmaps, selectie van actieve clipmaps en view frustum culling.

2.3.1

Clipmap datastructuur en updates

Het aantal clipmaps ligt op voorhand vast, net als het aantal triangles per vierkant en de grootte van een triangle. Deze parameters worden tijdens de initialisatie bepaald op basis van de totale terreingrootte. Er is geen specifieke methode om deze parameters te bepalen. Het is een applicatie afhankelijk probleem en moet handmatig geoptimaliseerd worden. Een applicatie waarbij de camera altijd dicht bij het oppervlak is zal niet veel clipmaps nodig hebben, omdat er nooit ver gekeken kan worden. Maar de clipmaps moeten wel een groter aantal triangles hebben. Wanneer de camera zich meestal hoog boven het terrein bevindt, zijn er per clipmap minder triangles nodig, maar moet er een groter aantal clipmaps zijn. Een clipmap grootte van 128 of 256 triangles is het minimum om popping artefacten te vermijden. Voor elke clipmap wordt een vertex buffer bijgehouden op de GPU, waardoor er minder data verstuurd moet worden tussen CPU en de grafische kaart. De hoogtedata, in de vorm van een regulier grid, wordt omgezet naar vertices in de vorm van (X, Y, Z). De terreindata die in main memory wordt bijgehouden als een hoogtemap (Sectie 1.2.1), wordt omgezet van 1 float per hoogtewaarde, (Z), naar 3 floats per hoogtewaarde, (X, Y, Z). Het centrum van de clipmap blijft altijd recht onder de camera gepositioneerd (Sectie 2.2). Als de camera beweegt moeten de buffers aangepast worden, zodat de verouderde data vervangen wordt door de correct hoogtedata. De verouderde data heeft bijna altijd een L-vormige structuur aan de rand van de buffer (Figuur 2.5). Enkel als de camera in de horizontale of verticale richting beweegt moet men slechts één zijde vernieuwen. De breedte van de L-vorm moet altijd een veelvoud van 2 zijn om de vertices gelijk te laten vallen met de coarser clipmaps.

Figuur 2.5: Verouderde buffer door camera beweging. De camera beweging zorgt er voor dat de randen van de clipmap verouderde data bevat (Grijs gebied). (a) Een diagonale beweging V verandert zowel de bovenrand als de rechterrand. (b) Een verticale beweging V verandert enkel de bovenrand. Bij geometry clipmaps wordt er gebruik gemaakt van wrap-around adressering om updates (Figuur 2.6) minimaal te houden. Wanneer een stuk van een clipmap oude data bevat, wordt de nieuwe data op de plaats van de oude gezet. Hierdoor zijn de hoogtewaarden in de vertex buffer meestal niet gealinieerd met de clipmap en is er een bijkomende kost om de positie van een vertex te bepalen. Wrap-around adressering heeft echter als voordeel dat slechts een klein deel van de data aangepast wordt en niet de hele vertex buffer. De positie bepalen in de buffer kan met de


28

modulo operatie2 . Het aanpassen van een clipmap heeft ook invloed op de next-coarser clipmap. Door de verplaatsing verandert de opening van de next-coarser clipmap en moet er altijd een extra triangle strip herberekend worden. Meer over triangle strips in sectie 2.3.3.

Figuur 2.6: Wrap-around adressering van een geometry clipmap. (a) Een hoogtemap in een vertex buffer met wrap-around adressering (b) Beweging van de camera zorgt ervoor dat een deel van de buffer verkeerde data bevat (c) Hoogtemap na de update – Afbeelding uit [AH05] Een geometry clipmap implementatie heeft op het vlak van datastructuur 2 mogelijkheden. De eerste manier buffert de triangles in gaten waar de finer clipmaps gerenderd worden. Hierdoor zijn alle buffers even groot en moeten er geen updates aan de binnenrand gebeuren. Er wordt meer geheugen gebruikt, maar het algoritme is eenvoudiger en sneller. Het voordeel van deze methode is dat de onzichtbare triangles altijd gebruikt gaan worden bij een camera beweging in het grondvlak. Geen enkele triangle wordt nodeloos gebufferd. De tweede mogelijkheid is om de triangles in de datastructuur zo te structureren dat er geen ruimte wordt verloren aan onzichtbare triangles. Op deze manier is er voor elke niet-finest clipmap 25% minder vertex buffer data nodig, maar stijgt het aantal updates met 50%. Ook vertraagt het aanpassen en uitlezen van de vertex buffer door ingewikkelde data-opslag. Dit is de klassieke afweging tussen geheugenverbruik/snelheid en is afhankelijk per applicatie. In de meeste gevallen is de eerste methode aangeraden omdat er dikwijls buffers aangepast worden.

2.3.2

Schalering van de datastructuur

Het aantal hoogtewaarden in een geometry clipmap is tot nu toe bewust klein gehouden. Er is altijd vanuit gegaan dat de volledige dataset in main memory past. Laten we eerst kijken naar het geheugengebruik voor een in-core geometry clipmap algoritme en daarna kijken naar een oplossing voor grotere terreinen. Tabel 2.1 toont aan dat voor relatief kleine terreinen een in-core methode haalbaar is op de huidige systemen. Uit deze tabel blijkt verder dat vooral textures veel geheugen innemen en dat de indices/vertex buffers in verhouding weinig plaats verbruiken. Merk op dat één enkele texture gedeeld wordt door alle clipmaps. Deze cijfers komen overeen met de thesis implementatie uit hoofdstuk 4. Merk verder ook op dat de huidige grafische hardware de gebruikte textures en normal maps compresseerd om geheugengebruik te verminderen. Een geometry clipmap met lengte en breedte van 4096 hoogtepunten is voor veel applicaties voldoende, maar uiteindelijk is het de bedoeling om arbitrair grote terreinen te renderen. Zeker wanneer ook andere zaken zoals 3D objecten, geluid, AI, . . . plaats gaan innemen. Een outof-core techniek is daarom noodzakelijk voor een aantal applicaties (Sectie 1.4.3). Bij geometry clipmaps is het mogelijk om tientallen gigabytes aan gegevens op te slaan door een zeer hoge 2 De

trage modulo operatie kan soms sneller door de AND operator: x M od (2n ) = x & (2n − 1)

HOOFDSTUK 2. GEOMETRY CLIPMAPS #4 1024x1024

4/Clip 64x64

#Clip 6

1024x1024

128x128

1024x1024

H I

Main(bytes) 1024x1024x4 64x64x2x4x6

5

H I

1024x1024x4 128x128x2x4x5

256x256

4

H I

1024x1024x4 256x256x2x4x4

4096x4096

64x64

8

H I

4096x4096x4 64x64x2x4x8

4096x4096

128x128

7

H I

4096x4096x4 128x128x2x4x7

4096x4096

256x256

6

H I

4096x4096x4 256x256x2x4x6

29

V N T V N T V N T V N T V N T V N T

GPU(bytes) 64x64x3x4x6 64x64x3x2x6 1024x1024x3x( 43 ) 128x128x3x4x5 128x128x2x3x5 1024x1024x3x( 43 ) 256x256x3x4x4 256x256x2x3x4 1024x1024x3x( 43 ) 64x64x3x4x8 64x64x3x2x8 4096x4096x3x( 43 ) 128x128x3x4x7 128x128x2x3x7 4096x4096x3x( 43 ) 256x256x3x4x6 256x256x2x3x6 4096x4096x3x( 43 )

Totaal 4288kb +4528kb 8.6Mb 4736kb +5536kb 10Mb 4736kb +5536kb 14.5Mb 65792kb +66076kb 128.7Mb 66432kb +67552kb 130.8Mb 68608kb +72448kb 137.8Mb

Tabel 2.1: In-core geheugen gebruik van het geometry clipmap algoritme. De tabel vergelijkt twee geometry clipmap groottes van 1024 en 4096 triangles in de lengte/breedte en met clipmap groottes: 64, 128 en 256. In main memory worden hoogtewaarden (H) en indices (I) van de triangle strips per clipmap bijgehouden. In het geheugen van de grafische kaart de vertex buffers (V), normal map(s) (N) en texture(s) + mipmaps (T). Hierbij worden er telkens 4 bytes gebruikt om integers of floats voor te stellen, behalve de normals, daarvoor worden 2 bytes gebruikt. compressiefactor van (1:100) te gebruiken. Met compressie kan het geometry clipmap algoritme gigantische terreinen visualiseren die volledig bewaard worden in main memory. Hoppe stelt voor om het compressie algoritme te gebruiken van Malvar [Mal00]. Dit lossy algoritme heeft een goede lokaliteit: naburige hoogtewaarden bevinden zich dicht bij elkaar, zodat snel een specifiek stuk van de data teruggevonden kan worden. Door de lokaliteit is het ook mogelijk om de dataset op de harde schijf te bewaren en de nodige stukken in main memory te brengen en vervolgens te decompresseren. Het compressie algoritme berekent offline verschillende versies van de hoogtedata waarbij elke versie overeen komt met een niveau van de geometry clipmap. De image coder van Malvar [Mal00] wordt gebruikt om de hoogteverschillen tussen de verschillende versies te compresseren. Deze hoogteverschillen worden residuals of residuen genoemd. De lossy compressie introduceert telkens een kleine afwijking, maar door de juiste data te compresseren kunnen we er voor zorgen dat de afwijking niet wordt doorgegeven naar volgende niveaus. Hieronder volgt het compressie algoritme dat de residuen berekent, die vervolgens gecompresseerd worden. Dit algoritme wordt ook weergegeven in figuur 2.7. 1. Bereken alle versies van finest naar coarsest niveau door telkens te downsamplen met een factor 2. 2. Compresseer de hoogtepunten van de coarsest versie (zeer weinig punten). Dit zijn eigenlijk residuals tussen de hoogtewaarde en het grondvlak waar de hoogtewaarde nul is. 3.

• Decompresseer tijdelijk het niveau dat net gecompresseerd is. De punten komen niet volledig overeen met de eigenlijke versie omdat de compressie lossy is.


30

• Bereken de residuals tussen de gedecompresseerde versie en de next-finer versie. • Compresseer de residuals en herhaal stap 3 zolang er een next-finer versie is. Door in stap 3 eerst te decompresseren wordt de lossy afwijking niet meegenomen naar het volgende niveau. Dit is ge¨ıllustreerd in figuur 2.7 waar er afwijkingen zijn in hoogtepunten 2, 3, 4 en 5. De fout die in punt 5 sluipt wordt echter niet meegenomen naar punt 3 en de fout in punt 3 heeft op zijn beurt geen invloed op punt 2 en 4.

Figuur 2.7: Compressie algoritme met down-sampling. Links: Verschillende niveaus worden opgebouwd. Rechts: Beginnende bij het laagste niveau worden de residuals bepaald afhankelijk van de vorige gecompresseerde waarden. – De lossy compressie veroorzaakt kleine afwijkingen, maar door de residuals te berekenen vanaf de gecompresseerde hoogte en niet de eigenlijke hoogte, wordt de fout niet doorgegeven naar hogere niveaus. De horizontale stippellijnen geven aan dat sommige opgeslagen waarden niet volledig gelijk zijn aan de eigenlijke waarden.

Floating point precisie Eén van de problemen bij zeer grote geometry clipmaps is de beperkte precisie van floating-point getallen. Omdat er gewerkt wordt met een grote orde van getallen is een 32-bit precisie te beperkt om alle co¨ ordinaten precies weer te geven. De meest gebruikte single precision floating point voorstelling gebruikt 23 bits om het getal voor te stellen, 1 bit voor het teken en 8 bits voor de exponent. Hiermee kan men een groter bereik van getallen voorstellen, maar gaat de fijne precisie verloren. Een eerste oplossing is de overschakeling van single precision float (4 bytes) naar double


31

precision float (8 bytes), maar dit verdubbelt het geheugengebruik en vertraagt het algoritme. Een betere methode wordt voorgesteld in [CGG+ 03], een planeet rendering algoritme, en gaat als volgt: de vertex co¨ ordinaten van de clipmaps worden voorgesteld in een nieuw coördinaten stelsel waar een schalering wordt toegepast. Zo kan men bijvoorbeeld een punt op positie (100,100,100) voorstellen met (2,2,2) terwijl het co¨ ordinaten stelsel 50 keer vergroot wordt. Op de GPU wordt het single-float getal dan omgezet naar double precision door een transformatiematrix met een double precision. Deze methode gebruikt evenveel geheugen als de single precision implementatie, maar is iets trager omdat de grafische kaart een omzetting uitvoert van single naar double precision. Single precision floating point getallen zijn enkel in extreem grote datasets onvoldoende, waardoor weinig systemen hier rekening mee moeten houden.

2.3.3

Rendering

Bij het renderen van de geometry clipmaps wordt er geen enkele vorm van triangle merging uitgevoerd, zoals bij andere algoritmen wel het geval is [HM93, DWS+ 97, Hop96]. Het gebruik van een regulier grid maakt het algoritme dus snel en simpel, maar zorgt er voor dat altijd het maximum aantal triangles getekend wordt. Indien een terrein overal even hoog zou zijn, dan zouden er evenveel triangles getekend worden als bij een sterk variërend landschap. Zoals al vermeld in de inleiding is het echter niet het aantal triangles dat de snelheid bepaalt, maar de kost per triangle. Om de grote hoeveelheid van triangles zo snel mogelijk te renderen en bustraffic tussen CPU en grafische kaart te verlagen, worden de triangles per clipmap met één triangle strip getekend. Een triangle strip is een speciale manier om een reeks van triangles te renderen. In plaats van een triangle te definiëren met 3 vertices wordt een triangle gerenderd op basis van voorgaande vertices. Bij het renderen van een quad (2 triangles) heeft men met de klassieke methode 6 vertices nodig, 3 vertices per triangle (Figuur 2.8). Deze 2 triangles hebben echter 2 vertices gemeen waardoor het mogelijk is om de quad te renderen met 4 vertices.

Figuur 2.8: Triangle strips. Een quad wordt klassiek gerenderd door de 2 triangles individueel te tekenen. Een triangle strip hergebruikt de laatste 2 triangles in combinatie met 1 nieuwe om zo een volgende triangle te renderen. Een triangle strip wordt berekend en opgeslagen in main memory. Per clipmap wordt een array gealloceerd die hergebruikt wordt, zodat er geen tijd verloren gaat aan trage memory allocation.


32

Om het aantal drawcalls minimaal te houden, worden verschillende rijen van triangles aan elkaar verbonden via degenerate triangles. Een triangle is degenerate als de 3 vertices op een rechte liggen. Dit houdt in dat de oppervlakte van de driehoek gelijk is aan nul en dus niet zichtbaar is. Wanneer een clipmap gerenderd wordt in wireframe modus zijn deze overgangen wel zichtbaar. Door het gebruik van degenerate triangles is er in plaats van N calls per clipmap ( met N gelijk aan de clipmap grootte) maar 1 call nodig. Dit vergemakkelijkt het algoritme omdat er maar 1 indices lijst nodig is. In figuur 2.9 wordt getoond hoe 2 rijen aan elkaar geplakt worden met degenerate triangles aan het begin en einde van elke rij, door de eerste en laatste vertex te herhalen. In het slechtste geval is er voor de finest clipmap een indices lijst van grootte 2 × (N + 1)2 nodig. Omdat te allen tijde een clipmap de finest kan zijn (Active clipmap selection, sectie 2.5.2), moet er voor elke clipmap een lijst van deze grootte gealloceerd worden.

Figuur 2.9: Concatenatie van rijen met degenerate triangles. Er zijn 6 degenerate triangles met de volgende indices: (1,2,3), (10,11,12), (11,12,13), (12,13,14) en (22,23,24) Telkens de camera beweegt en het centrum van de geometry clipmap verplaatst, kan het zijn dat een clipmap aangepast wordt met nieuwe vertices. Men moet dan de triangle strip herberekenen omdat een aantal triangles van de strip verwijzen naar verkeerde triangles. Men moet ook rekening houden met de wrap-around adressering van de vertex buffer3 . De herberekening is snel uitgevoerd omdat er enkel optellingen en vermenigvuldigingen nodig zijn, maar er zijn echter een paar kleine uitzonderingen. In tabel 2.2 zijn een aantal knelpunten ge¨ıllustreerd voor een beweging over de X-as. Als de X-positie van de camera beweegt naar posities zoals X=1024 of X=2048, zijn er zeer veel updates nodig. Dit wordt merkbaar door delays van een paar milliseconden. Camera positie X = 21 = 2 X = 22 = 4 X = 23 = 8 X = 24 = 16 ... X = 210 = 1024

Aantal verouderde clipmaps Finest en 0x next finest = 1 clipmap Finest en 1x next finest = 2 clipmaps Finest en 2x next finest = 3 clipmaps Finest en 3x next finest = 4 clipmaps ... Finest en 9x next finest = 10 clipmaps!

Tabel 2.2: Het aantal clipmaps dat aangepast moet worden is afhankelijk van de camera positie. In extreme gevallen zijn er zeer veel updates nodig.

2.3.4

Texture mapping

Texture mapping van de geometry clipmaps is redelijk eenvoudig door de reguliere gridstructuur van de hoogtemap. Bij een kleine geometry clipmap is één enkele texture voldoende. In de 3 Goede

pseudo-code voor het berekenen van de triangle strip is te vinden in [Bre05].


33

vertex shader kan de X en Y co¨ ordinaat van de vertex gemakkelijk gebruikt worden om een textureco¨ ordinaat binnen het domein [0;1] te genereren. Het is aan te raden om automatische mipmapping van textures uit te schakelen. Wanneer mipmapping aan staat, kan het zijn dat een andere versie van de texture gebruikt wordt binnen dezelfde clipmap. Dit resulteert in een storende, scherpe texture overgang. Door de versie van de texture manueel te selecteren per clipmap, komen de grenzen tussen verschillende mipmaps en clipmaps samen te liggen. Zo gebruikt de finest clipmap de hoogste texture resolutie. De net iets coarsere clipmap gebruikt de mipmap die net kleiner is dan de beste texture resolutie, . . . Deze methode heeft geen probleem van zichtbare mipmap grenzen binnen een clipmap. Met texture blending kan men de overgang tussen twee mipmap versies verbergen. Later in sectie 2.5.1 wordt getoond hoe vertices geblend worden tussen verschillende clipmaps. Dezelfde blending parameter kan gebruikt worden voor texture blending. Om zeer grote geometry clipmaps te texturen kan men gebruikmaken van de Clipmap van Tanner (Sectie 2.2.1). Met deze Clipmap, niet te verwarren met de verschillende clipmaps binnen een geometry clipmap, kan men arbitraire grote terreinen bedekken met een texture. Hiervoor moet de Clipmap point-of-interest gekoppeld worden aan de positie van de camera, zodat de Clipmap synchroon beweegt met de clipmap updates (Sectie 2.3.1).

2.3.5

Normal mapping

Normal mapping, ook gekend als bumpmapping, is een simpele real-time belichtingsmethode die oogt op het verhogen van realisme zonder extra triangles. Statische normal mapping Bij kleinere geometry clipmaps is het mogelijk om klassieke normal mapping toe te passen. In plaats van een normal map up-to-date te houden na camera movement, wordt er gebruik gemaakt van een statische normal map. Deze normal map wordt gegenereerd met formule 2.5 en nadien opgeslagen als een texture in de grafische kaart. In de vertex shader kan men de X en Y coördinaat van de vertex gebruiken als co¨ ordinaat voor texture sampling. Deze wordt dan doorgestuurd naar de fragment shader waar een kleur gesampled4 wordt. Deze kleur is eigenlijk de normaal van de vertex die eerder van het domein [-1 , 1] naar [0, 1] getransformeerd is. In de fragment shader kan men de omgekeerde transformatie uitvoeren om zo de normaal te vinden. Progressieve normal mapping Bij grote geometry clipmaps is het onmogelijk om een statische normal map bij te houden in het geheugen van de grafische kaart. Daarom moet het algoritme de normalen real-time herberekenen wanneer een clipmap verplaatst wordt. Voor elke hoogtewaarde in de verplaatste clipmap wordt een normaal berekend door te kijken naar het lokaal reliëf. De normalen worden opgeslagen op eenzelfde manier als de hoogtewaarden, waardoor normal updates gelijktijdig gebeuren als clipmap updates. Wanneer een clipmap aangepast wordt met nieuwe hoogtewaarden moet dit dus ook gebeuren voor de normalen. De normalen kunnen gevonden worden door de S en T vectoren van de hoogtewaarde H in punt (i, j) te berekenen (Formules 2.3 en 2.4). De normaal is gelijk aan het kruisproduct van S en T. Hiervoor definiëren we, net als in [Len02], de S en T vectoren als het verschil in hoogte rond het punt (i, j) in de X en Y richting. S(i, j) = h1, 0, H(i + 1, j) − H(i − 1, j)i 4 In

de Cg shading language is dit bijvoorbeeld mogelijk met tex2D(texture, float2(x,y)).

(2.3)


T (i, j) = h0, 1, H(i, j + 1) − H(i, j − 1)i

34

(2.4)

De vectoren S(i, j) en T (i, j) uit formule 2.3 en 2.4 kunnen dan gebruikt worden om een normaal N te construeren in punt (i, j). N (i, j) =

S(i, j) × T (i, j) h−Sz , −Tz , 1i =p ||S(i, j) × T (i, j)| | Sz2 + Tz2 + 1

(2.5)

Uit deze formules blijkt dat er 4 hoogtewaarden nodig zijn en een worteltrekking om te normaliseren. Het is vooral de normalisatie van N die de normal map update trager maakt dan de clipmap update. Eenmaal dat de normaal gekend is kan men een belichtingsmodel gebruiken, zoals dat van Phong [Pho75].


2.4

35

Evaluatie

In sectie 1.3 zijn er 4 criteria besproken die oordelen over de kwaliteit van een terrein redering algoritme: visuele correctheid, processortijd, geheugengebruik en real-time vervormbaarheid. Hier wordt het geometry clipmap algoritme geëvalueerd door te kijken naar deze eigenschappen.

2.4.1

Visuele correctheid

De visuele correctheid van geometry clipmaps wordt geanalyseerd met de schermafwijking methode. Omdat clipmaps kwadratisch groeien naargelang de afstand tot de camera blijft de schermafwijking ongeveer constant voor alle triangles van de geometry clipmap. Volgens Losasso en Hoppe is de schermafwijking per triangle minder dan een pixel zolang elke triangle ongeveer 3 pixels inneemt op het scherm [LH04]. Dit is een zeer kleine afwijking die voor de meeste applicaties meer dan voldoende is. Zonder verlies van veel visueel detail is het mogelijk om soepeler om te springen met de triangle grootte. De zeer kleine schermafwijking bij geometry clipmaps is te vergelijken met de resultaten van andere recente technieken zoals die van [SW06]. Dat de pixelafwijking kleiner is dan 1, geldt echter alleen voor triangles die dicht bij de camera liggen en moet met een korrel zout genomen worden. De afwijking van triangles in ver af gelegen clipmaps kan meer dan 10 pixels bedragen volgens Losasso en Hoppe [LH04], maar dit is niet zichtbaar omdat de fout geleidelijk aan kleiner en kleiner wordt, naarmate de afstand tot de triangles verkleind. In sectie 2.5.1 wordt uitgelegd hoe deze fout progressief verminderd.

2.4.2

Processortijd

Het geometry clipmap algoritme is bedacht rond de periode dat shaders een intrede deden bij het grote publiek. Het algoritme steunt daarom nog voor een groot deel op de CPU, maar maakt gebruik van (nieuwe) verbeteringen aan de grafische kaarten zoals shaders en vertex buffers. In sectie 2.3.1 wordt uitgelegd welke stappen uitgevoerd worden door de CPU, zoals de runtime decompressie en het opvullen van de vertex buffers. In vergelijking met oudere technieken zoals progressive meshes of ROAM (Sectie 1.5), gebeuren er geen complexe operaties op de CPU en wordt deze minder belast. Ook zorgt de uniforme gridstructuur voor een stabiele framerate. Het vertex shader algoritme, dat gebruikt wordt om gaten te bedekken en popping te vermijden, kan ge¨ımplenteerd worden met een 10 tot 15-tal GPU instructies [LH04, Bre05]. Arsirvatham en Hoppe beschrijven in [AH05] een verbetering van het algoritme waar intensief gebruik gemaakt wordt van vertex texture buffers op de grafische kaart. Met deze methode is het mogelijk om alle taken, behalve view frustum culling en decompressie, op de GPU uit te voeren. De CPU belasting is dan minimaal. Meer hierover in hoofdstuk 3.

2.4.3

Geheugengebruik

Geheugengebruik van geometry clipmaps kan opgedeeld worden in 2 groepen. Ten eerste is er de compressie van de hoogtewaarden die de dataset met een factor 100 verminderd. Hierdoor kan zeer veel terreindata in main memory opgeslagen worden. De hoge compressiefactor is ten opzichte van andere technieken gigantisch en is een van de redenen waarom geometry clipmaps zo interessant zijn. Ten tweede is er het geheugengebruik van de triangles die op elk moment gerenderd worden. Naarmate de camera beweegt verandert de clipmap en worden er andere triangles getekend. Hiervan kan gezegd worden dat het aantal zichtbare triangles hoog is in vergelijking met andere algoritmen. Dit komt omdat geometry clipmaps gebruik maken van een regulier grid en dus geen enkele vorm van triangle merging uitvoeren, waardoor zelfs de meest vlakke terreinen veel geheugen innemen. Dit is waarschijnlijk het grootste van het algoritme.


2.4.4

36

Real-time vervormbaarheid

Real-time vervorming van terrein is zeer moeilijk bij geometry clipmaps [Bre05]. Bij elke verandering van hoogtewaarden moet de gecompresseerde data in het geheugen aangepast worden. De compressie zelf is een traag offline proces en het is onwaarschijnlijk dat dit real-time mogelijk is. Behalve een complexe hercompressering, moet het algoritme na een vervorming ook de vertex buffers aanpassen. Real-time vervorming in combinatie met compressie is dus hoogst onwaarschijnlijk. Voor geometry clipmaps met een kleinere oppervlakte, waarbij de dataset ongecompresseerd in main memory past is vervorming wel mogelijk. De hoogtewaarden worden in main memory aangepast volgens een vervormingfunctie en tegelijkertijd worden de nodige vertex buffers aangepast. De functie kan alle soorten vormen aannemen: een simpele Gaussiaanse functie kan gebruikt worden om een kraterinslag te simuleren of kan men gemakkelijk een rivier toevoegen door een filter over de mesh te bewegen. Afhankelijk van het gebied dat aangepast wordt kan er een kleine vertraging optreden. Maar een modern systeem kan vlot een volledige clipmap herberekenen in een paar milliseconden, zodat filters van realistische grootte geen vertragingen veroorzaken. Deze manier van real-time vervorming is gerealiseerd in de implementatie van de thesis als proof-ofconcept (Hoofdstuk 4). Een voorbeeld van een vervorming is weergegeven in figuur 2.10 waar een berg drie keer verlaagd wordt.

Figuur 2.10: Real-time vervorming van de geometry clipmap. Berg Rainier links wordt 3 keer aangepast door alle hoogtewaarden binnen een rechthoekig gebied telkens te verlagen tot 90% van de hoogte. Het landschap rond de berg blijft onveranderd. Elke stap wordt uitgevoerd zonder merkbare vertraging.

2.5

Problemen

Net als vele andere level-of-detail technieken hebben geometry clipmaps last van gaten in de mesh. Bij geometry clipmaps ontstaan er gaten op de grens tussen twee clipmaps door de power-of-two verschil in resolutie. Verder heeft het algoritme ook last van popping artefacten door kleine hoogteverschillen na een clipmap update. Als de camera beweegt moeten de clipmaps aangepast worden (Sectie 2.3.1). Door het verschil in resolutie gaan er aan de rand van de clipmaps triangles verspringen. In deze sectie wordt uitgelegd hoe zowel de gaps als de popping artefacten met één morphing techniek oplost. In het tweede deel van deze sectie wordt getoond hoe de geometry clipmap efficiënt gerenderd kan worden van verschillende hoogtes door de nodige finest clipmaps te verbergen. Verder wordt er uitgelegd hoe view frustum culling gebruikt kan worden om het aantal frames per seconde te verhogen en er worden twee optimalisaties voorgesteld voor het view frustum culling algoritme van Losasso en Hoppe [LH04].


2.5.1

37

Transities tussen verschillende niveaus van detail

Naburige clipmaps verschillen van elkaar met een factor 2. Hierdoor ontstaan er T-junctions die gaten veroorzaken (Sectie 1.4.1). Om dit probleem op te lossen wordt er een overgangsregio toegevoegd waarin het detail geleidelijk aan overgaat (Figuur 2.11). Dit gebeurt door lineaire interpolatie in de vertex shader tussen de eigenlijke hoogte van de clipmap (Z) en de hoogtewaarde van de next coarser clipmap (W). Meestal is een vertex van de volgende vorm : (X,Y,Z,1). Om de extra hoogtewaarde ter beschikking te stellen aan de vertex shader, wordt de W coördinaat gebruikt om een tweede hoogtewaarde door te geven : (X,Y,Z,W). Deze manier van parameter passing werd al eerder gebruikt in het terrein rendering algoritme van Dalgaard [Lar03], waar de transitie gebeurt tussen verschillende blokken in een quad-tree.

Figuur 2.11: Transities tussen verschillende clipmaps. Links wordt het terrein gerenderd met texturing. Rechts zijn de overgangsregio’s zichtbaar in blauw. Wanneer de overgangsregio te klein is, kan de interpolatie zichtbaar worden en gaan vertices poppen (Sectie 1.4.2). Het is daarom belangrijk om de transitie-regio groot genoeg te kiezen en een voldoende aantal triangles per clipmap te gebruiken (> 128). Een te grootte transitie heeft dan weer als gevolg dat er te veel detail verloren gaat. Een transitie met een breedte van 10% van de totale clipmap breedte, is volgens Losasso en Hoppe [LH04] een juiste balans tussen detail en vlotte transitie. Het is echter niet zo’n goed idee om dit getal los over te nemen. De transitie grootte is afhankelijk van clipmap size en vooral ook van het soort terrein. In een ruw landschap moet men een grotere overgang kiezen om popping te vermijden. In [Lar03] wordt een transitie grootte gekozen per blok, afhankelijk van de afwijking tussen 2 blokken.

Berekening van de transitie Het vertex blending algoritme bestaat uit twee stappen: 1. Bepalen van α voor de lineaire interpolatie. α = max(αx , αy ) αx = min max

αy = min max

x − xlv −

xmax −xmin 2

(2.6)

−R−1

R y − yvl −

ymax −ymin 2

R

−R−1

!

!

,0 ,1 !

(2.7)

,0 ,1

! (2.8)


38

2. Interpolatie uitvoeren tussen de Z en W coördinaat5 . z 0 = (1 − α)z + αw

(2.9)

Waarbij α de lineaire interpolatie controleert; R de grootte van de transitie-regio is; (xmax , xmin , ymax , ymin ) de grenzen van de clipmap aangeven; (x, y, z, w) de vertex in de shader is en xlv , yvl het centrum van de clipmap. De bovenstaande formules (2.6–2.9) worden uitgevoerd in de vertex shader. De transitie wordt gestuurd door α, die een waarde aanneemt tussen 0 en 1 binnen een regio aan de buitenrand van de clipmap (Figuur 2.11). Het is de bedoeling α te bepalen zonder gebruik te maken van flow-control6 . Flow-control is enkel beschikbaar in de nieuwste grafische kaarten en vertaagt meestal de shader. De formules 2.7 en 2.8 kunnen beide in drie delen opgedeeld worden (Figuur 2.12a): 1. A = x − xlv — De afstand tussen de vertex x en het centrum van de clipmap xlv . min 2. B = xmax −x −R−1 — De afstand van het midden van de clipmap tot de eerste coördinaat 2 die ge¨ınterpoleerd moet worden. Eerst wordt de helft van de clipmap lengte berekend en vervolgens de breedte van de transitie-regio R er van afgetrokken.

3. min max A−B R , 0 , 1 — Wanneer de twee afstanden berekend zijn, wordt het verschil genormaliseerd door te delen door de lengte van de transitie regio R. Indien de vertex binnen de regio valt heeft α een waarde tussen [0, 1], anders is α = 0. Ten slotte wordt het maximum genomen van αx en αy omdat de grootste waarde de richting van de transitie aangeeft (Figuur 2.12b). Anders gezegd: indien αx > αy , dan bevindt de vertex zich dichter bij een rand op de X-as.

Figuur 2.12: Berekening van α voor de vertex interpolatie. (a) De onderdelen van formule 2.7. Analoog voor formule 2.8. Punten P1 en P2 zijn 2 vertices. Punt P1 heeft αx = 0, punt P2 heeft αx = ±0.5. (b) Het maximum van αx en αy duidt aan in welke richting de rand het dichtst benaderd wordt. 5 In

de Cg Standard Library[FK03] is dit mogelijk met lerp(a, b, α). in shaders maakt het mogelijk om if-tests, loops, ... te gebruiken.

6 Flow-control


39

Discussie Transities door morphing is een elegante manier om de overgangen onzichtbaar te maken, maar in [LH04] wordt er in alle talen gezwegen over de slechte resultaten bij een sterk variërend terrein. Wanneer het terrein lokaal sterk stijgt of daalt, denk aan een afgrond of steile helling, wordt de transitie zeer merkbaar. Dit is niet op te lossen door de transitie regio te vergroten of te verkleinen. Bij sterke hellingen is er ook het probleem dat er te weinig texturedata aanwezig is. Stel: twee hoogtepunten liggen naast elkaar, maar hebben een zeer groot verschil in hoogte. Er worden dan veel pixels gerenderd, maar er is weinig texturedata aanwezig om de pixels realistisch in te vullen. Hierdoor krijgt men uitgesmeerde en wazige texturing. Het gebrek om steile hellingen te renderen doet echter niet af aan de kwaliteit van de transitie, die zeer efficiënt en simpel te implementeren is en in de meeste gevallen perfect werkt.

2.5.2

Selectie van actieve clipmaps

In 2.3.3 is het begrip screen-space triangle size kort aangehaald. Screen-space triangle size is de grootte van een triangle die gerenderd wordt in schermcoördinaten. Een kleine driehoek die dichtbij is en een grote driehoek veraf kunnen met evenveel pixels gerenderd worden. Denk aan een portretfoto met op de achtergrond een bergketen. De persoon neemt veel meer plaats in dan de berg, hoewel de berg in wezen veel groter is. Screen-space triangle size is belangrijk voor de selectie van actieve clipmaps tijdens rendering. Elke clipmap is gecentreerd rond de kijkpositie waardoor alle triangles van een clipmap ongeveer dezelfde afstand tot de camera hebben. Ook zijn alle triangles van een clipmap even groot na projectie in het XY vlak (Figuur 2.4). Dit heeft als resultaat dat alle triangles binnen een clipmap ruw geschat de zelfde grootte hebben na projectie op het scherm. Door de power-of-two verhoudingen van de clipmaps zal de next coarser clipmap ongeveer de zelfde screen-space triangle size hebben als de finer clipmap. De conclusie is hier dat de grootte van alle triangles die gerenderd worden evenveel pixels gebruiken, onafhankelijk van de afstand tot de camera. Let op: dit is een ruwe schatting.

Afleiding van de screen-space triangle size Er volgt nu een afleiding van een formule om de screen-space triangle size te bepalen. Eerst wordt ervan uitgegaan dat de kijkrichting parallel is met het XY vlak. Daarna wordt er veralgemeend naar andere kijkrichtingen. De verhouding van screen-space triangle size op world-space triangle size is gelijk aan de verhouding van de afstand van de camera tot het projectievlak en de afstand van de camera tot de wereld positie (Figuur 2.13). Dit kunnen we schrijven als: s0 d0 = S D

(2.10)

d0 S D

(2.11)

of herschreven

s0 =

Wanneer de afstand tot het projectievlak (d0 ), afstand tot de triangle (D) en grootte van triangle in world-space (S) gekend zijn, dan is screen-space triangle size (s0 ) ook gekend.


40

Figuur 2.13: Verhouding van afstanden binnen een driehoek. • d’ – De afstand tot het projectievlak is afhankelijk van de breedte van het beeld (W ) en de kijkhoek grootte (φ), beter gekend als Field-of-View. Met behulp van de tangens is het simpel om d0 te bepalen aan de hand van formule 2.13 (Figuur 2.14). tan

W φ = 20 2 d

(2.12)

W 1 2 tan φ2

(2.13)

of herschreven d0 =

Figuur 2.14: Bepalen van de afstand tot het projectievlak. • D – De afstand tot de driehoek in wereldcoördinaten is te vinden via Euclidische afstand. Maar omdat dit per triangle niet echt nuttig is tijdens runtime, is het nodig om de gemiddelde afstand van elke triangle in de clipmap tot de camera te schatten. Herinner dat een clipmap altijd gecentreerd is rond de camera. Om een gemiddelde afstand te bepalen kan men alle punten in de clipmap doorlopen en telkens de afstand tot het nulpunt nemen. Bij een clipmap van breedte 1 zal het gemiddelde ongeveer uitkomen op 0.44. Deze afstand kan geschaald worden naar elke mogelijk clipmap door te vermenigvuldigen met het aantal triangles in een clipmap (N) en de grootte van een triangle (S). De bepaling van 0.44 gebeurt door een willekeurig aantal keer (X 2 ) te samplen (Figuur 2.15):


Dall =

41

s

X X X X i=−X j=−X

Dinner =

X

X

2 X

2 X

i= −X 2

j= −X 2

D=

i 2X

s

2

i X

j 2X

2

2

+

2 +

j X

(2.14)

Dinner Dall − 2X + 1 2X + 1

(2.15)

(2.16)

Een simpele uitwerking van de bovenstaande formules geeft aan dat D = 0.446381 met X = 8192. Dit is iets nauwkeuriger dan de gerapporteerde waarde in [LH04], waar D = 0.4 gebruikt wordt. Er wordt in formule 2.14 en 2.15 genormaliseerd binnen de Euclidische afstand om met een clipmap grootte van 1 te werken. De normalisatie brengt de punten tot het domein [−0.5; 0.5]. In formule 2.16 wordt er telkens gedeeld door het aantal samples. Toegepast op een clipmap met N triangles in zowel hoogte en breedte en met triangle size gl , geeft dit een gemiddelde afstand van : 0.44N gl

(2.17)

Figuur 2.15: Sample gebied voor triangle distance • S – De triangle grootte in world-space (S) is simpelweg de spacing tussen de triangles in de clipmap (gl ). Screen-space triangle size De combinatie van de zonet afgeleide formules leidt tot de formule 2.18 om de screen-space triangle size te berekenen in het grondvlak. Merk echter op dat wanneer de field-of-view niet gelijk is aan 90◦ , de gevonden waarde van 0.44 kan variëren naargelang de richting van de kijkas in het XY vlak. Dit is geen probleem omdat de formule enkel als schatting gebruikt wordt. s=

W W gl = (1.14) (0.44)N gl 2 tan φ2 N tan φ2

(2.18)

Er rest nog de veralgemening weg te werken die in het begin is gemaakt, namelijk dat de kijkrichting van de camera parallel loopt met het XY vlak. Wanneer de camera naar het terrein kijkt vanuit een punt boven het XY-vlak vergroot de screen-space depth D van de triangles (Figuur 2.16) en dus verkleint s. Hieruit kunnen we opmaken dat de afgeleide gemiddelde screen-space triangle size in formule 2.18 een bovengrens is voor elke clipmap.


42

Figuur 2.16: Screen-space triangle size is afhankelijk van de afstand. Een hogere camerastand verkleint de triangles in screen-space Waarom is de screen-space triangle size nu belangrijk? Eenmaal dat die gekend is kan er automatisch een actieve clipmap geselecteerd worden zonder de complexe formule 2.18 voor elk frame te berekenen. Als de screen-space triangle size kleiner dan 1 is, wordt er te veel detail gerenderd. Het is daarom nuttig om de finest clipmap te verbergen en de next-coarser clipmap te renderen zonder gap. Hierdoor blijft de framerate hoog als er meer terrein zichtbaar wordt. Om een clipmap te renderen zonder gap moet enkel de triangle strip opnieuw opgebouwd worden (Indien de gaps niet gebufferd worden, is er meer werk nodig (Sectie 2.3.1)). Het is gemakkelijk om de triangle size te schatten bij een arbitraire hoogte. Door (0.44)N gl in formule 2.18 te vervangen door formule 2.19, kunnen we de hoogte in rekeningen brengen. p

(0.44N gl )2 + h2

(2.19)

Het doel is uiteindelijk om de triangle size van alle zichtbare clipmaps ongeveer gelijk te houden. Omdat de screen-space triangle size reeds gekend is, is het gemakkelijk om een snellere vergelijking uit te voeren zonder een vierkantswortels en tangens berekening. Clipmaps worden onzichtbaar als de hoogte van de camera groter is dan de gemiddelde afstand tot de triangles vanuit het grondvlak, h ≥ 0.44N gl . Dit wil zeggen dat een clipmap verborgen wordt als de triangles kleiner zijn dan √1 = ±70% van de originele triangle size (Vervang h in formule 2.19), wat een redelijke aanname 2 is. Als we kiezen voor een screen-space triangle size van 1, wordt een clipmap onzichtbaar als de screen-space triangle size kleiner is dan 0.7.

Discussie Automatisch activeren/deactiveren van clipmap levels is een simpele en snelle manier om de framerate hoog te houden. Naarmate de camera stijgt, ziet men meer van het terrein waardoor de framerate zou dalen. Maar omdat het aantal triangles dat gerenderd wordt niet stijgt naarmate er meer terrein zichtbaar is, blijft de framerate stabiel. Wel moet er rekening gehouden worden met 2 mogelijke problemen. Ten eerste kan het algoritme in oscillatie gaan wanneer de hoogte variëert daar waar de clipmap onzichtbaar wordt. Hierdoor wordt de triangle strip herhaaldelijk herberekend en kan de framerate dalen. Door de grens waarop een clipmap terug zichtbaar wordt een klein beetje te verlagen is dit probleem opgelost. Ten tweede ontstaan er problemen wanneer de hoogtewaarden van het terrein ongeveer gelijk zijn als de hoogtegrens waarop een clipmap verborgen wordt. De afstand tussen camera en hoogtewaarde op een berg is veel kleiner dan van een dal. Het zou dus kunnen dat enkele clipmaps verborgen worden terwijl de camera zich net boven het terrein bevindt. Dit kan opgelost worden door een matrix bij te houden waarin gemiddelde hoogtewaarden staan van verschillende regio’s en per regio deze waarde aan de grens toe te voegen of simpelweg de waarde van het hoogste punt gebruiken als nulpunt. De mogelijkheid om clipmaps uit te schakelen en een coarser clipmap als ‘finest’ te beschouwen


43

heeft een extra voordeel. Wanneer de camera beweegt met een hoge snelheid kan het zijn dat de CPU de vertex buffers niet tijdig aangepast heeft. In dit geval kan men de finest clipmap verbergen en het aantal nodige updates verminderen, waardoor het algoritme snel blijft. De camera beweegt te snel waardoor de fijnste details verloren gaan aan het trage menselijk visueel systeem. Denk hierbij aan de vernauwing van het zicht bij hoge snelheden tijdens het autorijden. De framerate van het algoritme is ook direct afhankelijk van de resolutie van de camera. Bij een klein schermoppervlak verkleint de screen-space triangle size waardoor meerdere levels gedeactiveerd kunnen worden. Dit is een zeer interessante eigenschap die aangeeft dat geometry clipmaps bruikbaar zijn op verschillende systemen met uiteenlopende capaciteiten. Als de framerate te laag is, hoeft men enkel de schermresolutie te verlagen en enkele clipmap verbergen.

2.5.3

View Frustum Culling

Door de concentrische ligging van de clipmaps zal er dikwijls meer dan de helft van de triangles onnodig getekend worden. Enkel indien de camera recht naar beneden gericht, is moeten sommige clipmaps volledig getekend worden. Om het aantal triangles te verminderen is het nuttig om gebruik te maken van View Frustum Culling [Cla76]. Het doel bij VFC is de triangles die niet in de camera frustum liggen ook niet door de grafische pipeline te sturen, omdat ze toch niet zichtbaar zijn. Dit is een klassieke techniek om het aantal frames per seconde te verhogen in 3D applicaties. In de volgende stappen wordt uitgelegd hoe view frustum culling werkt bij geometry clipmaps :

Algoritme 1. Elke clipmap wordt in 4 regio’s opgedeeld die samen de totale oppervlakte bedekken. Dit kan gemakkelijk door te kijken naar het minimum en maximum van de huidige en finer clipmap regio’s (Figuur 2.17). De hoogte van alle bounding boxes wordt bepaald door het minimum en maximum van alle hoogtewaarden in de geometry clipmap. Deze punten vormen 4 AxisAligned Bounding Boxes. Een axis-aligned bounding box, of kortweg AABB, is een balk waarbij elke zijde evenwijdig is met het XY, XZ of YZ vlak.

Figuur 2.17: Clipmap opdeling in 4 axis-aligned bounding boxes. 2. De AABB’s worden onderverdeeld in drie categoriën : Outside, Intersecting, Inside [AM00] (Figuur 2.18). Dit gebeurt door de bounding boxes te vergelijken met de 6 vlakken7 die samen de view frustum bepalen [GH01, Mor00]. Door een slimme selectie van een diagonaal in de AABB moeten er slechts 2 punten vergeleken worden met de view frustum in plaats van 7 Een view frustum bestaat uit 6 vlakken: top, bottom, left, right, near en far planes, voorgesteld met een normaal en een punt in het vlak.


44

de 8 hoeken van de bounding box [SJ02] (zie 2.5.3). Afhankelijk van het resultaat worden de regio’s weggelaten, getekend of verder verfijnd (zie volgende stap).

Figuur 2.18: Mogelijke posities van een axis-aligned bounding box ten opzichte van een view frustum. 3. Wanneer het resultaat van de AABB–view frustum vergelijking (Stap 2) aangeeft dat de bounding box snijdt met de view frustum, is het nuttig om een stuk van de box te knippen. De bounding box wordt dan verkleind zodat enkel het deel dat wel binnen de view frustum ligt, getekend wordt (Figuur 2.19). Dit is vooral belangrijk bij regio’s 1 en 4 in figuur 2.17. Wanneer slechts een tipje zichtbaar is, zou er in verhouding enorm veel triangles verwerkt worden. Hoe dit precies gebeurt wordt hieronder beschreven.

Figuur 2.19: Clipping van een Axis-Aligned Bounding Box met een View Frustum. (a) De axis-aligned bounding box vormt een intersectie met de view frustum. (b) De axis-aligned bounding box uit (a) is geclipt naar een kleinere vorm.

Intersecties bepalen en clipping In het hierboven beschreven algoritme wordt er gebruikt gemaakt van één van de vier diagonalen van de axis-aligned bounding box om het aantal testen te minimaliseren [SJ02]. De richting van de diagonaal is afhankelijk van de normaal van het vlak waartegen getest wordt. De diagonaal die het meeste in de richting ligt van de normaal wordt gebruikt om een snijpunt te vinden met het vlak van de view frustum. Door te kijken naar de normaal van het vlak kan men afleiden of het nieuwe snijpunt een verbetering is. Goede pseudo-code voor de clipping vindt men in [Bre05]. Voor de selectie van de diagonaal wordt er verwezen naar [SJ02]. In figuur 2.20 wordt het effect van view frustum culling met clipping getoond.


45

Figuur 2.20: View frustum culling van de clipmaps met clipping van elke regio. Een view frustum met kijkhoek van 600 waarbij de regio’s uit figuur 2.19 geclipt zijn voor maximale snelheid. Er worden een aantal triangles te veel gerenderd, zichtbaar als uitstekende driehoeken aan de buitenrand van de view frustum. Discussie View frustum culling is een belangrijke optimalisatie in 3D graphics. Er is veel informatie te vinden op het web met enkele interessante optimalisaties zoals bounding spheres en hiërarchisch culling. Toch moet er goed opgelet worden bij de implementatie. Bepalen van de 6 view frustum planes, testen of een AABB binnen een view frustum valt, clippen van de AABB en ten slotte het herberekenen van de indices vormen samen een CPU bottleneck. Eenmaal dat de triangle strips aangemaakt zijn, is renderen zeer snel, maar zodra de camera draait of zich verplaatst, zijn de indices verouderd en moeten al de bewerkingen opnieuw gebeuren. De exacte snelheidswinst bepalen van view frustum culling is moeilijk omdat er geen enkele beperking is op de camerabeweging. Wanneer de kijkrichting van de camera horizontaal is met het grondvlak, kan men met formule 2.20 een schatting maken van de snelheidswinst W. De eigenlijke factor zal altijd iets kleiner zijn dan schatting W, omdat er altijd een aantal triangles teveel gerenderd worden (Figuur 2.20) en omdat view frustum culling zelf een kost heeft. Als de camera in een schuine hoek naar beneden of boven kijkt zal het aantal triangles ook dalen. In hoofdstuk 4 worden cijfers gegeven van view frustum culling met clipping in de thesis implementatie.

W =

360o + VFC overhead Field Of View

(2.20)

View frustum culling optimalisatie 1 Het is interessant om een view frustum te gebruiken dat groter is dan de eigenlijke view frustum. Hierdoor zijn er aan de randen iets meer triangles aanwezig dan eigenlijk nodig is, maar kan de indices lijst langer gebruikt worden. Het idee gaat als volgt: in plaats van de normale view frustum te bepalen, wordt een grotere view frustum gekozen (Figuur 2.21). Deze grotere frustum wordt gebruikt om te controleren op intersecties met axis-aligned bounding boxes en wordt ook gebruikt voor het clippen. De hoek α in figuur 2.21 geeft aan hoeveel rotatie er toegelaten is zonder dat er een herberekening nodig is. Afhankelijk van de applicatie kan men α groter of kleiner kiezen. Zo kan men voor een grote hoek kiezen in een first-person shooter game en voor een kleine hoek in een flight simulator. Op het moment van schrijven is er geen enkele andere implementatie gekend van


46

deze methode. Wanneer de camera draait over de kijkas, moet de indices lijst altijd herberekend worden.

Figuur 2.21: Uitbreiding van de view frustum. De normale view frustum met field-of-view β – Uitgebreide view frustum met kijkhoek β + 2 ∗ α. Ook de verticale kijkrichting moet groter gemaakt worden. De voorgestelde techniek is redelijk simpel te implementeren. De 6 view frustum planes worden geëxtraheerd uit het matrixproduct van de modelview- en projectie-matrix [GH01, Mor00]. Om te vergelijken met de grotere view frustum wordt voor de grotere frustum een tweede projectiematrix opgebouwd8 . Altijd als de camera verplaatst wordt, moeten zowel de planes van de normale als de grotere frustum herberekend worden. Men kan na gaan of één van de normale frustum vlakken verder gedraaid is dan één van de vlakken van de grotere frustum. Hiervoor hoeft men enkel één vergelijking per vlak uitvoeren tussen Vreal en Vlarge , waarbij het inproduct het vlak aanduidt dat het dichtst bij de kijkrichting E ligt (Figuur 2.22). Deze vergelijking is mogelijk omdat alle 12 vlakken snijden in de camerapositie. In figuur 2.22 is dit ge¨ıllustreerd voor het linkervlak van de frustum waarbij de normalen per conventie naar binnen wijzen.

Figuur 2.22: Vergelijking tussen 2 view frustums. (a) De twee normalen van het vlak waarbij de eigenlijke view frustum in de grotere view frustum ligt. (b) De normalen en de kijkrichting zijn genormaliseerd en samengebracht in het punt van de camera positie. De langere vector Vreal van de eigenlijke view frustum geeft aan dat het vlak nog binnen de piramide van de grotere view frustum ligt. 8 De

projectiematrix veranderd enkel als de viewport andere dimensies krijgt.


47

View frustum culling optimalisatie 2 Een grotere view frustum gebruiken kan het aantal herberekeningen van de triangle strip verminderen onder de meeste camera rotaties. Maar de view frustum kan ook het aantal updates verlagen wanneer een clipmap een update nodig heeft. Een gebruiker van de applicatie zal in de meeste gevallen een doel voor ogen hebben wanneer de camera beweegt. Als de gebruiker van de ene locatie naar de andere locatie wilt bewegen, zal hij of zij het interessantste pad zoeken tussen vertrek en aankomst. Het is logisch dat de gebruiker de camera gericht houdt op een punt in de buurt van zijn doel, tenzij de aandacht even wordt afgeleid of het doel veranderd. In plaats van clipmap updates voor de volledige rand uit te voeren, kan men de updates beperken binnen het gebied van de view frustum. Hierdoor zijn er veel minder updates nodig maar moet men bij camerarotatie of beweging niet enkel de triangle strip herberekenen, maar ook updates uitvoeren aan de linker- en rechterzijde van de view frustum. De oudere view frustum planes moeten gecached worden om te bepalen welke delen een update nodig hebben. Deze optimalisatie is echter niet zo triviaal en kan afhankelijk van de applicatie zelfs nadelig zijn voor de snelheid. Dit is bijvoorbeeld zo wanneer de camera enkel draait en er dus continu updates van vertex data nodig zijn, terwijl de data eigenlijk wel correct is.


2.6

48

Synthese voor extra detail

Gebrek aan detail op de finest clipmaps levels kan er voor zorgen dat het terrein er onrealistisch uitziet. De dataset vergroten om meer detail te bekomen is een oplossing, maar is dikwijls te kostelijk. Voor een verdubbeling van detail is er een dataset nodig met dubbel zoveel hoogtepunten. Een betere oplossing bestaat uit het toevoegen van extra detail door middel van synthese. Een Gaussiaanse ruis functie kan het detail verhogen zonder extra dataverbruik en met minder CPU instructies dan decompressie van hoogtewaarden. Toevoeging van ruis gebeurt door een tabel te vullen met een ruisfunctie en daarna de tabel te samplen aan de hand van de X en Y coördinaten van de hoogtewaarden. Met een voldoende grote tabel is herhaling van de ruis niet zichtbaar, omdat de hoogtewaarden van de gedecompresseerde clipmap levels zelf variëren. Het is niet onverwacht dat de functie sneller is dan decompressie. De tabel moet niet groot zijn en er gebeuren geen complexe berekeningen of lookups in grote tabellen. Indien het terrein veel vlakke gebieden bevat is het aangeraden om de tabel te vergroten om herhaling van patronen te vermijden. In figuur 2.23 wordt het effect van synthese getoond, toegepast op een terrein met zeer weinig hoogtewaarden.

Figuur 2.23: Extra clipmap detail door synthese. (a) De geometry clipmap heeft van dichtbij weinig variatie. (b) Extra detail toegevoegd via Gaussiaanse ruis. – Afbeelding uit [AH05]

2.7

Samenvatting

Geometry clipmaps zijn een interessante techniek om terrein te renderen. De uniforme gridstructuur zorgt voor een simpele, efficiënte opslag ten opzichte van oudere algoritmen die de mesh real-time aanpassen. Transities maken het mogelijk om overgangen tussen verschillende niveaus van detail naadloos uit te voeren terwijl uniforme gridstructuur en mogelijkheid tot uitschakeling van clipmaps de framerate constant houden. Klassieke view frustum culling methoden verhogen op een eenvoudige manier de snelheid, terwijl de combinatie van compressie en synthese voor een hoge graad van detail zorgen. De snelheid van het algoritme wordt echter beperkt door de continue herberekening van de triangle strip waardoor de CPU onder constante belasting staat. Geometry clipmaps zijn een goede methode om enorme terreinen te visualiseren, maar zijn echter niet geschikt om in een intensieve applicatie te gebruiken. In het volgend hoofdstuk wordt het algoritme verbeterd door een groot deel van de taken te verplaatsen naar de GPU. Het verbeterde algoritme [AH05] is CPU vriendelijk en daarom beter geschikt als terrein rendering algoritme.

Hoofdstuk 3

Geometry Clipmaps op de GPU Sinds de intrede van nieuwere hardware is het mogelijk om het geometry clipmap algoritme grotendeels te verplaatsen naar de grafische kaart. Dit is mogelijk door de hoogtewaarden op te slaan in verschillende textures die aangepast kunnen worden door de GPU. Het aanpassen van deze buffers was in oudere grafische kaarten enkel mogelijk door de processor. De nieuwe grafische processoren ondersteunen de mogelijkheid om textures te samplen in de vertex en fragment shaders1 . Dit is een veel natuurlijkere manier om hoogtewaarden op te slaan in vergelijking met 1D vertex buffers en triangle strips. Dit hoofdstuk handelt over de GPU implementatie van het geometry clipmap algoritme, ontwikkeld door Asirvatham en Hoppe [AH05]2 .

3.1

Algoritme

In deze sectie wordt uitgelegd hoe het algoritme aangepast wordt om zoveel mogelijk werk naar de GPU te verplaatsen. Eerst wordt er gekeken hoe de herberekening van triangle strips vermeden kan worden. Daarna worden de 4 subregio’s per clipmap uit sectie 2.17 aangepast voor view frustum culling en efficiënter geheugengebruik.

3.1.1

Datastructuur

De grootste bottleneck van het geometry clipmap algoritme is de continue herberekening van de triangle strips (Sectie 2.3.3). Behalve triangle strip herberekening is de CPU ook bezig met decompressie en opvulling van vertex buffers. Omdat de GPU nog geen ingewikkelde operaties toe laat, is het niet mogelijk om de gecompresseerde terrein data te verplaatsen naar de GPU. De CPU belasting kan dus enkel verlaagd worden door de triangle strip herberekening te vermijden. De niet-finest clipmaps vormen concentrische cirkels rond de kijker (Figuur 2.3). Verder is het aantal zichtbare triangles gelijk voor alle niet-finest clipmaps en verschillen twee aangrenzende clipmaps enkel met een factor 2 in lengte en breedte (Sectie 2.2.2). Met deze eigenschappen kan men alle vertices posities rond het clipmap centrum bepalen met dezelfde set van lokale coördinaten (Formule 3.1). Deze formule kan gebruikt worden om alle globale posities binnen een clipmap te berekenen vanaf de positie van de camera. Door de Scale factor per clipmap te verdubbelen vindt men de globale co¨ ordinaten (Xworld , Yworld ) van elke niet-finest clipmap, terwijl de lokale co¨ ordinaten (Xlocal , Ylocal ) onverandert blijven. 1 Vertex 2 GPU

textures zijn beschikbaar vanaf DirectX 9c en Shader Model 3.0. Gems 2 bevat een aantal interessante HLSL shaders voor dit algoritme.

49

HOOFDSTUK 3. GEOMETRY CLIPMAPS OP DE GPU

50

(Xworld , Yworld ) = (Xlocal , Ylocal ) × Scale + (Xcam , Ycam )

(3.1)

Scale = 2n

(3.2)

Waarbij Scale de exponentiële grootte is van het aantal triangles n in de clipmap. In figuur 3.1 wordt dit principe getoond voor de linker bovenste vertex. Stel even dat deze clipmap de eerste niet-finest clipmap is rond de finest clipmap. De vertices van de niet-finest clipmap hebben een bereik van X, Y ∈ [−4, 4] en de vertices van de finest clipmap, de opening in het midden, hebben een lokaal bereik van X, Y ∈ [−2, 2]. Men kan met de lokale coördinaat ordinaat bepalen door een factor Scale = 2 te gebruiken. Stel dat de camera (−4, 4) de globale co¨ gepositioneerd is in het punt (15, 10), dan heeft de linker bovenste vertex een globale coördinaat van : (−4, 4) × 2 + (15, 10) = (15 − 8, 10 + 8) = (7, 18)

Figuur 3.1: Lokale co¨ ordinaten in de vertex buffer. De vertex buffer bevat co¨ ordinaten t.o.v. de camera positie. Een combinatie van de twee geeft de wereldco¨ ordinaten. Via de formule 3.1 is het dus mogelijk om met één enkele vertex buffer, gevuld met lokale co¨ ordinaten , alle globale posities te berekenen. Dit is precies wat er gebeurt in de GPU implementatie. Een vertex shader samplet een aantal vertex textures van gelijke grootte en gebruikt de formule om de globale positie te berekenen voor alle hoogtewaarden in de vertex texture. Al wat de applicatie moet doen, is de juiste Scale factor doorgeven aan de vertex shader samen met de globale positie van de camera. Het gebruik van vertex textures (= 2D vertex buffers) met lokale coördinaten zorgt er voor dat er slechts één indices lijst nodig is en niet één lijst per clipmap. Sterker nog. De indices lijst moet nooit veranderd worden en waardoor men de triangle strip nooit moet herbereken.

3.1.2

Gaps en popping

Om gaten te vermijden tussen verschillende clipmaps wordt er nog altijd gebruik gemaakt van een lineaire interpolatie (Sectie 2.5.1). Ook hier weer wordt het probleem van popping artefacten gelijktijdig opgelost door de transitieregio’s. De W coördinaat die nodig is voor de interpolatie,


51

kan in de GPU implementatie elke frame berekend worden uit de vertex texture van de nextcoarser clipmap. Dit is mogelijk door de vertex texture een aantal keren te samplen (Sectie 2.3.1). Hierdoor wordt de CPU minder belast tijdens het updaten van de vertex texture. Het probleem met deze methode is echter de vertex texture lookup operaties op de GPU. De lookup instructie is in vergelijking met de andere GPU instructies zeer traag, waardoor er veel meer werk verricht moet worden. Naarmate de grafische kaarten verbeteren, zal de vertex texture lookup sneller worden, maar de huidige kaarten zijn nog te traag om dit intensief te gebruiken. Voorlopig is het dus beter om de W co¨ ordinaat nog steeds te berekenen met CPU.

3.1.3

Clipmap grootte

In het originele geometry clipmap algoritme hebben de clipmaps een lengte en breedte van 2n triangles, of (2n + 1) × (2n + 1) vertices. Omdat men in de GPU implementatie gebruik maakt van vertex textures in plaats van vertex buffers om de hoogtewaarden op te slaan, is het interessant om het aantal triangles in de lengte en breedte met 1 triangle per clipmap te verminderen. Het aantal vertices in de vertex texture is dan gelijk aan (2n ) × (2n ), wat een efficiëntere grootte is wanneer men met textures werkt. Hierdoor is het aantal triangles in de lengte en breedte echter oneven, (2n − 1) × (2n − 1), en sluiten de clipmaps niet volledig aan, ge¨ıllustreerd in figuur 3.2. Om dit probleem op te lossen kan men het aantal triangles in de lengte en breedte nogmaals met 1 triangles verminderen, zodat het een even aantal wordt, (2n − 2) × (2n − 2) triangles, of (2n − 1) × (2n − 1) vertices. Omdat de textures van grootte 2n zijn en het aantal vertices van grootte 2n − 1 wordt er 1 rij en 1 kolom niet gebruikt. Wrapping gaat dus als volgt: hXwrapped , Ywrapped i = hX mod (2n − 1), Y mod (2n − 1)i

(3.3)

Figuur 3.2: GPU clipmap grootte. Om efficiënter gebruik te maken van de ideale texture size 2n wordt het aantal vertices met 2 verminderd ten opzichte van het klassieke algoritme. Dit genereert een shift van 1 triangle per clipmap. In plaats van 2n triangles gebruikt men dus 2n −2 triangles, of 2n −1 vertices voor elke clipmap. Dit betekent wel dat er een afwijking is op de power-of-two verhoudingen tussen de clipmaps en de clipmaps niet perfect gecentreerd zijn rond het centrum. Dit probleem wordt in de volgende sectie opgelost door L-vormige banden toe te voegen.

3.1.4

L-shape fixup en view frustum culling

Omdat er wordt afgeweken van de power-of-two verhouding, komen de clipmap regio’s niet volledig overeen. Dit kan opgelost worden door de indices buffer uit de vorige sectie op te splitsen in 2 delen: een concentrische clipmap en een L-vormige fixup. Het probleem hierbij is het gebrek aan view frustum culling. Omdat de indices lijst onveranderd blijft, kan er geen view frustum culling uitgevoerd worden zoals in sectie 2.5.3. Asirvatham en Hoppe stellen daarom voor om de opsplitsing verder door te voeren in kleinere stukjes. Hun opdeling, ge¨ıllustreerd in figuur 3.3,


52

bevat 17 kleine stukjes. Dit is veel meer dan de 4 stukken die eerst gebruikt werden voor view frustum culling in sectie 2.5.3. De verdere opsplitsing is nodig omdat er geen clipping mogelijk is zoals in sectie 2.5.3. De CPU berekent per onderdeel of de axis-aligned bounding box binnen of buiten de view frustum valt. Wanneer een axis-aligned bounding box een intersectie vormt met de view frustum, wordt deze inside beschouwd omdat de statische indices geen clipping toelaten.

Figuur 3.3: Vertex buffers van een GPU clipmap. Een combinatie van verschillende blokken bedekt de volledige clipmap. Afhankelijk van het viewpoint wordt een andere L-vorm gebruikt. – Aangepaste afbeelding uit [AH05] De volledige clipmapregio wordt opgebouwd uit een aantal basisregio’s. Twaalf m × m blokken bedekken het grootste deel van de clipmapregio en vier m × 3 blokken vullen de gaten op tussen de m × m blokken. Voor de finest clipmap is er geen L-vormige fixup nodig, maar wordt de opening door 4 extra m × m en 4 m × 3 blokken opgevuld. Een kleine vertex texture van 3 × 3 sluit het centrum.

Effici¨ enter geheugengebruik De L-vormige strip moet in één van de vier richtingen gedraaid worden, afhankelijk van de evenheid/onevenheid van de X en Y co¨ ordinaten. Het mooie aan deze opsplitsing is de mogelijkheid om een aantal vertex buffers en indices te herdrukken. Zo kan men één vertex texture en indices lijst gebruiken voor alle m × m blokken. Door een uniforme variabele3 toe te voegen aan de vertex shader verandert de lokale offset en dus de globale positie van de vertices (Formule 3.4). De m × 3 blokken en de L-vormige (2m + 1) × 2 blokken delen geen vertex textures, maar voor deze twee vormen kan men wel telkens dezelfde indices lijst gebruiken.

(Xworld , Yworld ) = (Xlocal , Ylocal ) × Scale + (Xcam , Ycam ) + (Xunif orm , Yunif orm )

(3.4)

3 Uniforme variabelen zijn externe variabelen die instelbaar zijn door de applicatie en constant blijven voor een batch van vertices.


3.1.5

53

Clipmap updates

Hoogtewaarden Een clipmap updaten na camera beweging gebeurt ook op de GPU. In 2.3.2 werd uitgelegd dat de compressie residuals compresseert, het verschil in hoogte tussen twee opeenvolgende clipmaps. In plaats van deze op de CPU te sommeren met de hoogtewaarden van de coarsere clipmap kan men dit uitvoeren op de GPU. De residuals die nodig zijn voor de clipmap update worden eerst in een texture geplaatst. Een vertex shader samplet vervolgens de next-coarser clipmap en voegt aan die hoogtewaarde de residual toe uit de residual texture. Op deze manier wordt er optimaal gebruik gemaakt van de GPU parallellisatie om de updates snel uit te voeren4 . Synthese Tijdens het toevoegen van de residuals op de GPU kan men ook Gaussiaanse ruis berekenen voor extra detail. Hiervoor is een grid nodig met een hogere densiteit dan het hoogtewaarden grid (Figuur 3.4). Op de posities waar een punt overeenkomt met een hoogtewaarde, wordt de residual uitgelezen van de ‘residual texture’. Voor de tussenliggende punten worden residual berekend met de Gaussiaanse ruis functie. Net als in sectie 2.6 kan men een kleine tabel gebruiken met op voorhand berekende ruiswaarden. Bij de GPU implementatie kan men deze tabel opslaan als een kleine texture.

Figuur 3.4: Synthese van extra detail voor tussenliggende gridpunten. (a) Het terrein voorgesteld door een regulier grid. (b) Het reguliere grid wordt verder opgedeeld en de extra gridpunten krijgen een hoogtewaarde door de ruisfunctie.

Normal mapping Als een clipmap verschuift door camera beweging, moet men ook de normal map aanpassen. Hiervoor gebruikt men de methode uit sectie 2.3.5 waarbij het lokaal reliëf gebruikt wordt om de normaal te berekenen. Met formule 2.5 kan men met 4 vertex texture lookups de normal map aanpassen zonder enige tussenkomst van de CPU.

3.2

Discussie

De GPU implementatie heeft veel voordelen ten opzichte van de klassieke CPU implementatie. De CPU wordt enkel belast met decompressie (indien die gebruikt wordt), opvullen van de textures 4 Een implementatie van het clipmap update algoritme is te vinden in [AH05] en is geschreven in de High Level Shader Language.


54

per clipmap en moet elke frame view frustum culling uitvoeren zonder clipping. Door gebruik te maken van een kleine lookup tabel op de GPU kan men synthese toevoegen zonder tussenkomst van de CPU en de normalen worden ook volledig automatisch berekend door de GPU door de vertex texture te samplen. Het algoritme vereist duidelijk veel minder rekenkracht van de CPU. View frustum culling optimalisatie Een van de nadelen bij GPU gebaseerde geometry clipmaps is het aantal axis-aligned bounding box testen tegen de view frustum. In plaats van 4 testen zijn er 17 testen nodig. Om het aantal testen te verminderen kan men gebruik maken van hiërarchisch view frustum culling [SJ02]. Door verschillende bounding boxes samen te nemen in één bounding box kan men de 4 originele testen gebruiken als initiële schatting. Figuur 3.5 toont hoe 5 blokken samen getest worden. Indien de test faalt, moet er geen enkel blok in de bounding box verder gecontroleerd worden.

Figuur 3.5: Hiërarchisch axis-aligned bounding box culling. Een bounding box bevat 5 kleinere bounding boxes: boxes 1, 2, 3, 4 + (m × 3). Wanneer de eerste test negatief is, worden de kleine boxes niet verder getest.

3.3

Samenvatting

Door het hergebruiken van de vertex buffers en index lijsten spaart het GPU algoritme veel geheugen uit. De vertex buffers zijn zelfs zo klein ten opzichte van de textures dat ze bijna te verwaarlozen zijn. Efficiënt geheugengebruik, snellere updates door vector rekenkracht op de GPU en minder CPU verbruik, maken van dit algoritme een ideale kandidaat voor terrein rendering. Het GPU algoritme heeft namelijk dezelfde voordelen als het klassieke algoritme zoals decompressie, actieve clipmap selectie en view frustum culling. Momenteel is de grootste bottleneck de vertex texture lookup operatie om de hoogtewaarde uit te lezen van de texture. Per vertex is er 1 lookup nodig uit de vertex texture en per fragment wordt de normaal uitgelezen uit de normal texture. Hoewel dit snel is, is dit één van traagste operaties in een shader5 .

5 In http://developer.nvidia.com/object/using vertex textures.html spreekt men over 33 miljoen lookups per seconde.

Hoofdstuk 4

Implementatie Een groot deel van deze thesis is gericht op het implementeren en analyseren van een werkend geometry clipmap algoritme. Dit hoofdstuk bespreekt de aanpak en keuzes die gemaakt zijn tijdens de implementatie. De implementatie is gemaakt in C++ en maakt gebruik van de grafische library OpenGL in combinatie met Cg. Om vertex buffers op de grafische kaart aan te maken, wordt de OpenGL extensie GL ARB vertex buffer object gebruikt via de GLEW1 library. Er is gekozen voor C++ omdat er redelijk veel geheugen-manipulatie nodig is die zo efficiënt mogelijk moet gebeuren. Verder is de keuze van de grafische library gevallen op OpenGL in plaats van Direct3D door het gebrek aan kennis over Direct3D, maar dit zou in wezen geen verschil uitmaken. De vertex shaders en fragment shaders zijn geschreven in Cg, C for Graphics, een high-level shader taal ontwikkeld door NVIDIA. Ten slotte zorgt Qt2 ervoor dat de implementatie platform onafhankelijk is en dit vergemakkelijkt tegelijkertijd het gebruik van OpenGL. Deze laatste bleek naderhand een slechte keuze te zijn. De message queue’s die gebruikt worden in de grafische interface zijn redelijk traag waardoor de draw calls trager gebeuren en de framerate een klein beetje daalt.

4.1

Data structuur

Run-time decompressie van hoogtedata is niet ge¨ımplementeerd omdat het geen cruciaal onderdeel voor de juiste werking van het algoritme is. Hoewel het niet zo moeilijk zou zijn om de applicatie uit te breiden, is dit niet gebeurd omdat compressie/decompressie een vakgebied op zich is. De hoogtedata wordt ingelezen van een beeldbestand (png) met een grootte van (2n +1)×(2n + 1). Dit geeft een clipmap size van 2n × 2n triangles. De hoogtemap wordt voorgesteld door een grijswaardenbeeld waarbij een kleur tussen 0 en 255 de hoogte bepaalt. Het algoritme is getest met een aantal kleinere versies van de Puget Sound dataset (Sectie 1.4.3): (1024 × 1024), (2048 × 2048) en (4096 × 4096). Elke pixel van het beeldbestand wordt in main memory opgeslagen in een array van single precision floats. Per clipmap wordt er een vertex buffer3 bijgehouden op de grafische kaart. Deze vertex buffers zijn allemaal even groot.

1 GLEW

: http://glew.sourcefourge.net/ : http://www.trolltech.com/ 3 OpenGL Vertex Buffers : GL ARB vertex buffer object extensie. 2 Qt

55

HOOFDSTUK 4. IMPLEMENTATIE

56

Updates Bij een update wordt er voor elke nieuwe vertex de lokatie berekend in grafisch geheugen en vervolgens overschreven met de correcte hoogtewaarde. De coarsere hoogtewaarde, die nodig is voor de transities, wordt gelijktijdig in het geheugen geplaatst (Sectie 2.5.1). Een aantal van de coarsere W hoogtewaarden kunnen direct uitgelezen worden uit main memory omdat ze overeenkomen met de hoogtewaarde van de huidige clipmap. De andere hoogtewaarden W liggen tussen het grid van de coarser clipmap. In het tweede geval wordt het gemiddelde berekend van 2 hoogtewaarden. In figuur 4.1 is te zien hoe de hoogtewaarde van de coarser clipmap rechtstreeks uit main memory gelezen wordt (C) of berekend wordt met het gemiddelde van 2 punten (F).

Figuur 4.1: Berekening van hoogtewaarde W. Punten C worden rechtstreeks uitgelezen, punten F worden berekend door het gemiddelde te nemen van 2 hoogtewaarden.

Normal mapping Voor belichting wordt een normal map berekend in een offline proces. Hiervoor bestaan een aantal filters, zoals de Normal Map4 filter voor de Gimp applicatie. Deze wordt volledig als texture ingelezen en gesampled in de fragment shader. De normal map wordt dus niet on-the-fly herberekend, zoals nodig is bij geometry clipmaps met compressie. Omdat de berekening van de normalen gelijktijdig gebeurt met de vertex buffer updates zou dit slechts een kleine aanpassing zijn waarbij elke clipmap een extra texture krijgt.

4.2

Rendering

Rendering gebeurt zoals voorgesteld in sectie 2.3.3. Per clipmap wordt een strip van triangles opgebouwd waarbij rijen met elkaar verbonden worden via degenerate triangles. View frustum culling gebeurt door de 4 regio’s van een clipmap te controleren ten opzichte van 6 planes en zonodig te clippen (Sectie 2.5.3). View frustum culling geeft in het slechtste geval een speedup van ongeveer een factor 2 tijdens het renderen.

Transities De transities worden berekend met het algoritme van sectie 2.5.1. De Cg vertex shader berekent de lineaire interpolatie factor α voor de transitie op basis van de W coordinaat. Na de interpolatie wordt de W co¨ ordinaat op 1 gezet. Een van de verschillen hier is het aantal berekeningen dat 4 Gimp

Normal Map filter : http://nifelheim.dyndns.org/∼cocidius/normalmap/


57

gebeurt in de vertex shader. Wanneer we een deel van de transitiefunctie uit sectie 2.5.1 opnieuw bekijken,

αx = min max

x − xlv −

xmax −xmin 2

−R−1

R

!

!

,0 ,1

dan zien we dat een deel van de formule onveranderd blijft voor alle triangles binnen een clipmap. De afstand bepalen van het midden tot de eerste triangle die ge¨ınterpoleerd moet worden, is namelijk voor alle triangles gelijk: Di =

xmax − xmin −R−1 2

Sterker nog, de afstand tot de eerste triangle die ge¨ınterpoleerd moet worden, Di , blijft onveranderd gedurende de uitvoering van het algoritme. We moeten deze dus maar één keer berekenen en kunnen Di als uniforme variabele naar de vertex shader sturen. Dit verlaagt het aantal instructies van de vertex shader. Omdat de implementatie CPU-bound is, wegens grote traffic tussen CPU en GPU, kan de vertex shader zonder probleem bijhouden. De preciese impact van deze verbetering is dus niet gekend. Texture- en normalmapping Voor texture mapping wordt de texture ingeladen die overeenkomt met de hoogtemap, in dit geval een Puget Sound texture. De texturecoördinaten worden in de vertex shader berekend afhankelijk van de X en Y co¨ ordinaat van elke vertex. Hierdoor is de vertex shader iets trager, maar is er minder geheugen nodig per vertex. Een fragment shader program past simpele Phong belichting toe op de triangles. Een texture lookup wordt gebruikt om de normaal uit te lezen van de normal map en vervolgens gebruikt voor het berekenen van de diffuse Phong coëfficient. Vooraleer de normaal gebruikt kan worden moet er eerst een transformatie gebeuren van [0; 1] naar [−1; 1], omdat textures geen negatieve waarden toelaten.

4.3

Real-time vervorming

Omdat er geen compressie ge¨ımplementeerd is, is het mogelijk om realtime terrein modificatie uit te voeren. Dit is aanwezig in de applicatie als proof-of-concept: in een vierkantig gebied worden de hoogtewaarden met een factor geschaleerd. De nieuwe hoogtewaarden worden in main memory geplaatst en de nodige vertex buffers worden aangepast. Een voorbeeld van real-time vervorming is te zien in figuur 2.10. In figuur 4.2 is de impact van twee verschillende real-time vervorming gemeten. De framerate daalt heel even bij het herberekenen van de nieuwe hoogtewaarden. De eerste vervorming veranderde een gebied met hoogte en breedte gelijk aan (225 × 225). Dit komt neer op het herberekenen en aanpassen van 50625 hoogtewaarden. De tweede meting is gebeurd voor een kleiner gebied van (100 × 100) = 10000 hoogtewaarden. Merk op dat zowel (225 × 225) als (100 × 100) meer dan voldoende zijn om een bijvoorbeeld een inslagkrater voor te stellen. Op drie verschillende tijdstippen wordt dezelfde vervorming uitgevoerd op drie verschillende stukken terrein. De daling in framerate is vooral bij de eerste meting significant en ging gepaard met een hapering. De framerate daling bij de tweede meting was veel minder en bijna onmerkbaar. De vertraging is zoals te verwachten lineair afhankelijk van het aantal triangles dat aangepast wordt.


58

Figuur 4.2: Meeting van real-time vervorming. De vervorming veroorzaak een korte daling van de framerate. Vooral bij zeer grote vervormingen ondervindt de gebruiker vertragingen. In rust is de framerate ongeveer 350 frames per seconde.

4.4

Resultaten

In deze sectie worden verschillende eigenschappen van het geometry clipmap algoritme getoond aan de hand van screenshots uit de implementatie. Verder worden verschillende testen uitgevoerd om de efficiëntie van verschillende onderdelen aan te tonen.

Overzicht In figuur 4.3 wordt een overzicht gegeven van de Puget Sound dataset. Bovenaan een perspectief aanzicht van het Pudget Sound terrein en de overeenkomstige hoogtemap die gebruikt wordt om de hoogtewaarden voor te stellen. Onderaan twee aanzichten op de berg Rainier. De witte pijl toont de kijkrichting van de camera. Op het beeld rechtsonder is te zien dat de top van de berg met weinig detail wordt weergegeven. Dit komt omdat de texture een te kleine resolutie heeft in vergelijking met het terrein. Dit is op te lossen met synthese (Sectie 2.6).

Normal mapping De afbeeldingen in figuur 4.4 tonen de resultaten van normal mapping. Bovenaan twee aanzichten op het terrein. De grijswaarden geven de diffuse Phong belichtingsfactor aan. Een diffuse lichtbron in het midden van het terrein belicht zichtbare delen. Delen die niet zichtbaar zijn vanuit de positie van de lichtbron zijn donkerder. Rechtsboven is te zien hoe de sommige flanken van de heuvels sterk belicht zijn en andere donker zijn. Onderaan twee beelden vanuit dezelfde positie: links zonder normal mapping, rechts met normal mapping.

Transities tussen clipmaps De transitie regio’s die zorgen voor een naadloze verbinding tussen verschillende clipmaps worden ge¨ıllustreerd in figuur 4.5. Vier clipmaps vloeien in elkaar over met drie overgangsregio’s, aangegeven in het blauw. De felheid van de blauwe kleur geeft de interpolatiefactor aan (Sectie 2.5.1). De hoek van de finest clipmap valt samen met berg Rainier. Figuur 2.11, in hoofdstuk 2, is een gelijkaardige screenshot uit de implementatie.


59

Figuur 4.3: Overzicht van de Puget Sound dataset.

Gaps Tussen de aangrenzende clipmaps ontstaan er gaten door verschil in resolutie. Om deze zichtbaar te maken is de vertex shader, die de interpolatie uitvoert, tijdelijk uitgeschakeld (Figuur 4.6). In de twee bovenste rijen zijn de gaps te zien wanneer er geen interpolatie wordt gebruikt. Dit is vanuit de geometry clipmap camera standpunt. Omdat de afstand tot de gaps redelijk groot is, zijn ze slecht te zien. In de onderste rij worden de gaps van dichterbij getoond via een tweede camera die vrij kan bewegen.

Actieve clipmap selectie Figuur 4.7 toont hoe een camera hoog boven het terrein is geplaatst en recht naar beneden kijkt met zicht op berg Rainier. In de eerste rij is het aanzicht van de camera getoond. De tweede rij toont een zijaanzicht op het terrein, met de vrije camera, waarin te zien is dat het detail veel hoger is door gebrek aan clipmap selectie. Hierdoor wordt er in de rechter kolom veel minder triangles gebruikt dan in de linker kolom. Onderaan wordt het wireframe model van het zijaanzicht getoond. Merk op dat hier de degenerate triangles van de triangle strip zichtbaar zijn: de rechte lijnen onder de mesh die van linksboven naar rechsonder lopen. De rechthoekige banden in de linker figuren zijn de grenzen tussen de verschillende clipmaps. Deze zijn rechts niet te zien omdat de grens van de enige actieve clipmap buiten het scherm ligt.


Figuur 4.4: Normal mapping van Puget Sound.

Figuur 4.5: Transitie regio’s.

60


Figuur 4.6: Gaps tussen verschillende clipmaps.

61


Figuur 4.7: Actieve clipmap selectie.

62


63

View frustum culling View frustum culling is een belangrijke optimalisatie voor geometry clipmaps (Sectie 2.5.3). In figuur 4.8 wordt getoont wat het verschil is tussen view frustum culling met en zonder clipping. De afbeelding links boven toont een perspectiefaanzicht op het terrein. In de tweede rij is een bovenaanzicht te zien, met aan de rechterkant de verschillende clipmaps en de transities. De donkergrijzen driehoek is de camera frustum die gebruikt wordt voor de clipping. De onderste rij toont hetzelfde aanzicht, maar hier is clipping uitgeschakeld. Hierdoor worden de verschillende opdelingen per clipmap volledig gerenderd, ook al is dit niet nodig. Merk op dat in dit geval het aantal triangles dat gerenderd wordt ongeveer 3 keer meer is dan eigenlijk nodig is. Dit toont aan dat na¨ıve view frustum culling zonder clipping weinig bijdraagt tot een efficiënt algoritme.

Figuur 4.8: View frustum culling met clipping.


64

Extended view frustum culling Het grote nadeel van view frustum culling is de herberekening van de triangle strips. Na elke camerarotatie moet de strip opnieuw berekend worden. Dit kan opgelost worden door een grotere view frustum te gebruiken die meer rotatievrijheid biedt. Linksboven in figuur 4.9 is een perspectief aanzicht te zien vanop berg Rainier, met rechts het bovenaanzicht zonder view frustum culling. De camera staat op dezelfde positie als in figuur 4.3. Onderaan zien we hetzelfde bovenaanzicht, maar dan met view frustum culling. In de linker afbeelding wordt de uitgebreide view frustum gebruikt om het aantal triangle strip herberekeningen te verminderen. Rechts is, in het grijs, aangeduid welke gebieden normaal gerenderd worden met de gewone view frustum.

Figuur 4.9: Extended view frustum.

4.4.1

Testsysteem

De resultaten zijn gemeten met een Intel Core2 Duo 6600 (2x2.40Ghz), 2 Gb geheugen en een GeForce 7600 GT grafische kaart. De testen zijn uitgevoerd met een standaardinstallatie van Ubuntu(feisty). Het OpenGL venster heeft een schermresolutie van 1280 × 1024 pixels en een field of view van 60o . De geometry clipmap is getextured en belicht met normalmapping. Het gerapporteerde aantal triangles is een schatting en is in wezen iets minder.


4.4.2

65

Metingen

Er werden verschillende testen uitgevoerd om de ge¨ımplementeerde onderdelen te evalueren. De testen worden uitgevoerd met: • Een geometry clipmap van 4096 × 4096 hoogtewaarden • Clipmaps van 256 × 256 triangles in lengte en breedte • 7 genest clipmaps • Normal mapping De Puget Sound dataset bedekt een gebied van 16km × 16km in lengte en breedte. Hierdoor is de afstand tussen twee aangrenzende hoogtewaarden gelijk aan ±3.9 meter.

Rust toestand In de volgende tabel 4.1 worden cijfers weergegeven van de implementatie zonder camera beweging. De camera is gepositioneerd in het midden en kijkt naar een van de hoeken van de clipmap, evenwijdig met het grondvlak. Hierdoor wordt ongeveer 1/5de van de triangles gerenderd met view frustum culling en clipping. In een realistische situatie zou het natuurlijk beter zijn om het beeldresultaat op te slaan in Frame Buffer Object zodat er geen belasting is zolang de camera in rust is.

Figuur 4.10: Terrain size 2048x2048 2048x2048 4096x4096 4096x4096

Tri/Clipmap 128 256 128 256

Clipmaps 7 6 8 7

FPS/Triangles 310/120.000 170/390.000 280/160.000 160/490.000

FPS/Triangles + VFC 550/ 34.000 310/120.000 520/ 39.000 300/150.000

Tabel 4.1: Resultaten van een camera in rust. Deze cijfers zeggen iets over de doorvoercapaciteit van het algoritme. Aan of afzetten van normal mapping heeft geen invloed op de resultaten. Dit doet vermoeden dat de fragment shader weinig belast wordt ten opzichte van de vertexshader. De CPU is echter volledig belast. Dit geeft aan dat het busverkeer tussen de CPU en de GPU te hoog is. De grootste bottleneck tijdens rust is het continu doorsturen van de triangle strips.


66

View frustum culling Deze test onderzoekt welk effect view frustum culling heeft op de framerate en het aantal triangles. Eerst wordt een grondmodel gemeten waarbij geen view frustum culling gebruikt wordt. Daarna wordt de klassieke view frustum culling getest (Sectie 2.5.3). Ten slotte wordt aangetoond dat de voorgestelde optimalisatie een stabielere framerate geeft omdat er minder triangle strip herberekeningen nodig zijn (Sectie 2.5.3). De metingen worden uitgevoerd met een stilstaande camera die in 10 seconden één omwenteling maakt in het horizontale vlak (Figuur 4.11). De camera draait enkel omdat bewegingen in het horizontale vlak clipmaps updates veroorzaakt. Updates willen we echter vermijden, omdat dit de resultaten be¨ınvloed. In figuur 4.12 zijn de metingen te zien van de rotatie zonder view frustum culling. Omdat de framerate redelijk laag is door de grote hoeveelheid triangles, weegt de onnauwkeurigheid van de framerate counter door. Dit is vooral te merken aan de variërende framerate aan het begin en het einde van de meting. Hoewel de camera volledig stil staat, varieert de framerate nog altijd sterk.

Figuur 4.11: Rotatie test. Verschillende kijkrichtingen vanuit het centrum van de geometry clipmap tijdens de rotatie test met view frustum culling. De tweede meting toont de framerate en triangle count met normale view frustum culling (Figuur 4.13). De framerate ligt een stuk hoger omdat er veel minder triangles gerenderd worden. Het aantal triangles blijft ongeveer gelijk tijdens de rotatie. Door de symmetrische vorm van de clipmaps is de framerate en het aantal triangles ongeveer gespiegeld zodra er 180o gedraaid is. In de laatste meting is er gebruik gemaakt van een uitgebreidere view frustum. De grotere view frustum had een kijkhoek van 70o zodat er zowel rechts als links een hoek van 5o triangles onzichtbaar was. Dit laat een kleine rotatie toe zonder dat er een triangle strip herberekening nodig is. De framerate ligt iets lager maar is wel stabieler en de CPU wordt minder belast. Dit komt omdat er net iets meer triangles gebruikt worden dan bij de normale view frustum.

Actieve clipmap selectie De volgende test toont aan dat de framerate stabiel blijft naarmate een grotere oppervlakte zichtbaar wordt. De framerate blijft hoog door de finest clipmaps te verbergen van zodra er teveel detail aanwezig is (Sectie 2.5.2). De test bestaat uit drie individuele delen. Ten eerste wordt het algoritme getest zonder view frustum culling en zonder clipmap selectie (Figuur 4.15). Hieraan is te zien dat de framerate constant blijft. Dit is te verwachten omdat er op geen enkele manier het aantal triangles verminderd wordt. Vervolgens wordt actieve clipmap selectie geactiveerd en opnieuw beweegt de camera van laag naar hoog met de kijkrichting recht naar beneden. De resultaten in figuur 4.16 tonen aan dat de framerate stijgt naarmate meer en meer clipmaps verborgen worden. De exacte momenten dat de clipmaps verborgen worden kunnen afgeleid worden in het onderste deel van de grafiek. Het aantal triangles daalt in verticale sprongen. Merk op dat de tijd tussen verschillende ‘active selections’ kwadratisch stijgt. Dit komt omdat de camera met een constante snelheid stijgt terwijl de clipmap sizes kwadratisch groeien.


67

De laatste meting geeft een realistische situatie weer waarbij actieve clipmap selectie gecombineerd wordt met view frustum culling. De framerate blijft ongeveer stabiel met een minimum en maximum aantal triangles gedurende de beweging (Figuur 4.17). De kleine sprongen in de framerate zijn het gevolg van de triangle strip herberekening. In de onderste grafiek zien we ook dat het aantal triangles tussen twee ‘active selections’ kwadratisch groeit. Het minimum en maximum aantal triangles ligt redelijk ver uit elkaar maar wordt nooit overschreden. Dit garandeert een minimum framerate zoals te zien is in de bovenste grafiek. Deze test toont dus aan dat actieve clipmap selectie bijdraagt tot een stabiele framerate zonder verlies van zichtbaar detail. Clipmap updates De laatste test analyseert de kost van clipmap updates (Sectie 2.3.1). Dit is echter moeilijk te testen omdat het aantal updates sterk varieert naargelang de positie van de camera. Zo zullen er meer triangles gerenderd worden wanneer de camera in het midden van het terrein is, dan wanneer de camera zich aan de rand bevindt. Om de test zo objectief mogelijk te houden wordt er slechts 1 clipmap aangepast en gerenderd, namelijk de finest. Door enkel de finest clipmap te gebruiken blijft de trianglecount ongeveer gelijk wanneer de camera niet in de buurt van de geometry clipmap rand komt. De triangle count varieert lichtjes door de verschillende triangle strips. Afhankelijk van de wrapping zal elke strip meer of minder degenerate triangles bevatten. Ten slotte wordt er geen actieve clipmap selectie gebruikt en geen view frustum culling. De meting begint met een stilstaande camera met diagonale kijkrichting parallel met het X-Y vlak zodat zowel horizontale als verticale updates nodig zijn. Vervolgens versnelt de camera 5 keer. Het aantal clipmap updates per seconde is evenredig met de snelheid. Op hoogste snelheid beweegt de camera met 5 updates per seconden. Elke update vult 2 rijen en 2 kolommen van hoogtewaarden. Dit komt dus overeen met 10 hoogtewaarden in zowel lengte als breedte. De totale dataset bevat 4096 hoogtewaarden in de lengte en breedte en visualiseert een gebied van 16km × 16km. De camera beweegt dus met een snelheid van 39m/s, of 140km/h. In rust worden er ongeveer 700 frames per seconde gerenderd, op de hoogste snelheid daalt de framerate naar 600 frames per seconde. De framerate is sterk afhankelijk van het aantal updates per seconde (Figuur 4.18). Door echter de finest clipmaps te verbergen bij hoge snelheden kan de framerate hoog gehouden worden (Sectie 2.5.2).

4.4.3

Discussie

Uit de metingen blijkt dat zowel het herberekenen van de triangle strip als het updaten de vertex buffers veel invloed hebben op de framerate. Verder zorgt het busverkeer tussen CPU en GPU voor een extra vertraging door de grote hoeveelheid triangles. Toch is het algoritme snel genoeg om een zeer hoge framerate te halen. Maar zoals reeds gezegd, het algoritme is waarschijnlijk te CPU intensief om gebruikt te worden in uitgebreide applicaties.


Figuur 4.12: Rotatie test zonder view frustum culling.

Figuur 4.13: Rotatie test met de normale view frustum.

Figuur 4.14: Rotatie test met de uitgebreide view frustum.

68


Figuur 4.15: Actieve clipmap selectie test, grondmodel.

Figuur 4.16: Actieve clipmap selectie test zonder view frustum culling.

Figuur 4.17: Actieve clipmap selectie test met view frustum culling.

69


Figuur 4.18: Clipmap update test.

70

Hoofdstuk 5

Conclusie Sinds de eerste 3D toepassingen was er een vraag naar realistische terreinen. Doorheen de jaren zijn er verschillende algoritmen ontwikkeld. Deze algoritmen zijn zeer tijdsgebonden door de continu veranderende hardware. Een kleine groep van deze algoritmen zijn met succes toegepast in grote projecten. Dikwijls worden de nadelen van algoritmen, zoals bijvoorbeeld inefficiënt geheugengebruik of visuele artefacten, (onterecht) door de onderzoekers als ‘verwaarloosbaar’ beschouwd. Maar het zijn meestal net deze problemen die ervoor zorgen dat een algoritme onbruikbaar is. De terrein rendering algoritmen eisen dikwijls teveel systeem resources waardoor ontwikkelaars geneigd zijn om te kiezen voor onrealistische, maar simpele oplossingen. Zelfs op dit moment worden er applicaties ontwikkeld die statische modellen gebruiken om terreinen voor te stellen. Het gebeurt vaak dat gebruikers door een grot of ravijn lopen om een ander gebied te bereiken. De laatste jaren is de trend van quick-and-dirty oplossingen plaats aan het maken voor complexere algoritmen. Terreinen in multimedia systemen worden belangrijker naarmate de systemen uitbreiden. Om te voldoen aan de vraag van efficiënte en realistische terreinen, is het belangrijk om de algoritmen up-to-date te houden met de recentste hardware. In deze thesis is het geometry clipmap algoritme behandeld. De implementatie toont aan dat het algoritme, zoals vele voorgangers, teveel resources gebruikt om echt nuttig te zijn. Enkel applicaties waarin het terrein centraal staat, kunnen gebruik maken van dit algoritme. (Denk bijvoorbeeld aan Google Earth.) De GPU variant van het algoritme is daarentegen wel een goede kandidaat. Met een lage CPU overhead en een hoge triangle doorvoer is het geschikt voor interactieve systemen met nood aan grote terreinen. Maar de verhoogde afhankelijkheid van de grafische processor kan opnieuw een rede zijn om terug te vallen op de klassieke oplossingen. De implementatie biedt nog ruimte voor een aantal verbeteringen. Zo is het misschien interessant om te testen of vertex buffer updates over verschillende frames verspreid kunnen worden. In plaats van vertex buffers met grootte (2n + 1) × (2n + 1) te gebruiken, kan men buffers gebruiken van (2n + 5) × (2n + 5) vertices, of meer. Door slechts (2n + 1) × (2n + 1) van de vertex buffers te renderen kan men op voorhand een stuk van de update voorbereiden. Verder zou het interessant zijn om synthese toe te voegen. Het is volgens [AH05] mogelijk om synthese elke frame volledig in de fragment shader te berekenen zonder extra geheugengebruik. Ten slotte is het misschien mogelijk om een snel, maar minder efficiënt compressie algoritme te gebruiken, zodat real-time vervormingen snel gecompresseerd kunnen worden.

71

Bibliografie [AH05]

Arul Asirvatham and Hugues Hoppe. GPU Gems 2, chapter Terrain rendering using GPU-based geometry clipmaps. Addison Wesley, 2005.

[AM00]

Ulf Assarsson and Tomas Moller. Optimized view frustum culling algorithms for bounding boxes. Journal of graphics tools, 2000.

[Bre05]

Nick Brettell. Terrain Rendering using Geometry Clipmaps. PhD thesis, University of Canterbury, 2005. http://www.cosc.canterbury.ac.nz/research/reports/HonsReps/2005/hons 0502.pdf.

[CD04]

Marc Stamminger Carsten Dachsbacher. Rendering procedural terrain by geometry image warping. Eurographics Symposium on Rendering 2004, 2004.

[CGG+ 03] Paolo Cignoni, Fabio Ganovelli, Enrico Gobbetti, Fabio Marton, Federico Ponchio, and Roberto Scopigno. Planet-sized batched dynamic adaptive meshes (p-bdam). In VIS ’03: Proceedings of the 14th IEEE Visualization 2003 (VIS’03), page 20, Washington, DC, USA, 2003. IEEE Computer Society. [CH06]

Malte Clasen and Hans-Christian Hege. Terrain rendering using spherical clipmaps. In EuroVis 2006 - Eurographics / IEEE VGTC Symposium on Visualization, pages 91–98, 2006.

[Cla76]

James H. Clark. Hierarchical geometric models for visible surface algorithms. Commun. ACM, 19(10):547–554, 1976.

[D.04]

Wagner D. Terrain geomorphing in the vertex shader. In ShaderX2: Shader Programming Tips & Tricks with DirectX 9., 2004.

[dB00]

W. de Boer. Fast terrain rendering using geometrical mipmapping, 2000. http://www.flipcode.com/.

[DWS+ 97] Mark A. Duchaineau, Murray Wolinsky, David E. Sigeti, Mark C. Miller, Charles Aldrich, and Mark B. Mineev-Weinstein. ROAMing terrain: realtime optimally adapting meshes. In IEEE Visualization, pages 81–88, 1997. http://www.llnl.gov/graphics/ROAM/. [FK03]

Randima Fernando and Mark J. Kilgard. The Cg Tutorial: The Definitive Guide to Programmable Real-Time Graphics. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2003.

[GH01]

Gil Gribb and Klaus Hartmann. Fast extraction of frustum planes from the worldview-projection matrix. http://www2.ravensoft.com/users/ggribb/plane extraction.pdf.

[glp00]

OpenGL Performer programmer’s guide, chapter Chapter 15 : ClipTextures. Silicon Graphics, Inc., 2000. http://techpubs.sgi.com/. 73

viewing 2001.

BIBLIOGRAFIE

74

[HM93]

L. Hitchner and M. McGreevy. Methods for user-based reduction of model complexity for virtual planetary exploration, 1993.

[Hop96]

Hugues Hoppe. Progressive meshes. Series):99–108, 1996.

[Hop98a]

Hugues Hoppe. Efficient implementation of progressive meshes. Computers and Graphics, 22(1):27–36, 1998.

[Hop98b]

Hugues H. Hoppe. Smooth view-dependent level-of-detail control and its application to terrain rendering. In David Ebert, Hans Hagen, and Holly Rushmeier, editors, IEEE Visualization ’98, pages 35–42, 1998. http://research.microsoft.com/~hoppe/.

[Lar03]

Bent Dalgaard Larsen. Real-time terrain rendering using smooth hardware optimized level of detail, 2003.

[Len02]

Eric Lengyel. Mathematics for 3D game programming and computer graphics. Charles River Media, Inc., Rockland, MA, USA, 2002.

[LES07]

Kogan Livny and El-Sana. Seamless patches for gpu-based terrain rendering. WSCG, January 2007.

[LH04]

Frank Losasso and Hugues Hoppe. Geometry clipmaps: terrain rendering using nested regular grids. In SIGGRAPH ’04: ACM SIGGRAPH 2004 Papers, pages 769–776, New York, NY, USA, 2004. ACM Press.

Computer Graphics, 30(Annual Conference

[LKR+ 96] Peter Lindstrom, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust, and Gregory A. Turner. Real-time, continuous level of detail rendering of height fields. In SIGGRAPH ’96: Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pages 109–118, New York, NY, USA, 1996. ACM Press. [LP02]

P. Lindstrom and V. Pascucci. Terrain simplification simplified: A general framework for view-dependent out-of-core visualization, 2002.

[LWC+ 02] David Luebke, Benjamin Watson, Jonathan D. Cohen, Martin Reddy, and Amitabh Varshney. Level of Detail for 3D Graphics. Elsevier Science Inc., New York, NY, USA, 2002. [Mal00]

Henrique S. Malvar. Fast progressive image coding without wavelets. In DCC ’00: Proceedings of the Conference on Data Compression, page 243, Washington, DC, USA, 2000. IEEE Computer Society.

[Mor00]

Mark Morley. Frustum culling in http://www.artlum.com/pub/frustumculling.html.

[NL03]

Steen Lund Nielsen and Thomas Lauritsen. Rendering very large, very detailed terrains, 2003. http://www.terrain.dk/.

[Paj98]

Renato B. Pajarola. Large scale terrain visualization using the restricted quadtree triangulation. In IEEE Visualization 98, 1998.

[Pho75]

Bui Tuong Phong. Illumination for computer generated pictures. Commun. ACM, 18(6):311–317, 1975.

[PTJ78]

Fowler R.J. Peucker T.K. and Little J.J. The triangulated irregular network. In Proceedings of the ASP-ACSM Symposium on DTM’s, 1978.

[SJ02]

Daniel S´ ykora and Josef Jel´ınek. Efficient view frustum culling. http://www.cescg.org/CESCG-2002/DSykoraJJelinek/index.html.

opengl.

2000.

2002.

BIBLIOGRAFIE

75

[SW06]

Jens Schneider and R¨ udiger Westermann. Gpu-friendly high-quality terrain rendering. Journal of WSCG, 14(1-3):49–56, 2006.

[TMJ98]

Christopher C. Tanner, Christopher J. Migdal, and Michael T. Jones. The clipmap: a virtual mipmap. In SIGGRAPH ’98: Proceedings of the 25th annual conference on Computer graphics and interactive techniques, pages 151–158, New York, NY, USA, 1998. ACM Press.

[Ulr04]

Thatcher Ulrich. Rendering massive terrains using chunked level of detail control, 2004. http://www.tulrich.com.

[VTP]

VTP. Virtual terrain project - traditional implementation of terrain in games (19952002). http://www.vterrain.org/Games/history.html.

[Wil83]

Lance Williams. Pyramidal parametrics. In SIGGRAPH ’83: Proceedings of the 10th annual conference on Computer graphics and interactive techniques, pages 1–11, New York, NY, USA, 1983. ACM Press.

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: Geometry Clipmaps 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 Sulejmani Datum: 30.08.2007

Lsarev_autr

déçãéíêó=`äáéã~éë káéäë=pìäéàã~åá éêçãçíçê=w mêçñk=çêk=táã=i^jlqqb

Recommend Documents