Grote werelden op kleine laptops – mesh optimalisatie

In ons Urbo3D Klimaatspel gebruiken we de 3D Basisvoorziening-data om de 3D-wereld te genereren. Dankzij deze data kunnen we elke buurt in Nederland in ons spel opnemen.

De 3D-data in de 3D Basisvoorziening wordt automatisch gegenereerd op basis van de BGT (Basisregistratie Grootschalige Topografie), BAG (Basisregistratie Adressen en Gebouwen) en luchtfoto’s (stereobeelden) ¹. Dit proces resulteert in een dataset van hoge resolutie, waarbij de data voor één enkele buurt soms honderden duizenden driehoeken bevat. Hierdoor kunnen oudere laptops moeite hebben met het renderen van de 3D-wereld, wat leidt tot trage prestaties en frustratie bij spelers.

Omdat we ons spel toegankelijk willen houden voor alle scholen, hebben we onderzocht hoe we de 3D-dataset kunnen verkleinen, zodat het spel efficiënt draait op alle laptops.

Mesh optimalisatie

In de 3D Basisvoorziening zijn stukken grond opgebouwd uit veel driehoeken. Bekijk bijvoorbeeld dit perceel in Buitenveldert:

Om het aantal driehoeken te verminderen, voeren we de volgende stappen uit:

Stap 1: Omtrek bepalen

Het algoritme hiervoor is verrassend eenvoudig:

• Doorloop alle driehoeken en verzamel alle randen in een grote verzameling.
• Verwijder alle randen die duplicaten hebben.
• Maak gesloten contouren van de resterende randen.

Stap 2: Omtrek vereenvoudigen

Doorloop de omtrek en vervang hoeken die dicht bij 180 graden liggen door een enkele rechte lijn.

In deze stap is het belangrijk om alle meshes tegelijkertijd te optimaliseren. Wanneer je een punt uit de omtrek van een mesh verwijdert, moet hetzelfde punt ook uit de omtrek van de aangrenzende mesh worden verwijderd, anders ontstaan er gaten tussen de meshes.

Stap 3: Trianguleren van de vereenvoudigde omtrek

Voor de triangulatie van de vereenvoudigde omtrek gebruiken we het Earcut-algoritme². Let op: Earcut kan niet omgaan met randen die in een verticaal vlak liggen. Daarom optimaliseren we momenteel geen meshes die verticale randen bevatten.

Resultaat

Dit is hetzelfde perceel na de mesh-optimalisatie:

Met dit optimalisatie-algoritme kunnen we het aantal driehoeken in een 3D-wereld met 60% tot 70% verminderen. Dit zorgt ervoor dat het spel ook op oudere laptops soepel kan draaien. In de toekomst willen we ook de verticale delen aanpakken, wat ons nog meer winst kan opleveren.

1. Voor meer informatie over 3D Basisvoorziening zie: https://3d.kadaster.nl/praktijkhandleiding ↩︎
2. https://github.com/mapbox/earcut ↩︎