Navigation Meshes for Realistic Multi-Layered Environments

Abstract
Virtual characters often need to plan visually convincing paths through a complicated environment. For example, a traveler may need to walk from an airport entrance to a staircase, descend the staircase, walk to a shuttle, ride the shuttle to a destination, ride an elevator back to the ground floor, and finally move on the ground floor again to reach the desired airplane. Most previous research only supports path planning in a single plane because the underlying data structures are twodimensional. The goal of this paper is to permit visually convincing paths to be efficiently computed in a multilayered environment such as an airport or a multi-storey building. We describe an algorithm to create a navigation mesh, and our implementation demonstrates the feasibility of the approach.

A multi-layered environment is represented by a set of two-dimensional layers and a set of connections. Each layer is a collection of two-dimensional polygons that all lie in a single plane, and each connection provides a means of moving between layers.

We first compute the traditional medial axis of each two-dimensional layer in the environment. The connections are then used to iteratively merge this collection of medial axes into a single data structure. By adding a linear number of line segments to this structure, we obtain a navigation mesh that mathematically describes the walkable areas in a multi-layered environment. This mesh can easily be input into existing planners to generate visually convincing paths for thousands of virtual characters in real-time.

Reference
Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts.
Navigation Meshes for Realistic Multi-Layered Environments.
In IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3526-3532, 2011.
Full text [pdf] | Presentation pitch [ppt]

Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts.
Multi-Layered Navigation Meshes.
In ASCI - IPA - SIKS tracks, ICT.OPEN (ICT.OPEN 2011), 2011.
This paper has received the best paper award ASCI 2011.
Full text [pdf] | Presentation [ppt]

A multi-layered navigation (navmesh) mesh (computed in 46ms).
A multi-layered navigation mesh


Movie
The steps of our algorithm are visualized in the movie below.



Technique
A multi-layered environment in R3 can be represented as a set of two-dimensional layers and a set of connections between these layers. For example, the connection C_01 connects layer 0 and layer 1, and the connection C_12 connects layer 1 and layer 2. Each connection is directed in the sense that it can only be used through its access side. The obstacle side of a connection is an impassable obstacle.

A multi-layered environment in R3 can be represented as a set of two-dimensional layers and a set of connections between these layers.
2D layers and their connections

The medial axis of a simple multi-layered environment. The influence zone Z_ij is highlighted in blue. The intersection of M_i and M_j with C_ij is denoted by the points p_1, p_2 in C_ij.

The medial axis of a simple multi-layered environment (a-b).

The medial axis of a simple multi-layered environment (c-d).
The medial axis of a simple multi-layered environment.

Results
Our navigation mesh can be input into an existing path planner such as the Indicative Route Method to generate a visually convincing path through a multilayered environment. The figures illustrate 3D and 2D views of the same multi-layered environment. The navigation mesh was computed in 46ms and the path in less than 1ms.

The 3D top view of a visually convincing path extracted from a multi-layered navigation mesh (navmesh).      A 2D view of a visually convincing path extracted from a multi-layered navigation mesh (navmesh).
A visually convincing path extracted from a multi-layered navigation mesh in a 3D environment. This path is smooth, short, and has a desired amount of minimum clearance to the obstacles.

This paper is an extention of the 2D Explicit Corridor Map.
We have submitted a paper that allows dynamic updates in the multi-layered mesh.