A comparative study of navigation meshes


Autoria(s): Van Toll, Wouter; Triesscheijn, Roy; Kallmann, Marcelo; Oliva, Ramon; Pelechano, Nuria; Pettré, Julien; Geraerts, Roland
Contribuinte(s)

Utrecht University [Utrecht]

University of California, Merced (UCMerced) ; University of California, Merced

Universitat Politècnica de Catalunya [Barcelona] (UPC)

Visual servoing in robotics, computer vision, and augmented reality (Lagadic) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria) - Institut National de Recherche en Informatique et en Automatique (Inria) - Inria Rennes – Bretagne Atlantique ; Institut National de Recherche en Informatique et en Automatique (Inria) - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5) ; Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) ; Institut National des Sciences Appliquées (INSA) - Université de Rennes 1 (UR1) - Institut National de Recherche en Informatique et en Automatique (Inria) - Centre National de la Recherche Scientifique (CNRS) - Télécom Bretagne - École normale supérieure - Rennes (ENS Rennes) - CentraleSupélec - Université de Bretagne Sud (UBS) - Institut National des Sciences Appliquées (INSA) - Université de Rennes 1 (UR1) - Institut National de Recherche en Informatique et en Automatique (Inria) - Centre National de la Recherche Scientifique (CNRS) - Télécom Bretagne - École normale supérieure - Rennes (ENS Rennes) - CentraleSupélec - Université de Bretagne Sud (UBS) - Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) ; Institut National des Sciences Appliquées (INSA) - Université de Rennes 1 (UR1) - Institut National de Recherche en Informatique et en Automatique (Inria) - Centre National de la Recherche Scientifique (CNRS) - Télécom Bretagne - École normale supérieure - Rennes (ENS Rennes) - CentraleSupélec - Université de Bretagne Sud (UBS) - Institut National des Sciences Appliquées (INSA) - Université de Rennes 1 (UR1) - Centre National de la Recherche Scientifique (CNRS) - Télécom Bretagne - École normale supérieure - Rennes (ENS Rennes) - CentraleSupélec - Université de Bretagne Sud (UBS)

Cobertura

San Francisco, United States

Data(s)

10/10/2016

Resumo

International audience

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 conduct the first comparative study of 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. Finally, we use these metrics to compare various state-of-the-art navigation meshes in a range of 2D and 3D environments. 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 on navigation meshes in interesting directions.

Identificador

hal-01392267

https://hal.inria.fr/hal-01392267

https://hal.inria.fr/hal-01392267/document

https://hal.inria.fr/hal-01392267/file/comparative_study_of_navigation_meshes_main.pdf

DOI : 10.1145/2994258.2994262

Idioma(s)

en

Publicador

HAL CCSD

ACM

Relação

info:eu-repo/semantics/altIdentifier/doi/10.1145/2994258.2994262

Fonte

MIG '16 - 9th International Conference on Motion in Games

https://hal.inria.fr/hal-01392267

MIG '16 - 9th International Conference on Motion in Games , Oct 2016, San Francisco, United States. ACM, pp.91 - 100, 2016, <http://mig2016.inria.fr/>. <10.1145/2994258.2994262>

http://mig2016.inria.fr/

Palavras-Chave #navigation meshes #path planning #comparative study Concepts: •Computing methodologies → Mesh geometry mod- els #Motion path planning #General and reference → Metrics #Evaluation #[INFO.INFO-GR] Computer Science [cs]/Graphics [cs.GR]
Tipo

info:eu-repo/semantics/conferenceObject

Conference papers