Opsplitsen van 3D-modellen

Opsplitsen van 3D-modellen

Simulaties van mensenmassa’s worden gebruikt bij het ontwerpen van gebouwen en het voorbereiden op evenementen. Eén simulatiemethode maakt gebruik van een speciaal soort gelaagde plattegrond. Het vinden van deze plattegrond is geen makkelijke taak.

Arne Hillebrand

Hoeveel mensen kan het nieuwe Utrecht Cen­traal station per dag aan? En waar kunnen we opstoppingen van mensen verwachten bij grote evenementen? Dit zijn vraagstukken waar com­putersimulaties van mensenmassa’s ons mee kunnen helpen. Eén methode voor dit soort simulaties maakt gebruik van de Explicit Cor­ridor Map (ECM) ontwikkeld door Geraerts (2010) voor 2D-omgevingen. Met behulp van de ECM kan snel voor de mensen in een simulatie een realistische route worden bepaald. Hierbij wordt rekening gehouden met een minimale afstand tot obstakels en de andere mensen in de simulatie. Door meerdere 2D-omgevingen op een slimme manier aan elkaar te verbinden, is het Van Toll et al. (2011) gelukt om de Explicit Corridor Map ook toe te passen op een gelaagde 2D-omgeving.

Voor het gebruik van de ECM is het noodzakelijk om de omgeving eerst te versimpelen. In zo’n versimpelde weergave wordt alleen de meest elementaire informatie opgeslagen voor een simulatie van mensenmassa’s. Waar kunnen de mensen allemaal staan en bewegen? Alle andere informatie over bijvoorbeeld muren en ramen wordt weggegooid. Wat er nu overblijft is het beloopbare gebied. Dit gebied staat bekend als een polygonale omgeving. Een voorbeeld van zo’n omgeving is te zien in figuur 1. In figuur 1a zien we het beloopbare gebied van een model van de Universiteitsbibliotheek Uithof. Het beloop­bare gebied wordt in computers gerepresenteerd als een verzameling van veelhoeken/polygonen, in dit specifieke geval rechthoeken. De polygona­le omgeving wordt vervolgens opgedeeld in lagen of verdiepingen (bijvoorbeeld de verschillende verdiepingen van een gebouw, zoals een trein­station of voetbalstadion). Hiervoor moeten we de overgangen berekenen waar de verschillende verdiepingen aan elkaar gekoppeld zijn (bijvoor­beeld waar de trappen beginnen of eindigen). Een mogelijke opdeling van het beloopbare gebied in verschillende lagen is te zien in figuur 1b. De opsplitsing van het beloopbare gebied in lagen komt tot stand door het toekennen van polygonen aan verschillende lagen. Alle poly­gonen in één laag hebben in figuur 1b dezelfde kleur gekregen.

Toekennen van polygonen

Bij het toekennen van polygonen aan lagen is er één belangrijke beperking. De polygonen die bij elkaar in één laag zitten mogen elkaar niet overlappen. Een polygoon overlapt een andere polygoon als deze boven de andere geplaatst is. Dit concept is te zien in figuur 2. In figuur 2a overlappen de gestippelde polygonen met de gestreepte polygonen. Hierdoor mogen ze dus niet aan dezelfde laag worden toegekend. Als geen enkel polygoon uit één laag een ande­re polygoon overlapt, dan spreken we van een geldige multi-layered environment (MLE). De toekenning van de polygonen aan lagen zoals weergegeven in figuur 2a is dus niet correct en vormt daarmee geen geldig MLE. Een andere toewijzing van polygonen aan lagen is te zien in figuur 2b. Hier zijn de overlappende polygonen niet aan eenzelfde laag toegekend, waardoor deze MLE wel geldig is. Naast de vereiste dat over­lappende polygonen niet in dezelfde laag mogen zitten, bestaat de wens om het aantal lagen en het aantal overgangen in een MLE zo laag moge­lijk te houden. De tijd die benodigd is voor het maken van de Explicit Corridor Map is namelijk afhankelijk van het aantal lagen en overgangen in het MLE. Een groter aantal lagen of overgangen betekent een langere looptijd ervan. Idealiter vin­den we een MLE met zowel het minimale aantal lagen als het minimale aantal overgangen. Helaas is dit niet altijd mogelijk, zoals te zien is in figuur 3. In deze figuur zien we twee verschillende MLE’s voor dezelfde omgeving. Het MLE in figuur 3a heeft twee lagen en vier overgangen, terwijl het MLE in figuur 3b uit drie lagen en twee overgangen bestaat. Er bestaat geen MLE voor deze omgeving met twee of minder lagen en twee of minder overgangen. We hebben gekozen om te zoeken naar een MLE met zo min mogelijk overgangen, omdat het aantal overgangen in een MLE iets zegt over het maximale aantal lagen in een omgeving. Het aantal lagen zegt niets over het maximale aantal overgangen. Helaas kwamen we al snel tot de conclusie dat het vinden van een MLE met een minimaal aantal overgangen een erg moeilijk probleem is. We hebben name­lijk bewezen dat dit probleem behoort tot de klasse van NP-moeilijke problemen (Hillebrand, 2012). Voor een NP-moeilijk probleem is er in de praktijk geen manier om met een computer snel en efficiënt een oplossing te vinden.

Verschillende methoden

Na deze constatering zijn we op zoek gegaan naar methoden om MLE’s met weinig overgan­gen te vinden in plaats van het minimale aantal overgangen. In totaal hebben we vijf methoden ontwikkeld, waarvan er één altijd de optimale oplossing zal vinden. Deze methode doet er echter vaak erg lang over. De vier andere metho­den geven geen garantie over de kwaliteit van de oplossing. De gevonden oplossing kan het mini­male aantal overgangen hebben of er juist heel ver van af zitten. De twee methoden die de beste resultaten behaalden, worden hieronder verder beschreven. De eerste van deze methoden maakt gebruik van een werkwijze die bekend staat als ‘Lokaal Zoeken’ (Cerný, 1985). De andere metho­de is ‘Hoogteheuristiek’. Deze maakt gebruik van het feit dat we meestal een MLE willen vinden voor bestaande gebouwen of gebouwen die geschikt zijn voor mensen. Dit maakt dat we kunnen uitgaan van een bepaalde regelmaat in gebouwen, die we weer kunnen gebruiken om snel goede MLE’s te vinden.

‘Lokaal Zoeken’

Bij ‘Lokaal Zoeken’ gaan we uit van een bestaan­de oplossing voor het probleem. Deze bestaande oplossing proberen we daarna stapsgewijs te ver­beteren. Dit betekent dat we beginnen met een willekeurige multi-layered environment voor een omgeving. Deze MLE hoeft nog niet het minima­le aantal overgangen te bevatten. In onze imple­mentatie van ‘Lokaal Zoeken’ beginnen we steeds met een MLE waarin elke polygoon een laag vormt. Op zo’n MLE is een aantal wijzigingen mogelijk. Eén daarvan is het samenvoegen van twee aangrenzende lagen. Deze actie vermindert altijd het aantal lagen én het aantal overgangen. Een tweede mogelijke wijziging is het verplaat­sen van een polygoon van de ene laag naar een andere laag. Een voorbeeld van deze twee opera­ties is te zien in figuur 4. Als we beginnen met het MLE in figuur 4a, kunnen we het MLE in figuur 4b verkrijgen door één polygoon van de groene laag naar de rode laag te verplaatsen. Met deze actie verkrijgen we een MLE met twee overgangen minder. Vervolgens kunnen we het MLE in figuur 4c verkrijgen door twee ver­schillende lagen samen te voegen: de zwarte en de groene laag. Dit levert een vermindering van één laag en vier overgangen op. Overigens is het niet altijd zo dat deze operaties een MLE met een verminderd aantal overgangen oplevert; de operaties zijn zelfs niet altijd mogelijk. Om voor deze tekortkoming te compenseren, wordt er bij ‘Lokaal Zoeken’ altijd een ‘buurt’ aan mogelijke nieuwe MLE’s gegenereerd. Voor één MLE wor­den de verschillende operaties één of meerdere keren uitgeprobeerd op verschillende polygonen of lagen. De operatie die de grootste verbetering oplevert wordt vervolgens doorgevoerd. Dan nog kan het voorkomen dat er niet altijd een verbe­tering is. Dit kan twee oorzaken hebben: of we hebben de beste oplossing gevonden, of we zitten vast in een zogeheten lokaal minimum. Als we in een lokaal minimum zitten, is geen van de MLE’s die we kunnen maken met de beschreven opera­ties een verbetering. Een voorbeeld hiervan is te zien in figuur 3a. De lagen kunnen niet samen­gevoegd worden omdat dit een ongeldig MLE tot gevolg zou hebben. Door het verplaatsten van polygonen kunnen we in deze situatie ook niet een betere situatie bereiken. De polygonen die de twee lagen verbinden kunnen van laag wisse­len. De kwaliteit van de oplossing zal hierdoor niet verbeteren. Ter vermijding van het vast komen te zitten in een lokaal minimum hebben we meer diversiteit aangebracht in de gebruikte operaties en gebruikgemaakt van technieken als simulated annealing en tabusearch.

Hoogteheuristiek

De ‘Hoogteheuristiek’ maakt gebruik van de hoogte-informatie van een polygoon. In ‘normale’ omgevingen, zoals gebouwen en steden, is het onwaarschijnlijk dat een polygoon die zich op nul meter boven de grond bevindt in dezelfde laag terechtkomt als een polygoon die 60 meter boven de grond zweeft. Dit komt doordat ver­diepingen in normale gebouwen meestal recht zijn en er tussen de rechte verdiepingen maar een paar overgangen zijn, namelijk de trappen. Van dit gegeven maken we dankbaar gebruik: we groeperen de polygonen op hoogte. Allereerst worden polygonen die zich op exact dezelfde hoogte bevinden in dezelfde groep geplaatst. Polygonen binnen één groep mogen elkaar niet overlappen. Vervolgens worden aangrenzende groepen samengevoegd, zolang er geen overlap­pende polygonen in één groep terechtkomen. Als er geen groepen meer samengevoegd kunnen worden, worden er per groep één of meerdere lagen gegenereerd. In de laatste fase worden de polygonen tussen aangrenzende lagen herver­deeld in een poging het aantal overgangen verder te verminderen.

Experimenten

Alle methoden zijn getest op negen verschil­lende omgevingen, waarvan we er hier drie bespreken: de Universiteitsbibliotheek Uithof (‘uulib’); een model geïnspireerd op de studen­tenflat City Campus Max in Utrecht (‘max’) en een fictieve stad (‘tf2’). Deze omgevingen zijn te zien in figuur 5. Aanvullende details van deze omgevingen zijn opgenomen in figuur 6. Deze omgevingen geven een beeld van de verschillen­de soorten omgevingen die er zijn. De omgeving ‘tf2’ bestaat uit verschillende gebouwen die aan elkaar verbonden zijn door één laag. Daarentegen bestaan de omgevingen ‘max’ en ‘uulib’ slechts uit één gebouw. Het model ‘max’ onderscheidt zich door de hoeveelheid overlappingen die in deze omgeving zitten. Verder is het voor dit model voor mensen simpel om de optimale oplossingen te vinden, terwijl dit voor computers erg lastig blijkt. De omgeving ‘uulib’ is interessant omdat niet elke verdieping de andere verdieping com­pleet overlapt, zoals bijvoorbeeld bij ‘max’ wel het geval is. Van elk experiment werden de gevonden oplossingen opgeslagen en werd er bijgehou­den hoelang het duurde voordat deze oplossing gevonden was. In figuur 7 zijn deze gegevens te vinden. Van de methoden die we getest hebben is de ‘Hoogteheuristiek’ voor deze omgevingen de snelste methode. Bovendien behoren de oplos­singen die met deze methode gevonden worden meestal tot de beste. ‘Lokaal Zoeken’ is altijd langzamer en levert zelden betere oplossingen.

Conclusie

Voor de geteste omgevingen blijkt de ‘Hoogteheuristiek’ bijna altijd betere resultaten op te leveren voor het aantal overgangen; alleen ‘Lokaal Zoeken’ weet voor één omgeving betere resultaten neer te zetten. Hier stond wel tegen­over dat ‘Lokaal Zoeken’ er veel langer over deed dan de ‘Hoogteheuristiek’. Als we kijken naar de hoeveelheid tijd die nodig is voor het zoeken naar de oplossing is de ‘Hoogteheuristiek’ altijd beter. Dit komt waarschijnlijk doordat die methode ontworpen is met het oog op ‘gewone’ omge­vingen en de hier geteste omgevingen allemaal zijn gebaseerd op, of geïnspireerd door normale gebouwen. We kunnen ons afvragen hoe goed de ‘Hoogteheuristiek’ zal presteren op een minder normale omgeving, zoals een omgeving uit een computerspel waarin alle verdiepingen van de gebouwen een helling vormen. Het kan zijn dat de ‘Hoogteheuristiek’ in zo’n geval begint met een verkeerde groepering van de polygonen. De verwachting is dat ‘Lokaal Zoeken’ minder last zal hebben van niet-normale omgevingen, aangezien deze methode geen gebruik maakt van de hoogte-informatie van polygonen.

In vergelijking met methoden die in eerdere studies werden gebruikt om een MLE te vinden voor een 3D-model zijn de resultaten goed te noemen. Deze eerdere methoden waren niet in staat om met grote omgevingen, zoals ‘max’ en ‘tf2’ om te gaan of deden er uren over om voor deze omgevingen een MLE te vinden. Als we zowel de snelheid van het algoritme en de kwa­liteit van de oplossing in acht nemen, dan is de ‘Hoogteheuristiek’ de onbetwiste winnaar.

Door de hierboven beschreven methoden is het nu mogelijk om snel een willekeurige omgeving op te splitsen in verschillende lagen. Voorheen moest er nog iemand met de hand van een omge­ving een MLE maken of moest men gebruik­maken van MLE’s met relatief veel overgangen en lagen. Voor één van onze methoden is er een plug-in gemaakt voor de Unity3D game engine.

Naast de vraag of het vinden van een MLE sneller kan, is het interessant om te kijken hoe er vanuit een willekeurig model een MLE gegene­reerd kan worden. Op het moment zijn er alleen MLE’s gegenereerd vanuit een eigen bestands­formaat en niet vanuit bijvoorbeeld een CAD- of CityGML-bestand. Verder is er niet gekeken hoeveel impact het heeft om een MLE met minder overgangen te gebruiken voor de Explicit Corridor Map.

 

Arne Hillebrand heeft de master Computing Science aan de Universiteit Utrecht gevolgd. In de onderzoeksgroep Virtul Worlds van de Universiteit Utrecht schreef hij zijn masterscriptie Separating a polygonal environment into a multi-layered environment onder begeleiding van dr. ir. J.M. van den Akker, dr. J.A. Hoogeveen en dr. R.J. Geraerts. Voor zijn scriptie heeft hij de Ngi Informatie Scriptieprijs 2013 gewonnen. E-mail: a.hillebrand@gmail.com

Literatuurlijst

Cerný, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45, 41-51.

Geraerts, R. (2010). Planning short paths with clearance using explicit corridors. IEEE International conference on robotics and automation, 1997-2004.

Hillebrand, A. (2012). Separating a polygonal environment into a multi-layered environment. Faculty of Science Theses. Bereikbaar op http://dspace.library.uu.nl/handle/1874/259132

Toll, W. van & Cook IV, A.F. & Geraerts, R. (2011). Navigation meshes for realistic multi-layered environments. IEEE/RSJ International Conference on Intelligent Robots and Systems, 3526–3532.

 

 
 

Tag

Onderwerp



Niet gevonden? Vraag het de redactie!

Heeft u het antwoord op uw vraag niet gevonden, of bent u op zoek naar specifieke informatie? Laat het ons weten! Dan zorgen we ervoor dat deze content zo snel mogelijk wordt toegevoegd, of persoonlijk aan u wordt geleverd!

Stel uw vraag