Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Towards Real-Time NavMesh Generation Using GPU Accelerated Scene Voxelization
Blekinge Institute of Technology, Faculty of Computing, Department of Creative Technologies.
Blekinge Institute of Technology, Faculty of Computing, Department of Creative Technologies.
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Context. Producing NavMeshes for pathfinding in computer games is a time-consuming process. Recast and Detour is a pair of stateof-the-art libraries that allows automation of NavMesh generation. It builds on a technique called Scene Voxelization, where triangle geometry is converted to voxels in heightfields. The algorithm is expensive in terms of execution time. A fast voxelization algorithm could be useful in real-time applications where geometry is dynamic. In recent years, voxelization implementations on the GPU have been shown to outperform CPU implementations in certain configurations.

Objectives. The objective of this thesis is to find a GPU-based alternative to Recast’s voxelization algorithm, and determine when the GPU-based solution is faster than the reference. Methods. This thesis proposes a GPU-based alternative to Recast’s voxelization algorithm, designed to be an interchangeable step in Recast’s pipeline, in a real-time application where geometry is dynamic. Experiments were conducted to show how accurately the algorithm generates heightfields, how fast the execution time is in certain con- figurations, and how the algorithm scales with different sets of input data.

Results. The proposed algorithm, when run on an AMD Radeon RX 480 GPU, was shown to be both accurate and fast in certain configurations. At low voxelfield resolutions, it outperformed the reference algorithm on typical Recast reference models. The biggest performance gain was shown when the input contained large numbers of small triangles. The algorithm performs poorly when the input data has triangles that are big in relation to the size of the voxels, and an optional optimization was presented to address this issue. Another optimization was presented that further increases performance gain when many instances of the same mesh are voxelized.

Conclusions. The objectives of the thesis were met. A fast, GPUbased algorithm for voxelization in Recast was presented, and conclusions about when it can outperform the reference algorithm were drawn. Possibilities for even greater performance gains were identified for future research.

Place, publisher, year, edition, pages
2017.
Keyword [en]
Voxelization, Recast, GPU, Pathfinding
National Category
Computer Science
Identifiers
URN: urn:nbn:se:bth-14381OAI: oai:DiVA.org:bth-14381DiVA: diva2:1104795
Subject / course
DV2524 Degree Project in Computer Science for Engineers
Educational program
PAACI Master of Science in Game and Software Engineering
Supervisors
Examiners
Available from: 2017-06-07 Created: 2017-06-01 Last updated: 2017-06-07Bibliographically approved

Open Access in DiVA

fulltext(1876 kB)58 downloads
File information
File name FULLTEXT02.pdfFile size 1876 kBChecksum SHA-512
0c3c76769e6e17f749bb7ee5dca421301500651934b744c1bc78110e67ef30807b5bf622721cc4ef2498ef1699ad391305dc54adecbac4544a731c6279026d62
Type fulltextMimetype application/pdf

By organisation
Department of Creative Technologies
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 58 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 401 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf