Abstract
Path planning for walking characters in complicated virtual environments is a fundamental task in simulations and games. A navigation mesh is a data structure that allows efficient path planning. The Explicit Corridor Map (ECM) is a navigation mesh based on the medial axis. It enables path planning for diskshaped characters of any radius.
In this paper, we formally extend the medial axis (and therefore the ECM) to 3D environments in which characters are constrained to walkable surfaces. Typical examples of such environments are multistorey buildings, train stations, and sports stadiums. We give improved definitions of a walkable environment (WE: a description of walkable surfaces in 3D) and a multilayered environment (MLE: a subdivision of a WE into connected layers). We define the medial axis of such environments based on projected distances on the ground plane. For an MLE with n boundary vertices and k connections, we show that the medial axis has size O(n), and we present an improved algorithm that constructs the medial axis in O(n log n log k) time.
The medial axis can be annotated with nearestobstacle information to obtain the ECM navigation mesh. Our implementations show that the ECM can be computed efficiently for large 2D and multilayered environments, and that it can be used to compute paths within milliseconds. This enables simulations of large virtual crowds of heterogeneous characters in realtime.
References

Wouter G. van Toll, Atlas F. Cook IV, Marc J. van Kreveld and Roland Geraerts. The Medial Axis of a MultiLayered Environment and its Application as a Navigation Mesh. ACM Transactions on Spatial Algorithms and Systems. March 2018.

Wouter G. van Toll, Atlas F. Cook IV and Roland Geraerts. Navigation Meshes for Realistic MultiLayered Environments. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'11), pp. 35263532, 2011.

Wouter G. van Toll, Atlas F. Cook IV and Roland Geraerts. MultiLayered Navigation Meshes. In ASCI  IPA  SIKS tracks, ICT.OPEN (ICT.OPEN 2011), pp. 317323, 2011.
This paper has received the best paper award ASCI 2011.
Movie
The method is demonstrated in the following movie.
Navigation Meshes for Realistic MultiLayered Environments.
Input
The input for our algorithm is a multilayered environment.
A simple 3D environment for which we want to compute a navigation mesh.
The initial input is a 3D environment, which consists of a collection of polygons in 3D. From this environment, a walkable environment (WE) is extracted, which is a set of polygons along which characters can walk. A multilayered environment (MLE) is then a subdivision of the WE into 2D layers. Connections between layers are shown as bold line segments in this example. Please refer to our overview on how a multilayered environment can be extracted from a 3D environment.
Technique
First, a medial axis is computed for each layer using standard techniques. Then, interatively, each connection C_ij is opened. (a). Initially, C_ij is an obstacle on both sides, S_i and S_j. (b). 2D shows a top view of the area around C_ij. The influence zone Z_ij = Z_i + Z_j is shaded. The obstacle points N_ij = N_i + N_j that are nearest to Z_ij are shown in bold black. (c) When opening C_ij, the medial axis changes only inside Z_ij. This medial axis M_Z is defined by N_ij .
Opening a connection in a multilayered environment.
We compute the medial axis M_Z in three steps. Figure (a) shows the medial axis when C_ij is still closed. (b) M_Z,i uses only the obstacles of N_i and assumes that Z_j extends to infinity. We compute it using a plane sweep on the ground plane P, starting with the sweep line L at C_ij, without explicitly projecting all of N_i onto P at the same time. (c) Analogously, M_Z,j uses only N_j. (d) We merge the two parts to obtain M_Z.
Computation of the medial axis (in a multilayared environment) in three steps.
Application: The Explicit Corridor Map
The Explicit Corridor Map (ECM) is a navigation mesh that is closely related to the medial axis. Figure (a) shows the medial axis of a 2D environment. The ECM in (b) is a medial axis with nearestobstacle annotations, shown as orange line segments between vertices and their nearest obstacle points. These segments are not edges in the graph. In figure (c), you can find details of an ECM edge with four bending points. Each bending point bp_k stores its position p_k and its nearest obstacle points l_k and r_k.
The Explicit Corridor Map is easily derived from a medial axis.
Figure (a) shows some examples of query points (shown as large dots), their nearest obstacle points (small dots), and their retractions (circles). Given two positions s and g in figure (b), the retraction method is used to compute a path from s to g along the medial axis. A corridor describes the free space around this path. (c) Within the corridor, we can compute various types of indicative routes, e.g. with an amount of preferred clearance.
Some key operations defined on the Explicit Corridor Map..
Experiments
We've conducted experiments with 2D as well as multilayered environments.The set of 2D environments and their ECMs.
The set of 3D environments and their ECMs (part 1).
The set of 3D environments and their ECMs (part 2).
Such a mesh also allows dynamic updates when an obstacle is inserted, deleted or moved.
Results
The tested environments have the following properties.Details of the environments used in our experiments.
Here are the results for all tested environment. The ECM complexity columns show the number of vertices, edges, and bending points in the ECM computed using Boost. The ECM time columns show the ECM construction time for the three implementations: Vroni, Boost, and Boost with 5 parallel threads (for multilayered environments). All times are in milliseconds and have been averaged over 10 runs. Standard deviations are shown between square brackets.
Details of the ECMs for our experiments.
Conclusions
In robotics, simulations, and gaming applications, virtual walking characters often need to compute and traverse paths through an environment. A navigation mesh is a subdivision of the free space into polygons that allows realtime path planning for crowds of characters.
With this application area in mind, we have studied the medial axis for 3D environments with a consistent direction of gravity. A walkable environment (WE) describes where characters can walk. A multilayered environment (MLE) is a WE that has been subdivided into 2D layers connected by k connections with certain geometric properties. We have defined the medial axis for WEs and MLEs based on projected distances on the ground plane. We have presented an algorithm that computes this medial axis by initially treating all connections as closed obstacles and then opening them incrementally. Compared to previous work [van Toll et al. 2011], we have presented a new and correct algorithm for opening a connection, and we have improved the overall running time to O(n log n log k) by opening the connections in an efficient order.
We have presented an improved definition of the Explicit Corridor Map (ECM), which is a navigation mesh based on the medial axis. The ECM enables path planning for diskshaped characters of any radius. It supports efficient geometric operations such as retractions, nearestobstacle queries, dynamic updates, and the computation of short paths with preferred clearance to obstacles.
Our implementation computes the ECM efficiently for large 2D and multilayered environments. The ECM supports important applications and operations, such as path planning and dynamic updates. It is a useful basis for simulating large crowds of heterogeneous characters in realtime.