Publication details

Navigation Meshes for Realistic Multi-Layered Environments
Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts
In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3526-3532, 2011 (San Francisco, CA, USA).
Full text (pdf) - Presentation pitch (ppt)

Also published as:
Multi-Layered Navigation Meshes
Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts
In ICT.OPEN 2011, ASCI track (Veldhoven, The Netherlands).
Received the Best Paper Award of ASCI 2011.
Full text (pdf) - Presentation (ppt)


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.

BibTeX citation

    author = {van Toll, W.G. and {Cook IV}, A.F. and Geraerts, R.},
    title = {Navigation Meshes for Realistic Multi-Layered Environments},
    booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
    year = {2011},
    pages = {3526--3532}

More information

Additional information can be found on the research page of Roland Geraerts.