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).
Resources:
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.
Resources:
Full text (pdf) - Presentation (ppt)

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.

Video
BibTeX citation

@inproceedings{vanToll2011-MultiLayered,
    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.