A GPU Based Method for the Automatic Generation of Near-Optimal Navigation Meshes
No Thumbnail Available
Date
2012
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
In this paper we present a novel, robust and efficient GPU based technique to automatically generate a Navigation Mesh for complex 3D scenes. Our method consists of two steps: firstly, starting with a 3D scene representing a complex environment of one floor with slopes, steps, and other obstacles, it automatically generates a 2D representation based on a single polygon (floor) with holes (obstacles).This step can handle degeneracies of the starting 3D scene model, such as interpenetrating geometry. Secondly, a novel method that exploits the GPU efficiency is used to automatically generate a near-optimal convex decomposition which will represent the cell and portal graph of the environment. Such convex decomposition is a 2D representation of the walkable areas of the environment with portals indicating the crossing borders. The results show that the presented technique not only is more robust than previous CPU methods, but also for the tested environments with up to 1000 vertices, it performs five times faster.
Description
@inproceedings{10.2312:LocalChapterEvents/CEIG/CEIG12/049-056,
booktitle = {Spanish Computer Graphics Conference},
editor = {Isabel Navazo and Gustavo Patow},
title = {{A GPU Based Method for the Automatic Generation of Near-Optimal Navigation Meshes}},
author = {Oliva, Ramon and Pelechano, Nuria},
year = {2012},
publisher = {The Eurographics Association},
ISBN = {978-3-905673-92-0},
DOI = {10.2312/LocalChapterEvents/CEIG/CEIG12/049-056}
}