Title: Robust and Scalable Navmesh Generation with multiple levels and stairs support
Authors: Saupin, Guillaume
Roussel, Olivier
Le Garrec, Jeremie
Citation: WSCG 2013: Full Papers Proceedings: 21st International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision in cooperation with EUROGRAPHICS Association, p. 161-170.
Issue Date: 2013
Publisher: Václav Skala - UNION Agency
Document type: konferenční příspěvek
URI: http://wscg.zcu.cz/WSCG2013/!_2013-WSCG-Full-proceedings.pdf
ISBN: 978-80-86943-74-9
Keywords: generování mřížky;zjednodušení mřížky;plánování cesty
Keywords in different language: mesh generation;mesh simplification;path planning
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.
Rights: © Václav Skala - UNION Agency
Appears in Collections:WSCG 2013: Full Papers Proceedings

Files in This Item:
File Description SizeFormat 
Saupin.pdfPlný text3,16 MBAdobe PDFView/Open

Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/10606

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.