Robust and scalable navmesh generation with multiple levels and stairs support - Archive ouverte HAL Access content directly
Conference Papers Year : 2013

Robust and scalable navmesh generation with multiple levels and stairs support

(1) , (2) , (1)
1
2

Abstract

Automatically planning motion for robots or humans in a virtual environment is a complex task. The navigation cannot be done directly on the geometric scene. An internal representation of the environment is necessary. However, virtual environments complexity is growing at an important rate, and it is not unusual to work with millions of triangles and area as large as some square kilometers. In these cases, grid based methods require too much memory, and are too slow for A* algorithms. Polygons based methods are more memory and computation efficient, but they are difficult to generate and require complex preprocessing of the input mesh to ensure nice topological properties. In this paper, we propose an hybrid method, which uses 3D voxelization to generate a clean polygon mesh simple enough to perform fast A* search. Using this approach, we robustly generate Navigation Meshes for large environments with fine details, described by millions of triangles, without any assumption on the quality of the input mesh. The input mesh can contains holes, degenerated or intersecting triangles.
Not file

Dates and versions

cea-01842341 , version 1 (18-07-2018)

Identifiers

  • HAL Id : cea-01842341 , version 1

Cite

Guillaume Saupin, Olivier Roussel, Jeremie Le Garrec. Robust and scalable navmesh generation with multiple levels and stairs support. 21st International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, WSCG 2013, Jun 2013, Plzen, Czech Republic. pp.161-170. ⟨cea-01842341⟩
65 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More