Research overview
A multi-layered navigation mesh.
![](images/multi_layered_navigation_mesh.png)
We study how we can automatically create a data structure that represents the walkable surfaces in virtual environments, and how it can be updated dynamically and efficiently when it changes. We refer to this structure as a navigation mesh. This mesh enables efficient crowd simulation, which is our next topic of research. We study and develop a crowd simulation framework and its components, which ranges from global (AI) planning to local animation. We create models for realistic crowd behaviors, which includes studying how (groups of) people move and avoid collisions in such environments, based on agent profiles and semantics (such as terrain annotations).
Roland Geraerts. UU Crowd simulation research. May 2016. Presentation. In ICT.OPEN 2015 (ICT.OPEN 2015).
Wouter G. van Toll, Norman S. Jaklin and, Roland Geraerts.
Towards Believable Crowds: A Generic Multi-Level Framework for Agent Navigation.
In ICT.OPEN 2015 (ICT.OPEN 2015).
Wouter G. van Toll, Atlas F. Cook IV, Marc J. van Kreveld and Roland Geraerts. The Medial Axis of a Multi-Layered Environment and its Application as a Navigation Mesh. ACM Transactions on Spatial Algorithms and Systems. Vol. 4, No 1. pages 2:1-2:34. May 2018.
The results can be used
We cannot directly start a simulation by using the raw 3D geometry that describes the 3D environment. It first needs to be processed so that the simulation knows where agents can move or not. How does that work?
Polygonal environment![]() |
Walkable environment![]() |
Multi-layered environment![]() |
Multi-layered navigation mesh![]() |
We are given a 3D polygonal environment which consists of collection of polygons. We assume that there is a static gravitation vector (which implies for instance that we do not support sphere-like virtual worlds). We convert this environment into a walkable environment by removing polygons that are too steep, too close to a ceiling (e.g. an agent would otherwise bump his head) or polygons that are part of an area that is too small to move on. In the next step, we decompose this environment into a set of 2D layers (and connections between the layers) such that there is no internal overlap within each layer when its polygons would be projected onto the ground floor. Heuristics are applied to separate the layers. The resulting multi-layered environment is then in the right format for many algorithms that normally only work in 2D (such as algorithms that compute a shortest path which optionally has some minimum amount of clearance to obstacles, a visibility region, or a navigation mesh). For each layer, we compute a 2D navigation mesh, based on the generalized Voronoi diagram or medial axis. More specifically, the navigation mesh is a Corridor Map that decomposes the walkable environment into a set of non-overlapping simple cells that fully cover the walkable space. The meshes are stitched together at the connections such that a continuous multi-layered navigation mesh appears. We compared this navigation mesh with others in a comparative study.
When an polygonal obstacle is added, deleted, or moved, the navigation mesh can be locally updated to reflect the changes. This mesh can then be used in our simulation framework.
Our simulation framework consists of five levels of planning, which allows for efficient and flexible crowd simulations.
At the top of the hierarchy, event management and action planning (5) generate a set of geometric path planning queries, consisting of start/goal pairs. In this phase, we support for instance social groups, large groups, re-planning of agents when the navigation mesh changes or when crowd densities change.
Next, the global route planning level (4) uses a query to produce a static indicative route for an agent or group, which indicates how they should globally walk. There are many choices in how to create indicative routes. For instance, they can be the shortest path, or the shortest path with some amount of minimum distance to the obstacles, or they can be optimized for camera movement or stealth movement.
The three lower levels move the crowd in every step of the simulation. On the route following level (3), the global routes are being traversed using our Indicative Route Method, yielding preferred velocities (i.e. speed/direction pairs). These paths can also be generated in annotated environments by using its successor, MIRAN, which supports environments whose walkable polygons have received a weight.
The preferred velocities are adapted in the local movement level (2) where a pedestrian might temporarily deviate from its global route to coordinate its movements and to handle potential collisions with the crowd, yielding a velocity that is used by the animation system in level (1) to move an agent.
In our crowd prediction project, we extend our UU crowd simulation software to calibrate a crowd simulation in real-time (using video camera's) while an event is going on. In addition, we program a prediction model that can predict what the (near) future state of a crowd will be.
This project is the result of a software project carried out by our bachelor computer science students: Patrick van Eijk, Rens de Heer, Raphael Claasen, Sophie Huiberts, Martin Korevaar, Jurriaan Pijpers, Adolfo Ochahavia, Tim de Bie, Patrick Habekotte and Guido Oskam. Special thanks goes to Atlas Cook (voice), and my PhD students Arne Hillebrand and Wouter van Toll for their endless support.
Crowd simulation basis
Digital twins and Synthetic single environments
Machine learning
Pedestrian dynamics
Navigation meshes
Augmented reality and virtual reality
Path planning
Animation