Skip to Main content Skip to Navigation
Conference papers

Robust and scalable navmesh generation with multiple levels and stairs support

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Léna Le Roy Connect in order to contact the contributor
Submitted on : Wednesday, July 18, 2018 - 10:47:09 AM
Last modification on : Monday, July 4, 2022 - 10:15:57 AM


  • HAL Id : cea-01842341, version 1


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⟩



Record views