A GPU Based Method for the Automatic Generation of Near-Optimal Navigation Meshes

dc.contributor.authorOliva, Ramonen_US
dc.contributor.authorPelechano, Nuriaen_US
dc.contributor.editorIsabel Navazo and Gustavo Patowen_US
dc.date.accessioned2013-11-08T10:18:21Z
dc.date.available2013-11-08T10:18:21Z
dc.date.issued2012en_US
dc.description.abstractIn 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.en_US
dc.description.seriesinformationSpanish Computer Graphics Conferenceen_US
dc.identifier.isbn978-3-905673-92-0en_US
dc.identifier.urihttps://doi.org/10.2312/LocalChapterEvents/CEIG/CEIG12/049-056en_US
dc.publisherThe Eurographics Associationen_US
dc.subjectI.3.5 [Computational Geometry and Object Modeling]en_US
dc.subjectGeometric algorithmsen_US
dc.subjectlanguages and systemsen_US
dc.titleA GPU Based Method for the Automatic Generation of Near-Optimal Navigation Meshesen_US
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
049-056.pdf
Size:
437.48 KB
Format:
Adobe Portable Document Format
Collections