Informatica — Universiteit van Amsterdam
Bachelor Informatica
Out-of-core distributie en visualisatie van massive point cloud data (AHN2)
Shabaz Sultan
20 juni 2014
Supervisor(s): Robert Belleman (UvA) Signed: Robert Belleman (UvA)
2
Samenvatting Er is gekeken hoe grote datasets met hoogte-informatie op basis van point clouds kunnen worden gevisualiseerd. Hierbij is de AHN2 dataset als basis genomen en is gekeken hoe deze in een 3D omgeving gevisualiseerd kan worden. De grote uitdaging ligt in het omgaan met een zeer grote dataset die niet op de meeste harde schijven past, laat staan in het RAM of videogeheugen van de meeste systemen. Een server-client systeem is gerealiseerd zodat de data out-of-core over een netwerkverbinding kan worden geladen. Voor het weergeven zijn out-of-core rendering technieken gebruikt die wanneer nodig correcte data naar de GPU sturen. Een rendering pipeline is gerealiseerd die op basis van hoogte data in het videogeheugen deze met shaders kan samenvoegen, interpoleren en geometrie generatie kan toepassen. Dit geeft een aanzienlijke winst in performance in vergelijking met de uitvoering van deze stappen op de CPU. Met behulp van een multi-touch interface is de visualisatie toegankelijk voor gebruikers gemaakt. De combinatie van een intu¨ıtieve interface die een 3D visualisatie met voldoende performance aanstuurt is effectief gebleken in het verkenbaar maken van de gebruikte AHN2 dataset.
3
4
Inhoudsopgave
1 Introductie en Probleemstelling 1.1 Onderzoeksvraag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 8
2 Achtergrond (Literatuurstudie)
9
3 Dataset 3.1 Achtergrond AHN2 Dataset . . . . . . . . . 3.2 Analyse AHN2 Datapunten . . . . . . . . . 3.2.1 Statistieken van Dataset en Tegels in 3.2.2 Entropie (Data Compressie) . . . . . 3.2.3 Raster Piramide . . . . . . . . . . . 3.3 Bestandsformaten . . . . . . . . . . . . . . . 3.3.1 Arc/Info Grid Binary . . . . . . . . 3.3.2 RRD . . . . . . . . . . . . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
11 11 11 12 13 13 14 14 14
4 Systeemontwerp Overwegingen 4.1 Keuze Type Visualisatie (2D of 3D) . . . . . . . . . . 4.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Overwegingen Systeem Architectuur . . . . . . . . . . 4.3.1 Monolithisch versus Server-Client Systeem . . . 4.3.2 Verdeling Functionaliteit over Server en Client 4.3.3 Threading . . . . . . . . . . . . . . . . . . . . . 4.3.4 GPU Code . . . . . . . . . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
17 17 18 18 18 19 20 21
. . . . . . . . . . Dataset . . . . . . . . . . . . . . . . . . . . . . . . .
5 Systeemoverzicht 5.1 Server . . . . . . . . . . . . . . . . . 5.1.1 Data Loading . . . . . . . . . 5.1.2 Data Normalisatie . . . . . . 5.2 Netwerkprotocol . . . . . . . . . . . 5.3 Client . . . . . . . . . . . . . . . . . 5.3.1 Texture Manager . . . . . . . 5.3.2 Data Requests over Netwerk
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
23 23 23 24 25 26 27 27
6 Rendering Pipeline 6.1 CPU Code . . . . . . . . . . . . . 6.1.1 Bepalen Zichtbaar Gebied 6.1.2 Bepalen Detailniveaus . . 6.2 Eerste Render Stage . . . . . . . 6.3 Tweede Render Stage . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
29 30 30 31 32 32
. . . . .
. . . . .
5
7 Interface 7.1 Zoomen . . . . . . . 7.2 Rotatie . . . . . . . 7.3 Camera Bewegen . . 7.4 Kijkrichting Camera
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
35 35 36 38 38
. . . . . . . . Client . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
41 41 41 42 44
9 Conclusies en Aanbevelingen 9.1 Aanbevelingen voor Toekomstig Onderzoek . . . . . . . . . . . . . . . . . . . . .
47 48
Bibliografie
51
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
8 Meetresultaten 8.1 Test Omgeving . . . . . . . . . . . . . . . . . . . . . 8.2 Test Scenario’s . . . . . . . . . . . . . . . . . . . . . 8.3 Tests op een Single-Threaded versus Multi-Threaded 8.4 Verdeling Rendering over GPU en CPU . . . . . . .
6
. . . .
. . . .
. . . .
HOOFDSTUK 1
Introductie en Probleemstelling Het Actueel Hoogtebestand Nederland produceert voor Nederland een zeer gedetailleerde kaart met hoogte informatie die gebruikt wordt door verscheidene overheidsinstellingen [1]. De organisatie heeft een aantal datasets opgebouwd, waaronder de AHN2 dataset die gegevens bevat die tussen 2007 en 2013 zijn ingewonnen met behulp van LIDAR scans uit vliegtuig of helikopter. De AHN2 dataset bevat metingen voor elk 0.5 bij 0.5 meter voor Nederland, met een maximale foutmarge in de hoogte van 5 cm. Om inzicht te krijgen in deze dataset kan het nuttig zijn deze te visualiseren. Hiervoor kunnen 3D rendering technieken worden gebruikt uit onder andere games of vluchtsimulators. Het is hierbij de uitdaging om wanneer nodig een exacte en accurate weergave te geven van de data wanneer een gebruiker een deel van de dataset op zeer gedetailleerd niveau wilt bekijken. Daarnaast moet de gebruiker ook de mogelijkheid hebben om heel Nederland te beschouwen, wat in de meest na¨ıve implementatie de volledige dataset nodig zou hebben. De wens is dit allemaal performant te houden, met een stabiele en hoge framerate. De dataset is in de orde van grootte van honderden gigabytes. Dit maakt het lastig om de data samen met een applicatie te distribueren. Het is door de grootte van de dataset in plaats daarvan logischer om de data centraal op te slaan en via een netwerkprotocol te distribueren, waarbij een clientapplicatie slechts subsets van de data kan opvragen die deze op dat moment nodig heeft. Verder is het niet mogelijk alle data in GPU te uploaden. Per definitie heeft een applicatie in het bovenstaande client-server model niet alle data lokaal beschikbaar, maar zelfs als dit wel aanwezig zou zijn is het niet mogelijk op moderne hardware om deze data in het videogeheugen te laden. Dit maakt het noodzakelijk te kijken naar zogenaamde out-of-core rendering technieken. Voor de visualisatie is het verder nuttig om de data in verschillende detailniveaus aan te leveren bij de applicatie. Als bijvoorbeeld heel Nederland bekeken wordt hoeft de applicatie niet de complete dataset van honderden gigabytes te gebruiken, maar krijgt in plaats hiervan een gereduceerde representatie op een lager detailniveau. Hiervoor moet het netwerkprotocol deze aanvragen ondersteunen. Er is een diepe analyse gemaakt van de dataset representatie zoals deze door het AHN wordt aangeleverd. Hier is onder andere gekeken naar de gebruikte bestandsformaten, de manier waarop de individuele datapunten worden opgeslagen en of de eerder genoemde minder gedetailleerde detailniveaus reeds aanwezig zijn. Om het verkennen van de AHN2 dataset voldoende te faciliteren is er ook gekeken naar wat een effectieve interface zou zijn voor deze applicatie. Hierbij is in het bijzonder aandacht besteed aan de toepasbaarheid van multi-touch interfaces. 7
1.1 Onderzoeksvraag De centrale onderzoeksvraag is te formuleren als: Hoe kan de grote AHN2 dataset in een 3D omgeving gevisualiseerd worden? Er zijn daarbij een aantal subvragen te onderscheiden: Hoe kan de dataset gedistribueerd worden naar gebruikers systemen? Hoe kan de data in beeld gebracht worden met voldoende performance? Hoe kan de visualisatie gerealiseerd worden zonder te hoge systeemeisen te stellen? Wat is een intu¨ıtieve interface om de gevisualiseerde 3D omgeving mee te verkennen? Deze onderzoeksvragen hebben het onderzoek geleid dat voor deze scriptie is uitgevoerd.
8
HOOFDSTUK 2
Achtergrond (Literatuurstudie) In de literatuur over terrain rendering is Lindstrom et al. ´e´en van de bekendere aanpakken [LKR+ 96]. Het ROAM algoritme is ook bekend [DWS+ 97]. Wat al deze algoritmen met elkaar gemeen hebben is dat ze er van uit gaan dat de data voor het terrein in het geheugen past. Dit niet het geval voor de gekozen AHN2 dataset. Daarnaast stammen deze aanpakken uit de tijd voordat algemeen beschikbare 3D acceleratie hardware bestond. De Geometrical MipMapping aanpak heeft parallellen met het algoritme dat is gerealiseerd, met hoogtemap detailniveaus en trilinear filtering gelijkend aan MipMap systemen [DB00]. E´en van de verschillen is dat bij GeoMipMaps veel aandacht besteed wordt om de seams tussen verschillende level-of-detail niveaus goed te laten overgaan. De uiteindelijk gekozen aanpak geeft geen expliciete seams. Voor visualisatie van massive point cloud data kan gekeken worden naar Richter et al. [RD10]. Deze aanpak gebruikt een point gebaseerde rendering methode van de point cloud data. Deze aanpak is relevanter wanneer met een ongestructureerde point cloud data gewerkt wordt. Eerder werk met het visualiseren van specifiek de AHN2 dataset is gedaan door Haan [Haa09]. Het beschreven systeem gebruikt de ruwe point cloud dataset zoals door het Algemeen Hoogtebestand Nederland wordt aangeleverd. Het AHN levert ook een grid versie van de dataset. Dit is de versie van de AHN2 dataset die gekozen is om te visualiseren in het systeem dat later beschreven wordt. Daarnaast is bij Haan gekeken hoe een minimale geometrische representatie in de CPU gevormd kan worden om de GPU niet te veel te belasten. In ons systeem is onderzocht of zoveel mogelijk data op de GPU kan worden geladen, zodat in de GPU een geometrische representatie kan worden gevormd. In “Continuous Distance-Dependent Level of Detail for Rendering Heightmaps” wordt een aanpak beschreven die seams tussen detailniveaus vermijdt door geleidelijk tussen detailniveaus te ‘morphen’ [Str09]. Dit raakt aan de gekozen aanpak, waar ook geleidelijk tussen detailniveaus wordt ge¨ınterpoleerd en op deze manier worden seams vermeden. Voor het visualiseren van grote terrein datasets kan naar B¨osch et al. gekeken worden [BGP09]. Bij deze aanpak wordt geometrie op de GPU gegenereerd op basis van hoogte informatie in het videogeheugen. Dit heeft raakvlakken met het gerealiseerde systeem dat ook op de GPU geometrie aanmaakt. Voor distributie van massive point cloud data in het algemeen wordt door een medewerker van ´e´en van de bedrijven die de AHN2 dataset voor AHN heeft ingewonnen een online distributie service voorgesteld, met een data server, een applicatie server en een eindgebruikers applica9
tie [Kod10]. Door Martinet et al. is een overzicht opgesteld van werk met multi-touch apparaten om in een 3D ruimte te navigeren [MCG10]. Eerder werk met visualisatie in combinatie met een multitouch interface is gedaan door Belleman et al. voor de AHN2 dataset [BRS+ 10]. Eerder werk binnen de Universiteit van Amsterdam is gedaan met betrekking tot analyse van AHN datasets en met verkenning en visualisatie van UrbanFlood informatie [Bri12, Tor12].
10
HOOFDSTUK 3
Dataset 3.1 Achtergrond AHN2 Dataset Het Actueel Hoogtebestand Nederland (AHN) is een initiatief van Rijkswaterstaat en de Waterschappen met als doel het meten van hoogte-informatie voor heel Nederland. Dit wordt gedaan met behulp van laseraltemetrie (ook wel LIDAR genoemd) met metingen gedaan vanuit een helikopter of vliegtuig. Nederland was hierbij het eerste land dat door laseraltemetrie uit de lucht is opgemeten [SSK10]. De eerste dataset van het AHN is gemaakt op basis van metingen gedaan tussen 1996 en 2003. Nadat de metingen voor deze zogenaamde AHN1 dataset afgerond waren is in 2008 met metingen begonnen voor een tweede dataset met hogere precisie: AHN2. Deze metingen zijn in 2013 afgerond. De AHN2 dataset van het AHN geeft voor heel Nederland precieze hoogte-informatie. Hierbij zijn gemiddeld tussen de 6 en 10 datapunten per vierkante meter ingewonnen. Dit tegen een gemiddelde dichtheid van 1 datapunt per 16 vierkante meter voor de AHN1 dataset. Elk datapunt heeft een maximale systematische fout van 5 cm en een maximale stochastische fout van 5 cm. De collectie aan datapunten geeft een databestand in de vorm van een puntenwolk. Op basis van de puntenwolk wordt een databestand in de vorm van een regelmatig hoogtegrid opgesteld. Voor elke van de 0.5 bij 0.5 meter cellen van het grid worden enkel de datapunten die in de betreffende cel vallen meegenomen voor het bepalen van de hoogte van de cel in het hoogtegrid [vdZ13].
3.2 Analyse AHN2 Datapunten De dataset gebruikt het Rijksdriehoeksco¨ordinaten Stelsel als referentiesysteem voor de ligging van de datapunten in het gridbestand. Dit is een rechthoekig cartesisch co¨ordinatenstelsel. De hoogtewaarden in de dataset zijn gegeven in meters ten opzichte van het Normaal Amsterdams Peil. De data wordt voor de grid versie in 32 bits floating-point getallen aangeleverd. De datapunten maken echter niet gebruik van de volledige precisie van het gekozen dataformaat. In tabel 3.1 is te zien dat de datapunten (gegeven in meters) eigenlijk nooit meer dan drie decimale cijfers achter de komma hebben. De extra cijfers achter de komma zijn het resultaat van het feit dat binair floating-point niet alle decimale getallen achter de komma exact kan representeren. Dit is te verifi¨eren door te kijken naar de originele point cloud data, voordat deze in de grid versie is gestopt. Data in deze versie is in een ASCII gebaseerd decimaal floating-point dataformaat geleverd, in plaats van een binair floating-point formaat. Het is in deze versie zichtbaar dat voor de datapunten inderdaad 3 getallen achter de komma staan, nooit meer. Als deze getallen 11
als binair floating-point worden uitgedrukt (dat wil zeggen, als som van tweede macht breuken voor het deel achter de komma) dan komen de verwachte problemen met uitdrukken van decimale breuken overeen met wat in de aangeleverde grid versie van de data zit. Tabel 3.1: Aantal willekeurige datapunten uit de grid versie van de AHN2 dataset weergegeven met 20 significante cijfers.
1.2230000495910644531 1.2519999742507934570 1.2779999971389770508 1.3400000333786010742 1.4769999980926513672 1.4839999675750732422
1.2740000486373901367 1.2810000181198120117 1.2580000162124633789 1.5310000181198120117 1.4900000095367431641 1.5060000419616699219
1.2439999580383300781 1.2460000514984130859 1.2530000209808349609 1.5210000276565551758 1.4700000286102294922 1.5140000581741333008
1.2510000467300415039 1.2890000343322753906 1.2979999780654907227 1.5069999694824218750 1.4700000286102294922 1.5190000534057617188
Het feit dat de datapunten een vast aantal cijfers achter de komma hebben betekent dat een logischer formaat mogelijk een fixed-point dataformaat met drie getallen achter de komma zou zijn geweest. Aangezien de data in meters gegeven wordt is dit equivalent aan integers die in millimeters zijn gegeven. De dataset is opgedeeld in tegels met dimensies van 1000 meter van west naar oost en 1250 meter van zuid naar noord. Voor de grid dataset geeft dit 2000 bij 2500 datapunten per tegel op het hoogste detailniveau.
3.2.1 Statistieken van Dataset en Tegels in Dataset Elk van deze tegels heeft een bestand met een aantal statistieken. Voor elke tegel wordt het minimum, maximum, standaardafwijking en gemiddelde voor de datapunten in die tegel gegeven. Op basis van deze waarden voor de tegels kan het minimum, maximum en bereik van datapunten voor de gehele dataset worden bepaald. Tabel 3.2: Statistieken voor dataset en tegel met het grootste bereik, alle waarden in meters. Gefilterde waarden zijn op basis van dataset zonder twee tegels met bereik van 80km.
Volledige dataset Minimum dataset Maximum dataset Bereik dataset Aantal tegels met bereik ≤ 65536 Aantal bekeken tegels
Ongefilterd -31.280 83310.961 83341.241 27056 27070
Gefilterd -31.280 110.613 141.893 27056 27068
Tegel met grootste bereik Naam tegel minimum tegel gemiddelde tegel maximum tegel Bereik tegel
Ongefilterd i31az1_02 -5.100 -3.853 83310.961 83316.061
Gefilterd i40dz1_17 8.788 42.108 91.163 82.375
Er zijn tegels die ongeveer 80 kilometer als maximum opgeven (tegels i40bn2_07 en i31az1_02 om precies te zijn). Dit is duidelijk incorrect (hoogste bergen in de wereld zijn bijvoorbeeld ongeveer 9 kilometer) en wanneer deze tegels uit de dataset zijn gefilterd worden redelijkere waarden voor de rest van de tegels verkregen. Zoals eerder opgemerkt gebruiken de datapunten in de dataset eigenlijk enkel precisie tot op millimeters. Dit betekent dat voor de gehele dataset het bereik van de waarden in een datatype past met een bereik van 141893 waarden. Dit zou log2 (141893) ≈ 17.1 bits per datapunt vereisen. Dit is een stuk minder dan het gebruikte 32 bits floating-point datatype. Het bereik is echter 12
helaas net niet klein genoeg om in een 2 byte datatype te passen. Het maximum bereik van een tegel in de (gefilterde) dataset is wat lager dan het bereik voor datapunten in de gehele dataset, namelijk 82375. Dit zou log2 (82375) ≈ 16.3 bits per datapunt vereisen. Dit is helaas wederom net te groot om in de 16 bits van een 2 byte datatype te passen. Het bereik van 27056 van de 27070 tegels in de dataset is echter 65536 of lager, het maximum bereik van een 16 bits datatype. Het is dus mogelijk om het overgrote deel van de tegels op te slaan met 16 bits per datapunt. Opslag van datategels met 16 bits in plaats van 32 bits per datapunt zou de opslag door twee delen. Voor een datategel op volledige resolutie zou de opslag van 2500 × 2000 × 4 B = 20 MB naar 2500 × 2000 × 2 B = 10 MB gaan. Per tegel moet dan enkel nog het bereik van de waarden in absolute termen extra moeten worden opgeslagen, wat 4 bytes extra vereist om het originele minimum op te slaan. Een winst van 10 MB met een paar bytes aan extra metadata per tegel lijkt een redelijke ruil.
3.2.2 Entropie (Data Compressie) Om een idee te krijgen van de entropie en informatiedichtheid van de dataset is het DEFLATE compressie-algoritme op een willekeurig gekozen tegel (i10gn2_16) toegepast. Dit is gedaan met behulp van de gzip applicatie. De hoeveelheid compressie kan bij benadering een idee van de entropie van de data geven. Het toepassen van compressie is gedaan op zowel de originele 32 bits floating-point datapunten alsmede op een 16 bits fixed-point representatie van dezelfde datapunten. Tabel 3.3: Compressie statistieken voor ´ e´ en tegel (i10gn2 16).
32-bit 32-bit 16-bit 16-bit
floating-point floating-point met gzip fixed-point fixed-point met gzip
aantal bytes 20485284 7963205 10240000 5793885
grootte t.o.v. orgineel 100.0% 38.9% 50.0% 28.9%
Gzip kan de onbewerkte data comprimeren naar 40% van de originele grootte. In de onbewerkte data zitten bits die er eigenlijk niet toe doen; bits die decimalen kleiner dan een millimeter beschrijven. Zonder voorbewerking zal gzip deze bits in de compressie altijd meenemen, omdat het een lossless compressie-algoritme is. Door eerst een pre-processing stap uit te voeren en de data van 32 bits naar 16 bits op te slaan kan een grootte van 50% van het origineel worden bereikt. Het DEFLATE compressie-algoritme kan deze fixed-point dataset daarna nog verder comprimeren, naar minder dan 30% van de originele grootte. De inzichten van deze sectie en de sectie over opslag met 16 bits fixed-point zijn niet in het uiteindelijke systeem meegenomen voor de dataopslag. Daar is de keuze gemaakt zo veel mogelijk de originele opslag zoals aangeleverd door het AHN te gebruiken. Het inzicht over compressie is wel meegenomen in het ontwerp van het netwerkprotocol, zoals in sectie 5.2 te zien is.
3.2.3 Raster Piramide Naast de dataset op volledige resolutie is bij elke tegel ook een piramide aan datagrids van lagere resolutie geleverd. Deze worden in het RRD bestandsformaat gegeven, waarover in sectie 3.3 meer. In totaal worden maximaal vier extra rasters op lagere detailniveaus geleverd in deze bestanden. Op het hoogste detailniveau bevat de dataset 2000 bij 2500 datapunten. Elk minder gedetailleerd niveau heeft een kwart van de resolutie erboven, dus het ´e´en na meest gedetailleerde niveau heeft 1000 bij 1250 datapunten, het niveau daarna 500 bij 625. Het niveau na 500 bij 625 zou een resolutie van 250 bij 312.5 moeten hebben, maar het is 13
uiteraard niet mogelijk om een rij aan halve datapunten te hebben. Er is bij het aanmaken van deze lager detailniveau grids voor gekozen om de resolutie af te ronden, naar 250 bij 312 of 250 bij 313. Deze afronding is echter niet consistent en sommige tegels ronden naar boven af en sommige ronden de resolutie af naar beneden. De overgang van 500 bij 625 naar 250 bij 312.5 is niet de enige overgang waarbij de resolutie moet worden afgerond en helaas is de afronding bij de andere overgangen ook niet consistent.
3.3 Bestandsformaten De dataset wordt aangeleverd in een aantal bestandsformaten die voornamelijk gerelateerd zijn aan het ArcGIS product van Esri [2, 3]. ArcGIS is een Geographic Information System (GIS) met een aantal proprietary opslagmethoden die door het AHN gebruikt worden om data aan te leveren. De directorystructuur van de dataset plaatst de meeste bestanden in een map met de naam
/geogegevens/raster. Onder deze map zijn een aantal 3 letter mappen die op hun beurt de daadwerkelijke tegels bevatten. Elk van de tegels heeft de volgende bestanden: Tabel 3.4: Bestanden per tegel in de dataset.
Bestandsnaam
Beschrijving
.rrd
Reduced Resolution Dataset bestand, met een pyramide voor rasterdata in Erdas Imagine bestandsformaat extra informatie horend bij RRD bestand, met o.a. projectie informatie bounds co¨ ordinaten voor linksonder en rechtsboven van tegel header voor Arc/Info Grid met info over resolutie, compressie, datatype statistieken (minimum, maximum, standaardafwijking, gemiddelde) voor tegel data in Arc/Info Grid Binary index voor data in Arc/Info Grid Binary bestand
.aux /dblbnd.adf /hdr.adf /sta.adf /w001001.adf /w001001x.adf
3.3.1 Arc/Info Grid Binary De primaire opslag van de hoogtedata gebeurt in het Arc/Info Binary Grid formaat [4, 5]. In dit formaat kan rasterdata in een tweedimensionaal grid worden opgeslagen. De datapunten in het grid kunnen 4 byte integers of 4 byte IEEE floating-point zijn. In het geval van de AHN2 dataset zijn dit floating-point getallen. Het bestandsformaat maakt gebruik van opslag in blokken. Deze blokken bevinden zich in het w001001.adf bestand. Het w001001x.adf bestand functioneert als een index voor deze blokken, waarbij het de positie en grootte van elk van de blokken in w001001.adf aangeeft.
3.3.2 RRD Voor de meeste tegels is naast de data op volledige resolutie ook een set aan zogenaamde Reduced Resolution Dataset (RRD) bestanden aangeleverd [6]. Deze gebruiken intern het Erdas Imagine bestandsformaat [7]. Dit bestandsformaat slaat net als het Arc/Info Grid Binary formaat rasterdata op, maar kan daarnaast ook piramide lagen van een dataset opslaan. In het geval van de AHN2 dataset is de data op het meest gedetailleerde niveau niet in de RRD bestanden, maar de piramide lagen zijn hier wel terug te vinden. De structuur van een Erdas Imagine bestand volgt de structuur gegeven in het Erdas Imagine Hierarchical File Format (HFA). Het HFA formaat specificeert een methode om een tree 14
structuur in een bestand op te slaan. Bestanden hebben ook een dictionary sectie welke de mogelijke datanodes in de tree beschrijven, wat het formaat enigszins zelf-beschrijvend maakt. Om de RRD bestanden in te lezen is voornamelijk ´e´en van de mogelijke nodetypes interessant, namelijk Eimg_Layer_SubSample. In nodes van dit type zijn de rasters met lagere resolutie voor de dataset opgeslagen. Elk raster is in blokken opgeslagen, met een indexlijst aan pointers die aangeven waar de datablokken beginnen. Dit doet denken aan de blokopslag van Arc/Info Grid Binary bestanden. Elk van de blokken kan integer of floating-point data bevatten. Elk van de blokken kan ook gecomprimeerd zijn. Volgens de offici¨ele documentatie kunnen enkel integer blokken gecomprimeerd zijn. De RRD bestanden in de AHN2 dataset zijn in floating-point. Dit zou volgens de documentatie betekenen dat er geen AHN2 RRD bestanden met compressie bestaan, maar toch heeft de dataset RRD bestanden met rasters die gecomprimeerde blokken bevatten. Hiervoor worden tijdens compressie en decompressie de bytes behandeld alsof ze integer data bevatten. Dit is niet in de documentatie gedocumenteerd [8]. Het compressie-algoritme bestaat uit een run-length encoding voorafgegaan aan een normalisatie stap waar de laagste waarde van een blok als nieuw nulpunt voor de datapunten wordt gebruikt. Zo zou bijvoorbeeld -8, 5, 30 veranderen in 0, 13, 38 waarna met een run-length encoding gepoogd wordt een minimaal aantal bytes per datapunt te gebruiken.
15
16
HOOFDSTUK 4
Systeemontwerp Overwegingen Om de AHN2 dataset inzichtelijk te te maken zijn verschillende aanpakken te bedenken. Met statistische methoden en data analyse algoritmen zijn interessante eigenschappen van een dataset te vinden. Het moet echter bekend zijn welke eigenschappen gezocht worden wanneer deze vorm van analyse wordt toegepast. Als dit nog niet bekend is, dan is het lastig specifieke statistische methode te selecteren die relevant zijn en algoritmen op te stellen die de gewenste eigenschappen vinden. In plaats daarvan is het nuttiger in deze fase van analyse om verkennend te werk te gaan. Voor exploratief werk met een dataset is visualisatie bij uitstek geschikt. Hierbij wordt gebruik gemaakt van de menselijke visuele cortex om informatie te analyseren. Het is voor een systeem dat exploratief werk faciliteert belangrijk dat een gebruiker de data op een manier tot zich kan nemen die zowel accuraat als visueel helder is. Daarnaast is impliciet in het idee van exploratief werk dat een gebruiker een interface tot haar beschikking heeft die het makkelijk maakt de dataset te verkennen.
4.1 Keuze Type Visualisatie (2D of 3D) De dataset bestaat uit hoogte-informatie. Er zijn een aantal opties voor de visualisatie van dit type dataset. De versie van de dataset die hier beschouwd wordt is een 3D point cloud die naar een regulier 2D grid geresampled is. De hele dataset is voor te stellen als een zeer groot 2D grid met voor elk punt op het grid een hoogtewaarde. Het visualiseren hiervan zou kunnen door een platte weergave van delen van de dataset aan de gebruiker voor te stellen, waarbij enkel een translatie moet worden gemaakt van een bereik aan hoogtewaarden naar een bereik aan RGB kleurwaarden. Een andere optie zou zijn om te kijken naar de data geplaatst in een 3D ruimte. De point cloud versie van de dataset heeft een lange lijst aan 3D co¨ordinaten, waarbij het voor de hand ligt deze in een 3D omgeving te plaatsen bij een visualisatie. Voor de 2D grid versie zijn echter voor elk datapunt nog steeds drie ruimtelijke componenten af te leiden. Twee componenten zijn af te leiden aan de positie van een datapunt in het grid en de derde component is gegeven door de hoogtewaarde van het datapunt. Er is voor gekozen om de dataset in een 3D ruimte te plaatsen. Een weergave van het terrein kan worden gemaakt waar de hoogteverschillen in de data met een perspectivische projectie zichtbaar worden gemaakt. Op deze manier kan een ruimtelijke weergave van de AHN2 dataset worden opgesteld waar hoogteverschillen en ruimtelijkheid op een natuurlijke manier visueel worden aangeboden. De opties tot verkenning van de dataset zijn groter in een 3D omgeving; de gebruiker heeft meer opties voor hoe zij zich door de dataset verplaatst en selecties maakt van subsets van de 17
dataset. Dit heeft zowel voor- als nadelen. Voor verkend werk kunnen extra opties nuttig zijn. Extra interactie mogelijkheden kunnen de user experience echter ingewikkelder maken, wat een beter interface ontwerp noodzakelijk maakt.
4.2 Performance Naast de keuze voor 2D of 3D moet een keuze gemaakt worden voor de gewenste performance. Een mogelijkheid is om een gebruiker een selectie te laten invoeren voor welke sectie van de dataset zij wilt zien. Na enkele seconden geeft het systeem een uitvoer terug aan de gebruiker. Dit kan in sommige use-cases een zeer legitiem systeemontwerp zijn. Aangezien de use-cases van het systeem voor exploratief gebruik van de dataset zijn is dit echter niet acceptabel. De gebruiker moet de dataset kunnen verkennen in een real-time omgeving, met een interactief aantal frames per seconde. Als minimum kan hier een framerate rond 20-30 per seconde worden beschouwd, met als ideaal een framerate van 60 per seconde. Het doel van een hoge framerate is de tijd tussen invoer van de gebruiker en reflectie van deze invoer in de visualisatie te minimaliseren. Wanneer een gebruiker de invoer geeft om de 3D camera te verplaatsen moet het aanvoelen alsof dit ogenblikkelijk te zien is. Het is ook belangrijk dat data zo snel mogelijk zichtbaar is. Er is echter een verschil tussen het performance criterium van laadsnelheid van data en het criterium van framerate. Het is mogelijk dat een gebruiker de camerapositie verandert en dat dit snel wordt meegenomen zonder dat alle data geladen is. De camera moet zijn perspectief en positie snel kunnen veranderen, zelfs als dit betekent dat delen van het terrein met ongeladen data in beeld zijn. Het laadsnelheid criterium mag dus lager liggen dan het framerate criterium.
4.3 Overwegingen Systeem Architectuur 4.3.1 Monolithisch versus Server-Client Systeem server computer
server computer Server Application
Data on HDD
Data on HDD
Server Application
User Input
Network protocol
Client computer Client Application
Network protocol
User Input
Graphical Output
(a) monolithische architectuur
Graphical Output
(b) server-client architectuur
Figuur 4.1: Verschil in architectuur op het hoogste niveau.
Het complete systeem dat ontwikkeld wordt moet de mogelijkheid hebben relevante data uit de AHN2 dataset in te lezen, gebruikersinteractie in te nemen en een 3D visualisatie weergave uit te geven. Dit is te implementeren op ´e´en fysieke computer. Als dit gedaan zou worden zou het de complexiteit van het systeem ten goede komen. Het is dus zaak te analyseren of de monolithische aanpak gebreken vertoont voor hij verworpen wordt.
18
E´en van de grote uitdagingen van het werken met de AHN2 dataset is de grootte van de dataset. Dit heeft invloed op het ontwerp van het systeem. Als een monolithisch ontwerp voor de architectuur gekozen wordt, dan betekent dit dat als vereiste gesteld wordt dat het fysieke systeem de volledige dataset moet kunnen opslaan. Met een dataset rond de terabyte is dit een behoorlijk zware eis voor de meeste PCs en een onhaalbare eis voor meeste andere platformen (zoals smartphone of tablet). Naast de zware eis voor het fysieke systeem vereist het monolithische ontwerp veel gegevensoverdracht om een nieuw systeem op te zetten. De combinatie van deze twee eigenschappen zou betekenen dat mogelijk maar enkele fysieke systemen (zo niet ´e´en enkel systeem) kunnen worden gerealiseerd die het visualisatie systeem draaien. Het is de vraag of dit een onredelijke beperking in het gebruik van het systeem is. E´en van de ontwerp doelen voor dit systeem is het gemak te verhogen waarmee de AHN2 dataset verkend kan worden. Sterke restricties lijken hiermee in strijd te zijn. Het alternatief is een systeem waar slechts ´e´en of enkele fysieke systemen strenge eisen hebben qua opslag en installatie, maar waar daarnaast gebruikerssystemen draaien met lagere systeemeisen. Dit lijkt meer in lijn liggen met het doel van de toegankelijkheid en verkenbaarheid van de AHN2 dataset te verhogen. De keuze valt op een systeem waar ´e´en centraal deel bestaat die op een fysieke computer draait die de hoge eisen voor dataopslag haalt. De rest van het systeem kan dan draaien op een fysiek systeem waar veel lagere eisen qua opslag aan gesteld worden. Hierbij moet dit andere deel op zijn minst gebruikers input kunnen inlezen en grafische output aan de gebruiker kunnen tonen. Als extra complexiteit bij de keuze voor deze architectuur komt dat een communicatie systeem gerealiseerd moet worden om de twee delen met elkaar in verbinding te stellen.
4.3.2 Verdeling Functionaliteit over Server en Client server computer Server Application Data on HDD
server computer
Client computer
File Rendering Loading Network
User Input
Server Application
Client Application
Data on HDD
User IO Network
Client computer Client Application
File Loading
Rendering
Network
Network
Graphical Output
User Input
(a) thin-client architectuur
User IO
Graphical Output
(b) thick-client architectuur
Figuur 4.2: Render module op client of server.
Als het complete systeem bestaat uit twee delen dan moet worden besloten hoe de functionaliteit van het systeem verdeeld dient te worden over deze twee delen. De minimale functionaliteit die aan de server kant van het systeem gerealiseerd dient te worden is de mogelijkheid om de dataset in te lezen. De client kant moet minstens gebruikersinput kunnen inlezen en een grafische output aan de gebruiker kunnen weergeven. Een derde set aan functionaliteit is te onderscheiden: de functionaliteit die de data uit de dataset transformeert in een grafische 3D representatie. In figuur 4.2 is dit als de rendering module aangemerkt. Een eerste optie zou het plaatsen van de rendering module op de server kunnen zijn. Dit heeft als voordeel dat de vereisten voor de grafische kracht van de client computer zeer laag is. In de games industrie wordt deze zogenaamde thin-client aanpak onder andere toegepast 19
door Gaikai, PlayStation Now (op basis van Gaikai technologie) en OnLive. Het nadeel is dat de responsiviteit voor de gebruiker omlaag gaat. Als de gebruiker input geeft moet dit eerst over het netwerk reizen. Daarna moet op de server nieuwe grafische output op basis van de gebruiker input worden gegenereerd. En als laatste moet de grafische output terug over het netwerk reizen. Dit laatste punt zorgt voor een constante en grote datastroom tussen de server en client. Het netwerk systeem zal erg in complexiteit omhoog gaan om deze hoge datastroom enigszins effici¨ent door te geven. Zie bijvoorbeeld [CFGS12] voor informatie over het OnLive protocol. Het alternatief is het zogenaamde thick-client model, waarbij de rendering op de client gebeurt. Dit vereist een client systeem die een groter grafisch vermogen heeft dan in het thin-client model. De thick-client zal een lagere responstijd hebben voor gebruikersinteractie, omdat het lokaal dingen uitrenderd. Ook kan het netwerkprotocol een stuk simpeler zijn in dit model, omdat het enkel verantwoordelijk is voor het versturen van delen van de dataset. De keuze keuze is gemaakt voor het thick-client model. Dit vereist een client systeem dat meer grafische kracht heeft. De systeemeisen kunnen alsnog laag worden gehouden door te kiezen voor een renderingsysteem die niet al te hoge eisen stelt. Ook is de winst in complexiteit van het netwerk systeem en de betere responstijd erg aantrekkelijk bij het thick-client model.
4.3.3 Threading Client computer
Client computer
Client Application
Client Application Data loading thread
Network
User Input
Rendering
User IO
Main drawing thread
RAM Network Cache Rendering
Graphical Output
User Input
(a) single-threaded client
User IO
Graphical Output
(b) multi-threaded client
Figuur 4.3: Client met of zonder multithreading.
De keuze om de rendering uit te voeren op de client maakt het noodzakelijk te kijken naar het executie model van de client. De drie modules die zeer globaal zijn te onderscheiden zijn de netwerk module, de render module en de gebruikers input-output module. Er dient bepaald te worden hoe de executie van deze modules op de client verloopt. In figuur 4.3a zijn connecties tussen verschillende modules te zien. Twee van deze connecties zijn het belangrijkst. De gebruikersinteractie waarmee de render module bepaalt wat het wilt renderen. En de render module die op basis van wat het wilt renderen de juiste data via de netwerk module inlaad. Deze client architectuur vereist in de meest na¨ıeve vorm een constante stroom aan data voor elke frame die gerenderd wordt, zelfs als opvolgende frames exact dezelfde data tonen. Het ligt voor de hand om op zijn minst een caching laag tussen de render module die data opvraagt en de netwerk module te plaatsen. Op deze manier kan de client data een enkele keer over het netwerk laden, waarna het hergebruikt kan worden zonder dat de client over het netwerk dezelfde data dient in te laden. Het model met een lokale caching laag in de client is een grote verbetering voor frames waar data wordt weergegeven die al eerder geladen is. Voor frames die data weergeven die nog niet in eerdere frames gecached is bestaat echter nog steeds een probleem in responsiviteit. Deze frames 20
zijn genoodzaakt te wachten op de netwerklaag, waardoor deze frames een zeer lange render tijd zullen hebben. Als een gebruiker invoer geeft waardoor het camerastandpunt verandert dan zal dit vaak betekenen dat nieuwe data in beeld komt. Dit zal betekenen dat vaak veel tijd zal verstrijken tussen het moment dat een gebruiker invoer geeft en het moment dat een gebruiker dit in de grafische uitvoer gereflecteerd ziet. Een alternatief is om de executie van de render module en de executie van de netwerk module te scheiden. Hier zijn een aantal opties te onderscheiden; de client kan bijvoorbeeld in meerdere processen opgedeeld worden. Een andere optie die waarschijnlijk simpeler is, is het gebruik maken van threading. Als de client in meerdere executie-eenheden wordt opgedeeld moet er een kanaal voor communicatie tussen de threads bestaan. Een stuk shared memory die met behulp van mutexen thread-safe wordt gemaakt is de meest voor de hand liggende oplossing hiervoor. De eerder genoemde caching laag lijkt een redelijke kandidaat voor dit communicatie kanaal, als deze als shared memory behandeld wordt tussen de threads. Hierbij kan de rendering laag aanvragen voor data naar de caching laag wegschrijven en data uitlezen. De netwerklaag kan nieuwe aanvragen uitlezen en nieuwe data die over het netwerk is binnengekomen wegschrijven naar de shared memory caching laag. Het nadeel van een muli-threaded systeem is de extra complexiteit die komt kijken bij het realiseren van de communicatie tussen de threads in een thread-safe manier. De performance en responsiviteit voor frames waar nieuwe data wordt geladen is in de single-threaded aanpak echter zo slecht dat toch gekozen is om de client multi-threaded te maken.
4.3.4 GPU Code Rendering Data stiching & interpolation
Geometry Generation
Projection & Rasterization
Figuur 4.4: De drie modules waar rendering ruwweg in opgedeeld kan worden. Het is de vraag hoe deze over de CPU en GPU te verdelen.
Voor de rendering module moet een keuze gemaakt worden hoe deze op de client draait. Bij real-time 3D rendering op moderne computers is vrijwel altijd sprake van een deel van het render werk dat op dedicated GPU hardware wordt uitgevoerd. Er moet beslist worden welk deel van het grafische werk op de GPU wordt uitgevoerd en welk deel op de CPU. Om de rendering module over de GPU en CPU te verdelen moet bepaalt worden uit welke onderdelen deze module bestaat. De render module kan ruwweg in drie fases worden opgebroken. De eerste fase neemt stukken data samen en interpoleert tussen detailniveaus en in de ruimte voor scaling. De uitvoer van deze fase geeft hoogtedata van het deel van de dataset die op dit moment in beeld is, met het detailniveau dat correct is voor de huidige camerapositie. De tweede fase stelt op basis van de hoogtedata een geometrische representatie op. De laatste fase neemt de geometrische representatie en past een projectie en rasterisatie stap toe om een framebuffer te vullen die aan de gebruiker getoond kan worden. De laatste fase kan op zijn minst worden uitgevoerd op de GPU. Projectie transformatie en rasterisatie zijn het minimum aan functionaliteit die op een GPU in plaats van een CPU worden uitgevoerd om een redelijke performance te halen bij 3D applicaties. Het is dan de vraag of de stap om datategels samen te voegen en te interpoleren op de GPU kan en of het aanmaken van 21
geometrie op de GPU kan. Zou dit lukken dan zal dit waarschijnlijk de performance ten goede komen. De GPU kan dingen met een hoger niveau aan parallellisatie uitvoeren. Het uitvoeren van zoveel mogelijk code op de GPU voorkomt daarnaast communicatie heen en weer tussen de CPU en GPU. De CPU en GPU zijn onderdeel van hetzelfde fysieke computer systeem. Het is echter mogelijk om de CPU en GPU bijna als twee aparte systemen te beschouwen. Ze hebben beide hun eigen executie-eenheden en hun eigen geheugen. En communicatie tussen de twee executie-eenheden en gegevensoverdracht tussen de twee geheugen systemen is relatief duur. Het zo veel mogelijk uitvoeren op de GPU voorkomt dat tussenberekeningen heen en weer tussen de twee delen van de computer moeten reizen. De keuze valt op het zoveel mogelijk uitvoeren op de GPU. De data die over het netwerk is ingeladen moet in het videogeheugen worden ingeladen. Dit is de belangrijkste taak van de CPU code. Daarna worden zoveel mogelijk van de berekeningen gedaan op de GPU met behulp van shader code. Het nadeel is mogelijk dat GPU code meer ontwikkeltijd vereist. Qua performance is het echter bijna zeker een verbetering zonder veel voor de hand liggende negatieve bijwerkingen.
22
HOOFDSTUK 5
Systeemoverzicht
server computer Data on HDD Arc/ Info Grid Files
RRD Files
Client computer
Server Application
Data loading thread
Client Application Main drawing thread
GPU data stitching shaders
Data loading RAM Caching Layer
Network protocol
Network protocol
RAM Caching Layer
Texture Manager
Renderer tessellation equivalent shaders
Data Normalization
Figuur 5.1: Globaal overzicht van het complete systeem in diagram vorm.
Het ontwikkelde systeem heeft globaal gesproken een server-client structuur. De server is verantwoordelijk voor het beschikbaar maken van data die in bestanden op een harde schijf staan aan clients over een netwerkverbinding. De clientapplicatie is verantwoordelijk voor het ontvangen van data en het aanbieden van data in een 3D omgeving aan de gebruiker. De server- en clientapplicatie zijn elk in een aantal lagen op te delen. De server heeft toegang tot de AHN2 data in bestanden, opgeslagen in de formaten zoals aangegeven in sectie 3.3. Het heeft een pre-processing laag die de datategels tot op zekere hoogte normaliseert. De volgende laag cached data in het werkgeheugen, om hardeschijftoegang en processingtijd voor laden en normalisatie te verlagen. De laatste laag is een netwerklaag om de data via een simpel wire protocol toegankelijk te maken. De client heeft ook een netwerklaag en een werkgeheugen caching laag. In de volgende laag wordt data naar het videogeheugen gestuurd. Zodra de data zich in het videogeheugen bevindt, dient het als input voor de laatste laag, welke een datavisualisatie rendering pipeline bevat.
5.1 Server 5.1.1 Data Loading De serverapplicatie heeft als eerste taak het inlezen van data uit de RRD en Arc/Info Grid bestanden. Om dit te realiseren zijn importers voor twee bestandsformaten ge¨ımplementeerd. Een alternatief was geweest om de Geospatial Data Abstraction Library (GDAL) te gebruiken, welke de gegeven bestanden naar andere, mogelijk makkelijker in te lezen bestandsformaten had kunnen converteren (bijvoorbeeld GeoTIFF) [9]. 23
Omdat Arc/Info Grid in het bijzonder een vrij simpel formaat is, is ervoor gekozen om de server direct de AHN2 bestanden te laten inlezen. Voor de RRD bestanden die lager detailniveau rasterinformatie leveren is het bestandsformaat wat ingewikkelder. De importer voor deze bestanden is daarom wat beperkter en kan niet per se alle mogelijke bestanden in dit formaat aan, maar enkel degene die door het AHN zijn aangeleverd. Het verdient opgemerkt te worden dat de keuze om geen GDAL te gebruiken waarschijnlijk tot extra ontwikkeltijd heeft geleid. En zelfs als de ontwikkeltijd gelijk was gebleven met het gebruik van GDAL, dan is het alsnog waarschijnlijk dat de keuze voor eigen importeer code het geheel minder algemeen bruikbaar maakt en gevoeliger maakt voor edge cases in bestanden. Maar omdat ´e´en van de doelen het onderzoeken was van het dataformaat, heeft de ontwikkeling van data importeer code bijgedragen aan het inzichtelijk krijgen van de exacte opslag van datapunten in de aangeleverde dataset. Ook geeft het realiseren van eigen importeer code wat meer controle over de exacte manier van laden, wat het makkelijker maakt om op dit vlak te experimenteren met het oog op performance karakteristieken.
5.1.2 Data Normalisatie Na het laden van data uit de geleverde bestanden is een normalisatiestap noodzakelijk. Het werk dat in deze stap wordt uitgevoerd is in twee categorie¨en te verdelen: het aanmaken van missende Level of Detail (LoD) rasters en het resizen van data zodat deze voor elke tegel gelijk is bij het aanbieden aan de client. Bij het aanmaken van missende detailniveaus moet gekeken worden naar welke data wordt aangeleverd. De Arc/Info Grid bestanden leveren de data op volledige resolutie, met 2000 bij 2500 datapunten voor een 1km bij 1.25km gebied per tegel. De RRD bestanden leveren grids met een 16de resolutie, een 64ste resolutie, een 256ste resolutie en een 1024ste resolutie. Er wordt geen laag met een 4de van de originele resolutie aangeleverd, dus deze wordt on-the-fly aangemaakt door de serverapplicatie. Verder is het zo dat niet elk RRD bestand rasters heeft voor elk van de vier genoemde resolutie niveaus. In deze gevallen worden de missende niveaus aangemaakt. De server moet ook een aantal minder gedetailleerde lagen leveren, die niet in de RRD bestanden zitten. Enkele tegels hebben geen RRD bestanden meegeleverd. In deze gevallen worden alle LoD rasters op basis van de Arc/Info Grid data aangemaakt. Voor het resizen van data wordt gekeken naar twee dingen: tegels die niet een 1km bij 1.25km gebied beslaan en data uit de RRD bestanden die niet altijd dezelfde resolutie heeft voor een bepaald detailniveau. Voor het eerste probleem wordt de gegeven data in een 1km bij 1.25km datagrid gepositioneerd die voor de rest met NODATA datapunten gevuld is. Voor het tweede probleem moet omgegaan worden met rasterlagen uit de RRD bestanden die voor een bepaald detailniveau verschillende dimensies hebben, zoals in sectie 3.2.3 beschreven is. Er is gekozen om de twee meest gedetailleerde niveaus gelijk te houden aan wat wordt aangeleverd. Vanaf het derde niveau wordt in plaats van 500 bij 625 de resolutie van 512 bij 640 gehanteerd. Er is gekozen om voor de laag met een 16de resolutie de dimensie van 500 bij 625 naar 512 bij 640 aan te passen, omdat bij deze resolutie het makkelijker is de lagere resolutie detailniveaus aan te maken. De dimensies zijn bij deze resolutie steeds exact door twee te delen zijn. Als data voor een detailniveau uit een RRD bestand beschikbaar is, wordt deze met een nearest neighbour interpolatie naar de gewenste resolutie aangepast.
24
Tabel 5.1: Resoluties voor de verschillende Level of Detail rasters per 1km bij 1.25km tegel.
Detailniveau
fractie resolutie
exacte resolutie
genormaliseerde resolutie
1
2000 bij 2500 1000 bij 1250 500 bij 625 250 bij 312.5 125 bij 156.25 62.5 bij 78.125 31.25 bij 39.0625 15.625 bij 19.53125 7.8125 bij 9.765625 3.90625 bij 4.8828125
2000 bij 2500 1000 bij 1250 512 bij 640 256 bij 320 128 bij 160 64 bij 80 32 bij 40 16 bij 20 8 bij 10 4 bij 5
0 1 2 3 4 5 6 7 8 9
1 4 1 16 1 64 1 256 1 1024 1 2048 1 4096 1 8192 1 16384
Als een nieuw raster moet worden aangemaakt op basis van een meer gedetailleerd raster dan kunnen steeds exact vier datapunten worden genomen als invoer voor een datapunt van het raster met lagere resolutie. Hierbij wordt het gemiddelde genomen om aan het datapunt te komen voor het lagere resolutie raster. Als een invoer datapunt een NODATA punt is dan wordt deze niet in het middelen meegenomen. Dit betekent dat bij lagere resolutie rasters NODATA gaten in de dataset langzaam ingevuld worden. De reeds gemaakte LoD rasters in de RRD bestanden gebruiken hetzelfde interpolatie algoritme voor het cre¨eeren van lagere resolutie rasters. Er is voor gekozen dit interpolatie algoritme over te nemen. Rasters op basis van RRD bestanden en rasters die compleet door de serverapplicatie worden aangemaakt krijgen op deze manier een gelijk uiterlijk.
5.2 Netwerkprotocol Om de data te versturen van server naar client wordt een simpel request-response wire protocol gebruikt bovenop een TCP verbinding. De server kent een aantal simpele commando’s waarmee een client een datategel of een set aan datategels kan opvragen, met een specifiek detailniveau. Elke netwerk sessie begint met het aanmaken van een TCP verbinding tussen de clientapplicatie en de serverapplicatie. Vanaf dit moment kan een client requests sturen naar de server. Zie figuur 5.2 voor de layout van een request.
0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Command X Y Level of Detail )
Width Height
Enkel voor command=2
Figuur 5.2: Formaat van een client→server request, alle velden zijn 32 bit signed integers.
Er zijn twee typen requests te onderscheiden. Bij het eerste is het command veld 1 en wordt een enkele datategel opgevraagd, op positie (X, Y ) met een specifiek detailniveau. Het tweede type heeft command veld 2 en vraagt een blok aan tegels op, met (X, Y ) als de positie van de meest zuidwestelijke tegel en een totaal aan width × height tegels. Zodra de request binnen is bij de server begint de server data terug te sturen. Het formaat van een response is te zien in figuur 5.3. 25
0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Compression Uncompressed Data Size Compressed Data Size
)
Enkel voor compression=1
Actual Data ···
Figuur 5.3: Formaat van een server→client response, alle velden zijn 32 bit signed integers behalve ‘actual data’.
Het eerste veld geeft aan of de response gecomprimeerde data bevat. Als de response niet gecomprimeerd is, dan weet de client hoeveel data de server terug zal sturen op basis van hoeveel datategels met een specifiek detailniveau zijn opgevraagd. Bij een gecomprimeerde response is de grootte van de response voor een client niet te voorspellen, omdat het niet weet hoe groot de data na compressie is. Om deze rede wordt de grootte van de data na compressie meegestuurd (wat de grootte van de data in het laatste veld is). Voor het gemak wordt ook de grootte van data na decompressie meegestuurd. Als de request het commando 2 is (een request voor meerdere tegels) dan worden alle verschillende datategels achter elkaar gestuurd, al dan niet gecomprimeerd. De tegels hebben in dit geval dus niet een aparte set aan header velden per tegel; er is ´e´en response per request en er is ´e´en set aan header velden per response. De volgorde van de tegels bij een response met meerdere tegels is van links naar rechts en van onder naar boven. Dus als bijvoorbeeld tegels worden gevraagd met (4, 5) als meest zuidwestelijke tegel, width = 3 en height = 2, dan komen de tegels terug in volgorde (4, 5), (4, 6), (4, 7), (5, 5), (5, 6), (5, 7). Het compressie-algoritme dat gebruikt wordt is DEFLATE, zoals ge¨ımplementeerd door de Zlib bibliotheek [Deu96]. Niet elke data respons wordt gecomprimeerd terug gestuurd. Dit is gereflecteerd in het ontwerp van het netwerkprotocol. Als de response een hele kleine set aan data terugstuurt is compressie niet altijd nuttig. Voor zeer grote responses met meerdere tegels is compressie ook niet altijd nuttig. Zonder compressie kan de client al data gebruiken als het gedeeltelijk een response heeft ontvangen. Dit is echter niet mogelijk als de response gecomprimeerd is; de client moet met gecomprimeerde data wachten tot de hele response binnen is. In deze gevallen kan het nuttig zijn om compressie te vermijden.
5.3 Client De clientapplicatie heeft drie hoofdtaken: het praten met de server over het netwerkprotocol om de correcte data in te laden, het weergeven van de data met behulp van een grafische pipeline en het aanbieden van een interface aan een gebruiker. De werking van de grafische pipeline wordt in detail behandeld in hoofdstuk 6. Het ontwerp van de interface wordt in detail behandeld in hoofdstuk 7. De werking van de client is in twee threads opgedeeld. E´en van de threads draait de grafische code en interface. Op basis van wat op dit moment in beeld is maar niet aanwezig is als texture worden aanvragen gedaan bij een data caching laag. Deze data caching laag is een thread-safe object dat door beide threads gebruikt wordt. De eerste thread gebruikt het om cache requests weg te schrijven en data uit te lezen. De tweede thread gebruikt het om requests uit te lezen en data weg te schrijven. Deze tweede thread is verantwoordelijk voor het draaien van de requests over het netwerk voor de gevraagde data.
26
De scheiding in twee threads is zeer belangrijk voor een stabiele performance. Het voorkomt dat de grafische tekenloop blocking requests tegenkomt; deze zijn alle in de tweede thread ondergebracht. De hoofdthread heeft tussen de grafische pipeline laag en de data cache laag nog een texture manager laag. Zodra data beschikbaar is, moet het inladen als texture van de data in de hoofdthread gebeuren; dit is ´e´en van de vereisten voor multithreading onder OpenGL.
5.3.1 Texture Manager De texture manager maakt per datategel een floating-point texture aan, zodat de grafische pipeline toegang tot de data heeft. De texture manager laag is ook verantwoordelijk voor het samenvoegen van data uit meerdere 1km bij 1.25 km tegels in ´e´en texture. Dit is nodig voor de zeer lage resolutie detailniveaus waar duizenden tot tienduizenden tegels in beeld kunnen zijn. Het aanmaken van deze hoeveelheid textures is op zich geen probleem, maar het switchen en rebinden van deze hoeveelheid textures in ´e´en frame is een enorme performance bottleneck. In tabel 5.2 is een overzicht te vinden voor het texture merging process. Tabel 5.2: Overzicht van aanpak texture merging. Voor meer informatie over resolutie per datategel, zie sectie 5.1.2.
Detail Niveau 0 1 2 3 4 5 6 7 8 9
gebied per texture
aantal tegels samengevoegd
resolutie per datategel
1km bij 1.25 km 1km bij 1.25 km 1km bij 1.25 km 1km bij 1.25 km 1km bij 1.25 km 2km bij 2.5 km 4km bij 5 km 8km bij 10 km 16km bij 20 km 32km bij 40 km
1 1 1 1 1 4 16 64 256 1024
2000 bij 2500 1000 bij 1250 512 bij 640 256 bij 320 128 bij 160 64 bij 80 32 bij 40 16 bij 20 8 bij 10 4 bij 5
resolutie per texture 2000 1000 512 256 128 128 128 128 128 128
bij bij bij bij bij bij bij bij bij bij
2500 1250 640 320 160 160 160 160 160 160
De keuze voor waar begonnen wordt met het mergen van datategels in textures is in de huidige implementatie enigszins arbitrair en zou nader onderzocht kunnen worden. Het was echter duidelijk dat zonder texture merging de performance zeer laag werd bij een camerastandpunt van waaruit een groot deel van Nederland op laag detailniveau zichtbaar is. Texture mergen brengt een probleem met zich mee. Wat als enkel een deel van het gebied bestreken door een gemergde texture in beeld is en waar enkel datategels voor het deel in beeld zijn geladen? De texture kan dan niet worden aangemaakt, omdat niet alle datategels die de texture nodig heeft geladen zijn. Moet dan alsnog heel veel extra data over het netwerk opgevraagd worden om een texture te kunnen aanmaken? Dit is een optie, maar deze aanpak zou erg veel overbodige data inladen die niet in beeld is en mogelijk nooit in beeld komt. In plaats hiervan is een systeem gebouwd waar de texture manager tijdelijke gemergde textures kan aanmaken waar het eigenlijk nog niet alle benodigde datategels voor heeft. Elke frame wordt gecontroleerd of ondertussen extra data is binnengekomen die binnen het gebied valt die door een tijdelijke texture bestreken wordt. Zo ja, dan wordt de tijdelijke texture vernietigd en een nieuwe (al dan niet tijdelijke) texture aangemaakt. Deze aanpak heeft als bijkomend voordeel dat als een gemergde texture wel volledig in beeld is, maar meerdere frames nodig heeft om in te laden, hij al in eerdere frames zichtbaar kan worden gemaakt.
5.3.2 Data Requests over Netwerk De requests voor data gebeuren in een aparte thread. Deze thread neemt steeds de meest recente aanvraag uit de hoofdthread, kijkt hoeveel van die aanvraag al lokaal aanwezig is en probeert dan de niet aanwezige data over het netwerk uit de server op te halen. De aanvragen van de 27
hoofdthread komen binnen als rechthoekige secties van het terrein met een bepaald detailniveau die de hoofdthread op dit moment nodig heeft. Zoals uit het netwerkprotocol af te leiden is kunnen requests voor individuele tegels gedaan worden of voor een rechthoekig blok aan tegels. De client probeert data op te vragen met een minimum aan requests. Het neemt de huidige aanvraag en kijkt welke gebieden van de aanvraag nog niet geladen zijn. Het probeert deze gebieden dan te vullen met rechthoeken. Voor elk van deze rechthoeken wordt dan een netwerk request gedaan. Deze stap is belangrijk, omdat het doen van een request per tegel zeer veel overhead geeft. E´en aanvraag per tegel zou betekenen dat veel extra dataverkeer nodig is vanwege extra request en response headers. Dit verkeer kan verminderd worden met requests die meerdere tegels opvragen. Daarnaast leidt een request per tegel tot een extra request-response interactie per tegel, met bijbehorende roundtrip tijd. Dit zou het laden van tegels over het netwerk een stuk trager maken.
28
HOOFDSTUK 6
Rendering Pipeline
Het doel van het ontwikkelde systeem is om de dataset te visualiseren op een aantrekkelijke manier, zonder een accurate weergave op te offeren. De visualisatie is bedoeld om de data inzichtelijk te maken. Een goed ontworpen user experience is hiervoor noodzakelijk. Onder user experience valt een goed interface ontwerp, maar ook een voldoende hoge en stabiele performance. Dit geeft de context voor de twee hoofddoelen van de rendering pipeline: zoveel mogelijk de originele data gebruiken en dit doen met een zo hoog mogelijke performance. Naast deze twee hoofdrestricties is gekozen om OpenGL 2 te nemen als platform, in plaats van een moderner grafisch platform zoals OpenGL 4. Dit betekent dat enkel fragment en vertex shaders gebruikt worden en geen geometry of tessellation shaders. Hier is voor gekozen omdat OpenGL 2 door een grotere hoeveelheid PC hardware ondersteund wordt (waaronder een specifiek touchscreen systeem dat binnen de UvA aanwezig is). Een ander voordeel van de keuze voor OpenGL 2 is dat de restricties die deze versie van OpenGL met zich meebrengt ongeveer dezelfde zijn als de restricties die OpenGL ES 2 heeft. Dit betekent dat een OpenGL 2 pipeline makkelijker te porten is naar platformen die de ES 2 API ondersteunen, zoals smartphones en tablets. Daarnaast is WebGL – de 3D API standaard voor het web – een implementatie van OpenGL ES 2, wat betekent dat porten naar het web ook makkelijker is (zeker met tools als Emscripten en ASM.JS). Globaal is de rendering pipeline op te delen in drie fases. In de CPU code worden berekeningen gedaan waarmee vastgesteld wordt wat op een bepaald moment in beeld is en met welk detailniveau. Op basis hiervan worden aanvragen gedaan over het netwerk voor deze data. Ook wordt op basis van dezelfde berekeningen een geometrische representatie van de wereld opgebouwd die net voldoende is om de data aan elkaar te plakken, maar niet genoeg om de volledige 3D informatie die in de data zit te visualiseren. Deze data gaat naar een eerste set aan shaders. Deze krijgen de data als floating-point textures binnen, zodat zoveel mogelijk in de GPU gewerkt kan worden met de originele datapunten. Deze shaders interpoleren de data zodat verschillende datategels worden samengevoegd, met de scaling en detailniveau die nodig is voor de huidige camerapositie. De output van deze eerste shaderstage is een hoogtemap, met datapunten die perspectivisch correct zijn weergegeven vanuit de camerapositie. De laatste shader stage krijgt een hoogtemap binnen, samen met een vast raster aan geometrie. Dit raster is voor elke frame gelijk. Het raster wordt op het deel van het z = 0 vlak geplaatst dat voor het huidige frame in beeld is. Dit gebeurt in de shaders met behulp van informatie over de camera. Met informatie van de hoogtemap uit de eerste render stage wordt het raster vervormd zodat het de hoogtedata weergeeft. 29
6.1 CPU Code Voor maximale performance dient zoveel mogelijk werk op de GPU in shader code te worden gedaan. Een aantal taken kunnen echter niet op de GPU uitgevoerd worden. De CPU moet weten wat op elk moment in beeld is van de dataset. Het moet verder weten met welk detailniveau dit gebied in beeld is. Dit is noodzakelijk, omdat de CPU code de netwerk aanvragen voor deze data doet. Verder moeten vanuit de CPU de textures worden aangemaakt, een geometrie layout worden aangemaakt waarmee de datategels in de shader aan elkaar worden geplakt en de CPU moet de texture binding doen voor de textures die op dit moment in beeld zijn.
6.1.1 Bepalen Zichtbaar Gebied
Figuur 6.1: Illustratie van kijk frustum (groene lijnen), intersectie frustum met z = 0 vlak (groene polygoon), axis-aligned rechthoek (rood) en ingeladen data (zwart-wit).
Om te bepalen welk deel van de dataset zichtbaar is wordt de intersectie tussen het kijkvolume (het zogenaamde camera frustum) en het vlak waar het terrein zich bevindt gevonden. Voor het vlak is de vergelijking z = 0 een redelijke benadering van waar de hoogte-informatie zich bevindt (zeker voor een plat land als Nederland) en goed genoeg om de correcte data in te laden. Om de intersectie te vinden tussen het camera frustum en het vlak worden de locaties van de vertices van het frustum gevonden. Op basis van de vertices worden vergelijkingen opgesteld voor de lijnstukken tussen deze punten. De snijpunten tussen de set aan lijnen en het vlak worden daarna gezocht. De combinatie aan snijpunten die worden gevonden geven de hoekpunten aan van de polygoon die het gebied beschrijft van het z = 0 vlak dat op dit moment in beeld is. Dit is de groene polygoon in figuur 6.1. Nadat de hoekpunten van de polygoon zijn gevonden kan een zogenaamde axis-aligned rectangle opgesteld worden, die de polygoon als subsectie heeft. Het is makkelijker te rekenen met een rechthoek dan een willekeurige polygoon, dus vandaar de keuze hiervoor. Daarnaast wordt de data ook in rechthoeken aangeleverd die axis-aligned zijn, wat betekent dat het opvragen van data makkelijker is als axis-aligned rectangles gebruikt zijn bij het bepalen van welke data wordt inladen. De axis-aligned rectangle is rood in figuur 6.1. 30
6.1.2 Bepalen Detailniveaus Als de rechthoek is gevonden waarbinnen het zichtbare terrein zich bevindt moet bepaald worden welke detailniveaus nodig zijn voor het zichtbare terrein. Met een bepaald detailniveau is een bepaalde afstand van de camera geassocieerd waar de camera exact de hoeveelheid detail in dat detailniveau kan zien. Alle punten die een specifieke afstand tot de camera hebben vormen een bol met de camera als middelpunt. De intersectie wordt genomen tussen de bollen die de afstand aangeven waar een bepaald detailniveau weergegeven wordt en het vlak z = 0. De punten worden genomen waar de vergelijkingen p (x − Xc )2 + (y − Yc )2 + (z − Zc )2 = R en z = 0 beide waar zijn, met R als radius van de bol, (Xc , Yc , Zc ) het middelpunt van de bol en (x, y, z) de set aan snijpunten met het vlak. p (x − Xc )2 + (y − Yc )2 + (z − Zc )2 = R p (x − Xc )2 + (y − Yc )2 + (0 − Zc )2 = R q (x − Xc )2 + (y − Yc )2 + Zc 2 = R (x − Xc )2 + (y − Yc )2 + Zc 2 2
(x − Xc ) + (y − Yc ) p
2
(x − Xc )2 + (y − Yc )2
= R2 = R 2 − Zc 2 q = R 2 − Zc 2
Als de tweedimensionale ruimte die door het vlak beschreven wordt genomen wordt, dan kan de laatste vergelijking geplaatst worden in deze context. In de ruimte beschreven door p het vlak liggen de punten (x, y) in een cirkel met het middelpunt (Xc , Yc ) en een radius van R2 − Zc 2 . Om deze cirkel kan wederom een axis-aligned rectangle gelegd worden, zoals eerder met de frustumvlak intersectiepolygoon gedaan was. Op basis van deze berekeningen is een set rechthoeken bepaald die aangeven waar een bepaald detailniveau geldig is en een rechthoek die aangeeft wat zichtbaar is van het z = 0 vlak. Het rest enkel om de overlap tussen de detailniveau rechthoeken en de zichtbaarheidsrechthoek te nemen om te weten wat met welk detailniveau moet worden geladen.
(a)
(b)
Figuur 6.2: (a) Verschillende detailniveaus in verschillende gekleurde ringen. De onderliggende geometrie waaraan de textures zijn gebonden is weergegeven met rode lijnen. In (b) wordt de camera van (a) vanuit een extern perspectief weergegeven. Lagere resolutie detailniveau ringen gebruiken grotere textures om minder geometrie te hoeven aanmaken om textures aan te binden, zoals behandeld in sectie 5.3.1.
Op basis van dezelfde rechthoeken wordt ook geometrie aangemaakt waaraan de ingeladen data als floating-point textures wordt gekoppeld. Aan elke rechthoek van een bepaald detailniveau k wordt zowel data voor niveau k en het gedetailleerdere niveau k − 1 gekoppeld. Dit wordt gedaan zodat de shader kan interpoleren tussen twee detailniveaus. 31
6.2 Eerste Render Stage De eerste render stage bestaat uit een vertex en een fragment shader. Als input krijgen deze shaders geometrie waaraan twee floating-point textures gebonden zijn. De data in de floatingpoint textures heeft wereldco¨ ordinaten die aangeven waar in de wereld de data geplaatst dient te worden (zogenaamde georeference co¨ordinaten). De co¨ordinaten van de geometrie neemt deze wereldco¨ ordinaten over. De shaders krijgen ook de camerapositie binnen. Op basis hiervan kan in de fragment shader voor elk fragment de afstand tot de camera berekend worden. Op basis van deze afstand kan het benodigde detailniveau bepaald worden. De fragment shader controleert dan of het detailniveau voor het huidige fragment (welke een re¨eel getal is) tussen de twee detailniveaus ligt waarvoor het data tot zijn beschikking heeft. Zo ja, dan rendert de shader het fragment met data uit de twee gegeven floating-point textures. Het interpoleert tussen deze twee op basis van het eerder berekende fragment specifieke detailniveau. Als het detailniveau voor het huidige fragment echter niet valt binnen de detailniveaus van de textures die de shader tot zijn beschikking heeft, dan tekent de shader niet: het doet een discard in GLSL termen. Dit heeft als resultaat dat een serie ringen wordt getekend. Elk van de ringen behoort bij een combinatie aan data uit twee detailniveaus. Elke ring heeft aan de binnenkant een cirkel met de radius die hoort bij het meest gedetailleerde detailniveau van de twee en de buitenkant hoort bij de cirkel met de radius met het minder gedetailleerde detailniveau. Dit zijn dezelfde cirkels zoals behandeld in sectie 6.1.2.
(a)
(b)
(c)
Figuur 6.3: (a) Een 3D weergave van dieptedata. (b) Dezelfde weergave met verschillende detailniveau ringen gemarkeerd met verschillende kleuren. (c) Een extern perspectief met de camera op dezelfde plek. Groene lijnen geven kijk frustum aan. De ringen geven aan wat geladen is met verschillende detailniveaus om vanuit het perspectief van (a) en (b) uit te renderen.
In figuur 6.3 is goed zien dat in ringen wordt gerenderd. Elke stap laat een gat in de vorm van een cirkel die door geometrie waar meer gedetailleerde textures aan gebonden is wordt ingevuld. Als laatste moet worden opgemerkt worden dat discard, het commando om de gaten te maken, negatieve performance implicaties heeft. Bepaalde hardware optimalisaties waar meerdere fragments worden samengenomen kunnen niet gedaan worden als discard commando’s in een shader worden gebruikt. Het is daarom mogelijk nuttig te kijken naar andere manieren om gaten te slaan (bijvoorbeeld met OpenGL blend functionaliteit). De fragment shader schrijft geen RGB kleurwaarden naar een framebuffer, maar floating-point getallen met hoogtewaarden. Dit wordt naar een floating-point texture geschreven die gekoppeld is aan een Framebuffer Object (FBO).
6.3 Tweede Render Stage De tweede render stage bestaat wederom uit een vertex en fragment shader. Als input wordt de floating-point texture gebruikt die de output van de eerste render stage was. Daarnaast krijgen 32
de shaders een vaste set aan geometrie als invoer. Deze geometrie wordt ´e´en keer aangemaakt en opgeslagen in een Vertex Buffer Object (VBO).
(a)
(b)
(c)
(d)
Figuur 6.4: (a) Het geometrie grid opgebouwd uit rechthoeken (wit), geplaatst voor de camera (frustum met groene lijnen). (b) Raycasting lijnen (rood) door de hoekpunten van de rechthoeken, op zoek naar snijding met het z = 0 vlak. (c) Het grid wordt geplaatst op de snijpunten met het vlak gevonden door de raycasting. (d) Detail view van grid nadat het geplaatst is door de raycasting stap. Het is te zien dat niet elk hoekpunt een raycasting lijn heeft, wat enkel voor dit plaatje zo is (de lijnen zouden anders te veel informatie verbergen). In werkelijkheid wordt een raycasting berekening voor elk hoekpunt gedaan.
De geometrie bestaat uit een grid aan rechthoeken (OpenGL quads om precies te zijn). De hoekpunten van de rechthoeken hebben hetzelfde aantal in de breedte en de hoogte als het aantal pixels van de output van de eerste render stage. Dit grid wordt met behulp van een ingegeven matrix geplaatst voor de camera. Voor elke vertex wordt daarna in de vertex shader een vergelijking opgesteld van de lijn tussen de camera en de vertex. Met behulp van een raycasting algoritme wordt gevonden waar deze lijn het z = 0 vlak snijdt. Met de uitkomst van het raycasten in de vertex shader kan het grid aan rechthoeken geplaatst worden op de positie van het terrein dat op dit moment in beeld is. Dit proces is in figuur 6.4 te zien.
(a)
(b)
(c)
Figuur 6.5: Nadat met raycasting de geometrie grid op de juiste plek is gezet (a) wordt de hoogtedata uit de eerste render stage genomen (b) en over de geplaatste geometrie gelegd (c).
Nadat de geometrie is geplaatst in de ruimte wordt de hoogte-informatie uit de eerste shaderstage over het grid gelegd (zie figuur 6.5). Dit gebeurd in de vertex shader. De laatste stap die in de vertex shader gebeurd is dat de hoogte component van de grid hoekpunten wordt aangepast. Omdat het grid geplaatst is door te raycasten met het z = 0 vlak, hebben alle hoekpunten een waarde van 0 voor de z component. Door de hoogte-informatie uit de eerste shaderstage te samplen kan dit worden aangepast, waarbij het grid wordt vervormt om het hoogteverloop van het terrein weer te geven (figuur 6.6).
33
(a)
(b)
Figuur 6.6: (a) Output van de eerste render stage, met slechts een kleur mapping toegepast om aan de floating-point waarden grijswaarden toe te kennen. (b) Deformatie van terrein door de tweede render stage, met dezelfde kleur mapping als (a).
De functionaliteit die in deze render stage is gerealiseerd lijkt erg op wat in tessellation shaders mogelijk is. Omdat gekozen is enkel OpenGL 2 technologie te gebruiken is deze functionaliteit niet beschikbaar. Het is echter toch mogelijk gebleken om equivalente functionaliteit te bouwen die kan draaien op systemen waar minder strenge systeemeisen aan zijn gesteld.
34
HOOFDSTUK 7
Interface Om de data inzichtelijk te maken is het nodig de data accuraat en aantrekkelijk weer te geven. De gebruiker moet ook de mogelijkheid hebben de dataset te verkennen. Hiervoor is een intu¨ıtieve interface belangrijk. De gebruiker moet snel kunnen leren omgaan met de applicatie. Multi-touch interfaces zijn bij uitstek geschikt om geografische datasets toegankelijk te maken voor ruimtelijke verkenning [JLG+ 12]. Ze bieden de mogelijkeid om verscheidene interactie mogelijkheden aan te bieden via ´e´en input apparaat. Daarnaast zullen veel gebruikers reeds bekend zijn met multi-touch interfaces die voor consumentenapparaten beschikbaar zijn, zoals tablets, smartphones en multi-touch trackpads. Om het user interface design “Principle of Least Astonishment”principe te volgen is gekozen om een aantal multi-touch interacties te implementeren waar een gebruiker van bijvoorbeeld Google Earth op multi-touch devices al mee bekend zal zijn. Dit zijn ook de interacties die in andere wetenschappelijke visualisatie toepassingen met een multi-touch interface gebruikt worden [BRS+ 10].
7.1 Zoomen
(a)
(b)
(c)
Figuur 7.1: De twee gele cirkels geven de positie van de twee vingers. In (a) heeft de gebruiker net haar vingers op het multi-touch apparaat gelegd zonder ze te bewegen. In (b) zijn de vingers uit elkaar gegaan t.o.v. (a) en is het terrein dichterbij gekomen. In (c) zijn de vingers dichterbij elkaar t.o.v. (a) en de camera staat nu verder van het terrein af.
Voor het zoomen worden twee vingers gebruikt. De gebruiker kan door de twee vingers van elkaar af te bewegen inzoomen en het terrein dichter bij de camera halen. Door de vingers dichter bij elkaar te brengen kan de gebruiker de camera verder van het terrein af bewegen. Deze interacties zijn ge¨ıllustreerd in figuur 7.1. In het geval waar de camera recht naar beneden kijkt is het zoomen equivalent aan een tweedimensionale zoom. Dit maakt deze gevallen voor de hand liggend qua implementatie. Als zoomen 35
wanneer de camera gekanteld is een mogelijke interactie is, dan moet deze kanteling in het zoomen worden meegenomen.
(a)
(b)
(c)
(d)
Figuur 7.2: Zoomen van een camera met een tilt. De gele cirkels geven de positie van de twee vingers aan. De rode cirkel geeft de positie tussen de twee vingers aan. Wat zich onder de rode cirkel bevindt bepaalt de richting van het zoomen. In (a) hebben de vingers nog niet bewogen. Bij (b) zijn ze uit elkaar en is het terrein dichterbij, bij (c) zijn de vingers bij elkaar en is het terrein verder weg. (d) Het kijk frustum van (a) in groen en de zoom richting (rode lijn) van (a).
Om zoomen in een 3D omgeving correct te laten verlopen wordt er gezoomd naar het punt van het terrein dat zich tussen de twee vingers bevindt. Het schermco¨ordinaat van dit punt wordt bepaald, waarna met behulp van een raycasting algoritme het punt van het terrein dat zich daar op het scherm bevindt wordt achterhaald. De vector die tussen dit punt en de camerapositie ligt bepaalt de richting van het zoomen. Deze vector is duidelijk te zien in figuur 7.5d.
7.2 Rotatie Voor rotatie wordt wederom eerst het scenario waar de kijkrichting haaks staat op het terrein genomen. De camera kijkt dus eerst recht naar beneden. Dit geval is conceptueel eenvoudiger, omdat de rotatie gelijk is aan een tweedimensionale rotatie. Het is makkelijker in te schatten wat het verwachte gedrag is.
36
(a)
(b)
(c)
Figuur 7.3: De twee gele cirkels geven de positie van de twee vingers. De rode cirkel geeft de positie tussen de twee vingers en bepaalt de as waaromheen gedraaid wordt. Bij (a) zijn de vingers net neergezet, bij (b) hebben ze iets met de klok mee gedraaid en bij (c) zijn ze verder met de klok meegedraaid. Het terrein volgt de draaiing van de vingers.
De gebruiker gebruikt twee vingers om het terrein te roteren. Hierbij draaien de vingers om een imaginair middelpunt dat tussen de twee vingers ligt. Dit middelpunt bepaald het punt waaromheen het terrein draait. De hoeveelheid draaiing van de vingers bepaalt de hoeveelheid draaiing van het terrein.
(a)
(b)
(c)
(d)
(e)
(f)
Figuur 7.4: De twee gele cirkels in (a), (b) en (c) geven de posities van twee vingers aan. Deze draaien met de klok mee. (d), (e) en (f) laten de cameraposities van (a), (b) en (c) vanuit een extern perspectief zien. De vector tussen de camera en het punt onder de vingers is in beeld (rode lijn). Ook de vector waaromheen gedraaid wordt is te zien (gele lijn), welke loodrecht op het terrein vlak staat.
Bij het draaien met een gekantelde camera wordt gekeken naar het punt dat tussen de twee vingers ligt. De vector tussen de camera en het terrein dat onder dit punt ligt is te zien in figuur 7.4. Het lijkt logisch om deze vector als draaiings-as te gebruiken. Dit zou echter betekenen dat de horizon niet meer horizontaal zou staan vanuit de camera. Dit is iets dat vermeden dient te worden, omdat de gebruiker zijn ruimtelijke houvast anders kan kwijtraken. In plaats daarvan is een andere draaings-as gekozen. Het punt van het terrein dat tussen de vingers ligt wordt genomen en een vector wordt opgesteld dat vanaf dit punt recht omhoog gaat. Dit is de draaings-as, waarbij tijdens de rotatie de kantelhoek van de camera behouden blijft. In figuur 7.4 draait de rode vector om de gele vector en behoudt de rode vector dezelfde hoek ten opzichte van de gele vector. 37
7.3 Camera Bewegen
(a)
(b)
(c)
(d)
Figuur 7.5: Twee vingers worden met gele cirkels aangegeven in (a) en (b). Het middelpunt tussen de vingers is met een rode cirkel gemarkeerd. Hetzelfde stuk terrein blijft onder de rode cirkel wanneer de vingers bewegen tussen (a) en (b). (c) en (d) geven de cameraposities van (a) en (b) weer vanuit een extern perspectief. Het uiteinde van de rode vector blijft op hetzelfde punt van het terrein zitten tijdens de translatie terwijl de camera beweegt.
Voor het bewegen van de camera worden wederom twee vingers gebruikt. De positie van het terrein dat tussen de twee vingers ligt wordt bepaald. Als de vingers bewegen zodat dit punt ergens anders op het scherm terecht komt, dan wordt bepaald wat het nieuwe punt van het terrein is dat nu tussen de vingers ligt. De vector die tussen deze twee punten van het terrein ligt – het punt bij de start van de vingerbeweging en het punt bij het einde – kan dan worden opgesteld. Dit is de vector waarmee in omgekeerde richting de camerapositie wordt getransleerd. Dit heeft als effect dat het lijkt alsof hetzelfde stukje van het terrein onder de vingers blijft zitten wanneer de vingers bewegen. Verder werkt het goed samen met de zoom en rotatie interacties. Als het middelpunt tussen de vingers bij het zoomen of roteren een beetje verspringt, dan zorgt de translatie stap dat hetzelfde punt van het terrein tussen de vingers blijft liggen.
7.4 Kijkrichting Camera Voor het veranderen van de kijkrichting van de camera worden drie vingers gebruikt. Bij deze vorm van interactie blijft de camera op dezelfde positie in de ruimte. De camera verandert enkel de kijkhoek ten opzichte van het terrein.
38
(a)
(b)
(c)
(d)
(e) Figuur 7.6: De drie gele cirkels geven de posities van drie vingers aan. De vingers beginnen in het midden bij (c). Bij (b) en (d) zijn de vingers respectievelijk naar rechts en naar links bewogen t.o.v. (c), waarbij de camera naar links en naar rechts is gedraaid. Bij (a) en (e) zijn de vingers respectievelijk naar beneden en naar boven bewogen t.o.v. (c), waarbij de camera naar beneden en naar boven is gedraaid.
Als naar figuur 7.6 gekeken wordt, dan is te zien dat de camera zich in de tegengestelde richting van de vingers draait. Dit is gedaan om de gebruiker het gevoel te geven dat het terrein ongeveer onder de vingers blijven zitten tijdens de beweging van de vingers. Dit is niet zo exact bedoelt als wat bij sectie 7.3 is gerealiseerd om het terrein onder de vingers te houden. Het terrein kan ingebeeld worden als een projectie op een bol. Om de kijkrichting interactie voor te stellen kan deze inbeelding gebruikt worden. De vingers pakken de bol en draaien deze wanneer ze bewegen. Een andere optie waarmee de interactie kan worden voorgesteld is dat wanneer de vinger naar links en rechts bewegen ze de camera laten nee knikken. En als de vingers naar boven en beneden bewegen laten ze de camera ja knikken.
39
40
HOOFDSTUK 8
Meetresultaten Bij het ontwerpen van het systeem zijn een aantal keuzes gemaakt. De aanname was dat deze keuzes ten goede zouden komen van onder andere de performance en responsiviteit. Om te testen of de onderliggende aannames correct waren zijn metingen uitgevoerd met meerdere versies van de software, waar een gemaakte keuze wordt gecontrasteerd met een versie waar deze keuze anders is gemaakt.
8.1 Test Omgeving De server gebruikt voor het testen is een systeem met een Intel Xeon E5620 processor draaiende met een kloksnelheid van 2.4 Ghz, met 4 cores die een totaal van 8 threads kunnen draaien (2 threads per core). Op het systeem zijn 24 GB aan RAM geheugen aanwezig. De software omgeving van de server is de x86-64 versie van Ubuntu 10.04.4 LTS met de 2.6.32-24-server #43-Ubuntu SMP Linux kernel. De client omgeving draait op een 2012 MacBook Pro (type 9,1) met een Intel Core i7 processor draaiende met een kloksnelheid van 2.3 Ghz, met 4 cores die een totaal van 8 threads kunnen draaien (2 threads per core). Op het systeem zijn 4 GB aan 1600 MHz DDR3 RAM geheugen aanwezig. De software omgeving van de client is OS X 10.9.3. De GPU van het client systeem is een NVIDIA GeForce GT 650M videokaart met 512 MB videogeheugen. Het systeem heeft daarnaast ook een Intel HD Graphics 4000 GPU, maar deze draait niet tijdens het testen. De netwerkverbinding van de server heeft een upload snelheid naar de client van ongeveer 1.1 MB/s. Deze is gevonden door met scp een bestand van de server naar de client te versturen. De server heeft een download snelheid van ongeveer 5.5 MB/s, gevonden door met wget het bestand http://speedtest.wdc01.softlayer.com/downloads/test10.zip op te halen. Het client systeem heeft een netwerkverbinding met een download snelheid van ongeveer 113 Mb/s (14 MB/s) en een upload snelheid van ongeveer 6 Mb/s (0.75 MB/s). Deze snelheden zijn gevonden met speedtest.net.
8.2 Test Scenario’s Om de metingen te verrichten zijn een aantal test scenario’s uitgewerkt. Bij deze scenario’s kan de camera in de client een set aan vaste posities innemen die vooraf ingeprogrammeerd zijn. Dit lijdt tot een systeem dat meerdere malen gedraaid kan worden op gelijke wijze, waarbij enkel het aspect van het systeem dat onderzocht wordt gevarieerd wordt. Scenario A Laat de camera boven het midden van Nederland beginnen, recht naar beneden kijkend. De camera begint op een hoogte van 1km. In een minuut verplaatst de camera zich hierna van 1km naar 150km hoogte. De verplaatsing gebeurt met een constante snelheid. In een 41
tweede minuut verplaatst de camera zich dan van 150km naar 100m hoogte. Dit test scenario neemt dus in totaal 2 minuten in. Scenario B Laat de camera ook boven het midden van Nederland beginnen, recht naar beneden kijkend. De camera begint op een hoogte van 180 m. De camera blijft daarna 20 seconden stilstaan. Daarna verdubbelt de camera zijn hoogte (naar 360 m) en blijft daarna 20 seconden stilstaan. Dit verdubbelen en stilstaan herhaald zich tot de camera een hoogte van 180 m × 210 = 184.32 km heeft bereikt. De camera blijft nog 20 seconden stilstaan, waarna de test eindigt. Dit test scenario neemt een totaal aan 220 seconden in. Metingen zijn genomen met een client die op een resolutie van 800 bij 600 draait. De verticale synchronisatie (vsync) staat uit tijdens de metingen.
8.3 Tests op een Single-Threaded versus Multi-Threaded Client E´en van de ontwerp beslissingen die voor het systeem is genomen is om de client multi-threaded te maken. Zoals in sectie 4.3.3 te lezen is was de motivatie het voorkomen van lange pauzes bij frames waar nieuwe informatie in beeld komt. Om dit te testen is het systeem gedraaid met test scenario A, met de client in zowel een singlethreaded als multi-threaded modus. Scenario A is gekozen omdat de camera constant in beweging is, waardoor het vaak delen van het terrein en detailniveaus in beeld zal hebben die nooit eerder gezien zijn. Aangezien dit het verwachte struikelblok van de single-threaded aanpak is geeft scenario A een mogelijkheid dit te testen. Daarnaast gaat een deel van de camera beweging in scenario A langs terrein dat al eerder gezien is, waar gekeken kan worden of het inderdaad correct was aan te nemen dat in deze gevallen het single-threaded model minder problemen heeft, zolang het een cache laag heeft.
(a)
(b)
(c) Figuur 8.1: Metingen van de client in single-threaded modus. Bij (c) is te zien wat tijdens de 120 seconden durende test de framerate was van de client. Bij (a) wordt dezelfde data uit (c) puntsgewijs weergegeven. Bij (b) is een frequentie plot gemaakt, waarbij is gekeken hoeveel frames er zijn met een bepaalde framerate. De drie verticale lijnen bij (b) representeren van links naar rechts het gemiddelde min de standaardafwijking, het gemiddelde en het gemiddelde plus de standaardafwijking van de framerate.
42
Als naar figuur 8.1 gekeken wordt dan is voor ongeveer de eerste 45 seconden een zeer lage framerate te zien. Dit ligt in de periode van scenario A waar de camera verder naar boven gaat en waar dus vaak een frame met nieuwe data in beeld zal voorkomen. In deze periode van de test worden maar enkele frames per seconde getekend, omdat de client veel tijd kwijt is met het wachten op data die over het netwerk vanuit de server verstuurd wordt. In de periode van 45-60 seconden van de test schommelt de framerate tussen zeer laag en relatief hoog; tussen over de 60 en onder de 10. Dit is de fase waar de camera hoog genoeg is dat enkel het minst gedetailleerde detailniveau nodig is. Het moet dus af en toe nieuwe data laden dat in beeld komt, maar hoeft niet compleet nieuwe detailniveaus te laden zoals eerder in de test. In de periode tussen de 60 en de 90 seconden (ongeveer) is de framerate relatief stabiel en hoog. Dit is de periode waar de camera daalt en hoogtes langsgaat die het eerder heeft gepasseerd. De single-threaded versie van de client heeft wel de lokale caching laag die in sectie 4.3.3 genoemd was. Het is te zien dat dit inderdaad effectief is in het verbeteren van performance wanneer er frames zijn met terrein dat eerder geladen is geweest. In de laatste 30 seconden van de test begint de framerate weer sterk te oscilleren. Dit omdat de camera lager is dan het ooit geweest is in deze periode. Hetzelfde fenomeen als in de periode van 45-60 is hier waar te nemen.
(a)
(b)
(c) Figuur 8.2: Metingen van de client in multi-threaded modus. Bij (c) is te zien wat tijdens de 120 seconden durende test de framerate was van de client. Bij (a) wordt dezelfde data uit (c) puntsgewijs weergegeven. Bij (b) is een frequentie plot gemaakt, waarbij is gekeken hoeveel frames er zijn met een bepaalde framerate. De drie verticale lijnen bij (b) representeren van links naar rechts het gemiddelde min de standaardafwijking, het gemiddelde en het gemiddelde plus de standaardafwijking van de framerate.
In figuur 8.2 is dezelfde meting gedaan, maar met een multi-threaded client. De gemiddelde framerate is bijna twee keer zo hoog is als bij de single-threaded versie. Daarnaast zijn er geen lange perioden waar bijna geen frames getekend worden. Er zijn wel enkele momenten waar dips in de framerate aanwezig zijn. Rond de 45, 80 en 110 seconden hebben enkele frames een framerate die zeer traag zijn. Dit zou mogelijk kunnen gebeuren tijdens het aanmaken van textures. Het netwerkverkeer is in deze versie in een aparte thread geplaatst, maar het genereren van textures moet vanwege een OpenGL beperking in de hoofdthread gebeuren. Als naar de twee metingen gekeken wordt dan is te zien dat eerder gedane aannames klop43
ten. De lokale RAM cache helpt bij de single-threaded versie voor frames met reeds geziene data. Deze versie heeft echter een zeer groot performance probleem met het in beeld brengen van niet eerder geziene dingen. Dit zal ook betekenen dat de responsiviteit voor de gebruiker zeer laag is. Wanneer de gebruiker bij de single-threaded versie een niet eerder gezien deel van het terrein in beeld brengt zal dit tot zichtbaar hangen van de applicatie leiden. Het is ook te zien dat de aanname correct was dat een multi-threaded versie van een client grotendeels de framerate hoog houdt. De framerate blijft hoog ongeacht of een frame nieuwe of eerder geziene delen van het terrein in beeld brengt. Dit is exact wat gewenst is.
8.4 Verdeling Rendering over GPU en CPU In sectie 4.3.4 is gekeken naar de componenten waar zeer globaal de rendering stap in is te verdelen. Hierbij waren drie delen te onderscheiden: het samenvoegen en interpoleren van data, het aanmaken van geometrie op basis van data en rasterisatie van de geometrie. Het was de aanname dat het zoveel mogelijk uitvoeren van deze stappen op de GPU voordelig zou zijn voor de performance. Er is gekeken naar een versie van de client die de eerste twee stappen in de CPU uitvoert en enkel projectie en rasterisatie door de GPU laat doen. Deze client is vergeleken met een versie die het samenvoegen en interpoleren van data en het aanmaken van geometrie op de GPU doet.
(a)
(b)
(c) Figuur 8.3: Metingen van een client die op de CPU data samenvoegt, interpoleert en geometrie aanmaakt. Bij (c) is te zien wat tijdens de 220 seconden durende test de framerate was van de client. Bij (a) wordt dezelfde data uit (c) puntsgewijs weergegeven. Bij (b) is een frequentie plot gemaakt, waarbij is gekeken hoeveel frames er zijn met een bepaalde framerate. De drie verticale lijnen bij (b) representeren van links naar rechts het gemiddelde min de standaardafwijking, het gemiddelde en het gemiddelde plus de standaardafwijking van de framerate.
Voor het testen wordt testscenario B gebruikt. De client die meer op de CPU uitvoert heeft geen multi-threading ingebouwd. Het lange stilstaan bij scenario B geeft deze client toch de kans om na het laden een periode te draaien zonder dat de performance aan het netwerkverkeer gebonden is. Dit scenario zal genoeg frames hebben waar de data reeds geladen is en de camera stilstaat om een idee te krijgen van de performance van CPU interpolatie en CPU geometrie generatie.
44
In figuur 8.3 is te zien dat de framerate een aantal grote dips heeft, ongeveer elke 20 seconde. Dit zijn de momenten in scenario B waar de camera van plek verandert. Aangezien de client niet multi-threaded is zijn dit de moment waar de client over het netwerk data inlaad. Het is echter ook te zien dat de client periodes heeft waar het een relatief stabiele framerate heeft zolang de camera stilstaat. Deze framerate is echter behoorlijk laag, tussen de 1.5 en 2.5 frames per seconde wanneer deze stabiel is.
(a)
(b)
(c) Figuur 8.4: Metingen van een client die op de GPU data samenvoegt, interpoleert en geometrie aanmaakt. Bij (c) is te zien wat tijdens de 220 seconden durende test de framerate was van de client. Bij (a) wordt dezelfde data uit (c) puntsgewijs weergegeven. Bij (b) is een frequentie plot gemaakt, waarbij is gekeken hoeveel frames er zijn met een bepaalde framerate. De drie verticale lijnen bij (b) representeren van links naar rechts het gemiddelde min de standaardafwijking, het gemiddelde en het gemiddelde plus de standaardafwijking van de framerate.
In figuur 8.4 zijn de testresultaten te zien van een client die alle render stappen op de GPU uitvoert. Er is een dramatisch verschil in performance te zien, met een gemiddelde framerate die bijna een factor 90 hoger ligt. Het lijkt er dus op dat de verplaatsing van de data samenvoeging, interpolatie en geometrie generatie naar de GPU nuttig is geweest. Het is ook te zien dat rond de periode waar de camera van positie veranderd de framerate tijdelijk minder hoge pieken heeft. Dit is mogelijk weer te verklaren door het feit dat textures in de hoofdthread worden aangemaakt. Het is ook mogelijk dat het client systeem in het algemeen drukker is wanneer het nieuwe data aan het laden is en dat het niet specifiek texture generatie is die de hoge framerate pieken tijdelijk drukt. De gedane test geeft niet genoeg informatie om dit exact te achterhalen. Als laatste wordt nogmaals naar een CPU gerichte versie van de client gekeken. Deze keer is de client echter enkel data aan het samenvoegen en interpoleren. Het aanmaken van geometrie en het rasteriseren staat uit (wat betekent dat een gebruiker niets zou zien). De resultaten van de test met deze client zijn in figuur 8.5 te zien. De framerate is verdubbeld ten opzichte van de client die wel geometrie aanmaakt (in de CPU) en rasteriseert. Dit is een behoorlijke verbetering in relatieve termen. In absolute termen is het bereik van 3 tot 5 frames per seconde echter niet bijzonder hoog. Het is aan deze test af te leiden dat data samenvoegen en interpolatie op de CPU een behoorlijke performance impact heeft. De CPU heeft tussen de 200 en de 300 milliseconde per frame nodig om dit uit te voeren, 45
wat behoorlijk lang is voor real-time 3D applicaties.
(a)
(b)
(c) Figuur 8.5: Metingen van een client die op de CPU data samenvoegt en interpoleert, maar geen geometrie aanmaakt of rasteriseert. Bij (c) is te zien wat tijdens de 220 seconden durende test de framerate was van de client. Bij (a) wordt dezelfde data uit (c) puntsgewijs weergegeven. Bij (b) is een frequentie plot gemaakt, waarbij is gekeken hoeveel frames er zijn met een bepaalde framerate. De drie verticale lijnen bij (b) representeren van links naar rechts het gemiddelde min de standaardafwijking, het gemiddelde en het gemiddelde plus de standaardafwijking van de framerate.
Het is ook af te lijden dat geometrie generatie op de CPU en rasterisatie op de GPU enkele honderden milliseconde per frame aan tijd toevoegen, om het verschil in framerate te verklaren tussen figuur 8.3 en figuur 8.5. Het is niet onredelijk om aan te nemen dat van de twee rasterisatie op dedicated GPU hardware het minste tijd zal innemen en dat de geometrie generatie op de CPU verantwoordelijk is voor het verschil in framerate tussen de twee CPU gerichte client versies die getest zijn. Op basis van deze laatste test kan worden geconcludeerd dat zowel het interpoleren van data op de CPU als het aanmaken van geometrie op de CPU een grote performance invloed heeft. Het verplaatsen van beide stappen naar de GPU is noodzakelijk om de gewenste performance te halen.
46
HOOFDSTUK 9
Conclusies en Aanbevelingen Het is mogelijk om een grote dataset beschikbaar te maken aan gebruikers die deze niet lokaal kunnen opslaan. Met een serverapplicatie die deze data opvraagbaar maakt over een netwerkverbinding kan een clientapplicatie gerealiseerd worden die geen grote lokale opslag van de data nodig heeft. Dit is echter niet genoeg wanneer de gebruiker een overzicht van de hele dataset wilt. In de meest na¨ıve implementatie zou dit een onbehapbaar grote hoeveelheid dataverkeer vereisen. In plaats hiervan moet de server ook data op lagere detailniveaus kunnen aanleveren. Omdat het on-the-fly aanmaken van lagere detailniveaus veel tijd kost, moet dit van tevoren zijn gebeurd. Nauwkeurige studie van de dataset heeft tot de ontdekking geleid dat deze lagere resolutie versies van de dataset gedeeltelijk reeds geleverd worden. Deze aangeleverde versies zijn echter niet compleet, hebben niet altijd de gelijke resolutie voor een bepaald oppervlak en een bepaald detailniveau. Dit maakt het noodzakelijk om waar nodig alsnog gereduceerde resolutie versies van de data aan te maken. En waar reeds data beschikbaar is moet deze genormaliseerd worden. Gedetaileerde studie van de dataset heeft ook tot het inzicht geleid dat de datapunten als 32 bit floating-point getallen worden gegeven, maar eigenlijk als 16 bits fixed-point kunnen worden opgeslagen. Daarnaast is een behoorlijke winst te behalen met compressie. Dit inzicht is gedeeltelijk meegenomen in het ontwerp van het netwerkprotocol. Deze heeft de optie om data gecomprimeerd te versturen. Omdat gecomprimeerde data echter niet gedeeltelijk uit te lezen is, geeft dit niet altijd een performance voordeel. Om de juiste data op te vragen moet de client weten wat in beeld is en met welke detailniveaus. Dit zou berekent kunnen worden op de GPU. De CPU moet echter toegang hebben tot deze informatie zodat het de correcte netwerk requests kan uitvoeren. Het is mogelijk gebleken om met een aantal simpele berekeningen op de CPU te bepalen wat in beeld is. Het is daarbij redelijk gebleken om polygonale gebieden van het terrein als axis-aligned rectangles uit te drukken. Deze keuze maakt de berekeningen simpeler. Maar de keuze is redelijk, omdat de opgevraagde data ook gestructureerd is in axis-aligned rectangles. Er is voor gekozen om de rendering uit te voeren met OpenGL 2 niveau technologie. Dit maakt het lastiger bepaalde grafische algoritmen te implementeren, maar betekent dat het op een bredere spectrum hardware kan draaien. Het is mogelijk gebleken door meerdere render stappen te gebruiken tessellation shader gedrag te simuleren zonder daadwerkelijke tessellation shaders te gebruiken (welke OpenGL 4 niveau technologie zijn). Floating-point textures zijn een nuttige manier gebleken om zoveel mogelijk de data in de vorm zoals aangeleverd wordt in het videogeheugen te uploaden. Dit maakt het mogelijk voor shaders om toegang te hebben tot deze originele data. Alle duurdere berekening voor data interpolatie tussen detailniveaus en interpolatie in de ruimte kunnen op deze manier op de GPU uitgevoerd 47
worden. De CPU is op deze manier primair verantwoordelijk voor het opvragen van data van de server, het zo snel mogelijk in het videogeheugen stoppen van de data en het opstellen van tekeninstructies die berekeningen in de shaders kunnen starten. Performance en correctheid van data worden hiermee gecombineerd. Het is gebleken dat een multi-touch interface een nuttige manier is om de dataset verkenbaar te maken. In combinatie met hardware zoals touchscreens, tablets en multi-touch trackpads maakt dit type interface het mogelijk voor een gebruiker om op een intu¨ıtieve manier door de dataset te navigeren.
9.1 Aanbevelingen voor Toekomstig Onderzoek Het systeem gebruikt geen ingebouwde hardware functionaliteit voor het interpoleren van mipmaps. Dit heeft twee redenen. Door de interpolatie tussen detailniveaus handmatig te doen is er meer controle over de interpolatie. Daarnaast is voor veel van het terrein op de client niet de volledige resolutie hi¨erarchie aanwezig die nodig is om mipmaps aan te maken. Het is echter nuttig om te onderzoeken of het interpoleren tussen detailniveaus toch in mipmaps gevangen kan worden. Het dient dan ook onderzocht te worden of dit een performance voordeel heeft. Frustum culling gebeurt in het gerealiseerde systeem op basis van een axis aligned rectangle. Deze is opgesteld op basis van een polygoon. Het zou onderzocht kunnen worden hoeveel extra complexiteit qua implementatie het vergt om de frustum culling op basis van de polygoon te doen en of dit een performance voordeel heeft. Het systeem kent twee punten waar er veel gegevensoverdracht plaatsvindt en waar compressie mogelijk nuttig is. Gegevensoverdracht vindt plaats van de server naar de client, over een netwerkverbinding. Gegevensoverdracht vindt ook plaats van het RAM geheugen in de client naar het videogeheugen. Voor de eerste vorm van gegevensoverdracht is er een compressie optie in het ontwerp van het netwerkprotocol. Er bestaan echter ook compressie methoden die specifiek bedoelt zijn om de gegevensoverdracht van RAM geheugen naar videogeheugen effici¨enter te maken. Deze vormen van compressie zijn door de GPU snel en hardwarematig uit te pakken (zie bijvoorbeeld de set aan S3 compressie-algoritmen). Het zou onderzocht kunnen worden of het gebruik van deze compressie bij texture uploads voordelig zou zijn. Het zou verder onderzocht kunnen worden of de compressie voor texture uploads en voor netwerk uploads gelijk zou kunnen zijn en of dit voordelig uitpakt (mogelijk minder effici¨ente compressie van netwerkverkeer tegenover het vermijden van een tweede compressie stap bij texture upload). Het systeem dat gebouwd is werkt enkel met de AHN2 dataset. Visualisatie van andere databronnen, zoals voor overstromingssimulaties (zie bijvoorbeeld [KSM+ 11]) zou in de context van de AHN2 visualisatie geplaatst kunnen worden. Daarnaast zou topografische informatie uit bijvoorbeeld de Basisregistratie Topografie (BRT) van het Kadaster gebruikt kunnen worden om context aan de visualisatie van de AHN2 data toe te voegen. Het laden en normaliseren van data gebeurd op basis van een single-threaded applicatie op de server. Het zou onderzocht kunnen worden of een multi-threaded aanpak hier een performance winst zou geven. De client heeft een cache in het RAM geheugen om eerder geladen data niet telkens opnieuw te hoeven laden. Deze cache blijft echter enkel geldig per sessie. Als de clientapplicatie afgesloten wordt vervalt de data in deze cache. Het kan onderzocht worden of het nuttig is om de client cache gedeeltelijk op te slaan in een bestand, op de permanente (non-volatile) opslag van de client. Het gerealiseerde systeem werkt met een grid versie van de AHN2 dataset. Deze versie is gebaseerd op een 3D point cloud dataset. Het zou onderzocht kunnen worden of bij camerastandpunten waar het meeste detail zichtbaar is de point cloud data ge¨ıntegreerd kan worden in 48
de visualisatie. In de literatuurstudie komen veel aanpakken voor die ofwel met een 2D hoogteraster of met een 3D point cloud werken. Mogelijk is een hybride aanpak die voornamelijk met het hoogteraster werkt, maar ook met de point cloud voor het meest gedetailleerde camerastandpunten interessant.
49
50
Bibliografie [BGP09]
Jonas B¨ osch, Prashant Goswami, and Renato Pajarola. RASTeR: Simple and efficient terrain rendering on the GPU. In Proceedings EUROGRAPHICS Areas Papers, Scientific Visulization, pages 35–42, 2009.
[Bri12]
Sam Briels. Performance implications on urbanflood inundation simulations with the transition of ahn-1 to ahn-2 data. Bachelor’s thesis, Universiteit van Amsterdam, 2012.
[BRS+ 10] R.G. Belleman, F.I. Rusadi, G.S. Shirshov, V.V. Krzhizhanovskaya, and B.J. Broekhuijzen. Interactive flood simulation and visualisation on a multitouch table. Proceedings of the Joint UrbanFlood & SSG4Env Workshop on Monitoring and Flood Safety, pages 16–16, 2010. [CFGS12] M. Claypool, D. Finkel, A. Grant, and M. Solano. Thin to win? network performance analysis of the onlive thin client game system. In Network and Systems Support for Games (NetGames), 2012 11th Annual Workshop on, pages 1–6, Nov 2012. [DB00]
Willem H De Boer. Fast terrain rendering using geometrical mipmapping. Unpublished paper, available at http://www.flipcode.com/articles/article geomipmaps.pdf, 2000.
[Deu96]
L Peter Deutsch. Deflate compressed data format specification version 1.3. IETF, 1996.
[DWS+ 97] Mark Duchaineau, Murray Wolinsky, David E. Sigeti, Mark C. Miller, Charles Aldrich, and Mark B. Mineev-Weinstein. Roaming terrain: Real-time optimally adapting meshes. In Proceedings of the 8th Conference on Visualization ’97, VIS ’97, pages 81–88, Los Alamitos, CA, USA, 1997. IEEE Computer Society Press. [Haa09]
Gerwin de Haan. Scalable visualization of massive point clouds. Nederlandse Commissie voor Geodesie KNAW, 49:59–67, 2009.
[JLG+ 12] Hans-Christian Jetter, Svenja Leifert, Jens Gerken, S¨oren Schubert, and Harald Reiterer. Does (multi-)touch aid users’ spatial memory and navigation in ‘panning’ and in ‘zooming & panning’ uis? In Proceedings of the International Working Conference on Advanced Visual Interfaces, AVI ’12, pages 83–90, New York, NY, USA, 2012. ACM. [Kod10]
MP Kodde. The art of collecting and disseminating point clouds. NCG KNAW, page 9, 2010.
[KSM+ 11] V.V. Krzhizhanovskaya, G.S. Shirshov, N.B. Melnikova, R.G. Belleman, F.I. Rusadi, B.J. Broekhuijsen, B.P. Gouldby, J. Lhomme, B. Balis, M. Bubak, A.L. Pyayt, I.I. Mokhov, A.V. Ozhigin, B. Lang, and R.J. Meijer. Flood early warning system: design, implementation and computational modules. Procedia Computer Science, 4(0):106 – 115, 2011. Proceedings of the International Conference on Computational Science, {ICCS} 2011. 51
[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 Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’96, pages 109–118, New York, NY, USA, 1996. ACM. [MCG10]
A. Martinet, G. Casiez, and L. Grisoni. The design and evaluation of 3d positioning techniques for multi-touch displays. In 3D User Interfaces (3DUI), 2010 IEEE Symposium on, pages 115–118, March 2010.
[RD10]
Rico Richter and J¨ urgen D¨ollner. Out-of-core real-time visualization of massive 3d point clouds. In Proceedings of the 7th International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa, AFRIGRAPH ’10, pages 121–128, New York, NY, USA, 2010. ACM.
[SSK10]
Corn van der Sande, Sylvie Soudarissanane, and Kourosh Khoshelham. Assessment of relative accuracy of ahn-2 laser scanning data using planar features. Sensors, 10(9):8198–8214, 2010.
[Str09]
Filip Strugar. Continuous distance-dependent level of detail for rendering heightmaps. Journal of Graphics, GPU, and Game Tools, 14(4):57–74, 2009.
[Tor12]
Richard Torenvliet. Flood simulator browser. Bachelor’s thesis, Universiteit van Amsterdam, 2012.
[vdZ13]
Niels van der Zon. Kwaliteitsdocument ahn2. Technical report, Actueel Hoogtebestand Nederland, 2013.
Web Referenties [1] Actueel Hoogtebestand Nederland. http://www.ahn.nl/ [2] ArcGIS. https://www.arcgis.com/ [3] Esri. http://www.esri.com/ [4] Arc/Info Binary Grid Format informatie van GDAL. http://home.gdal.org/projects/aigrid/aigrid_format.html Opgehaald via: https://web.archive.org/web/20121124091208/http://home.gdal.org/projects/ aigrid/aigrid_format.html [5] ESRI ArcInfo Grid informatie van de Digital Preservation afdeling van de Library of Congress. http://www.digitalpreservation.gov/formats/fdd/fdd000281.shtml [6] Reduced resolution dataset files informatie uit ArcGIS Help 10.1. http://resources.arcgis.com/en/help/main/10.1/index.html#// 009t00000025000000 [7] Erdas IMAGINE bestandsformaat document. http://home.gdal.org/projects/imagine/iau_docu1.pdf Opgehaald via: https://web.archive.org/web/20130129182320/http://home.gdal.org/projects/ imagine/iau_docu1.pdf [8] “HFA reading code does not handle reduced precision properly” ticket uit GDAL bugtracker. https://trac.osgeo.org/gdal/ticket/1000 52
[9] Geospatial Data Abstraction Library. http://www.gdal.org/
53
