A comparative study of navigation meshes

Autor: van Toll, W.G., Triesscheijn, Roy, Kallmann, Marcelo, Oliva, Ramon, Pelechano, Nuria, Pettré, Julien, Geraerts, R.J., Sub Computer Graphics, Computer Graphics
Přispěvatelé: Utrecht University [Utrecht], University of California [Merced] (UC Merced), University of California (UC), 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), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), University of California [Merced], University of California, CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ViRVIG - Grup de Recerca en Visualització, Realitat Virtual i Interacció Gràfica, Sub Computer Graphics, Computer Graphics
Jazyk: angličtina
Rok vydání: 2016
Předmět:
Computer science
02 engineering and technology
computer.software_genre
Navigation meshes
Virtual reality
Three dimensional imaging
Navigation mesh
Taverne
0202 electrical engineering
electronic engineering
information engineering
comparative study Concepts: •Computing methodologies → Mesh geometry mod- els
General and reference → Metrics
Computer vision
Polygon mesh
Motion planning
Representation (mathematics)
Multituds -- Simulació per ordinador
Evaluation
path planning
comparative study
Path planning
Infografia tridimensional
Informàtica::Infografia [Àrees temàtiques de la UPC]
Realitat virtual
business.industry
Crowds -- Computer simulation
020207 software engineering
Mobile robot navigation
[INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR]
navigation meshes
Computer engineering
Motion path planning
Virtual machine
Benchmark (computing)
020201 artificial intelligence & image processing
Crowd simulation
Artificial intelligence
Comparative study
business
computer
Zdroj: MIG '16-9th International Conference on Motion in Games
MIG '16-9th International Conference on Motion in Games, Oct 2016, San Francisco, United States. pp.91-100, ⟨10.1145/2994258.2994262⟩
International ACM SIGGRAPH Conference on Motion in Games, 91. ACM
STARTPAGE=91;TITLE=International ACM SIGGRAPH Conference on Motion in Games
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
instname
MIG
DOI: 10.1145/2994258.2994262⟩
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: