Navigation Meshes for Realistic Multi-Layered Environments
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
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.
The steps of our algorithm are visualized in the movie below.
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.
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.
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.
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.