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.
Resources:
Full text (pdf) - Presentation pitch (ppt)
Also presented at a national conference:
Multi-Layered Navigation Meshes
Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts
In ICT.OPEN 2011, ASCI track.
Received the Best Paper Award of ASCI 2011.
Resources:
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.
@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}
}
Additional information can be found on the research page of Roland Geraerts.