in alle mogelijke mediaformaten, - bestaande en in de toekomst te ontwikkelen -, aan de Universiteit Hasselt

Auteursrechterlijke overeenkomst Opdat de Universiteit Hasselt uw eindverhandeling wereldwijd kan reproduceren, vertalen en distribueren is uw akkoord voor deze overeenkomst noodzakelijk. Gelieve de tijd te nemen om deze overeenkomst door te nemen, de gevraagde informatie in te vullen (en de overeenkomst te ondertekenen en af te geven). Ik/wij verlenen het wereldwijde auteursrecht voor de ingediende eindverhandeling met Titel: Frontier sets Richting: master in de informatica - multimedia

Jaar: 2009

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

Ik ga akkoord,

BOVIJ, Yannick Datum: 14.12.2009

cêçåíáÉê=ëÉíë

v~ååáÅâ=_çîáà éêçãçíçê=W mêçÑK=ÇêK=táã=i^jlqqb=

=

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

Samenvatting Genetwerkte virtuele omgevingen (GVO’s) zijn een sterk groeiende tak binnen de computer graphics. Denk maar aan allerhande simulaties, conferencing applicaties, tal van online communities zoals Second Life of There en games zoals World of Warcraft. Typisch voor deze GVO’s zijn het grote aantal gebruikers. Er ontstaat een schaalbaarheidsprobleem wanneer de GVO het toenemende aantal gebruikers niet langer kan ondersteunen. Een toename van gebruikers stelt immers meer eisen aan de computers, alsook aan het netwerk. Talrijke manieren werden doorheen de jaren al onderzocht om de netwerk load te drukken. Belangrijke keuzen zijn hier de netwerkarchitectuur, methode van datadistributie alsook een aantal andere technieken om het bandbreedteverbruik terug te dringen. Interest management is e´ e´ n van de methoden om het dataverkeer tussen verschillende gebruikers in een GVO te verminderen. Zo wordt enkel data tussen gebruikers uitgewisseld wanneer ze ’interesse’ hebben in elkaar; wanneer ze zich bijvoorbeeld in elkaars buurt bevinden. Het bepalen of 2 gebruikers met elkaar dienen te communiceren kan gebeuren op basis van visibility. Wanneer gebruikers elkaar onmogelijk kunnen zien, zijn ze meestal ook niet ge¨ınteresseerd in elkaar. Vaak wordt bij GVO’s de virtuele omgeving opgedeeld in verschillende cellen. Voor elke cel kan dan bepaald worden welke andere delen van de omgeving mogelijk zichtbaar zijn. Dit levert Potentially Visible Sets op (PVS). Frontier sets bouwen verder op deze PVS. Voor elk cellenpaar worden er (indien mogelijk) twee regio’s van wederzijdse onzichtbaarheid bepaald binnen de omgeving, de zogenaamde frontiers. Zolang gebruikers elk binnen hun frontier blijven, kunnen ze elkaar onmogelijk zien en is er tussen hen geen nood aan communicatie. Het gebruik van frontier sets resulteert in een grote besparing op het bandbreedteverbruik.

Inhoudsopgave 1

Woord vooraf

5

2

Inleiding

6

3

Genetwerkte Virtuele Omgevingen 3.1 Positie binnen computer graphics 3.2 Definitie . . . . . . . . . . . . . 3.2.1 Belangrijke aspecten . . 3.2.2 Kenmerken . . . . . . . 3.2.3 Aandachtspunten . . . . 3.3 Geschiedenis . . . . . . . . . . 3.4 Slot . . . . . . . . . . . . . . .

4

5

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

Schaalbaarheid 4.1 Data distributie . . . . . . . . . . . . . . 4.2 Netwerk architecturen . . . . . . . . . . . 4.2.1 Client/Server . . . . . . . . . . . 4.2.2 Peer-to-peer . . . . . . . . . . . . 4.2.3 Hybride architecturen . . . . . . . 4.3 Datamodellen . . . . . . . . . . . . . . . 4.3.1 Replicated homogene omgeving . 4.3.2 Shared gecentraliseerde omgeving 4.3.3 Shared gedistribueerde omgeving 4.4 Resource management . . . . . . . . . . 4.4.1 Aggregatie . . . . . . . . . . . . 4.4.2 Compressie . . . . . . . . . . . . 4.4.3 Dead reckoning . . . . . . . . . . 4.4.4 Level of detail . . . . . . . . . . 4.4.5 Zoning . . . . . . . . . . . . . . 4.4.6 Interest management . . . . . . . 4.5 Conclusie . . . . . . . . . . . . . . . . . Interest Management 5.1 Definitie . . . . . . . . . . . . . . . 5.2 Specificatie van interesse-expressies 5.2.1 Formules . . . . . . . . . . 5.2.2 Cellen . . . . . . . . . . . . 2

. . . .

. . . .

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

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

. . . .

. . . . . . .

8 8 9 9 9 10 12 13

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

15 15 17 17 21 22 22 22 23 24 24 25 25 26 27 28 29 29

. . . .

30 30 30 30 31

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

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

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

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

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

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

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

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

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

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

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

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

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

32 32 32 32 33 33 33 33 33 34 34 34 35 35 35 38

Visibility (culling) 6.1 Inleiding . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Potentially visible sets . . . . . . . . . . . . 6.1.2 Voorbeeld . . . . . . . . . . . . . . . . . . . 6.2 Occlusion culling . . . . . . . . . . . . . . . . . . . 6.3 From-region methods . . . . . . . . . . . . . . . . . 6.3.1 Cells and portals . . . . . . . . . . . . . . . 6.3.2 Arbitrary scenes . . . . . . . . . . . . . . . 6.4 Point-based methods . . . . . . . . . . . . . . . . . 6.4.1 Object-precision . . . . . . . . . . . . . . . 6.4.2 Image-precision . . . . . . . . . . . . . . . . 6.5 PVS als techniek om netwerkverkeer te verminderen 6.5.1 Voorbeeld: RING . . . . . . . . . . . . . . . 6.6 Conclusie . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

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

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

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

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

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

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

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

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

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

39 39 40 40 41 42 42 44 48 48 50 54 55 56

. . . . . . . . . .

58 58 59 59 61 62 62 62 64 65 67

5.3

5.4

5.5

5.6 6

7

5.2.3 Extensies . . . . . . . . . . . . 5.2.4 Precisie van interesse-expressies Frequentie van interesse-expressies . . . 5.3.1 System Design . . . . . . . . . 5.3.2 Execution Initiation . . . . . . . 5.3.3 Runtime . . . . . . . . . . . . . 5.3.4 Frequentie/temporeel . . . . . . Architectuur . . . . . . . . . . . . . . . 5.4.1 Bij de bron . . . . . . . . . . . 5.4.2 Bij de ontvanger . . . . . . . . 5.4.3 Tussen bron en ontvanger . . . 5.4.4 Multicast . . . . . . . . . . . . Implementaties . . . . . . . . . . . . . 5.5.1 Verdeling over server cluster . . 5.5.2 IM in P2P-NVE systemen . . . Conclusie . . . . . . . . . . . . . . . .

Frontier sets 7.1 Definitie . . . . . . . . . . . . 7.2 Basis algoritme . . . . . . . . 7.2.1 Opstellen van frontiers 7.2.2 Evaluatie . . . . . . . 7.2.3 Voor- en nadelen . . . 7.3 Uitbreidingen . . . . . . . . . 7.3.1 Opstellen van frontiers 7.4 Toepassing: Quake2 . . . . . . 7.4.1 Vergelijking . . . . . . 7.5 Conclusie . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

3

. . . . . . . . . .

. . . . . . . . . .

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

. . . . . . . . . .

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

. . . . . . . . . .

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

. . . . . . . . . .

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

. . . . . . . . . .

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

. . . . . . . . . .

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

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

8

9

Implementatie 8.1 Library’s . . . . . . . . . . 8.1.1 Irrlicht . . . . . . 8.1.2 RakNet . . . . . . 8.2 Architectuur . . . . . . . . 8.2.1 Client/server . . . 8.2.2 Protocol . . . . . . 8.3 Frontier sets . . . . . . . . 8.3.1 Inleiding met PVS 8.3.2 Initialisatie . . . . 8.3.3 Simulatie . . . . . 8.4 Resultaten/vergelijking . . 8.5 Slot . . . . . . . . . . . .

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

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

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

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

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

Conclusies

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

68 68 68 70 71 71 71 72 72 72 73 73 75 76

4

Hoofdstuk 1 Woord vooraf Om eerlijk te zijn geloofde ik er vijf maanden geleden niet meer in. Het schrijven van deze masterthesis wilde maar niet vlotten en ik dacht dat ik er nooit een punt achter zou kunnen zetten. Ook al bij het maken van mijn bacheloreindwerk bleek immers dat het schrijven van wetenschappelijke teksten niet een van mijn sterkste punten is. Moest iemand mij hadden voorgesteld om nog 4 extra examens af te leggen in de plaats van het schrijven van deze thesis had ik onmiddellijk toegestemd. Maar uiteindelijk is het er alsnog (zij het met een niet meer onsignificante vertraging) van gekomen. Indien ik er alleen voor had gestaan zou het mij nooit gelukt zijn. Zowel van familie, vrienden, mijn baas en mijn begeleider heb ik steun gehad. Daarom wil ik de volgende personen expliciet bedanken in dit voorwoord: • Mijn ouders (Paul en Mireille): voor alle morele en financi¨ele steun die ik van jullie heb gehad van jongs af aan. • Mijn zus en haar man (Michelle en Matty): voor achter mijn rug om toch mijn ouders te overtuigen dat ik mijn masterthesis koste wat kost MOEST afmaken. • Mijn vrienden (Stijn, Frederik, Ben, Wim, Kevin, ...): voor het moraal hoog te houden via tal van extracurriculaire activiteiten. • Mijn baas (Walter): voor het vertrouwen en het mogen nemen van onbetaald verloofd om de laatste loodjes te schrijven. • En vooral mijn begeleider (dr. Peter Quax): voor het in mij blijven geloven, het brengen van structuur in mijn thesis, het nalezen van de tekst en alle andere hulp die ik van je heb mogen ontvangen. Enorm bedankt allemaal!

5

Hoofdstuk 2 Inleiding Al meer dan 50 jaar probeert men met virtual reality nieuwe realistische omgevingen te cre¨eren. Virtual reality probeert de ’echte’ wereld zo realistisch mogelijk na te bootsen. Dit maakt van virtual reality een samensmelting van verschillende andere computer graphics domeinen, zoals graphic rendering, animaties, computersimulaties en human-machine interacties. Een belangrijk aspect van deze virtuele omgevingen is de interactie. Een rijke interactie tussen gebruiker en omgeving vergroot het gevoel van immersie. Deze virtuele werelden worden vaak gebruikt voor allerhande simulaties. Door verschillende simulaties aan elkaar te koppelen kunnen meer gebruikers dezelfde virtuele ervaringen delen. Zo ontstonden geleidelijk aan de genetwerkte virtuele omgevingen (GVO’s), waarbij verschillende gebruikers binnen eenzelfde netwerk dezelfde omgeving kunnen delen en met elkaar kunnen interageren. Geleidelijk aan groeide het bereik deze GVO’s van kleine lokale netwerken (Local Area Network of LANs) naar omgevingen gedeeld door gebruikers overal ter wereld (Wide Area Networks of WANs). GVO’s proberen een real-time globale omgeving weer te geven waarin meerdere gebruikers met deze omgeving en met elkaar kunnen interageren. Vaak worden deze gebruikers door middel van avatars binnen deze wereld voorgesteld, om zo elkaar te herkennen. De interactie tussen de gebruikers kan al snel erg complex worden. Naarmate het aantal gebruikers toeneemt zal de GVO steeds meer eisen stellen aan het netwerk en de computers, tot de GVO het aantal gebruikers niet meer kan ondersteunen. Er ontstaat dus een schaalbaarheidsprobleem waar oplossingen voor gezocht werden. Voor grotere GVO’s dient men meestal het dataverkeer tussen de deelnemers van de GVO op e´ e´ n of andere manier te verminderen. Zo speelt de keuze van de datadistributie methode alsook de netwerkarchitectuur een belangrijke rol. Hiernaast kunnen ook verschillende aanvullende algoritmen gebruikt worden om de hoeveelheid data tussen gebruikers te verminderen, door bijvoorbeeld aggregatie, compressie, dead-reckoning of zoning toe te passen. Vaak is een gebruiker op een bepaald moment in slechts een beperkt aantal andere gebruikers binnen de virtuele omgeving ge¨ınteresseerd. Meestal zijn dit de gebruikers die ze

6

kunnen ’zien’, of die zich dicht bij hen in de buurt bevinden. Potentially Visible Sets kunnen gebruikt worden om te bepalen welke delen van de omgeving mogelijk zichtbaar zijn vanuit een bepaalde positie. Zo kan het dataverkeer tussen gebruikers die elkaar onmogelijk kunnen zien vermeden worden. Frontier sets nemen deze PVS algoritmen een stap verder. Voor elke 2 cellen in de virtuele omgeving kunnen twee gebieden bepaald worden waarin gebruikers elkaar onmogelijk kunnen zien indien ze deze gebieden niet verlaten. Ook al verplaatsen gebruikers zich van cel tot cel binnen deze frontiers is er tussen hen geen dataverkeer nodig. Uit de praktijk blijkt dat frontier sets het dataverkeer binnen een GVO drastisch kan verminderen. Belangrijk hierbij is wel de manier waarop de omgeving kan opgedeeld worden. Echter blijkt ook dat het bepalen van de mogelijk zichtbare delen van de omgeving vanuit een bepaalde cel of punt echter niet eenvoudig implementeerbaar is en behoorlijk wat rekentijd kan kosten. In een eerste hoofdstuk wordt er kennis gemaakt met deze GVO’s, en wordt er een korte geschiedenis gegeven over hoe deze omgevingen tot stand kwamen. Hun belangrijkste kenmerken worden ook opgesomd, alsook hun aandachtspunten en beperkingen. Een volgend hoofdstuk verduidelijkt een aantal methodes en technieken om een groter aantal gebruikers binnen deze GVO’s te ondersteunen. Interest management speelt hierbinnen een belangrijke rol. Hierna volgt een beschrijving van verschillende visibility algoritmen die men kan aanwenden om een Potentially Visible Set te bepalen. Daarna wordt uitgelegd hoe deze PVS kan gebruikt worden voor de opbouw van frontier sets. Een laatste hoofdstuk zal dan de eigen implementatie van frontier sets beschrijven. Hierbij zal een vergelijking gemaakt worden om het nut van frontier sets verder te verduidelijken.

7

Hoofdstuk 3 Genetwerkte Virtuele Omgevingen 3.1

Positie binnen computer graphics

Virtual reality is het onderzoeksdomein binnen computer graphics waarbij de gebruikers met een virtuele omgeving interageren. De gebruikers worden als het ware binnen de virtuele omgeving geplaatst, en men tracht de gewaarwording van de gebruikers in deze omgeving zo realistisch mogelijk voor te stellen. Cruciaal hierbij is de interactie tussen de gebruikers met de omgeving, alsook deze tussen de gebruikers onderling. Hierdoor voelen de gebruikers zich meer betrokken in de omgeving. Door de loop der jaren werd de traditionele interactieapparatuur (als muis en keyboard) aangevuld met rijkere invoerapparaten, zoals ruimtelijke sensors, haptics, spraakondersteuning,... Dit zorgde voor een nog realistischere ervaring van de virtuele omgeving. Door het netwerkaspect aan een virtuele omgeving toe te voegen is het mogelijk om fysisch van elkaar verwijderde gebruikers binnen dezelfde omgeving te plaatsen. De gebruikers kunnen dan onafhankelijk met elkaar interageren alsof ze zich in dezelfde omgeving begeven. Belangrijk is dat elke gebruiker dezelfde representatie van de omgeving heeft. Een bepaald event in de virtuele omgeving moet voor elke gebruiker transparant zijn. Deze genetwerkte virtuele omgevingen (GVO’s) groeiden geleidelijk aan van lokale netwerken (LANs) tot meer globale netwerken (WANs) van duizenden en zelfs meer deelnemers. Dit werd mogelijk gemaakt door betere netwerkarchitecturen en algoritmen die de datacommunicatie verder optimaliseren. Het Amerikaanse leger speelde een heel belangrijke rol in de ontwikkeling van deze GVO’s. Ze waren bij de eerste om verschillende virtuele simulaties met elkaar te linken. Zo konden verschillende gebruikers aan dezelfde training deelnemen. Later verschenen deze GVO’s ook in de industrie en entertainment. Hierdoor groeide de omvang en toepassingsgebieden enorm. Vandaag zijn GVO’s te vinden van (militaire) simulaties, games tot volwaardige online communities en leeromgevingen.

8

3.2

Definitie

Volgens Singhal & Zyda is een genetwerkte virtuele omgeving een software systeem waarbij meerdere gebruikers in real-time met elkaar kunnen interageren in een gesimuleerde virtuele omgeving, zelfs wanneer ze zich op aarde fysisch ver van elkaar bevinden [SZ99]. De belangrijkste aspecten van deze definitie zijn globaal, real-time, meerdere gebruikers en interactie.

3.2.1

Belangrijke aspecten

Globaal De gebruikers hebben het gevoel zich dicht bij elkaar te bevinden in een gemeenschappelijke virtuele omgeving, ook al zijn ze fysisch ver verwijderd. Binnen deze omgeving ervaren de gebruikers dezelfde karakteristieken zoals de tijd, het weer, geluiden, enz. Waar vroeger virtuele omgevingen meestal in een lokaal netwerk gesimuleerd werden kregen ze door de groei van het Internet steeds meer en meer globale proporties. Real-time De acties van een gebruiker moeten direct weerspiegeld worden in de virtuele omgeving, en de andere gebruikers moeten deze acties ook onmiddellijk kunnen waarnemen. Hierdoor moet niet alleen de rendering real-time gebeuren, maar moeten de acties ook tijdig uitgewisseld worden. Meerdere gebruikers Een grotere groep gebruikers geeft een realistische virtuele omgeving. De gebruikers herkennen elkaar binnen de virtuele omgeving aan de hand van virtuele representaties, de zogenaamde avatars. Er kunnen ook gebruikers aanwezig zijn die bestuurd worden door computers zelf. Het betreden en het verlaten van de virtuele omgeving is zichtbaar voor de andere deelnemers. Interactie Om de ervaring van de gebruikers te verbeteren moet het mogelijk zijn om met elkaar en met de omgeving te interageren. Deze interactie omvat de mogelijkheid om de omgeving en zijn objecten met elkaar te delen, alsook de communicatie tussen de gebruikers zelf via (voice) chat, video en gebaren.

3.2.2

Kenmerken

Een GVO moet voor iedere gebruiker transparant zijn. Iedereen moet hetzelfde gevoel van tijd en ruimte hebben. Binnen een GVO heeft elke gebruiker een virtueel alter ego of avatar, die de gebruikers toelaat elkaar te identificeren en te herkennen. Deze avatars verpersoonlijken de acties van het menselijk lichaam in de virtuele omgeving. Er ontstaat zo de illusie dat men zich in dezelfde ruimte en tijd bevindt. 9

Belangrijk in een GVO is de interactie tussen de gebruikers met de omgeving en de interactie tussen de gebruikers onderling. Gebruikers kunnen verschillende acties ondernemen, waaronder zich verplaatsen en ori¨enteren in de virtuele omgeving, communiceren met andere gebruikers, interageren met de virtuele omgeving zelf of objecten gebruiken en delen met elkaar. Andere gebruikers kunnen te allen tijde deze acties ook waarnemen omdat ze elkaar continu op de hoogte houden door deze acties te encoderen in netwerkberichten die dan onderling uitgewisseld worden. De onderliggende fysieke structuur bestaat uit een verzameling van lokale netwerken (Local Area Networks of LANs) die aaneengeschakeld worden door een grootschalig netwerk dat regionale of nationale grenzen overschrijdt (Wide Area Network of WAN), waarvan het best bekende WAN het Internet is. Een computer in een LAN kan deelnemen aan de simulatie van de virtuele omgeving door een simulator te draaien die een of meerdere entiteiten tegelijkertijd simuleert. Hierdoor kunnen in de virtuele omgeving gebruikers die zich geografisch ver van elkaar bevinden met elkaar interageren in een gedeelde en gesimuleerde omgeving, en deelnemen aan activiteiten die anders fysisch onmogelijk zouden kunnen zijn.

Figuur 3.1: Koppeling tussen de GVO en het onderliggend netwerk.

3.2.3

Aandachtspunten

Het is niet eenvoudig om genetwerkte virtuele omgevingen op een correcte manier te implementeren. Ze zijn een combinatie van gedistribueerde systemen, grafische en interactieve applicaties en ze moeten ook samenwerken met andere applicaties zoals database- en authenticatiesystemen.

10

Belangrijk bij een gedistribueerd systeem is het beheren van netwerkcomponenten. Typisch aan een netwerk zijn beperkte bandbreedte, vertragingen, pakketverlies en jitter. Ondanks deze problemen moet de virtuele omgeving te allen tijde consistent blijven voor iedereen. De virtuele omgeving moet zo realistisch mogelijk in real-time weergegeven worden. Het weergeven aan een voor de mens acceptabele frame rate is hierbij noodzakelijk. Men moet er echter rekening bij houden dat de beperkte rekenkracht en geheugen ook gebruikt zal worden voor andere taken. Realistische interactie bepaalt in grote mate de kwaliteit van de virtuele omgeving. De gebruikers zouden de virtuele omgeving moeten kunnen waarnemen alsof deze zich lokaal afspeelt. De interactie moet dan ook in real-time verwerkt kunnen worden door de virtuele omgeving. Het optimaliseren van e´ e´ n eigenschap kan een negatieve invloed hebben op andere eigenschappen. Bij het ontwikkelen van een genetwerkte virtuele omgeving moet men een zo goed mogelijke balans weten te vinden tussen verschillende factoren: • Bandbreedte: omdat de bandbreedte van het netwerk beperkt is en deze gebruikt moet worden voor allerlei soorten communicatie tussen gebruikers moet deze effici¨ent verdeeld worden. • Consistentie: elke gebruiker moet identiek dezelfde acties en toestanden waarnemen dan andere gebruikers om het gevoel van een gedeelde ruimte te behouden. Omdat netwerkberichten met toestandswijzigingen vertraagd kunnen aankomen of helemaal verloren gaan, is de consistentie van de virtuele omgeving behouden niet voor de hand liggend. • Responsiviteit: gezien mensen interageren in de virtuele omgeving zijn vertragingen die voortvloeien uit vertraagde of missende netwerkberichten ongewenst. De gebruikers moeten in real-time de consequenties van hun acties kunnen waarnemen. Consistentie en responsiviteit zijn vaak moeilijk te balanceren. • Schaalbaarheid: hoe meer gebruikers deelnemen in de virtuele omgeving, des te hogere eisen gesteld worden aan het netwerk (bandbreedte) en de computersystemen die de groter wordende stroom van netwerkberichten moeten verwerken. Het systeem zo ontwerpen dat een grote toename aan gebruikers het systeem niet overbelast is dan ook van hoge prioriteit. • Persistentie: sommige objecten in de virtuele omgeving moeten dag en nacht aanwezig blijven, ook wanneer een gebruiker zijn sessie verlaat. • Betrouwbaarheid: om een continue en kwalitatief goede service aan te bieden moeten hard- en softwarefouten op een ordentelijke wijze afgehandeld worden. Problemen als pakketverlies, netwerkfalingen,... • Beveiliging: naast het beveiligen van gebruikersgegevens (in al dan niet commerci¨ele systemen) moet het systeem ook resistent zijn voor potenti¨ele aanvallen van hackers. 11

• Configuratie: er zijn talrijke systeemarchitecturen mogelijk die allemaal hun eigen voor- en nadelen hebben. De keuze van een architectuur hangt dan ook af aan de noden van de gewenste GVO.

3.3

Geschiedenis

De oudste systemen die onder de term GVO vallen zijn waarschijnlijk de multi-user dungeons (MUD’s) van de jaren zeventig [Mat97]. Dit waren volledig tekstgebaseerde RPG’s, die erg populair waren in de academische wereld. Ze evolueerden geleidelijk aan naar meer grafische applicaties, met verbeterde interactiemogelijkheden. Tijdens de jaren ’80 ontstond er bij het Amerikaanse leger een nood aan software die gebruikt zou kunnen worden om hun troepen te laten deelnemen aan militaire oorlogssimulaties en trainingsoefeningen. SIMNET [MJ95] was een project dat bestaande militaire simulaties aan elkaar moest koppelen om de interactie tussen meerdere deelnemers mogelijk te maken. Het werkte op dedicated netwerken via broadcasting. Hierbij werd het DIS protocol [DIS] ontworpen. Ook werd dead-reckoning reeds toegepast om het dataverkeer te verminderen. In de begin 90 begonnen de GVO’s meer en meer in andere professionele toepassingen op te duiken. DIVE [ACOS] was ontwikkeld met voor een publiek internet. Gebruikers werd hierbij voorgesteld met hun eigen avatar. NPSNET [MZP+ ] werd met behulp van het DIS protocol ontworpen, al werd broadcasting vervangen door multicasting om zo over het internet te kunnen communiceren. Het is ook de eerste GVO die een ’area of interest management’ toepaste om bandbreedte te beperken. Dit werd gedaan door een bubbel rond de gebruiker en te gebruiken om te bepalen of er communicatie nodig was met andere deelnemers.

Figuur 3.2: NPSNET militaire simulatie Het idee van ’area of interest management’ werd verder uitgewerkt door MASSIVE [GB]. Hierbij was er enkel communicatie tussen gebruikers indien hun area of interest elkaar overlapten. Het maakte ook gebruik van peer-to-peer unicast ipv. broadcasting of multicasting.

12

Figuur 3.3: MASSIVE omgeving In de loop van de jaren 90 groeide de interfaces van de GVO’s enorm, door de toenemende rekenkracht van de PC’s alsook door grafische processoren. Dit leverde een bloeiende gaming industrie, die zorgde voor de introductie van first person shooters, sport- en racesimulaties, real-time strategy games, RPG’s,... Naast de grafische vooruitgang waren er ook verschillende verbeteringen op vlak van inen uitvoerapparatuur. Dit leverde allerlei immersieve systemen, die de gebruiker en nog realistisch geval van de omgeving gaven. Door de opkomst van breedband internet groeide de GVO systemen ook enorm in omvang. Dit leidde tot immersieve digitale werelden zoals Second Life [sec] en There [the] en Massively Multiplayer Online Games (MMOG’s) zoals World of Warcraft [wow],... Deze GVO’s boden ook allerlei aanvullende aspecten zoals voice ondersteuning, multimedia content, ... om een nog realistischere virtuele omgeving te bekomen.

Figuur 3.4: MMOG: World of Warcraft. Hedendaags zijn GVO’s te vinden in militaire domeinen, medische toepassingen, allerhande simulaties en trainingen, teleconferencing, games tot zelfs online klaslokalen. Deze toepassingen zullen in de toekomst nog verder groeien.

3.4

Slot

In dit hoofdstuk werd een definitie gegeven van een GVO, en werden ze geplaatst binnen de computer graphics. Er werd ook een korte geschiedenis van deze GVO’s gegeven. Verder 13

werden de belangrijkste begrippen gerelateerd aan de definitie van de GVO’s kort toegelicht. Ook werden enkele eigenschappen van deze GVO’s opgesomd, alsook hun voornaamste aandachtspunten en beperkingen. Hieruit blijkt dat om een groter aantal gebruikers toe te laten bij aan GVO dit een niet evidente zaak is. In een volgend hoofdstuk zal deze schaalbaarheid verder besproken worden, en zullen tal van mogelijke oplossingen aan bod komen.

14

Hoofdstuk 4 Schaalbaarheid Onder schaalbaarheid verstaan we het vermogen van een GVO om al dan niet een groot bereik aan deelnemers te ondersteunen zonder in te boeten aan de kwaliteit van de simulatie (consistentie, responsiviteit, ...). Dit hangt samen met de mate waarin de beperkte hoeveelheid systeembronnen (rekenkracht en bandbreedte) afnemen wanneer er nieuwe deelnemers de simulatie betreden. In een idealistische wereld kan een grote groep gebruikers real-time op een betrouwbare manier aan een virtuele omgeving deelnemen. In de realiteit moet men vaak afwegingen maken voor de data distributie en de architectuur om de omgeving zo goed mogelijk te kunnen weergeven. Vaak zijn hierbij nog diverse methoden nodig om het bandbreedteverbruik verder te beperken.

4.1

Data distributie

Eerst en vooral kan men een onderscheid maken tussen de verschillende manieren waarop data over het netwerk verstuurd kan worden [CDKR03]. Unicast: bij unicast transmissie wordt de data verstuurd van e´ e´ n bron op het netwerk naar e´ e´ n ontvanger. Typisch is dat het aantal connecties evenredig groeit met het aantal gebruikers. De data die over elke connectie loopt is echter onafhankelijk van data op andere connecties. Ook indien dezelfde informatie verstuurd moet worden naar meerdere hosts moet er voor elke host een aparte connectie opgezet worden van bron tot ontvanger. Door dit nadeel is unicast minder geschikt voor een groot aantal gebruikers. Broadcast: bij broadcast transmissie wordt de data gelijktijdig van e´ e´ n bron verstuurd naar alle hosts binnen het netwerk. De hosts moeten alle data verwerken, ook indien deze niet van belang zouden zijn. Hierdoor is het erg ineffici¨ent bij een groter aantal gebruikers. Broadcast wordt niet ondersteund op het Internet, het is meestal enkel toepasbaar op Local Area Networks. Multicast: bij multicast transmissie wordt de data verstuurd naar een set van hosts die zich hebben ingeschreven op een bepaalde service. Host kunnen tijdens de simulatie zich bij andere groepen inschrijven en uitschrijven. Zo is er een grote controle over het 15

versturen van data naar bepaalde gebruikers. Multicast wordt slechts in kleine mate ondersteund op het Internet. Ook security is hier een issue. Anycast: bij anycast transmissie wordt net als bij multicast de data geadresseerd naar een set van hosts, maar de data wordt ten allen tijde enkel naar e´ e´ n host (bv. de meest dichtstbijzijnde) verstuurd.

(a)

(b)

(c)

(d)

Figuur 4.1: Unicast (a), broadcast (b), multicast (c) en anycast (d).

16

4.2

Netwerk architecturen

Een netwerkarchitectuur bepaalt op welke manier de data gedistribueerd kan worden over het netwerk. Bepaalde netwerkarchitecturen schalen beter dan anderen. Hoofdzakelijk zijn er 2 soorten architecturen: Client/Server (C/S) en Peer-to-Peer (P2P) [Fun96]. Ook bestaan er hybride architecturen die de voordelen van beiden trachten te combineren. Oorspronkelijk werd vooral broadcasting en later ook multicasting gebruikt om data te versturen. Dit was zeer geschikt voor lokale netwerken, maar wordt slechts beperkt ondersteund over het Internet. Bovendien is broadcasting erg ineffici¨ent en zorgt voor een hoog verbruik in bandbreedte. Hierdoor is broadcasting niet geschikt voor grotere omgevingen. Multicasting is (theoretisch) echter beter schaalbaar, maar wordt tot dusver slechts heel beperkt ondersteund. Andere architecturen zijn dus nodig.

4.2.1

Client/Server

Bij client/server architecturen communiceren alle clients met e´ e´ n gecentraliseerde server. Deze server beheert de volledige wereld, ontvangt de toestandswijzigingen van alle clients en kan beslissen welke informatie naar wie gepropageerd moet worden. De gebruikers dienen slechts 1 connectie te onderhouden, namelijk deze met de server. Dit verlaagt de netwerklast van de clients enorm. Ze hoeven geen informatie van andere clients bij te houden. De server doet dit voor hun. Deze manier van werken vraagt wel veel van de server. Deze moet immers alle connecties beheren, en is ook verantwoordelijk voor de distributie van de data tussen alle clients. Servers kunnen ook maar een beperkt aantal clients ondersteunen, hetgeen hen minder geschikt maakt voor een grotere schaalbaarheid. Anderzijds levert de server een grotere persistentie. Doordat de data distributie centraal is, kan deze ook eenvoudiger geoptimaliseerd worden.

Figuur 4.2: Elke client connecteert met de server. Voordelen • Gecentraliseerd beheer van de wereld. 17

• Beveiliging is eenvoudiger op te zetten. • Clients moeten enkel een verbinding maken met de server (O(n) connecties). Nadelen • De server wordt een potenti¨ele bottleneck. • Client/server GVO’s zijn in hun zuivere vorm niet goed schaalbaar, omdat de server een beperkt aantal gebruikers kan ondersteunen. • De wereld gaat verloren indien de server crasht. • Extra vertraging treed op omdat alle communicatie via de server gaat. Gedecentraliseerde servers Om de load van 1 server te verdelen kunnen verschillende server toegevoegd worden. Meestal is er 1 master server die alle functionaliteiten van de andere server kent en die de verschillende clients verdeeld onder de andere servers. De clients connecteren eerst met een master server die een lijst bijhoudt van alle servers. De clients vragen informatie (vertraging, aantal deelnemers, ...) op over deze servers. Afhankelijk van deze informatie kies de client 1 server en maakt uiteindelijk een rechtstreekse verbinding met de server van hun voorkeur. Deze server beheert de virtuele omgeving. Meestal zijn er verschillende servers die dezelfde omgeving beheren. Deze servers opereren echter onafhankelijk. Hierdoor kan een gebruikers slechts met een beperkt aantal andere gebruikers communiceren.

Figuur 4.3: Een client connecteert eerst met een master server alvorens met 1 game server te connecteren. Deze game servers zijn niet met elkaar gelinkt. Voordelen • De load wordt over meerdere servers verdeeld. Hierdoor hoeven deze minder zware hardware eisen te stellen. 18

• Een server crash heeft slechts invloed op een beperkt aantal gebruikers. • De simulatie is beter schaalbaar dan zuivere client/server. Nadelen • De clients worden verdeeld over onafhankelijke servers. • Indien de master server crasht is er geen lijst van servers beschikbaar. Gedistribueerde servers Analoog aan gedecentraliseerde servers maken de clients eerst een verbinding met een centrale server. Deze verwijst de clients door naar e´ e´ n server in een cluster van servers die met elkaar verbonden zijn. In tegenstelling tot gedecentraliseerde servers kunnen de clients over verschillende server elkaar blijven zien. Dit zorgt voor een grotere schaalbaarheid. Niet verwonderlijk is deze architectuur vaak gekozen bij grotere online communities.

Figuur 4.4: Een client connecteert eerst met een master server alvorens met 1 game server te connecteren. Deze game servers zijn met elkaar gelinkt. Voordelen • De load wordt over meerdere servers verdeeld. • Alle gebruikers bevinden zich in dezelfde virtuele omgeving. Een gebruiker kan met iedere gebruiker communiceren. Dit levert een grote schaalbaarheid. • Een server crash is minder kritisch en een groot deel van de wereld kan blijven bestaan.

19

Nadelen • De communicatie tussen de verschillende server is cruciaal, en stelt zware eisen van het (lokale) netwerk. • Indien de centrale server crasht worden clients niet doorverbonden naar de andere servers. Proxy servers Een andere variant op de client/server architectuur is het gebruik van proxy servers. Deze proxy servers fungeren dan als laag tussen de clients en de logische servers en databases. Typisch is zo een proxy server verantwoordelijk voor het beheren van een aantal clients. Vanuit een pool van beschikbare proxy servers worden clients toegewezen aan 1 proxy server op basis van een aantal eigenschappen, zoals bijvoorbeeld latency en het aantal connecties. Deze pool van proxy servers wordt beheerd door een centrale entiteit, die instaat voor de authenticatie en het beheer van de netwerk resources. Een proxy server beheert geen entiteiten in de wereld. Dit is de taak van de logische en database servers. Ze verzorgen enkel de communicatie tussen de clients en deze servers. De proxy servers zorgen ervoor dat het aantal connecties die de clients moeten onderhouden met de servers drastisch wordt verminderd. Ook hoeven de logische servers minder connecties te onderhouden, hetgeen hun overhead verminderd. Hiernaast kunnen de proxy servers ook data die passeert cachen, hetgeen de response tijd van de servers verbetert. Een voorbeeld van deze aanpak is het ALVIC-NG algoritme [QCD+ 09].

Figuur 4.5: Een client connecteert met een proxy server, die connecties onderhoudt met de game servers. Voordelen • Zowel de clients als de logische servers hoeven minder connecties te onderhouden, waardoor deze hun resources elders voor kunnen gebruiken.

20

• Deze architectuur is heel schaalbaar, en zorgt voor een abstractie van de verschillende lagen. Nadelen • Complexere architectuur, die een groter aantal servers vereist. • Response tijd tussen client en logische server kan vergroten doordat alle data via de proxy server moet passeren.

4.2.2

Peer-to-peer

In peer-to-peer (P2P) architecturen is er geen centrale server en connecteren de clients onderling met elkaar. De clients dienen zelf de connecties met elkaar op te zetten en te onderhouden. Ze beheren ook de data distributie zelf. Dit stelt hogere eisen van de clients. De toestandswijzigingen worden rechtstreeks naar de andere gebruikers doorgestuurd. Er is geen server meer dit voor extra vertraging zorgt. Dit maakt P2P uitermate geschikt voor real-time niet-kritische data zoals (voice) chat. Het ontbreken van een centrale server lost ook het ’single point of failure’ op. Persistentie en beveiliging is veel complexer. Ook is er geen centrale opslag plaats; de client dienen dit zelf te doen.

Figuur 4.6: Elke peer connecteert met alle andere peers. Voordelen • Minder vertraging omdat de communicatie rechtstreeks gebeurt. • Geen dure serverinfrastructuur noodzakelijk. • Het ontbreken van een server vermijdt een ’single point of failure’. • Het wegvallen van een gebruiker heeft geen grote impact op de virtuele omgeving

21

Nadelen • Het aantal connecties groeit exponentieel met het aantal clients (O(n2 )). • Clients beheren de connecties zelf, hetgeen meer rekenkracht en geheugen vereist. • De gebruiker moet elke message sturen naar iedereen. Dit levert veel (identiek) data verkeer. • Geen controle mogelijk op de data die wordt uitgewisseld. • Geen centrale beveiliging.

4.2.3

Hybride architecturen

Zowel de client/server als de P2P architectuur hebben verschillende nadelen. Toch kunnen beide architecturen worden gecombineerd om zo verschillende van hun nadelen te verhelpen. Hybride architecturen zijn combinaties van P2P aspecten met client/server aspecten. Zo kan bijvoorbeeld een centrale server instaan voor de beveiliging en het algemene beheer van de wereld. Hierbij kunnen clients eventueel rechtstreek met een beperkt aantal andere clients een verbinding opzetten om zo snellere communicatie te verwezenlijken. Meestal zijn deze systemen erg complex.

4.3

Datamodellen

Naast de data distributie en de netwerk architectuur is het beheer van de data van de virtuele omgeving erg belangrijk. Deze datamodellen hebben een effect op de schaalbaarheid, communicatie benodigdheden en de betrouwbaarheid van de GVO [MZ97].

4.3.1

Replicated homogene omgeving

Een eerste datamodel is om de data bij iedere host te bewaren. Elke host heeft dan informatie over het terrein, de geometrie modellen en gedrag van alle entiteiten in de wereld. Doordat deze informatie bij iedere host aanwezig is, dient deze informatie niet over het netwerk verstuurd te worden. Dit levert relatief kleine pakketten op. Hiertegen staat wel dat het model niet echt flexibel is. Wanneer er data wijzigt of nieuwe data wordt toegevoegd in de wereld, dient deze data bij iedere host aanwezig moeten zijn. Dit gebeurt meestal voordat een sessie gestart wordt. Hierdoor kan de initialisatie van een sessie een langere tijd in beslag nemen.

22

Figuur 4.7: Replicated homogene omgeving

4.3.2

Shared gecentraliseerde omgeving

Een andere mogelijkheid is om de data slechts op 1 centrale lokatie bij te houden. De verschillende host hebben dan geen lokale data, ze ontvangen deze van de centrale entiteit. Hierdoor moet wel meer data over het netwerk verstuurd worden. Dit is wel een erg flexibel model. Indien er data wijzigt hoeft deze maar op 1 lokatie aangepast te worden. Dit dient enkel op de centrale entiteit te gebeuren. Maar deze centrale entiteit kan dan een bottleneck worden.

Figuur 4.8: Shared gecentraliseerde omgeving

23

4.3.3

Shared gedistribueerde omgeving

De data kan ook verdeeld worden onder de verschillende host. Ipv. de data dan op 1 lokatie bij te houden, wordt deze data verdeeld onder de host. Hierdoor wordt de bottleneck van de centrale entiteit vermeden. Ook hoeft alle data niet gekopieerd te worden naar alle hosts, zoals bij de replicated model. Nadeling is wel dat dit een grotere belasting is van het netwerk. Elke host dient de lokale data te verzenden naar alle andere hosts. Het is niet evident om een globale consistente omgeving te hebben. Ook beveiliging kan een issue zijn. De shared gedistribueerde omgeving kan zowel op een client/server model als op een peerto-peer model [SKH02]. In het eerste model beheert 1 of enkele servers de communicatie van het datamodel, bij het andere model doen de hosts dit zelf.

Figuur 4.9: Shared gedistribueerde omgeving

4.4

Resource management

Alhoewel de keuze van netwerkarchitectuur een significante impact heeft op de inherente schaalbaarheid van een GVO, kan men ook pogingen ondernemen om de hoeveelheid data die verstuurd moet worden over het netwerk terug te dringen. Er zijn tal van methodes [SKH02] ontworpen die weliswaar wat extra rekenkracht vergen bij de deelnemende hosts, maar de besparing in bandbreedteverbruik maakt dit meestal meer dan goed. De resource in een genetwerkte applicatie zijn meestal beperkt, en kunnen uitgedrukt worden als: Resources = M × H × B × T × P met M het aantal berichten dat verstuurd wordt, H het gemiddelde aantal nodes per bericht, B de gemiddelde bandbreedte nodig om een bericht te versturen, T de tijd waarbinnen een bericht verstuurd dient te worden, en P het aantal process cycles nodig om een bericht te ontvangen en verwerken. Het optimaliseren van 1 van deze resources impliceert meestal het verhogen van een andere resource.

24

4.4.1

Aggregatie

Netwerkpakketten hebben altijd een header nodig waarin ondermeer aangegeven wordt naar welk IP-adres en poort het pakket verstuurd moet worden, hoe groot het gehele pakket (header + data) is, etc. Wanneer er veel kleine pakketten verstuurd moeten worden over het netwerk (bv. positie-updates van deelnemers in de GVO) kunnen de verstuurde headers een groot aandeel hebben in de verbruikte bandbreedte. Door aggregatie toe te passen wacht de verzender met het versturen van pakketjes tot er genoeg data is (quorumgebaseerde aggregatie) of tot een bepaalde tijd verstreken is (time-outgebaseerde aggregatie). De tot dan verzamelde data wordt uiteindelijk gebundeld in e´ e´ n groot pakket waardoor het aantal verstuurde pakketten (incl. headers) afneemt.

Figuur 4.10: Verschillende pakketten worden geaggregeerd tot 1 pakket In gevallen waar de responsiviteit van een GVO van groot belang is kan men het beste aggregatie achterwege laten of een lage timeout waarde instellen. Wanneer het optimaliseren van de netwerkstroom prioritair is zal quorumgebaseerde aggregatie de meest voor de hand liggende keuze zijn. Een combinatie van beide kan gebruikt worden in toepassingen waarbij zowel de responsiviteit als het bandbreedteverbruik geoptimaliseerd moet worden. Voordeel • Door pakketten te groeperen dienen minder pakketten op het netwerk verzonden te worden. Nadeel • Samenvoegen van pakketten levert grotere pakketten. • Her verwerken van deze grotere pakketten vereist meer rekenkracht.

4.4.2

Compressie

Het doel van compressie is het aantal bits terug te dringen die benodigd zijn om bepaalde informatie te beschrijven. Na het comprimeren van netwerkpakketten bij de verzender worden deze kleinere pakketjes verzonden over het netwerk waardoor het bandbreedteverbruik zal afnemen. Bij de ontvanger worden deze pakketjes uiteindelijk gedecomprimeerd. Men kan compressiealgoritmen in 2 categorie¨en indelen door te kijken in welke mate de originele data bewaard blijft na compressie.

25

Bij lossless compressie gaat er geen informatie verloren tijdens het comprimeren, maar het aantal bits dat men hiermee kan uitsparen is sterk begrensd en soms niet voldoende. Bij lossy compressie wordt minder belangrijke data weggelaten of minder nauwkeurig gerepresenteerd om nog betere compressieratios te kunnen halen. Ook kan men een onderscheid maken op basis van de manier waarop deze algoritmen omgaan met data in netwerkpakketten. Interne compressiealgoritmen beschouwen enkel de data binnen e´ e´ n pakket. Er worden geen referenties gemaakt naar eerder verstuurde pakketten. Transmissie over onbetrouwbare netwerkprotocollen zoals UDP is dus perfect mogelijk. Externe compressiealgoritmen kunnen wel eerder verstuurde informatie gebruiken bij het aanmaken van nieuwe pakketten. In plaats van absolute gegevens kunnen ze er voor kiezen om enkel de wijzigingen ten opzichte van vorige toestanden door te sturen indien hier minder bits voor nodig zijn. Als dezelfde data opnieuw zou voorkomen kunnen ze er ook naar refereren in plaats van deze gegevens opnieuw door te sturen. Externe compressiealgoritmen comprimeren beter, maar omdat ze afhankelijk zijn van eerder verstuurde pakketten is transmissie over betrouwbare netwerkprotocollen een noodzaak. Men kan een keuze of een combinatie maken tussen deze vormen van compressie op basis van verschillende factoren: • Frequentie van updates • Inhoud van pakketten • Soort van toepassing • Architectuur en protocollen voor distributie van pakketten Voordeel • Compressie zorgt voor kleinere pakketen. Nadeel • Verwerking van deze pakketten kost extra rekenkracht.

4.4.3

Dead reckoning

Een andere methode om bandbreedteverbruik terug te dringen is simpelweg minder updates doorsturen. Het tekort aan informatie moet dan wel op andere manieren gecompenseerd worden. In het bijzondere geval van positie-informatie kan dead reckoning toepast worden. Hierbij gaat een voorspellingstechniek aan de hand van vorige ontvangen positieupdates (met hun eventuele locatie/snelheid/versnelling) de huidige positie van een object voorspellen. Deze berekende posities worden gebruikt totdat er een nieuwe update met de werkelijke locatie van het object binnenkomt. Een convergentietechniek moet er dan voor

26

zorgen dat het eventuele verschil in positie op een zo realistisch mogelijke wijze gecorrigeerd wordt.

(a)

Figuur 4.11: Dead reckoning. Voordeel • Minder positie-updates op het netwerk zijn nodig. Nadeel • Er is een kans op fouten door predictie. Hierdoor is convergentie nodig. • Niet iedere gebruiker heeft exact zelfde view, aangezien de predictie kan afwijken van de eigenlijke data. • Meer process time is nodig, vooral bij convergentie. • Kan erg complex worden qua implementatie.

4.4.4

Level of detail

Hoe verder objecten verwijderd zijn van het gezichtspunt, hoe minder details we er van kunnen opmerken. Hierop kan ingespeeld worden door deze objecten minder gedetailleerd te renderen in de virtuele omgeving of er minder frequent updates van uit te sturen. Meerdere datakanalen kunnen per object gebruikt worden om deelnemers van zowel gedetailleerde informatie als ruwe informatie te voorzien. Naarmate de gebruikers zich dichterbij het object begeven schrijven ze zich ook in op de kanalen die gedetailleerde informatie bevatten.

27

Figuur 4.12: Verschillende levels of detail. Voordeel • Snellere rendering door eenvoudigere primitieven. • Het verzenden van eenvoudigere primitieven kost minder bandbreedte. Nadeel • Verschillende representaties zijn nodig voor zelfde entiteit. • Meer pakketten dienen verzonden te worden, omdat 1 entiteit verschillende representatie kent. • Meer processing door keuze uit verschillende representaties.

4.4.5

Zoning

Bij zoning wordt de wereld op voorhand ingedeeld in regio’s waarin de gebruikers enkel met elkaar connecteren en updates uitwisselen. De beste regio’s zijn deze die de deelnemers zo evenredig mogelijk verdelen. Zoals we verder zullen zien is dit eigenlijk een beknopte vorm van interest management waarbij enkel de locaties van de deelnemers een rol spelen bij het bepalen van de interesse-expressies.

Figuur 4.13: Verdeling van een UT2003 omgeving in verschillende zones

28

4.4.6

Interest management

De informatie die op het netwerk gezet wordt is niet voor elke gebruiker even interessant. Een piloot van een vliegtuig hecht normaal gezien veel meer belang aan de vliegroutes van andere vliegtuigen dan aan de verplaatsingen van willekeurige personen op de begane grond. Ook is het onzinnig om updates te ontvangen van objecten waar toch geen interactie mee mogelijk is (bv. onzichtbare objecten die te ver verwijderd zijn in de virtuele omgeving). Door interest management technieken toe te passen kan een deelnemer aangeven welke subset van informatie voor hem relevant is en in welke mate. Hiermee rekening houdend kunnen onnodige berichtenstromen op het netwerk zo veel mogelijk vermeden worden en moeten de gebruikers zelf veel minder tijd besteden aan het verwerken van irrelevante informatie. In het volgende hoofdstuk wordt interest management in meer detail besproken.

4.5

Conclusie

Genetwerkte Virtuele Omgevingen zijn systemen waarin enorme aantallen gebruikers met elkaar kunnen interageren in real-time. Grote gevoel van betrokkenheid en realisme. Om de consistentie van de virtuele omgeving te garanderen moeten veel toestandswijzigingen uitgewisseld worden over het netwerk. Schaalbaarheid als uitdaging. Verschillende technieken om de schaalbaarheid te vergroten werden besproken, met hun voor- en nadelen. Interest management speelt hierin een belangrijke rol.

29

Hoofdstuk 5 Interest Management Zoals eerder vermeld kan interest management gebruikt worden om de set van ontvangen berichten te reduceren tot enkel de set van berichten die relevant zijn voor de ontvangers.

5.1

Definitie

Vaak wil men enkel communicatie tussen gebruikers die ’interesse’ hebben in elkaar. Hierbij drukken de deelnemers in het netwerk hun area of interest (AOI) uit door gebruik te maken van interesse-expressies (IEs). Deze interesse-expressies geven aan welke data een deelnemer nodig heeft om met de andere deelnemers correct te kunnen interageren. Hierin wordt gerefereerd naar eigenschappen van de zendende deelnemer of zijn entiteiten, bv. het type entiteit (alle grondvoertuigen...), het gewenste bereik (...binnen een straal van 4km...) of de frequentie van de te ontvangen informatie (...elke minuut). Interest managers (IMs), die deel uitmaken van de simulatie-infrastructuur, filteren dan aan de hand van deze interesse-expressies de berichten naar enkel die subsets die relevant zijn voor de ontvangers.

5.2

Specificatie van interesse-expressies

Een interesse-expressie is een benadering van de area of interest van een entiteit. Specificiteit is de kracht van een taal of formalisme om IEs in uit te drukken (of het verschil tussen de data die de deelnemer wilt en de data die hij mag vragen). Men onderscheidt 3 verschillende klasses: formules, cellen en uitbreidingen.

5.2.1

Formules

De meest intu¨ıtieve manier om interesse-expressie uit te drukken is mbv. formules. Bij formules gebruikt men een mathematische of predikaat-formule om de interesse-expressie te specifi¨eren. Een voorbeeld van zo een formule is class(entity) = ground vehicle&distance(entity, self ) < 4 Door deze formule te gebruiken zou men updates kunnen ontvangen van grondvoertuigen die zich hoogstens 4km van de aanvrager bevinden. Hoewel dit conceptueel eenvoudig is, is de implementatie van formules vrij complex. Er wordt verwacht dat de interest manager 30

afstanden kan berekenen tussen de verschillende entiteiten, en dit in de juiste eenheid. Dit is niet triviaal omdat dynamische entiteiten voortdurend kunnen bewegen binnen de virtuele omgeving. Wanneer entiteiten zich bewegen dient de IM voortdurend deze formules opnieuw te evalueren. Evaluatie van dergelijke formules is in de praktijk erg kostelijk. Ook kunnen berichten eventueel ge¨evalueerd worden met meerdere formules, wat een hoge overhead veroorzaakt bij de interest manager.

Figuur 5.1: AOI met formules. Het JPSD algortimen [PLWT96] maakte gebruik van formule filtering met predicaten in conjunctieve normaalvorm. Mogelijke termen zijn is-gelijk-aan, valt-binnen-bereik of functie die true of f alse evalueren. Ook ALSP [MBD00] gebruikte formules voor filtering.

5.2.2

Cellen

Een simpelere implementatie zijn cellen. Cellen verdelen de ruimte op voorhand in discrete gebieden. Alle deelnemers weten hun eigen positie en kunnen hieruit afleiden naar welke cellen men informatie moet sturen en van welke cellen men informatie kan ontvangen. Het betreden en het verlaten van een gebied kan impliciet via multicast of expliciet met join/leave berichten gebeuren. De verwerkingstijd van berichten ligt nu een stuk lager omdat ze simpelweg gepropageerd kunnen worden naar de relevante cellen zonder elk bericht a.d.h.v. formules te evalueren. Het managen van cellen veroorzaakt weinig overhead bij de interest manager, maar door de discretisering kan de kwaliteit van het filteren verminderen. Een entiteit met een kleine area of interest maar die dicht bij de rand van meerdere cellen ligt krijgt ineens te veel data binnen.

Figuur 5.2: AOI met cells. In dit voorbeeld dient de tank te communiceren met 9 cellen. Een voorbeeld van filtering met cellen is te vinden in het ModSAF [SRS95] algoritmen. De omgeving werd vooraf opgedeeld door middel van een eenvoudige grind. Gedurende de 31

simulatie werden deze cellen niet aangepast. NSPNET [MBZ+ 95] verdeelde de omgeving het zeshoeken, die dichter aanleunen bij de realiteit (waar cirkels het meest representatief zijn). Andere voorbeelden zijn CCTT en STOW-E.

5.2.3

Extensies

Implementatie gebaseerd op extensies kunnen een balans geven tussen cellen en formules. Bij extensies worden de interesse-expressies gelimiteerd tot n-dimensionale rechthoeken in de vooraf bepaalde filterruimte, maar de bepaling van grootte en de locatie gebeurt atruntime. Met behulp van deze techniek kan men data met meer precisie filteren dan cellen, maar met minder precies dan formules. De intersectieberekeningen tussen extensies zijn eenvoudiger dan formule-evaluaties en moeten enkel berekend worden wanneer de extensies wijzigen in plaats van voor elk bericht. Het managen van extensies zorgt wel voor een hogere overhead bij de interest manager dan bij cellen. Voorbeelden van extensie filtering is terug te vinden in HLA en STOW ACTD.

Figuur 5.3: AOI met extents.

5.2.4

Precisie van interesse-expressies

Onder precisie verstaat men het verschil tussen de data die de deelnemer vraagt en de data die hij uiteindelijk krijgt. Een interest manager is enkel correct wanneer hij op zijn minst de gevraagde data levert, zij het exact de gevraagde data of ongeveer. Voorbeelden van exacte precisie zijn ModSAF, NSPNET en JPSD. Een benaderende filtering werd gebruikt bij STOW ACTD en HLA.

5.3

Frequentie van interesse-expressies

Ook het tijdstip waarop het domein van IEs vast gelegd wordt is van belang.

5.3.1

System Design

Wanneer tijdens het ontwerp van een systeem de interesse-expressies reeds vastgelegd worden, dan heeft de IM gebruiker hier totaal geen controle over. Enkel de vastgelegde queries mogen gesteld worden. Oudere systemen zoals ModSAF, ALSP, CCTT, NSPNET en de vroegere STOW [HCNF94] algoritmen kende filtering vastgelegd tijdens system design. 32

5.3.2

Execution Initiation

Hierbij kunnen de simulatiedesigners tot vlak voor de executie vastleggen welke interesseexpressies mogelijk zijn. Tijdens de simulatie kunnen dan geen nieuwe expressies worden toegevoegd. Dit levert een grotere flexibiliteit op in vergelijking met de system-design aanpak. Bovendien kan de IM zo worden geoptimaliseerd dat niet relevante data tijdens de execution niet nodeloos wordt meegenomen in de berekeningen. Filtering gedefinieerd tijdens de initialisatie fase gebeurt in de JPSD, STOW-ED en HLA algoritmen.

5.3.3

Runtime

At-runtime evaluaties geven de meest flexibele oplossing. Op eender welk tijdstip kan eender welke data gevraagd worden in de hoop dat een andere simulator deze voorziet. De IM voorziet enkel een algemene syntax voor deze evaluaties. Dit geeft een grotere vrijheid aan de simulaties. Een voorbeeld is JPSD.

5.3.4

Frequentie/temporeel

Typisch heeft niet elke simulatie alle data nodig van de andere simulaties. Men kan dan aan een IM vragen om niet alle berichten te propageren, maar slechts om een gegeven aantal berichten (frequentie) of een gegeven aantal tijdseenheden (temporeel). Zo kan met het aantal updates van entiteiten die van minder belang zijn verder beperken. Een beperkte vorm waar de frequentie van updates werd beperkt is te vinden in ModSAF en STOW-E.

5.4

Architectuur

De architectuur van het netwerk heeft ook zijn invloed. De IM-filtering kan simpelweg een impliciete overeenkomst zijn tussen deelnemers (bv. het gebruik van multicast) of een software implementatie bij de deelnemer zelf of elders op het netwerk. Filtering kan op 3 locaties gebeuren: bij de bron, bij de ontvanger of er tussenin. Filtering tussen bron en ontvanger kan verschillende vormen aannemen, van een node tussen deze in tot een multicast router.

5.4.1

Bij de bron

Filtering bij de bron heeft het hoogste potentieel om het dataverkeer te verminderen. Alle data die de bron reeds kan uitsluiten hoeft al niet meer over het netwerk verzonden te worden. Zo wordt het merendeel van data reeds gefilterd vooraleer het netwerk bereikt. JPSD is hiervan een voorbeeld.

33

5.4.2

Bij de ontvanger

Filtering bij de ontvanger is meestal het meest correct. De ontvanger kan immers zelf de lokale simulatie kiezen om zo de data van de zenders optimaal te kunnen verwerken. Omdat de ontvanger data van elke zender krijgt, is de kans om fouten minimaal. Nadeel bij deze manier van werken is dat er geen vermindering is van het dataverkeer. Alle zenders blijven naar alle ontvanger data versturen. Ook is er geen mogelijkheid om de verwerking van deze data te beperken. Deze manier van werken werd gebruikt voor ModSAF.

5.4.3

Tussen bron en ontvanger

Om bron of ontvanger te ontlasten kan de filtering ook tussen beide gebeuren. De precisie kan lager zijn dan filteren bij de bron of ontvanger gezien zowel de belangen voor filtering van de bron en ontvanger gegroepeerd kunnen worden. Het STOW-E [HCNF94] algoritme had voor elke LAN een node bij de WAN overgang, die data van de andere nodes ontving en verzamelde. Deze data werd dan binnen de LAN verstuurd. Deze nodes zorgde ook voor de filtering. Ook CCTT en NPSNET filteren tussen bron en ontvanger.

5.4.4

Multicast

Multicast wordt als netwerkarchitectuur gebruikt bij Interest Management. De GVO wordt opgedeeld in verschillende berichtgroepen (per regio, per type van entiteiten,...) en deelnemers schrijven zich in op groepen die overeenkomen met hun AOI. Zowel het netwerkverkeer als de verwerking ervan kan vrij goed verminderd worden. Elke deelnemer verwerkt enkel een relevante set van berichten, namelijk deze binnen hun groep. Nadeel van het gebruikt van multicasting is de beperkte ondersteuning binnen netwerken. Er zijn niet genoeg adressen beschikbaar om grootschalige multicast applicaties mogelijk te maken. Ook het opzetten van goede multicast groepen is niet evident en kan enige tijd kosten.

Figuur 5.4: Schaalbaarheid van Client-Server(a) en Multicast(b). Duidelijk te zien is dat multicasting minder impact ondervind van het aantal nodes. Bij CCTT [MR95] wordt de omgeving verdeeld over een discrete grid. Aan elke cel van de grid wordt een multicast groep toegekend. At-runtime worden deze groepen niet aangepast. Elke node wordt ingeschreven in 1 groep, en kan door van cel te veranderen 34

groepen verlaten of ertoe treden. Andere multicast toepassingen zijn ModSAF, NPSNET en STOW-ED.

5.5 5.5.1

Implementaties Verdeling over server cluster

1 server heeft een beperkt aantal connecties mogelijk. Om dit schaalbaarheidsprobleem te verhelpen, kunnen verschillende servers in cluster worden gebruikt. Het verdelen van de client over deze servers is echter niet evident. Een client wil immers met eer server geconnecteerd zijn die een lage latency heeft, en die geconnecteerd is met andere client waarin de ene client ge¨ınteresseerd is. Een predictie patroon kan de verdeling vergemakkelijken [SAh03]. Density maps geven weer waar veel client bij elkaar zijn. Het model kan dan verdeeld worden door een threshold te vergelijken met de som van de dichtheden van een bepaalde regio. Een eerste mogelijke verdeling kan gebeuren met een quad tree. De relatieve dichtheid van een regio wordt berekend en indien deze boven een bepaalde threshold ligt, dan wordt deze regio verdeeld in 4 kleinere regio’s. Er wordt hier gestart met 1 regio. Een andere oplossing is het gebruik van een K-d tree. Hier wordt de regio slechts in 2 onderverdeeld, door een horizontale of verticale lijn. Deze lijn dient de dichtheid van beide regio’s evenredig te splitsen. De onderverdeling kan echter ook de regio’s niet gelijk verdelen, indien een verdere onderverdeling een betere schaalbaarheid oplevert.

5.5.2

IM in P2P-NVE systemen

De client/server architectuur kent een zekere limiet voor het aantal gebruikers. Een server kan maar een bepaald aantal connecties onderhouden. Deze beperking blijft ook deels bestaan in een multi server omgeving. De meest schaalbare omgevingen zijn peer-to-peer omgevingen [HCC06]. Deze kennen echter geen limiet op het aantal host. Om P2P GVO’s schaalbaar te maken is er een ’neighbor discovery’ algoritme nodig. Het is immers onmogelijk voor een host om met alle andere host te communiceren. Er is enkel communicatie mogelijk met een beperkt aantal. Daarom is de keuze van host waarmee gecommuniceerd wordt cruciaal. Dit dienen hosts te zijn dit zich in de omgeving van de gebruiker. Hieronder volgt een overzicht van enkele van de belangrijke P2P implementaties die gebruik maken van een ’neighbor discovery’ algoritme. Enhanced point to point Hierbij heeft elke peer weet van de andere peers in de simulatie maar worden Interest Management technieken toegepast zodat enkel de relevante berichten verstuurd worden. Voorbeelden zijn Update Free Regions (UFR) [GG04] waarbij enkel berichten verstuurd worden tussen peers wanneer ze elkaar kunnen zien. Hiervoor worden voor elkaar onzichtbare gebieden in de GVO met elkaar gekoppeld. Wanneer beide peers in verschillende UFRs blijven moeten geen berichten uitgewisseld worden, pas wanneer een van beide zijn UFR 35

verlaat is dit nodig. Er kan dan een nieuwe UFR opgesteld worden als ze elkaar nog steeds niet kunnen zien, in het andere geval worden berichten verstuurd naar elkaar. Echter schaalt Enhanced point to point niet goed: elke peer moet communiceren met alle andere peers. Bij crowding zijn veel buren zichtbaar en ook wanneer de GVO niet genoeg occlusie voorziet (te veel visibiliteit) moeten er te veel berichten worden verstuurd. DHT Gezien multicast-hardware niet wijdverspreid is werden er pogingen ondernomen om multicast op de applicatielaag te verwezenlijken (bv. SimMud). Hierbij wordt een Distributed Hash Table (DHT) [Knu04] gebruikt als onderliggende infrastructuur. De GVO wordt opgedeeld in regionen, waarbij voor elke regio een peer als supernode wordt beschouwd, die in feite de root is van een multicast tree. Deze supernode ontvangt updates van alle andere peers uit het gebied en stuurt toestandswijzigingen door naar hen. Links tussen supernodes maken het mogelijk om als peer van gebied te veranderen. Nadelen hierbij zijn dat een supernode overwelmd kan worden door crowding in een bepaald gebied, en omdat supernodes alle pakketten doorsturen kan er veel vertraging optreden. Neighbour list exchange Bij deze methode worden er geen supernodes of servers gecontacteerd om de dichtstbijzijnde peers te ontdekken, maar wordt beroep gedaan op de buurlijsten van reeds bestaande peers [KAM04]. Om nieuwe buren te ontdekken worden deze lijsten continu uitgewisseld tussen de peer in kwestie en zijn meest dichtstbijzijnde buren (volledig gedistribueerd schema). Omdat er directe connecties opgesteld worden is de vertraging zeer laag, maar er moet wel enorm veel berichten verstuurd worden naar elkaar omdat de buurtlijsten continu uitgewisseld moeten worden. Indien peers ver uit elkaar komen te liggen kunnen nodes zelfs contact met tussenpersonen verliezen waardoor het netwerk gepartitioneerd wordt. Dit kan wel verholpen worden door een schema te gebruiken waarbij elke peer ten minste een buur bewaart in elke 4 draairichtingen van de peer, waardoor de globale connectiviteit bewaard blijft. Mutual Notification Omdat er veel redundante informatie verstuurd wordt bij neighbour list exchange kan men beter enkel wanneer het noodzakelijk is nieuwe buren op de hoogte brengen van de huidige situatie [KS02]. Hierdoor connecteert elke peer met de buren in zijn AOI, die deze peer dan op de hoogte zullen brengen wanneer er nieuwe peers aankomen. Elke node dient in de polygoon te blijven van zijn buren om globale connectiviteit te garanderen. Indien dit niet het geval is kan het vinden van nieuwe buren soms mislopen. Om dit te verhelpen moet er actief gezocht worden naar nieuwe buren waardoor de ontdekkingsprocedure vertraagt. Client-Server hybrid Knopen worden georganiseerd in groepen en maken gebruik van multicast reflectors om gewenste informatie te versturen, te verkrijgen en nieuwe buren te ontdekken [RBD04].

36

Deze multicast groepen worden gecre¨eerd en gemodificeerd door control servers, waar de knopen bij terecht kunnen om de mapping te verkrijgen tussen de groepen en de multicast reflectors. De schaalbaarheid van het gehele netwerk hangt ook hier af van de maximale bandbreedte en verwerkingskracht van de server cluster. P2P hybrid Hierbij worden technieken zoals DHT, neighbour list exchange en direct transfer bij elkaar gebracht [YV05]. De GVO wordt opgedeeld in hexagonale cellen, en DHT zorgt voor de globale connectiviteit. Per cel houdt een meesterknoop een lijst bij van slaafknopen en wisselt zijn lijst uit met dichtstbijzijnde meesterknopen. De slaafknopen worden door de meesterknopen op de hoogte gebracht van nieuwe buurknopen. Slaafknopen wisselen onderling rechtstreeks informatie uit om vertraging te voorkomen. Om crowding tegen te gaan moet een voldoende aantal meesterknopen gealloceerd worden. De frequentie van uitwisseling is ook hier een balanceren tussen bandbreedteverbruik en tijdige buurontdekking. Voronoi gebaseerd VON [HCC06] is een Voronoi gebaseerde implementatie. Een Voronoi diagram verdeeld een vlak in een Voronoi regio’s, zodat elke regio die punten bevat die dichter bij een vastgelegd ge¨ısoleerd punt van die regio’s site dan de vastgelegde geisoleerde punten van alle andere regio’s. Voor een entiteit wordt met behulp van een AOI aura de ’enclosing’ en ’boundary’ buren gezocht. Enclosing buren zijn buren diens regio volledig binnen de aura vallen, en boundary buren zijn deze waar de regio slechts gedeeltelijk erbinnen vallen. Elke entiteit houdt dan een rechtstreekse connectie met zijn buren. Om dit aantal beperkt is, is de kost om de Voronoi diagram up-to-date te houden laag.

(a)

Figuur 5.5: Voronoi gebaseerd design. Binnen de AOI heeft een element (blauwe circel) enclosing neighbors (rode vierkanten en sterren) and boundary neighbors (rode driehoeken en sterren). Updates worden dan naar elke van deze buren gestuurd, alsook naar enclosing buren buiten de AOI aura. Buren worden herkend door communicatie van de boundary buren. 37

Tijdens het verplaatsen van een entiteit zal deze constant nieuwe entiteiten ontdekken, en met andere entiteiten hun connectie afbreken wanneer deze zich buiten de aura bevinden. Hierdoor wordt er enkel gecommuniceerd met de buren binnen de AOI, zodat VON een uiterst schaalbaar algoritme is onafhankelijk van de schaal van de omgeving. Wanneer een entiteit onder crowding kan zwichten, dan zal diens aura verkleint worden om dit tegen te gaan. Deze aura zal terug naar de oorspronkelijke grootte veranderen indien het aantal geconnecteerde buren onder een bepaalde limiet vallen. Besluit Hoe meer gedistribueerd, hoe meer responsief het systeem wordt, ten koste van een hoger bandbreedteverbruik. Er is minder bandbreedte vereist wanneer superknopen minder tolerant zijn voor crowding en het uitvallen van knopen. Andere verschillen zijn de snelheid van buurontdekking en de mogelijkheid om gebeurtenissen te rangschikken. Peer to Peer netwerken zijn potentieel meer schaalbaar dan Client-Server designs, maar de meest voorkomende problemen zijn de tolerantie voor crowding en de snelheid waarbij buurknopen ontdekt kunnen worden.

5.6

Conclusie

Interest management werd verder besproken als oplossing voor de schaalbaarheid. Verschillende aspecten van IM werden uit de doeken gedaan, en werden met elkaar vergeleken. Ook werden verschillende implementaties van IM aangehaald, met hun voor- en nadelen.

38

Hoofdstuk 6 Visibility (culling) 6.1

Inleiding

Een van de meest fundamentele problemen binnen de Computer Graphics is het opdelen van alle objecten in een scene als (deels) zichtbaar of onzichtbaar vanuit een bepaald standpunt. In de jaren ’70 werden Hidden Surface Removal (HSR) technieken ontwikkeld om de zichtbare delen van grafische primitieven in een beeld te detecteren. Dit probleem is grotendeels opgelost: voor interactieve applicaties wordt meestal een Z-buffer algoritme gebruikt. Door de steeds toenemende grootte van 3D datasets is het vaak echter te duur om alle objecten in real-time te verwerken in de rendering pipeline. Visibility culling technieken proberen de onzichtbare objecten in een scene zo vlug mogelijk te detecteren en deze buiten beschouwing te laten voor verdere verwerking. Idealiter wordt enkel de zichtbare subset van primitieven bewaard: deze die op zijn minst een bijdrage van 1 pixel in het uiteindelijke beeld leveren. Waar dure HSR algoritmen detecteren welke delen van polygonen zichtbaar zijn, moeten de goedkopere visibility culling algoritmen enkel beslissen welke polygonen onzichtbaar zijn. Doordat visibility culling technieken hopelijk conservatief het aantal zichtbare polygonen overschat, kan men achteraf Hidden Surface Removal uitvoeren op slechts een subset van het origineel aantal polygonen om alsnog correcte beelden te bekomen. De performantiewinst die men kan halen uit het toepassen van visibility culling hangt sterk af van de te renderen scene. In grote, dicht bebouwde omgevingen kan de zichtbare set van polygonen vanuit een bepaald standpunt slechts een fractie blijken van het totale aantal polygonen waardoor het render-proces enorm versneld wordt. In open sc`enes waar weinig culling kan plaatsvinden zal de winst miniem zijn. Desalniettemin zouden goede visibility culling technieken output sensitive moeten zijn: de berekeningstijd hangt hierbij af van het aantal zichtbare polygonen. Er bestaan verschillende soorten visibility culling: • Back-face culling mijdt het renderen van polygonen die wegkijken van het gezichtspunt.

39

• View-frustum culling mijdt het renderen van objecten die buiten het gezichtsveld liggen. Indien de objecten deels buiten het gezichtsveld liggen wordt het onzichtbare deel verwijderd door een clipping algoritme. • Contribution culling mijdt het renderen van objecten die weinig tot geen bijdrage leveren in het uiteindelijke beeld. • Occlusion culling mijdt het renderen van objecten die afgeschermd worden door een andere objecten (occluders) in de scene.

(a)

Figuur 6.1: Visibility culling technieken: view-frustum culling, back-face culing en occlusion culling.

6.1.1

Potentially visible sets

Potentially visible sets berekenen vooraf voor alle mogelijke viewpoint de zichtbare objecten [Laa03]. Voor elke viewpoint worden deze objecten bijgehouden en at-runtime worden enkel deze objecten gerenderd die door de vooraf berekende viewpoint zichtbaar zijn. Het berekenen van de zichtbare objecten uit alle mogelijke viewpoint is echter niet haalbaar. Daarom wordt de 3D omgeving meestal onderverdeeld in verschillende cellen. Voor elke cel wordt dan de mogelijke zichtbare objecten gerekend, en at-runtime wordt dan de cel gebruikt waar de viewpoint binnen valt.

6.1.2

Voorbeeld

In figuur 6.2 zien we hoe het gebruik van Potentially Visible Sets kan helpen bij het renderen van een 3D scene (afbeelding (a)) uit een computerspel. In afbeeldingen (b) en (c) zien we dezelfde scene weergegeven als draadmodel, waarbij enkel de ribben van effectief gerenderde polygonen worden afgebeeld. Merk op dat in afbeelding (b) alle polygonen die binnen het gezichtsveld liggen worden gerenderd, ook al zijn ze onzichtbaar vanuit het 40

huidige gezichtspunt. In afbeelding (c) worden zo veel mogelijk onzichtbare polygonen verwijderd van de scene vooraleer deze gerenderd wordt, waardoor het renderproces sneller kan verlopen.

(a)

(b)

(c)

Figuur 6.2: a) Een gerenderde scene. b) Wireframe (PVS aan). c) Wireframe (PVS uit).

6.2

Occlusion culling

Omdat occlusion culling relaties tussen objecten moet beschouwen is het een globale visibility culling techniek en meer complex dan de 3 andere soorten van visibility culling. Een onderscheid kan gemaakt worden tussen algoritmen die occlusion culling berekenen voor een bepaald gezichtspunt (point-based) of voor een heel gebied in de ruimte (fromregion) [CoCSD00]. Het voordeel van from-region algoritmen is dat de berekende visible set geldig is voor meer dan 1 frame en dat de kost van deze te berekenen dus gespreid kan worden over de tijd. Ook kan men objecten die zichtbaar zouden kunnen worden in naburige cellen al op voorhand kunnen inladen. De preprocessing tijd en de benodigde opslagruimte liggen echter een stuk hoger dan bij point-based algoritmen en het is ook moeilijker voor from-region algoritmen om bewegende objecten correct af te handelen. Point-based algoritmen hebben beeld- of objectprecisie naargelang hun visibiliteitsberekeningen als input de hele objecten zelf of hun representatie als fragments in het rasterisatieproces gebruiken voor hun berekeningen. Binnen from-region algoritmen vinden we cell-and-portal en generic scenes methodes. Cell-and-portal algoritmen delen de omgeving op voorhand in cellen met als links ertussen portals. Ze beginnen met een lege potentieel zichtbare set van objecten voor elke cel en voegen objecten toe die zichtbaar zijn door een reeks van portals. Generic-scenes algoritmen daarentegen beschouwen alle objecten eerst als zichtbaar en proberen dan te achterhalen welke objecten onzichtbaar zijn, zonder specifieke karakteristieken van de omgeving uit te buiten. De manier waarop visibiliteitsalgoritmen zichtbare van niet-zichtbare polygonen onderscheiden heeft een impact op de beeldkwaliteit (met of zonder fouten) en de performance at-runtime (optimaal of suboptimaal). • Conservatieve algoritmen overschatten consistent de zichtbaarheid van polygonen. Dit resulteert uiteindelijk wel in correcte beelden, maar de performance at-runtime 41

is suboptimaal omdat bepaalde niet-zichtbare polygonen toch doorgestuurd worden naar de rendering pipeline. • Agressieve algoritmen onderschatten consistent de zichtbaarheid van polygonen. Hierdoor treden fouten op in beelden gezien sommige zichtbare polygonen niet gedetecteerd worden. Deze worden gebruikt voor sc`enes waar conservatieve algoritmes te veel overschatten, de foutenmarge moet wel acceptabel blijven. • Benaderende algoritmen labelen zowel zichtbare polygonen als niet-zichtbaar en omgekeerd. Ze worden alleen gebruikt wanneer de preprocessing kost zo laag mogelijk moet blijven. • Exacte algoritmen berekenen optimale (exacte) zichtbare sets van polygonen. Enkel de werkelijk zichtbare polygonen worden gevonden, wat leidt tot correcte beelden en een optimale at-runtime performance. Ze zijn echter ingewikkeld te implementeren en de pre-processing kost ligt voor deze algoritmen een stuk hoger.

6.3 6.3.1

From-region methods Cells and portals

Deze methoden zien de wereld opgedeeld in cellen. Portals zijn de openingen tussen de cellen waardoor de ene cel de andere ziet. Voor elke cel wordt een potentially visible set berekend. Deze set is een groep van objecten die mogelijks zichtbaar zijn vanuit de cel. At run-time wordt deze set gebruikt om verder de zichtbare polygonen te berekenen. Volume-to-polygon visibility Airey stelde 2 technieken voor om een PVS te berekenen: een methode die door het berekenen van schaduw volumes de visible set conservatief bepaalt en een point sampling variant waarbij ray shooting de visible set agressief bepaalt [ARFPB90]. Vooraf moet de scene opgesplitst worden in een aantal cellen. De onderverdeling dient voor elke cel een zo klein mogelijke PVS te genereren (voor de grootst mogelijke performantiewinst) met toch een zo klein mogelijk aantal cellen (te ineffici¨ent om voor elk viewpoint een PVS te berekenen). Alle grote gesloten oppervlakken in de scene worden gecontroleerd of ze een goede opdeling van de scene opleveren. Een oppervlak is een goede kandidaat indien het de huidige scene evenredig verdeeld (de balans factor), indien de 2 delen goed van elkaar verborgen zijn (de occlusion factor) en indien er niet te veel individuele polygonen worden gesplitst(de split factor). Voor elke cel wordt een set van zichtbare objecten bepaald. Hierbij zorgen de portals tussen de cellen ervoor dat objecten in aangrenzende cellen ook zichtbaar kunnen zijn. Een subset van de objecten in deze cel dient mee toegevoegd te worden aan de set van zichtbare cellen. Er werden 2 manieren om deze objecten te bekomen voorgesteld.

42

Een eerste methode maakt gebruikt van point sampling om de zichtbare objecten door een portal te bepalen. Deze techniek leunt sterk aan tegen point sampling in radiositeit. De gevonden objecten vormen echter enkel een subset van de mogelijke zichtbare objecten. De andere methode berekend occlusie relaties tussen polygonen. Dit is gebaseerd op shadow volumes [Cro77]. Dit is echter een duur proces. Hierdoor wordt een gedeeltelijke oplossing gebruikt, die de set zichtbare objecten gaat overschatten. Cell-to-cell visibility Een andere manier om visibility tussen cellen te bepalen is door gebruik te maken van een visibility graph [TS91]. De scene wordt opgedeeld in cellen aan de hand van de voornaamste ondoorzichtbare oppervlakken, zoals muren. Kleinere objecten worden niet beschouwd als occluders, en worden in de preprocessing stap niet gebruikt. Op de grenzen van de cellen worden de doorzichtbare oppervlakten gezocht. Dit zijn bijvoorbeeld deuren en ramen. Met deze portals kan dan een graph worden opgesteld die aangeeft welke cellen aan elkaar grenzen.

(a)

Figuur 6.3: Adjacency graph en stab tree.

Nu kan de zichtbaarheid tussen de cellen bepaald worden. 2 cellen kunnen elkaar zien als er een punt van de ene cel verbonden kan worden met een punt van de andere via een sequentie van portals. De adjacency graph wordt iteratief doorlopen om te bepalen of 2 portals elkaar kunnen zien. Vanaf een cel wordt voor elke portal nagegaan of er in de volgende cel portals zijn die zichtbaar zijn vanuit de oorspronkelijke cel. In bovenstaand voorbeeld heeft cel A een portal naar cel B. Dan worden alle portals van cel B afgelopen en wordt gecontroleerd of er portals zijn die zichtbaar zijn vanuit cel A via de portal met cel B (hier C, D en E). Indien dit het geval is, is de cel zichtbaar vanuit cel A. Vanuit deze cel worden dan ook weer alle portals beschouwd, en wordt bepaald welke zichtbaar zijn. Voor elke cel wordt dan een set van zichtbare cellen bijgehouden. 43

At run-time wordt van de huidige cel via de potentially visible set enkel nog een subset van de objecten gecontroleerd op zichtbaarheid. Een cel is zichtbaar indien ze binnen het view-volume ligt, alle cellen in de stab tree binnen het view-volume liggen en er een lijn bestaat binnen het view-volume dat via de portals deze cel bereikt. Conservatieve benadering De benaderende techniek bestaat erin om iteratief de grenzen van de zichtbare regio aan te passen. Wanneer elke portal wordt toegevoegd, worden de omgrenzende oppervlakken die de zichtbare regio omvatten ge¨update. Deze oppervlakken komen overeen met een visual event. Voor elke rand van een portal worden alleen de externe oppervlakken beschouwd. Invloed van cellen Het aantal cellen speelt een belangrijke rol in de complexiteit van potentially visible sets. Grotere cellen resulteren in een groter aantal zichtbare objecten dat in rekening wordt gebracht voor een viewpoint. Vele objecten worden als mogelijk-zichtbaar beschouwd, en de at-runtime berekeningen nemen toe. Wanneer er anderzijds een groter aantal cellen zijn, neemt de berekentijd at-runtime af, maar deze preprocessingtijd neemt toe. Ook de opslagcapaciteit zal vergroten. Het bepalen van het aantal cellen is een afweging die voor iedere omgeving anders is.

6.3.2

Arbitrary scenes

Door visibility te berekenen voor een cel ipv. een punt dient deze niet meer voor elk frame berekend te worden. Individuele occluders kunnen samengevoegd worden tot grotere occluders om zo minder berekeningen te moeten uitvoeren. Deze algoritmen zijn meestal conservatief. Conservative volumetric visibility met occluder fusion Deze techniek maakt gebruik van een discrete indeling van de scene, en aangrenzende occluders worden samengevoegd tot grotere occluders [SDDS00]. De scene wordt eerst verdeeld in verschillende cellen via een discrete indeling. De grenzen van de objecten worden binnen deze cellen geplaatst, en de binnenkant wordt opgevuld met dichte voxels. Voor elke cel worden deze dichte voxels gegroepeerd tot effectieve blokker. Vanuit de cel wordt voor de blokker bepaald welk deel van de scene niet zichtbaar is. De overeenkomende voxels worden dan als occluded beschouwd. Wanneer er reeds delen gevonden waren die niet zichtbaar waren vanuit de cel, dan kunnen blokkers worden samengevoegd tot grotere blokkers. Indien at run-time de voxels die een intersectie hebben met een bepaald object als niet zichtbaar zijn aangeduid, dan is dit object niet zichtbaar.

44

(a)

Figuur 6.4: Occluder fusion.

Conservative visibility preprocessing met extended projecties Dit algoritme is een uitbreiding op hi¨erarchische occlusion maps of hi¨erarchische Z-buffer. Objecten worden op een vlak geprojecteerd vanuit de view-cel en zijn niet zichtbaar indien hun hele oppervlak bedenkt is met de projectie van een occluder [DDTP00]. Een extended depth map wordt opgebouwd uit een discrete representatie van de projecties. De projecties van verschillende occluders worden samengevoegd (occluder-fusion).

(a)

Figuur 6.5: Extended projections.

Virtual occluders Een virtual occluder [KCCo00] is een eenvoudig convex object dat voor een gegeven view cel gegarandeerd volledig niet zichtbaar is, en fungeert als de effectieve occluder. Vooraf worden een aantal objecten als ’seed object’ bestempeld. Voor elk seed object wordt een cluster van nabije objecten beschouwd, zodat 1 enkele virtual occluder de occlusion voor deze hele cluster voorstelt. Vertrekken met het seed object worden per stap meer objecten toegevoegd, die de virtuele occluder laten groeien. Deze virtuele occluder wordt net achter het verste object in de cluster geplaatst.

45

(a)

Figuur 6.6: Virtual occluders.

Occluder fusion voor urban walkthroughs Vanuit enkele discrete sample point van een view cel kan een conservatieve benadering van de visibility berekend worden [WWS00]. Een object is niet zichtbaar indien het vanuit elk sample point niet zichtbaar is. Dit is echter niet exact correct, aangezien er view-points kunnen zijn binnen de cel die het object wel zien.

(a)

Figuur 6.7: Sampling.

Wanneer de occluders met een offset e worden verkleind, blijven objecten die niet zichtbaar waren dit indien het view-point niet meer dan een afstand e verplaatst wordt. Deze offset e zorgt er ook voor dat de occluder geldig is voor een kleine cel e. Als dan de volledige cel overspannen wordt met deze kleine cellen, dan is een object dat niet zichtbaar is voor alle sample points ook niet zichtbaar voor de hele cel. De keuze van e is belangrijk. Indien te klein zullen er te veel sample points nodig zijn, en indien te groot zullen de occluders erg snel klein worden. Dual ray space Een dual space transformatie kan gebruikt worden om het probleem van visibility naar een alternatieve 2 dimensionale ruimte te brengen [KCCO01]. Hierdoor kan computer hardware gebruikt worden om zo snellere en accuratere resultaten te bekomen. Een scene wordt als een kd-tree beschouwd. Vanuit een view-cel wordt deze tree top-down 46

doorlopen. Voor elk node wordt nagegaan of de bounding box ervan zichtbaar is vanuit de view-cel. Wanneer er een occluder node wordt bereikt, stopt de recursie.

(a)

Figuur 6.8: Sc`enes met hun dual ray space.

De visibility tussen 2 cellen is herleid tot een visibility probleem tussen 2 segmenten op een vlak, met het source segment als de view-cel en de target segment als de bounding box van de node. Elke ray vanuit het source segment dat een intersectie heet met het target segment komt overeen met een punt in de dual ray space. Alle rays vanuit een source segment door een segment van een occluder vormen een polygon. Indien de occluders samen alle rays vanuit het source segment blokkeren, dan is het target segment niet zichtbaar. Dit kan bekomen worden door te testen of een unie van polygonen een onvattende dual ray space overspannen. Deze test kan gedaan worden door de unie van polygonen te discretiseren tot een bitmap dmv. graphics hardware. Alle polygonen worden in het wit zonder Z-buffering of schaduwen getekend op een zwarte achtergrond. Als een pixel zwart blijft, dan kunnen het source en target segment elkaar niet zien. Hardly-visible sets Occlusion culling kan gecombineerd worden met een level-of-detail [ASVNB00]. Door gedeeltelijk zichtbare objecten van volledig zichtbare objecten te onderscheiden kunne deze gedeeltelijke zichtbare objecten gerenderd worden met minder detail, omdat deze minder ruimte op het scherm innemen. Een set occluders wordt vereenvoudigd tot een collectie van gedeeltelijk-overlappende boxen. Occlusion culling met deze boxen kan gebruikt worden om de ’volledig-zichtbare’ delen van de HVS te vinden. Enkel individuele boxen worden gebruikt, er is geen occlusion fusion. Alle occluders worden eerst vergroot met een kleine factor. Met deze vergrote occluders wordt er dan geculled. De objecten die zichtbaar zijn door de culling met de originele occluders en niet meer met de vergrote, worden als gedeeltelijk zichtbaar beschouwd. Ze kunnen dan met een lagere graad van detail worden gerenderd. 47

Er kunnen verschillende HVS worden berekend, telkens voor een andere LoD. At run-time kan dan het LoD bepaald worden aan de hand van de verschillende HVS. Merk op dat deze objecten best volledig zichtbaar kunnen zijn.

6.4

Point-based methods

Point-based algoritmen berekenen de visibility voor een specifiek view-point. Hierdoor worden minder objecten als mogelijk zichtbaar beschouwd dan algoritmen die gebruik maken van cellen, maar dient deze visibility voor elk frame opnieuw volledig berekend te worden. Deze groep algoritmen kunnen onderverdeeld worden in object-precision en image-precision methodes.

6.4.1

Object-precision

Deze groep algoritmen bepaald de visibility vanuit een punt vertrekkende van de objecten in een scene. Cellen en portals Cellen worden on-the-fly recursief doorlopen volgens hun diepte, waarbij de dichtstbijzijnde geprojecteerde cellen eerst behandeld worden [LG95]. Deze techniek levert conservatieve culling, is eenvoudig en redelijk effici¨ent.

(a)

Figuur 6.9: Recursieve culling adhv. portals.

48

Eerst wordt de cel die de viewer bevat gerenderd. De portals van deze cel die binnen het view-volume ligt worden dan ge¨ıdentificeerd. Voor deze portals wordt een 2D gealigneerde bounding box opgesteld die de projectie van de portal op het scherm weergeeft. Alle zichtbare objecten dienen immers in de projectie van deze portals te liggen. Dit wordt dan herhaald voor de cellen grenzend aan deze portals. Elke stap worden de nieuwe portals geclipt tegen de reeds behandelde portals. Dit leidt tot kleinere nieuwe portals, totdat er geen zichtbare portals meer over blijven. Grote convexe occluders Grote objecten kunnen gebruikt worden als grote convexe occluders om zo andere objecten als onmogelijk-zichtbaar te kunnen bestempelen [CT97]. Voor 2 objecten worden de separating en supporting oppervlakken gebruikt, in combinatie met de positie van de viewer tov. deze oppervlakken. Indien de viewer tussen de supporting oppervlakken is en achter 1 van de objecten, dan is het niet mogelijk het andere object te zien. Zolang de viewer binnen hetzelfde gebied blijft, blijft het object niet zichtbaar. Indien de viewer van gebied veranderd, treed er een visual event op, en dient het object als zichtbaar beschouwd te worden.

(a)

Figuur 6.10: Supporting en separating oppervlakken.

Deze manier van werken kan een groot aantal visual events genereren. Door een subset van de silhouette edges en vertices van de relevante primitieven te gebruiken, kan het aantal visual events drastisch beperkt worden. Het gebruik van een object hi¨erarchie kan voor een verdere effici¨entie zorgen. Toch blijft het dynamisch genereren van visual events erg duur en moeilijk te implementeren. Shadow frusta Een gelijkaardige manier maakt gebruikt van het principe dat een object niet zichtbaar is vanuit een punt indien het in de schaduw ligt van een occluder [HMC+ 97]. 49

Voor de n beste occluders die binnen het view-volume ligt wordt een shadow frustum vanuit het punt door de occluder. De scene wordt in een hi¨erarchische structuur opgebouwd en topdown getest tegen deze shadow frusta. Indien een node van de boom volledig binnen 1 van deze shadow frusta ligt, is het niet zichtbaar. Indien de node volledig buiten elk shadow frusta ligt, is het volledig zichtbaar. Indien de node slecht gedeeltelijk binnen een shadow frusta ligt, dan dienen de kinderen van deze node dezelfde test te ondergaan.

(a)

Figuur 6.11: Shadow frustum.

BSP tree culling De shadow frusta kunnen echter gecombineerd worden in een occlusion BSP tree [BHS98]. De boom begint met een enkel zichtbaar blad. Occluders worden in de boom toegevoegd. Indien een occluder op een zichtbaar blad komt, verandert het de boom met zijn shadow frustum. Indien het op een niet-zichtbaar blad komt, wordt het genegeerd. Wanneer de occlusion tree is opgebouwd kan deze gebruikt worden bij het hi¨erarchisch testen van de scene. De boom wordt voor elke node hi¨erarchisch afgelopen, tot de node volledig zichtbaar of volledig in een shadow frustum van een occluder ligt. Deze methode heeft als voordeel dat niet n shadow frusta dient getest te worden (O(N ) complexiteit), maar een boom (O(logN )).

6.4.2

Image-precision

Point-based image-precision technieken cullen op de discrete representatie van de image. Tijdens de rendering van de scene wordt de image opgevuld en objecten worden geculled door het reeds ingevulde deel van de image. Door een discrete representatie te gebruiken 50

van een beperkte resolutie zijn deze technieken eenvoudiger en robuuster dan hun objectprecision tegenhangers. Benaderende oplossingen kunnen ook gevonden worden door objecten die door een onbelangrijk aantal pixels zichtbaar zijn toch als occluded te beschouwen. Dit kan grote snelheidswinsten opleveren. Ray casting Ray casting is 1 van de eenvoudigste image-synthese algoritmen. Voor elke pixel wordt bepaald welk object zichtbaar is. Door een ray te schieten vanuit het viewpoint door de pixel kan het dichtstbijzijnde object voor die pixel gezocht worden. Zo worden occluded objecten nooit gerenderd. Het opbouwen van de image is echter erg complex. Voor elke ray dienen alle objecten gecontroleerd te worden. Door back-to-front ordening te gebruiken kan dit proces enorm versneld worden [BDT99]. Hi¨erarchische Z-buffer De hi¨erarchische Z-buffer [GKM93] is een uitbreiding op een zeer gekende hidden surface removal techniek: de Z-buffer. Er worden 2 hi¨erarchieen gebruikt: een octree in objectprecision en een Z-pyramide in image-precision. De Z-pyramide is een gelaagde buffer met op elk level een andere resolutie. Op het fijnste level is het de inhoud van de Z-buffer. Elk volgend level wordt bepaald door halvering van de dimensies en elk element houdt de verste z-waarde van het overeenkomstig 2x2 window van het vorige level. Dit wordt iteratief gedaan tot er slechts 1 waarde aan de top is. Bij wijzigingen aan de Z-buffer worden deze waarden gepropageerd naar de top.

(a)

Figuur 6.12: Hi¨erarchische Z-buffer.

Wanneer de scene opgebouwd is in een octree wordt deze top-down en front-to-back doorlopen. Indien een node occluded is, wordt het overgeslaan. Anders worden de kinderen behandeld. Zo worden niet-occluded primitieven gerenderd en wordt de Z-buffer aangepast. Om te weten of een primitief zichtbaar is wordt het vergeleken met de inhoud van de Zpyramide. Vanaf het top level wordt nagegaan of het verder is dan de z-waarde. Als dit het

51

geval is, is het niet zichtbaar. Anders wordt verder gegaan met de volgende levels, tot het uiteindelijk als zichtbaar beschouwd wordt. Omdat het Z-buffer algoritme hardware ondersteuning kent, kan de hi¨erarchische Zbuffer in real-time gebeuren. Door primitieven die zichtbaar waren in het vorig frame prioritair te behandelen kan dit proces nog verder versneld worden. Hi¨erarchische occlusion map Dit algoritme leunt sterk aan tegen de hi¨erarchische Z-buffer, maar werd ontworpen op basis van huidige graphics hardware [Zha98]. De visibility test wordt ontkoppeld in een overlap test en een diepte test. De overlap test geeft aan of een object overlapt wordt met een occluder in screen space, terwijl de diepte test bepaalt of de occluder zichtbaar is. Verder kan ook benaderende technieken gebruikt worden door objecten die slecht door enkele pixels zichtbaar zijn toch als niet-zichtbaar te beschouwen door gebruik te maken van een threshold. De hi¨erarchische occlusion map houdt enkel een informatie over de zichtbaarheid bij; de diepte wordt in de Z-buffer bijgehouden. Vooraf worden een groep van mogelijke occluders verzameld. At-runtime wordt enerzijds de HOM opgebouwd en anderzijds gebruikt voor de occlusion culling.

(a)

Figuur 6.13: Hi¨erarchische occlusion map.

De groep mogelijke occluders worden eerst gerenderd. De objecten worden volledig in het wit zonder texturing, belichting en Z-buffering gerenderd. Het resultaat is een occlusion map op het hoogste niveau. Volgende levels worden bekomen door het gemiddelde van een 2x2 gebied van het vorige level. Dit levert buiten witte en zwarte pixels nu ook grijze. Texturing hardware kan gebruikt worden om dit proces te versnellen.

52

Nadien wordt voor elk object de bounding box op het scherm geprojecteerd en wordt een occlusion map gezocht waar de pixels ongeveer even groot zijn als de projectie van de bounding box. Indien de box pixels overlapt die niet opaque zijn (of boven een threshold liggen voor benaderende technieken), dan kan de box niet geculled worden. Anders wordt het object op de regio die het omvat geprojecteerd en is een diepte test nodig om te bepalen of het object geculled kan worden. Directional discretized occluders Directional discretized occluders [BESK00] werkt analoog aan HZB en HOM methode. In een proprocessing fase wordt de complexe geometrie van objecten vervangen door een view-afhankelijke polygonale occluder. Elke rand van elke cel in de octree wordt als een mogelijke occluder beschouwd. Voor een object wordt dan een voorgesteld door een reeks randen van cellen in de octree. Door deze eenvoudige geometrie te gebruiken kunnen culling testen sneller gebeuren. De preprocessing is echter erg duur.

(a)

Figuur 6.14: Directional discretized occluders.

Verdere hardware ondersteuning Er komt steeds meer hardware ondersteuning voor occlusion culling. Via OpenGL kan men met een stencil buffer een virtual occlusion buffer maken [BMH98]. Deze buffer wordt opgevuld met bounding boxes van de objecten indien de Z-buffer test slaagt, terwijl de frame buffer en de Z-buffer ongewijzigd blijven. Objecten diens bounding box (deels) in de bevindt, zijn dan mogelijk zichtbaar.

53

Er komt ook meer occlusion-culling specifieke hardware ondersteuning [KHM+ 96]. Dit is mogelijk door een feedback loop naar de hardware wanneer er een wijziging is aan de Z-buffer. Approximate volumetric visibility Een manier om visibility te benaderen is om volumetrische representatie te gebruiken ipv. geometrische visibility berekeningen [KS00]. Voor elke cel kan de dichtheid van de geometrie gebruikt worden om visibility van andere cellen te bepalen. Cellen met veel geometrische data hebben immers een grotere kans om occluders te bevatten. Een opgelegde threshold bepaalt dan of een cel al dan niet zichtbaar is. Dit is een agressief algoritme, en levert dus fouten op. Het kan wel effici¨ent gebruikt worden als gedeeltelijke oplossing binnen een groter geheel. Occluder shadow footprints Veel 3D sc`enes zijn in feite slechts 2.5D sc`enes, die gebruik maken van een hoogte map. Vanuit het viewpoint kan voor een occluder een occluder shadow berekend worden. De projectie van deze ’schaduw’ op de bodem is de shadow footprint [WS99]. De shadow footprint bevat hoogtes die aangeeft hoe groot de kans is op visibility. Een object ligt is niet zichtbaar indien het in de schaduw van de occluder is en beneden de hoogte blijft. De Z-buffer kan gebruikt worden om de shadow footprint effici¨ent te berekenen.

(a)

Figuur 6.15: Occluder shadow footprints.

6.5

PVS als techniek om netwerkverkeer te verminderen

Oorspronkelijk waren PVS algoritmen vooral terug te vinden in de render pipeline. Deze algoritmen kunnen echter ook gebruikt worden binnen een netwerk topologie. Zo kan communicatie vermeden worden tussen entiteiten die elkaar onmogelijk kunnen zien. Dit leidt tot grote besparingen op het bandbreedteverbruik.

54

6.5.1

Voorbeeld: RING

RING is een client-server opstelling voor om in real-time visuele interactie tussen een groot aantal gebruikers in een gedistribueerde virtuele omgeving mogelijk te maken [Fun95]. Om een consistente toestand van de virtuele omgeving bij elk systeem te onderhouden, zouden er normaal gezien M × N berichten per seconde gegenereerd moeten worden naar een gecentraliseerde database, met M het aantal entiteiten (incl. positie en/of ori¨entatie) en N de gewenste update rate. Bij een groot aantal gebruikers en/of een update rate kan het netwerk dan de datastroom niet meer verwerken. Bij het RING systeem worden toestandswijzigingen enkel verstuurd naar de systemen die entiteiten beheren die dit kunnen zien. Berichten worden niet verstuurd van client naar client zelf, maar elke client stuurt zijn updates door naar een netwerk van servers, die op hun beurt bijhouden welke clients zich waar bevinden in de virtuele omgeving. Door op voorhand de omgeving op te delen in cellen en voor elke cel te berekenen welke set van cellen zichtbaar zijn, kunnen de RING servers snel bepalen via welke servers de berichten naar de clients gepropageerd moeten worden, in plaats van tijdens de simulatie zelf in realtime zware visibiliteitsberekeningen te moeten doen.

Figuur 6.16: RING gebruikt PVS om het aantal datapakketten te verminderen Wanneer een client een update bericht doorstuurt, zal de server deze eerst verwerken alvorens dit bericht verder te versturen naar de andere clients. De server bepaalt voor welke clients en servers dit bericht relevant is. Dit wordt bepaald door de PVS. De PVS wordt bepaald door voor elke portal van elke cel een projectie op te stellen die de mogelijke zichtbare delen van de omgeving weergeeft. Zo wordt bepaald voor elke cel welke andere cellen zichtbaar zijn. Door periodische berichten te versturen tussen de verschillende servers kunnen deze server bepalen in welke cel de verschillende clients zich bevinden. De real-time berichten worden enkel naar servers en clients verstuurd die entiteiten bevatten in mogelijk zichtbare cellen. De visibility voor de cellen wordt vooraf conservatief overschat. Tijdens de simulatie hoeven dan enkel maar eenvoudige ’look-ups’ uitgevoerd te worden om de visibility tussen entiteiten te bepalen.

55

Naast de ’gewone’ bericht kunnen de RING servers ook hulp-berichten naar clients versturen. Deze hulp-berichten kunnen dan later gebruikt worden tijdens de verwerking van de eigenlijke berichten. De servers kunnen zelfs berichten vervangen door andere die voor de client beter geschikt zijn. Hierdoor verlichten de servers de verwerking van de berichten voor de clients.

Figuur 6.17: RING architectuur Voordelen • De vereiste opslagcapaciteit, processorkracht en netwerkbandbreedte van de clients neemt niet toe naarmate het aantal entiteiten in de virtuele omgeving groter wordt (in ’dichtbebouwde’ virtuele omgevingen zijn de PVS immers meestal van constante grootte - het maakt dan niet uit hoe groot de totale omgeving is) • Relatief weinig opslagcapaciteit en processorkracht wordt vereist van de servers (64MB geheugen is voldoende om 1 miljoen entiteiten te ondersteunen) • Het onderhoud van de virtuele omgeving (bv. het toevoegen of verwijderen van een entiteit) kan gedaan worden door de servers zonder elke client op de hoogte te moeten brengen Nadelen • De berichten komen met extra latency aan bij andere clients omdat ze via minimaal 1 en maximaal 2 RING-servers doorgestuurd worden (1 of 2 extra ’hops’).

6.6

Conclusie

In dit hoofdstuk werd een definitie van een PVS, en werden verschillende occlusion culling algoritmen besproken om de PVS te berekenen. Ook werd uitgelegd hoe deze PVS algorit56

men kunnen gebruikt worden binnen een netwerktopologie. Als voorbeeld hiervan werd de RING architectuur besproken. In een volgend hoofdstuk worden de berekende PVS gebruikt als basis voor de frontier sets.

57

Hoofdstuk 7 Frontier sets Frontier sets gaan een stap verder dan Potentially Visible Sets [SA04]. Nadat we de volledige Potentially Visible Set structuur hebben berekend voor de in cellen opgedeelde virtuele omgeving, zouden we deze kunnen gebruiken om te controleren of er daadwerkelijk interactie tussen paren van entiteiten plaats moet vinden: er moet immers enkel gecommuniceerd worden met de entiteiten die zich bevinden in de PVS van de huidige cel. Wanneer een van beide entiteiten echter zijn huidige cel verlaat, moet deze de anderen onmiddellijk op de hoogte brengen van zijn nieuwe positie, ook in het geval wanneer ze nog steeds onzichtbaar zouden zijn voor elkaar.

(a)

Figuur 7.1: Potentially visible set voor cel I.

7.1

Definitie

Om dit probleem te verhelpen kan men een Frontier Set opstellen. Elke frontier in zo’n set bestaat uit een gebied van cellen en wordt steeds gelinkt aan een andere frontier. Geen enkele cel in e´ e´ n frontier mag zichtbaar zijn voor eender welke cel in de andere frontier. Indien een entiteit zijn cel verlaat maar binnen zijn huidige frontier blijft, is het niet nodig zijn positie door te geven aan de entiteit die zich in de andere frontier bevindt. Ze kunnen elkaar immers nog steeds niet zien. Enkel wanneer een entiteit zijn frontier verlaat moet hij de andere entiteit op de hoogte brengen van zijn nieuwe positie en kan er getracht worden om nieuwe frontiers af te spreken. Indien dit niet zou lukken wilt dit zeggen dat ze elkaar nu wel kunnen zien en dient er gecommuniceerd te worden. Door frontiers op te stellen voor elk mogelijk cellenpaar binnen de virtuele omgeving bekomt men een Frontier Set.

58

7.2 7.2.1

Basis algoritme Opstellen van frontiers

In een eerste fase worden de frontiers opgesteld. Gegeven twee cellen A en I kunnen frontiers FAI en FIA opgesteld worden enkel en alleen indien A en I elkaar niet kunnen zien. De doorsnede tussen beide frontiers moet dus te allen tijde ledig zijn, want anders zou dit betekenen dat er een cel bestaat die zichtbaar is vanuit beide frontiers, in strijd met de definitie. Indien I zich niet bevindt in de PVS van A (en omgekeerd) kunnen de frontiers ge¨ınitialiseerd worden met FAI = A en FIA = I. Er kunnen verschillende frontiers bemiddeld worden voor een koppel cellen (die al dan niet even optimaal gekozen zijn). Nu wordt elke set uitgebreid met aangrenzende cellen tot een zo groot mogelijk geheel. Cellen worden recursief toegevoegd aan een frontier indien ze zichtbaar zijn door 1 of meer cellen die reeds tot deze frontier behoren. Tijdens deze recursieve stop dient de doorsnede wel leeg te blijven, anders worden deze cellen niet aan de frontier toegevoegd. In de meest eenvoudige methode, region growing, doorloopt men de verbindingsgraaf (waarin cellen als knopen worden voorgesteld, en de verbindingen tussen cellen als links tussen deze knopen) in breadth-first volgorde vertrekkende vanuit beide cellen. Nu gaat men vanuit cel A en B alternerend een cel toevoegen aan FAB en FBA indien de toe te voegen cel niet zichtbaar is voor eender welke cel van de andere set in de frontier. Telkens wanneer we een cel toevoegen aan de frontier wordt de PVS van deze cel samengevoegd met de PVS van de frontier in opbouw.

59

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

Figuur 7.2: Werking van het region growing algoritme. Wanneer er 2 gebruikers in respectievelijk cel A en I zich bevinden, dan worden de frontiers FAI en FIA ge¨ınitialiseerd met resp. A en I (stap a). Dit is mogelijk omdat beide cellen elkaar niet zien. Vervolgens worden de aangrenzende cellen beschouwd als mogelijke kandidaten om toegevoegd te worden aan de frontiers. Voor cel A is dit cel D, en voor cel I is dit cel F . Frontier FAI kan uitgebreid worden met cel D, aangezien deze cel niet aanwezig is in de PVS van frontier FIA (b). Cel F kan om dezelfde reden toegevoegd worden aan frontier FIA (c). De PVS van beide frontiers wordt uitgebreid met de extra cellen die zichtbaar zijn vanuit de toegevoegde cellen. Cel H wordt toegevoegd aan de PVS van FAI , en de PVS van FIA wordt uitgebreid met cellen B en H. Ook cel G kan toegevoegd worden aan FAI (d), en aan de PVS van FAI wordt E toegevoegd. C wordt toegevoegd aan FIA (e). De PVS van deze frontier blijft ongewijzigd. Cel H kan niet worden toegevoegd aan FAI want deze zit in PVS(FIA ) (f). Ook E kan niet worden toegevoegd aan FIA want deze zit in PVS(FAI ) (g). B kan wel nog toegevoegd worden aan frontier FIA (h). De PVS blijft ongewijzigd. Op dit moment kunnen geen cellen meer toegevoegd worden aan de frontiers. De uiteindelijke situatie is bereikt (i). Keuze van cellen Men zou, indien 2 cellen elkaar niet kunnen zien, een legitieme frontier kunnen maken bestaande uit enkel deze 2 cellen zelf. Hierbij boekt men echter geen winst ten opzichte van PVS gebaseerde network culling, want zodra een entiteit zijn frontier (in dit geval, zijn cel) verlaat moet er meteen gecommuniceerd worden. Indien we op voorhand zouden weten welk bewegingspatroon de entiteiten volgen, kunnen we de frontiers optimaal vastleggen: deze die zo lang mogelijk stand houden tijdens de simulatie zelf. Omdat we dit echter 60

meestal niet weten kunnen we enkel een zo goed mogelijke schatting maken. Dit houdt in dat we proberen om frontiers op te stellen waarvan beide sets cellen ongeveer even groot zijn, en zo groot mogelijk. Tijdstip van generatie Men kan de frontiers berekenen vooraleer men de simulatie begint, of enkel de benodigde frontiers real-time berekenen tijdens de simulatie zelf (dan weet men immers exact in welke cellen de entiteiten zich bevinden). In het geval van real-time generatie, moet men wel kunnen garanderen dat beide clients dezelfde frontiers berekenen, en is het van groot belang dat de berekening van goede frontiers tijdig kan gebeuren zodat de simulatie geen vertraging oploopt.

7.2.2

Evaluatie

Wanneer de frontier sets bepaald zijn, kunnen ze gebruikt worden at-runtime om te bepalen wanneer er communicatie nodig is tussen gebruikers. Elke frame van de simulatie kan gekeken worden indien een van beide entiteiten de huidige frontier verlaten hebben. Indien dit het geval is wordt de huidige frontier verwijderd en wordt de andere entiteit op de hoogte gebracht van de huidige positie zodat ook daar de frontier verwijderd kan worden. Daarna wordt er getracht een nieuwe frontier op te stellen. Omdat niet elke keer posities uitgewisseld moeten worden wanneer er een entiteit een cel verlaat komt dit de schaalbaarheid van de simulatie ten goede. In het onderstaande voorbeeld wordt er uitgelegd hoe frontiers dynamisch aangemaakt en verwijderd worden tijdens een simulatie met 2 entiteiten. Op tijdstip τ 0 (a)) bevindt de rode entiteit zich in cel A en de paarse in cel I. Voor cel A zijn cellen D en G direct zichtbaar, en voor cel I zijn dit B, C en F . Omdat er geen cellen direct zichtbaar zijn vanuit beide cellen, kunnen de initiele frontiers opgesteld worden als volgt: FAI = {A, D, G} en FIA = {B, C, F, I}. Wanneer beide entiteiten binnen hun frontier blijven moeten er voorlopig geen nieuwe toestandswijzigingen meer verstuurd worden naar elkaar. Wanneer een van beide entiteiten zich buiten zijn frontier begeeft kunnen er ofwel nieuwe frontiers opgesteld worden, of geen omdat ze elkaar op dat moment kunnen zien. Wanneer 1 van beide entiteiten buiten hun frontier gaat, dienen deze sets aangepast te worden (tijdstip τ 1 (b))). De rode entiteit verplaatste zich naar cel D en de paarse entiteit verplaatst zich buiten zijn frontier (naar cel E). Er dienen nieuwe frontiers opgesteld worden. Dit levert de frontiers FDE = {A, D} en FED = {B, C, E, F, I}. Wanneer de paarse entiteit zich naar cel H begeeft (tijdstip τ 2 (c))) is het onmogelijk om frontiers op te stellen want cellen D en H kunnen nu elkaar zien. Op dit moment kan er niet langer dataverkeer zijn tussen beide entiteiten genegeerd worden. Tijdstip τ 3 toont het gevolg wanneer de rode entiteit zich terug naar cel A verplaatst. Er kunnen opnieuw frontiers gevormd worden, FAH = {A} en FHA = {B, C, E, F, H, I}.

61

(a)

(b)

(c)

(d)

Figuur 7.3: Dynamische werking van frontiers.

7.2.3

Voor- en nadelen

Voordelen • Veel minder netwerkverkeer dan bij na¨ıeve peer-to-peer of peer-to-peer met PVS culling. • De latency ligt een stuk lager dan bij client-server systemen, omdat de pakketten rechtstreeks naar andere peers verstuurd worden in de plaats van langs de server moeten passeren. Nadelen • Er moeten bij de clients meer berekeningen gebeuren. • De discretisering van de omgeving in cellen heeft een grote impact, en is meestal niet eenvoudig te bepalen. • Het is moeilijker om de toestand van de simulatie te synchroniseren met alle deelnemers dan bij client-server systemen.

7.3 7.3.1

Uitbreidingen Opstellen van frontiers

Region growing Het region growing algoritme werd hierboven reeds beschreven. Het is waarschijnlijk de meest eenvoudige manier om de frontiers op te stellen. Toch heeft deze techniek al interessante eigenschappen. • Voordelen – Het dataverkeer tussen gebruikers is beperkt volgens de visibiliteit. – PVS en frontier set worden beide op voorhand berekend. Hierdoor is er atruntime enkel een eenvoudige lookup cost. • Nadelen – Er is een O(N 3 ) opslagruimte benodigd volgens het aantal cellen. – Indien de omgeving tamelijk groot is is compressie van PVS noodzakelijk. 62

Distance based frontiers Bij een verbeterde methode, distance based frontiers, houdt men rekening met de visibiliteitsafstand tussen cellen bij het opstellen van de frontiers [SA05]. • De visibiliteitsafstand tussen een cel A en zichzelf is 0. dist(A, A) = 0 • De visibiliteitsafstand tussen een cel A en een cel B ∈ P V S(A) is 1: ∀A ∈ P V SA : dist(A, B) = 1 • De visibiliteitsafstand tussen een cel A en een cel B ∈ / P V S(A) is de lengte van het kortste pad van cellen tussen de twee waarvoor elke volgende cel in de PVS van de vorige cel zit: ∀A ∈ / P V SA : dist(A, B) = shortestpath(A, C1 , ..., Cn , B) : C1 ∈ P V SA , Ci + 1 ∈ P V SCi , B ∈ P V SCn Vooraleer de simulatie plaatsvindt wordt er een Enhanced PVS (EPVS) berekend door de originele PVS matrix te nemen waarbij: (A, B) = 1 : B ∈ P V SA (A, B) = ∞ : B ∈ / P V SA en dan een kortste pad algoritme (zoals bijvoorbeeld Dijkstra [Dij59]) hierop los te laten. Distance based frontiers zijn ook effici¨enter qua geheugengebruik. In tegenstelling tot de originele PVS die O(N 2 ) opslagruimte inneemt, neemt de EPVS meer opslagruimte in (O(N 2 log2 (M axDistance(EP V S)))) omdat er nu integers(afstanden) ipv. bits in worden opgeslaan. Frontiers worden in deze methode at runtime berekend: FAB = C|dist(A, C) ≤ dist(B, C) − 1 FBA = D|dist(B, D) < dist(A, D) − 1 At runtime worden alle cellen doorlopen en aan de hand van de visibiliteitsafstanden tov A en B worden ze in een van deze frontiers geplaatst. Hiervoor zijn er dus 2N-2 value lookups (2x dist(X,Y) - dist(X,X) en dist(Y,Y)) nodig en O(N) opslagruimte per paar). Voor M clients zou deze berekening M-1 keer kunnen gebeuren elk frame. Maar het hele idee achter frontiers gebruiken is dat er slecht zeldzaam een nieuwe frontier berekend moet worden. • Voordelen – Minder geheugencapaciteit is nodig. 63

– Enkel benodigde frontiers worden berekend, waardoor geen dure initialisatie kost nodig is. • Nadelen – At-runtime berekeningen worden duurder. – Kan leiden tot ongebalanceerde frontiers. Greedy frontiers Omdat er bij het berekenen van distance frontiers enkel rekening gehouden wordt met de visibiliteitsafstanden kan het gebeuren dat er ongebalanceerde frontiers opgebouwd worden wanneer een cel sterk verbonden is met veel andere cellen en de andere niet [SA]. Een greedy frontier algoritme gaat net als bij het region growing algoritme alternerend een nieuwe cel toevoegen aan een kant van de frontier, maar het opbouwen van deze frontiers gebeurt nu at runtime, zodat enkel de benodigde frontiers berekend moeten worden. De kost van deze berekening ligt hoger dan bij distance frontiers, in theorie zelf O(N 2 ) omdat het combineren van de PVS (dat O(N ) als kost heeft) er bij komt, maar in de praktijk leunt het eerder tegen O(N ) aan gezien het combineren van de PVS niet voor elke cel moet gebeuren en de operatie zelf een goedkope bitwise OR is van de rijen in de binaire matrix. Door de breadth-first lijsten te sorteren op afstand tot de originele cel verkrijgt men beter uitgebalanceerde frontiers. • Voordelen – Grotere en meer effici¨ente frontiers dan distance frontiers. • Nadelen – At runtime zelfs nog iets duurder dan distance frontiers.

7.4

Toepassing: Quake2

Frontier sets in de praktijk toegepast bij Quake2 [SA04]. Quake2 [qua] gebruikt een client / server model, meestal met een dedicated server en rond 16 spelers. Het bevat reeds een PVS structuur die zowel gebruikt wordt voor de rendering te versnellen alsook om dataverkeer tussen onderling niet-zichtbare client te beperken. Een doorsnee level in Quake2 bevat tussen de 1000 en 3000 cellen. Wanneer dan de frontier vooraf berekend worden, zal dit voor zo een groot aantal cellen echter relatief veel opslagcapaciteit vragen, omdat deze capaciteit O(N 3 ) toeneemt volgens het aantal cellen. Hierdoor is het aangewezen compressie toe te passen [PS99]. Zelfs het terugbrengen van het aantal cellen tot 256 levert nauwelijks een verlies van visibility. Onderstaande tekening geeft een voorbeeld van een frontier. Zolang beide spelers (rood en groen) hun frontiers (resp. donkerrood en donkergroen) niet verlaten moeten ze geen toestandswijzigingen uitwisselen.

64

(a)

Figuur 7.4: Beide spelers bevinden zich in verschillende frontiers (resp. donkerrood en donkergroen). Tussen hen is geen communicatie nodig.

7.4.1

Vergelijking

Vergelijking met traditionele modellen In een eerste vergelijking werden 5 simulaties uitgevoerd: Client/server: Een client zend per frame zijn pakket naar de server en deze verstuurt dit pakket onmiddellijk verder naar alle andere clients. Client/server met aggregatie: Een client stuurt eerst zijn pakket naar de server. De server zal dan deze pakketten voor iedere client verzamelen en slecht bij elke frame 1 pakket versturen naar alle clients. Dit pakket bevat dan de data van alle clients. Na¨ıeve peer-to-peer: Een client verstuurt per frame zijn pakket rechtstreeks naar alle andere clients. Perfecte peer-to-peer: Een theoretisch model waarbij elke client per frame enkel een pakket naar een andere client verstuurt indien deze client zichtbaar is. In de praktijk is deze simulatie niet mogelijk aangezien dan iedere client perfect dient te weten waar alle andere client zich bevinden. Hiervoor dient de client elke frame de data van alle andere client reeds te bezitten. Frontier gebaseerd: Een client stuurt enkel een pakket naar een andere client indien dit volgens het frontier sets algoritme vereist is. Het client/server en naive peer-to-peer model stellen de traditionele netwerk modellen voor. Quake2 gebruikt standaard reeds het client/server model met aggregatie. Dit levert wel een grotere latency op. Ook zijn de pakketten groter hetgeen de vergelijking met frontier sets bemoeilijkt. Er werd echter (foutief) van uitgegaan dat de geaggregeerde pakketten niet groter waren dan de originele. De perfectie peer-to-peer implementatie wordt enkel vermeld als theoretische ondergrens. 65

Onderstaande tabel geeft een vergelijking van de verschillende modellen van het aantal pakketen per client per frame voor 3 maps: q2dm3, q2dm4 en q2dm8. Dit zijn 3 standaard Qauke2 maps, allen met verschillende eigenschappen. Q2md4 is een grote ongeveer volledige 2D map, waar q2dm8 een compactere map is met veel verticale levels met een kleine visibility tussen de levels. Q2dm3 is een compacte map met minder verticale levels, ook met een kleine visibility tussen de levels. Een vergelijking van deze eigenschappen van de maps leert dat voor q2dm3 en q2dm8 het percentage van de celparen waarvoor een frontier gevonden kon worden respectievelijk 83,9 en 84,2 is. Voor de q2dm4 map is dit zelfs 93%. Een map waar de cellen dichter bij elkaar liggen is dit getal lager aangezien cellen sneller in elkaars PVS kunnen liggen. De grootte van de frontiers speelt ook een belangrijke rol in de simulatie. Het percentage van cellen die verdeeld kunnen worden over de frontier van een celpaar is voor de q2dm3 map 38,7, en voor de q2dm4 en q2dm8 map 67,3 en 68,2. Voor grotere uitgespreide maps levert dit een hoger percentage, aangezien meer cellen tot de PVS van een cel behoren. Map q2dm3 q2dm4 q2dm8

C/S Geaggregeerd C/S Na¨ıeve P2P Perfecte P2P Frontier sets 4,7 1,9 15,0 3,7 5,4 2,8 1,8 15,7 1,9 2,6 5,2 2,0 14,4 4,2 5,9

Tabel 7.1: Vergelijking van het aantal pakketten per client per frame van de verschillende modellen.

Hieruit blijkt dat het geaggregeerde client/server model de beste resultaten levert. Hierbij dient wel opgemerkt te worden dat de pakketten in de realiteit verschillende malen groter zijn dat de standaard pakketten, en dat deze pakketten met een grotere latency verstuurd worden dan de traditionele client/server. Het gebruik van frontier sets levert inderdaad betere resultaten dan de na¨ıeve peer-to-peer implementatie, aangezien het dataverkeer tussen peers beperkt wordt tot de enkel zichtbare peers. Ook komt de frontier sets dicht in de buurt van de perfecte peer-to-peer, en levert deze techniek gelijkaardige resultaten aan de traditionele client/server. Vergelijking van verschillende frontier sets implementaties In een tweede test werden de verschillende frontier sets algoritmen met elkaar vergeleken. Dezelfde Quake2 maps werden gebruikt. Eerst en vooral levert de greedy frontiers grotere frontiers op. Voor de q2dm3 en q2dm8 groeide het percentage tot 67,2 en 65,8, en voor de q2dm4 map zelfs tot 82,3. Deze groei is echter te verwachten aangezien greedy frontiers meer gebalanceerde frontiers opleveren. Om deze reden leveren de greedy frontiers ook betere resultaten dan de distance based aanpak. Wanneer deze resultaten worden vergeleken met de resultaten uit de eerste test, dan blijkt dat de greedy frontiers ook betere resultaten leveren dan de traditionele client/server. 66

Map q2dm3 q2dm4 q2dm8

Distance based frontiers Greedy frontiers 5,4 4,4 2,6 2,3 5,9 4,9

Tabel 7.2: Vergelijking van het aantal pakketten per client per frame van de verschillende frontier sets implementaties.

7.5

Conclusie

Er werd in dit hoofdstuk een uiteenzetting gegeven van frontier sets. Ze werden geplaatst als uitbreiding op PVS. Er werd uitgelegd hoe frontier sets worden opgebouwd en hoe ze worden gebruikt at-runtime. Frontier sets gaven duidelijk aan dat de beschikbare bandbreedte effici¨enter gebruikt wordt. Ook werden enkele uitbreidingen op frontier sets opgesomd, die deze techniek verder optimaliseren.

67

Hoofdstuk 8 Implementatie Nu volgt een bespreking van de eigen implementatie, met een vergelijking om de kracht van frontier sets verder te verduidelijken.

8.1 8.1.1

Library’s Irrlicht

Irrlicht [irr] is een open source platform onafhankelijke C++ 3D engine. Irrlicht staat vooral bekend door zijn beperkte omvang en compatibiliteit met zowel nieuwe als oudere hardware. Eigenschappen Irrlicht ondersteunt verschillende 3D rendering engines, waaronder OpenGL, DirectX en software rendering. Andere renderers kunnen eenvoudig worden toegevoegd, waardoor ondersteuning op allerhande devices zoals de iPhone mogelijk is. Het biedt ook een ondersteuning aan pixel en vertex shaders, waarmee realistischere grafische rendering mogelijk is. Hiernaast worden verschillende file formaten ondersteunt, zoals 3ds Max files, Maya .obj objects alsook volledige Quake 3 .bsp maps. Dit maakt het heel eenvoudig om snel een grafische omgeving op te zetten. Deze omgevingen kunnen dan verder aangevuld worden met belichting, een camera en de 3D objecten. Deze worden als nodes in een tree of ’scene nodes’ bijgehouden. Deze nodes kunnen in groepen verdeeld worden, die kunnen interageren met elkaar, verschillende animators zoals een zwaartekracht, of door input van de gebruiker. Er is reeds een grote waaier aan nodes, waar zowel indoor als outdoor omgevingen mee kunnen worden opgezet. Nieuwe nodes kunnen ook eenvoudig worden toegevoegd. Onder deze nodes vindt men oa. terrein renderes, sky boxes, skeleton animated meshes, stencil schadows en allerhande particle-gebaseerde systemen. Hiernaast is ook een 2D GUI beschikbaar, voor een betere human-machine interface. Dit alles maakt van Irrlicht een uiterst geschikt framework voor het implementeren van mijn project. 68

Gebruikte features ´ en van de features die direct opvallen in een GVO is het renderen van terrein. Deze E´ werd ge¨ımplementeerd dmv. een height map. De omgeving werd in verschillende cellen opgedeeld, met ertussen enkele portals.

(a)

Figuur 8.1: De height map van de virtuele omgeving.

(a)

Figuur 8.2: De virtuele omgeving gerenderd in Irrlicht.

Ondanks het feit dat de virtuele omgeving in dit voorbeeld echter simplistisch lijkt, kan men deze techniek ook gebruiken bij meer geavanceerde en complexere omgevingen. Elke cel kan een paar andere cellen zien, en zo kan een PVS worden opgesteld voor deze omgeving. Om de server niet te overspoelen met netwerk pakketten, is er een frame limit van 60 fps. De gebruiker kent een third person camera om zijn en andere avatars te kunnen zien binnen de wereld. Verder zijn enkele eenvoudige animaties toegevoegd, alsook collision detection (bij de clients). 69

8.1.2

RakNet

RakNet [rak] is een platform onafhankelijke C++ game netwerk engine. Het is ontworpen voor hoge performance, is gemakkelijk te gebruiken en is een volledige oplossing voor games en andere applicaties. Eigenschappen RakNet kent een grote ondersteuning van verschillende netwerk features. Enkele van de belangrijkste zijn: Verschillende architecturen: Een netwerk library is niets zonder de ondersteuning van de 2 belangrijkste netwerkarchitecturen: de client/server en peer-to-peer. Lobby systemen: Lobby gebaseerd op databases met ondersteuning voor verschillende gebruikers, rooms, quick match, ranking, email, ... Object replicatie systemen: Automatische aanmaak, verwijdering en verzending van de objecten van de omgeving. Secure connecties: Ondersteuning voor SHA1, AES128, SYN cookies en RSA, om netwerkaanvallen te detecteren en te voorkomen. Robuuste communicatielaag: Automatische flow control, ordening van berichten over verschillende kanalen, samenvoeging en splitsing van berichten en opbouw van pakketten. Autopatcher: Updates voor gebruikers met binaire delta patches, gebaseerd op een database. Ook eenvoudigere mechanismen voor updates zijn mogelijk voor oa. user skins en maps. Remote procedure calls: Mogelijkheid om C en C++ procedures op te roepen via een automatisch geserialiseerde parameter lijst. Voice communicatie: Audio bindings voor Port Audio, FMOD and DirectSound. NAT punchthrough: Essentieel voor voice communicatie en peer-to-peer applicaties. Gebruikte features Er werd een eenvoudige client/server communicatie opgezet, met unicast over TCP. Hierdoor komen berichten gegarandeerd aan in de juiste volgorde. Het gebruik van TCP zorgt echter voor grotere pakketten dan communicatie over UDP. Unicast heeft een grotere ondersteuning op het Internet dan multicast.

70

8.2

Architectuur

8.2.1

Client/server

Op heden is de meest gebruikte architectuur voor virtuele omgevingen een client/server systeem, met verschillende servers in cluster. Daarom werd geopteerd om een eenvoudige client/server architectuur te gebruiken om de kracht van frontier sets aan te tonen. Hierdoor is het ook mogelijk om de data van de omgeving, PVS en frontiers ook consistent te houden op 1 centrale locatie, en blijft deze data dus ten alle tijden accuraat. De clients hebben geen notie van de cellen met hun PVS en frontiers, hetgeen hen lightweight clients maakt. Aanpassingen aan de server hebben zo ook een minimale impact op deze clients, waardoor een betere schaalbaarheid mogelijk is.

8.2.2

Protocol

Er zijn 3 verschillende berichten: 1 voor gebruikers de GVO te laten betreden, 1 voor hun positie te updaten en 1 indien de gebruikers de simulatie wensen te verlaten. Join Een client stuurt een verzoek naar de server. Indien de evaluatie van dit bericht door de server positief is (geldig IP en poort, client limiet nog niet bereikt) stuurt de server een antwoordt naar deze client en worden de andere clients verwittigd. Dit bericht bestaat uit een id voor de client (gebaseerd op IP en poort), een name en model voor de avatar alsook een initiele positie en richting. Er is ook een veld voorzien met een antwoord van de server of het toevoegen van deze gebruiker in de omgeving is toegestaan. Leave Een client stuurt dit bericht met zijn id naar de server, die dit verder verstuurd naar alle clients. De client wordt dan bij alle andere clients uit de simulatie verwijderd. Positie update Naast de id van de client bevat dit bericht ook een positie en een richting. Wanneer de server dit bericht ontvangt, wordt in een na¨ıeve simulatie dit bericht verstuurt naar de andere clients. In volgende secties wordt dit geoptimaliseerd, en worden berichten enkel verstuurd naar client die interesse hebben in dit bericht. Zoning Een eerste ge¨ımplementeerde optimalisatie mbv. interest management is zoning. Hierbij is er enkel communicatie tussen gebruikers binnen dezelfde cel. Wanneer 2 gebruikers in verschillende cellen zich bevinden is geen communicatie nodig. Wel dient de server aan alle clients mee te delen wanneer een gebruiker van cel veranderd. Een nadeel van zoning is wanneer 2 gebruikers in verschillende cellen zich bevinden, maar

71

elkaar wel kunnen zien. In een na¨ıeve implementatie is er tussen hen toch geen communicatie. Men zou er voor kunnen opteren ook communicatie tussen aangrenzende cellen toe te laten, maar PVS gebaseerde technieken leveren een accurater resultaat.

8.3

Frontier sets

Alvorens een implementatie van frontier sets mogelijk is, dient er eerst een PVS systeem bepaalt te worden.

8.3.1

Inleiding met PVS

In een eerste fase moet voor elke cel bepaald worden welke andere cellen van hieruit zichtbaar zijn. Voor eerder vermeld voorbeeld geeft dit: P V S(A) = {D, G} P V S(B) = {C, F } P V S(C) = {B, E, F, I} P V S(D) = {A, G, H} P V S(E) = {C, F, G, H, I} P V S(F ) = {B, C, E, H, I} P V S(G) = {A, D, E, H} P V S(H) = {D, E, F, G} P V S(I) = {C, E, F } Zoning kan verder geoptimaliseerd worden met deze PVS. Zo kan er enkel communicatie toegestaan worden tussen gebruikers die zich in cellen bevinden die elkaar mogelijk kunnen zien. Als gebruiker 1 zich bijvoorbeeld in cel A bevind en gebruiker 2 in cel G, dan is er tussen hen communicatie nodig. Wanneer gebruiker 2 zich verplaatst naar cel H, dan stopt de communicatie tussen hen omdat cel H geen element is van P V S(A). Vergeleken met de implementatie zonder interest management is het voordeel direct te merken. Zo is er minder dataverkeer tussen de verschillende clients. Ook bevat deze PVS gebaseerde techniek betere resultaten dan de na¨ıeve zoning, omdat er altijd communicatie is tussen gebruikers die elkaar zien, en geen overbodige communicatie met gebruikers die zich in aangrenzende cellen bevinden.

8.3.2

Initialisatie

De eerder berekende PVS kan gebruikt worden om de communicatie verder te optimaliseren door frontiers set te bepalen. De frontiers worden berekend tijdens het initialiseren van de omgeving. Voor elke 2 cellen wordt er een frontier opgezet indien ze niet in elkaar PVS zijn. Iteratief worden dan cellen binnen de PVS van de frontier aan deze frontier toegevoegd, zolang cellen in de ene frontier niet in de PVS is van de andere frontier. Wanneer er een cel aan een frontier wordt toegevoegd wordt ook de PVS van die frontier uitgebreid met de PVS van de toegevoegde cel. Dit wordt herhaald tot er geen cel meer kan toegevoegd worden aan de frontier.

72

Wanneer voor elk paar cellen de frontiers bepaald zijn, is de frontier set volledig en kan deze gebruikt worden tijdens de simulatie.

8.3.3

Simulatie

Voor elk paar gebruikers dient een frontier set opgebouwd te worden. Tijdens de verplaatsingen van deze gebruikers worden diens frontier set gebruikt om te bepalen of er communicatie nodig is. Nieuwe gebruiker Wanneer een nieuwe gebruiker binnen de omgeving komt, krijgt hij een initi¨ele positie en wordt de bijbehorende cel bepaald. Dan wordt voor deze gebruiker fontiers sets aangemaakt per gebruiker. Nadat de cellen van de 2 gebruikers bepaald zijn wordt in de eerder berekende frontier set de overeenkomstige frontiers gezocht en dit wordt voor de nieuwe gebruiker bijgehouden. Deze informatie wordt ook voor de andere gebruiker opgeslagen. Hierdoor is er per gebruiker een lijst van id’s van de andere gebruikers met hun overeenkomstige frontiers. Nu is er enkel communicatie tussen deze gebruiker en een andere gebruiker indien er tussen deze geen frontiers opgesteld kunnen worden. Positie updates Zolang een gebruiker binnen een cel blijft, veranderd er niets aan de communicatie. Wanneer hij echter van cel veranderd, dient de server de frontiers van met de andere gebruikers te controleren. Indien er gebruikers zijn waarvoor de nieuw bezochte cel geen element is van de eigen frontier, dan dient er voor dit paar een nieuwe frontier set bepaald te worden. Dit wordt gedaan mbv. de nieuwe cel van de gebruiker en de actuele cel van de andere gebruiker. Merk op dat de cel van de andere gebruiker niet noodzakelijk dezelfde is dan diens basis cel van de andere frontier. Indien een nieuwe frontier kan worden opgezet, is er nog steeds geen communicatie tussen dit paar nodig. In het andere geval zal er wel communicatie tussen hen zijn, tot 1 van het weer van cel veranderd. Dan zal weer opnieuw hun situatie ge¨evalueerd worden en getracht worden frontiers op te zetten.

8.4

Resultaten/vergelijking

De onderstaande resultaten werden bekomen via een lokale test met 4 gebruikers in een omgeving met 100 cellen (10x10).

73

(a)

Figuur 8.3: De heightmap van de testopstelling.

(a)

(b)

Figuur 8.4: De virtuele omgeving van de testopstelling.

Pakketten Totaal Per sec.

Zoning Na¨ıef PVS Frontier sets 1845 16900 10639 10524 6,76 61,95 39 38,58

Tabel 8.1: Vergelijking van het aantal pakketten verstuurd door de server bij deze implementaties. Zoning houdt geen rekening met de zichtbaarheid van deelnemers in andere cellen. Dit resultaat kan dus niet vergeleken worden met de andere implementaties, maar het geeft wel dat er enorm veel bandbreedte gespaard kan worden wanneer het niet nodig is om deelnemers in andere cellen te zien bewegen. Er is een duidelijk verschil op te merken tussen het gebruik van PVS of frontier sets en de na¨ıeve implementatie. Frontier sets geven betere resultaten dan PVS, maar het verschil is minder groot. Voor grotere omgevingen met meer cellen is dit resultaat groter. Telkens wanneer een gebruiker van cel verandert zal er immers e´ e´ n pakket minder verstuurd moeten

74

worden bij frontier sets dan bij PVS. Naarmate het aantal cellen toeneemt en er meer deelnemers bewegen wordt dit verschil al vlug groter. Omdat ik bij lokale tests slechts e´ e´ n deelnemer tegelijkertijd kon bewegen liggen de waardes heel dicht bij elkaar. Een nadeel van frontier sets is dan er meer geheugen nodig is, en dit groeit evenredig met het aantal gebruikers. Ondanks er per gebruiker slechts een zeer beperkt hoeveelheid nodig is, kan dit toch oplopen wanneer er een (zeer) groot aantal gebruikers wordt ondersteund.

8.5

Slot

Het voordeel van frontier sets is erg duidelijk. Zo is er tussen de server en clients veel minder dataverkeer nodig. Hierdoor is de omgeving beter schaalbaar naar een groot aantal gebruikers. Het voordeel van frontier sets tov. PVS is echter minder duidelijk. Dit heeft vooral te maken met de beperkte complexiteit van de omgeving. Het gebruik van frontier sets is echter niet zonder kost. Het bepalen van een PVS kan voor sommige omgevingen niet eenvoudig zijn. Verder is het mogelijk dat frontier sets slechts kleine gebieden kunnen scheiden, hetgeen een beperkt voordeel tov. PVS levert. Ook groeit de verwerkings- en geheugenkost van frontiers set per client. Voor een groot aantal client kan het geheugengebruik een niet meer verwaarloosbare factor blijven. Meestal is het voordeel van frontier sets groter dan dit nadeel, zodat ze toch in veel toepassingen nuttig zijn.

75

Hoofdstuk 9 Conclusies GVO’s zijn een sterk groeiende tak binnen de virtual reality. Het ondersteunen van een groot aantal gebruikers bij GVO’s vraagt veel van het netwerk. Belangrijke aspecten binnen de GVO zijn de netwerkarchitectuur, data distributie en het datamodel. De eenvoudige client/server architectuur is te beperkt schaalbaar, waardoor peer-to-peer en server cluster architecturen beter gebruikt worden. Ook de verschillende data distributie technieken en datamodellen hebben elk hun voor- en nadelen, waardoor de keuze van groot belang is voor de GVO. Vaak verschilt deze keuze afhankelijk van de applicatie en de omvang van de omgeving. Typisch is een goede keuze van deze algoritmen echter niet voldoende. Verschillende andere technieken, zoals compressie en dead-reckoning, worden vaak toegevoegd om het bandbreedteverbruik te drukken. Dit heeft echter een negatief effect op andere resources, zoals processing tijd en geheugen. Meestal is dit effect te verwaarlozen tov. het positief effect dat deze technieken hebben op het bandbreedteverbruik. Een techniek die het bandbreedtegebruik drastisch kan doen verminderen is interest management. Dit steunt op het principe dat gebruikers meestal enkel met een beperkt aantal andere gebruikers wil communiceren, bijvoorbeeld enkel met gebruikers die ze mogelijk kunnen zien. In deze thesis werd aangetoond dat PVS technieken kunnen gebruikt worden om het dataverkeer over een netwerk te verminderen. Frontier sets nemen de PVS technieken een stap verder. Frontier sets verdelen de omgeving in 2 gebieden, waardoor er geen communicatie nodig is tussen 2 gebruikers wanneer ze zich in deze verschillende gebieden blijven begeven. Er werd aangetoond dat dit een nog grotere winst op het bandbreedteverbruik oplevert dan gewone PVS technieken.

76

Lijst van figuren 3.1 3.2 3.3 3.4

Koppeling tussen de GVO en het onderliggend netwerk. . NPSNET. . . . . . . . . . . . . . . . . . . . . . . . . . MASSIVE. . . . . . . . . . . . . . . . . . . . . . . . . MMOG: World of Warcraft. . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

10 12 13 13

4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13

Unicast, broadcast, multicast en anycast. Client/Server. . . . . . . . . . . . . . . Gedecentraliseerde servers. . . . . . . . Gedistribueerde servers. . . . . . . . . . Proxy servers. . . . . . . . . . . . . . . Peer-to-peer. . . . . . . . . . . . . . . . Replicated homogene omgeving . . . . Shared gecentraliseerde omgeving . . . Shared gedistribueerde omgeving . . . . Aggregatie . . . . . . . . . . . . . . . . Dead reckoning. . . . . . . . . . . . . . Verschillende levels of detail. . . . . . . Zoning . . . . . . . . . . . . . . . . . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16 17 18 19 20 21 23 23 24 25 27 28 28

5.1 5.2 5.3 5.4 5.5

AOI met formules. . . . . . . . . . . . . . . . AOI met cells. . . . . . . . . . . . . . . . . . . AOI met extents. . . . . . . . . . . . . . . . . Schaalbaarheid van Client-Server en Multicast. Voronoi-based Peer-to-Peer Design . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

31 31 32 34 37

6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 6.11 6.12 6.13

Visibility culling technieken. . . . . . . Potentially Visible Set in de praktijk. . . Adjacency graph en stab tree. . . . . . . Occluder fusion. . . . . . . . . . . . . . Extended projections. . . . . . . . . . . Virtual occluders. . . . . . . . . . . . . Sampling. . . . . . . . . . . . . . . . . Sc`enes met hun dual ray space. . . . . . Recursieve culling adhv. portals. . . . . Supporting en separating oppervlakken. Shadow frustum. . . . . . . . . . . . . Hi¨erarchische Z-buffer. . . . . . . . . . Hi¨erarchische occlusion map. . . . . . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

40 41 43 45 45 46 46 47 48 49 50 51 52

77

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

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

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

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

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

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

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

6.14 6.15 6.16 6.17

Directional discretized occluders. . Occluder shadow footprints. . . . PVS bij RING . . . . . . . . . . . RING . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

53 54 55 56

7.1 7.2 7.3 7.4

Potentially visible set voor cel I. . . Region growing frontiers. . . . . . . Dynamische werking van frontiers. . Frontier sets in de praktijk: Quake2.

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

58 60 62 65

8.1 8.2 8.3 8.4

De height map van de virtuele omgeving. . De virtuele omgeving gerenderd in Irrlicht. De heightmap van de testopstelling. . . . . De virtuele omgeving van de testopstelling.

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

69 69 74 74

78

Bibliografie [ACOS]

M. Andersson, C.Carsson, O.Hagsard, and O. Stoahl. Dive - the distributed interactive virtual environment technical reference manual. Kista, Swedish institute of computer science.

[ARFPB90] J. M. Airey, J. H. Rohlf, and Jr. F. P. Brooks. Towards image realism with interactive update rates in complex virtual building environments. SIGGRAPH Comput. Graph., Vol.24(2):41–50, 1990. [ASVNB00] C. Andjar, C. Saona-V´azquez, I. Navazo, and P. Brunet. Integrating occlusion culling and levels of detail through hardly-visible sets. Computer Graphics Forum, Vol.19(3):499–506, 2000. [BDT99]

K. Bala, J. Dorsey, and S. Teller. Interactive ray-traced scene editing using ray segment trees. Computer Graphics (Proceedings of 10th Eurographics Workshop on Rendering), pages 39–52, 1999.

[BESK00]

F. Bernardini, J. El-Sana, and J. T. Klosowski. Directional discretized occluders for accelerated occlusion culling. Eurographics 2000, Vol.19(3), 2000.

[BHS98]

J. Bittner, V. Havran, and P. Slavk. Hierarchical visibility culling with occlusion trees. Computer Graphics (Proceedings of Computer Graphics International 1998), pages 207–219, 1998.

[BMH98]

D. Bartz, M. Meissner, and T. H¨uttner. Extending graphics hardware for occlusion queries in opengl. Computer Graphics (Proceedings of HWWS ’98), pages 97–104, 1998.

[CDKR03] M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. Scalable application-level anycast for highly dynamic groups. In In Networked Group Communications, 2003. [CoCSD00] D. Cohen-or, Y. Chrysanthou, C.T. Silva, and F. Durand. A survey of visibility for walkthrough applications, 2000. [Cro77]

F. C. Crow. Shadow algorithms for computer graphics. SIGGRAPH Comput. Graph., Vol.11(2):242–248, 1977.

[CT97]

S. Coorg and S. Teller. Real-time occlusion culling for models with large occluders. Computer Graphics (Proceedings of the 1997 Symposium on Interactive 3D Graphics), pages 83–90, 1997. 79

[DDTP00]

F. Durand, G. Drettakis, J. Thollot, and C. Puech. Conservative visibility preprocessing using extended projections. Computer Graphics (Proceedings of SIGGRAPH 27), pages 239–248, 2000.

[Dij59]

E.W. Dijkstra. A note on two problems in connexion with graphs. In Numerische Mathematik, 1, 1959.

[DIS]

DIS. Standard for information technology, protocels for distributed interactive sumulation. ANSI/IEEE std.

[Fun95]

T.A. Funkhouser. Ring: a client-server system for multi-user virtual environment. Symposium on Interactive 3D Graphics, pages 85–92, 1995.

[Fun96]

T.A. Funkhouser. Network topologies for scalable multi-user virtual environments. pages 222–228, 1996.

[GB]

C. Greenhalgh and S. Benford. Massive: A distributed virtual reality system incorporating spatial trading. Proceedings of the 15th International Conference.

[GG04]

A. Goldin and C. Gotsman. Geometric message-filtering protocols for distributed multiagent environments. Presence, 13(3):279–295, 2004.

[GKM93]

N. Greene, M. Kass, and G. Miller. Hierarchical z-buffer visibility. Computer Graphics (Proceedings of SIGGRAPH ’93), pages 231–238, 1993.

[HCC06]

S. Hu, J.-F. Chen, and T.-H. Chen. Von: A scalable peer-to-peer network for virtual environments. IEEE computer, 2006.

[HCNF94] D.J. Van Hook, J.O. Calvin, M.K. Nexton, and D.A. Fusco. An approach to dis scalebility. 11th workshop om standards for the interoperability of distributed simulations, pages 347–356, 1994. [HMC+ 97] T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff, and H. Zhang. Accelerated occlusion culling using shadow frusta. Computer Graphics (Proceedings of the ACM Symposium on Computational Geometry), pages 1–10, 1997. [irr]

Irrlicht engine. http://irrlicht.sourceforge.net/.

[KAM04]

Y. Kawahara, T. Aoyama, and H. Morikaw. A peer-to-peer message exchange scheme for large-scale networked virtual environment. Telecomm. Sys, 25(34):353–370, 2004.

[KCCo00]

V. Koltun, Y. Chrysanthou, and D. Cohen-or. Virtual occluders: An efficient intermediate pvs representation. Computer Graphics (Proceedings of the 11th Eurographics Workshop on Rendering Techniques), pages 59–70, 2000.

[KCCO01] V. Koltun, Y. Chrysanthou, and D. Cohen-Or. Hardware-accelerated fromregion visibility using a dual ray space. Computer Graphics (Proceedings of the 12th Eurographics Workshop on Rendering Techniques), pages 205–216, 2001. 80

[KHM+ 96] J. T. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Transactions on Visualization and Computer Graphics, Vol.4:21–36, 1996. [Knu04]

B. Knutsson. Peer-to-peer support for massively multiplayer games. in Proc. INFOCOM, pages 96–107, 2004.

[KS00]

J. T. Klosowski and C. T. Silva. The prioritized-layered projection algorithm for visible set estimation. IEEE Transactions on Visualization and Computer Graphics, Vol.6(2):108–123, 2000.

[KS02]

J. Keller and G. Simon. Towards a peer-to-peer shared virtual reality. in Proc. 22nd Int. Conf. Distributed Computing Systems (Workshops), pages 695–700, 2002.

[Laa03]

M. Laakso. Potentially visible set (pvs). Helsinki university of technology, 2003.

[LG95]

D. Luebke and C. Georges. Portals and mirrors: simple, fast evaluation of potentially visible sets. Computer Graphics (Proceedings of the 1995 Symposium on Interactive 3D Graphics), pages 105–106, 1995.

[Mat97]

M. Matijasevic. A review of networked multi-user virtual environmets. summer course EECE 619, 1997.

[MBD00]

K.L. Morse, L. Bic, and M. Dillencourt. Interest management in large-scale virtual environments. Massachusetts institute of technology, 9(1), 2000.

[MBZ+ 95] M.R. Macedonia, D.P. Brutzman, M.J. Zyda, D.R. Pratt, P.T. Barham, J. Falby, and J. Locke. Nspnet: a multi-player 3d virtual environment over the internet. Proceedings of the 1995 symposion on interactive 3D graphics, pages 93–94, 1995. [MJ95]

D.C. Miller and J.A.Thorpe. Simnet: the advent of simulator networking. Proceedings of the IEEE, Vol.83(8):1114–1123, 1995.

[MR95]

T.W. Mastaglio and R.Callahan. A large-scale complex virtual environment for team training. IEEE computer, 27(7):49–56, 1995.

[MZ97]

M.R. Macedonia and M.J. Zyda. A taxonomy for networked virtual environments, 1997.

[MZP+ ]

M.R. Macedonia, M.J. Zyda, D.R. Pratt, P.T. Barham, and S. Zeswitz. Npsnet: A network software architecture for large scale virtual environments. Presence: Teleoperators and Virtual Environments, MIT Press, Boston.

[PLWT96]

E.T. Powell, L.Mellon, J.F. Watson, and G.H. Tarbox. Joint precision strike demonstration (jpsd) simulations architecture. 14th workshop om standards for the interoperability of distributed simulations, pages 807–810, 1996.

[PS99]

M. Van De Panne and A.J. Stewart. Effective compression techniques for precomputed visibility. In Proc. Eurographics rendering workshop, 1999. 81

[QCD+ 09] P. Quax, B. Cornelissen, J. Dierckx, G. Vansichem, and W. Lamotte. Alvic-ng: state management and immersive communication for massively multiplayer online games and communities. 2009. [qua]

Id software (1999) quake2. http://www.idsoftware.com/games/quake/quake2/.

[rak]

Raknet - multiplayer game network engine. http://www.jenkinssoftware.com/.

[RBD04]

S. Rooney, D. Bauer, and R. Deydier. A federated peer-to-peer network game architecture. IEEE Commun. Mag., 42(5):114–122, 2004.

[SA]

A. Steed and C. Angus. Enabling scalability by partitioning virtual environments using frontier sets. Department of Computer Science, University College London.

[SA04]

A. Steed and C. Angus. Frontier sets: A partitioning scheme to enable scalable virtual environments. The Eurographics Association, 2004.

[SA05]

A. Steed and C. Angus. Supporting scalable peer to peer virtual environments using frontier sets. IEEE VR2005 Bonn, 2005.

[SAh03]

A. Steed and R. Abou-haidar. Partitioning crowded virtual environments. In Proceedings of the ACM symposium on Virtual reality software and technology, pages 7–14, 2003.

[SDDS00]

G. Schaufler, J. Dorsey, X. Decoret, and F. X. Sillion. Conservative volumetric visibility with occluder fusion. Computer Graphics (Proceedings of SIGGRAPH 27), pages 229–238, 2000.

[sec]

Linden labs (2009) secondlife. http://www.secondlife.com.

[SKH02]

J. Smed, T. Kaukoranta, and H. Hakonen. A review on networking and multiplayer computer games. pages 1–5, 2002.

[SRS95]

J. Smith, K.L. Russo, and L.C. Schuette. Prototype multicast ip implemetation in modsaf. 12th workshop om standards for the interoperability of distributed simulations, pages 175–178, 1995.

[SZ99]

S. Singhal and M. Zyda. Networked virtual environments: design and implementation. ACM Press/Addison-Wesley Publishing Co., 1999.

[the]

There (2009). http://www.there.com.

[TS91]

S. J. Teller and C.H. S´equin. Visibility preprocessing for interactive walkthroughs. SIGGRAPH Comput. Graph., Vol.25(4):61–70, 1991.

[wow]

Blizzard (2009) world of warcraft. http://www.worldofwarcraft.com.

[WS99]

P. Wonka and D. Schmalstieg. Occluder shadows for fast walkthroughs of urban environments. Computer Graphics (Proceedings of EUROGRAPHICS 1999), pages 51–60, 1999.

82

[WWS00]

P. Wonka, M. Wimmer, and D. Schmalstieg. Visibility preprocessing with occluder fusion for urban walkthroughs. Computer Graphics (Proceedings of the 11th Eurographics Workshop on Rendering Techniques), pages 71–82, 2000.

[YV05]

A. Yu and S.T. Vuong. Mopar: a mobile peer-to-peer overlay architecture for interest management of massively multiplayer online games. in Proc. NOSSDAV, pages 99–104, 2005.

[Zha98]

H. Zhang. Effective occlusion culling for the interactive display of arbitrary models. PhD thesis, 1998.

83