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 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. 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. 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.      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.