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

A Comparative Study of Navigation Meshes

A Comparative Study of Navigation Meshes.

We compare the following navigation Meshes: Local Clearance Triangulation, the Explicit Corridor Map, the Clearance Disk Graph, Recast, NEOGEN, and a grid.

Abstract

A navigation mesh is a representation of a 2D or 3D virtual environment that enables path planning and crowd simulation for walking characters. Various state-of-the-art navigation meshes exist, but there is no standardized way of evaluating or comparing them. Each implementation is in a different state of maturity, has been tested on different hardware, uses different example environments, and may have been designed with a different application in mind.

In this paper, we develop and use a framework for comparing navigation meshes. First, we give general definitions of 2D and 3D environments and navigation meshes. Second, we propose theoretical properties by which navigation meshes can be classified. Third, we introduce metrics by which the quality of a navigation mesh implementation can be measured objectively. Fourth, we use these properties and metrics to compare various state-of-the-art navigation meshes in a range of 2D and 3D environments. Finally, we analyze our results to identify important topics for future research on navigation meshes.

We expect that this work will set a new standard for the evaluation of navigation meshes, that it will help developers choose an appropriate navigation mesh for their application, and that it will steer future research in interesting directions.

References

  • Wouter van Toll, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré and Roland Geraerts. Comparing navigation meshes: theoretical analysis and practical metrics. Computer and Graphics, 91, pp. 52-82, 2020.

    pdf

  • Wouter van Toll, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré and Roland Geraerts. A Comparative Study of Navigation Meshes. In 9th International ACM SIGGRAPH Conference on Motion in Games, pp. 91-100, 2016 (San Francisco, USA).

    pdf pdf zip pptx

  • Wouter van Toll, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré and Roland Geraerts. A Comparative Study of Navigation Meshes. Presentation and poster in ICT.OPEN 2018, ASCI track (Amersfoort, The Netherlands). This poster has reveived the ICT.OPEN 2018 Best poster award (3rd prize).

    pdf pdf pptx

Test environments

We used the following test environment in our comparative study. Their sources (in OBJ-format) can be downloaded here.

2D test environments.

2D test environments.

The number of polygon vertices n and the physical dimensions d (in meters) are shown in brackets.

3D test environments.

3D test environments.

Each layer of an environment is shown in a different color. Connections between layers are shown in red. The number of polygon vertices n and the physical dimensions d (width × depth × height, in meters) are shown in brackets.