Homepage > Crowd simulation > List of publications > Paper

We study how we can automatically create a data structure that represents the walkable surfaces in such an environment, and how it can be updated dynamically and efficiently when it changes. We refer to this structure as a navigation mesh. This mesh enables efficient crowd simulation, which is our next topic of research. We study and develop a crowd simulation framework and its components, which ranges from global (AI) planning to local animation. We create models for realistic crowd behaviors, which includes studying how (groups of) people move and avoid collisions in such environments, based on agent profiles and semantics (such as terrain annotations).

The Medial Axis of a Multi-Layered Environment and its Application as a Navigation Mesh

A multi-layered navigation mesh.

Abstract

Path planning for walking characters in complicated virtual environments is a fundamental task in simulations and games. A navigation mesh is a data structure that allows efficient path planning. The Explicit Corridor Map (ECM) is a navigation mesh based on the medial axis. It enables path planning for disk-shaped characters of any radius.

In this paper, we formally extend the medial axis (and therefore the ECM) to 3D environments in which characters are constrained to walkable surfaces. Typical examples of such environments are multi-storey buildings, train stations, and sports stadiums. We give improved definitions of a walkable environment (WE: a description of walkable surfaces in 3D) and a multi-layered environment (MLE: a subdivision of a WE into connected layers). We define the medial axis of such environments based on projected distances on the ground plane. For an MLE with n boundary vertices and k connections, we show that the medial axis has size O(n), and we present an improved algorithm that constructs the medial axis in O(n log n log k) time.

The medial axis can be annotated with nearest-obstacle information to obtain the ECM navigation mesh. Our implementations show that the ECM can be computed efficiently for large 2D and multi-layered environments, and that it can be used to compute paths within milliseconds. This enables simulations of large virtual crowds of heterogeneous characters in real-time.

References

  • Wouter G. van Toll, Atlas F. Cook IV, Marc J. van Kreveld and Roland Geraerts. The Medial Axis of a Multi-Layered Environment and its Application as a Navigation Mesh. arXiv:1701.05141v2 (submitted to a journal), 26 July 2017.

    Full text
  • Wouter G. van Toll, Atlas F. Cook IV and Roland Geraerts. Navigation Meshes for Realistic Multi-Layered Environments. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'11), pp. 3526-3532, 2011.

    Full text Full text
  • Wouter G. van Toll, Atlas F. Cook IV and Roland Geraerts. Multi-Layered Navigation Meshes. In ASCI - IPA - SIKS tracks, ICT.OPEN (ICT.OPEN 2011), pp. 317-323, 2011.
    This paper has received the best paper award ASCI 2011.

    pdf pptx

Movie

The method is demonstrated in the following movie.

Navigation Meshes for Realistic Multi-Layered Environments.

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.

Representation of a multi-layered environment.

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.

Construction of a multi-layered environment.

Results

More examples of multi-layered navigation meshes can be found on our page on crowd simulation software.

A multi-layered library, generated in 0.009s. Each layer has its own color.

A multi-layered library, generated in 0.009s (9ms).

Such a mesh also allows dynamic updates when an obstacle is inserted, deleted or moved.