Title: Parallelization of BVH and BSP on the GPU
Other Titles: Parallelisierung von BVH und BSP auf der GPU
Language: English
Authors: Imre, Martin 
Qualification level: Diploma
Keywords: GPU; Bounding Volume Hierarchy; Binary Split Planes
Advisor: Purgathofer, Werner 
Issue Date: 2016
Number of Pages: 77
Qualification level: Diploma
Rendering is a central point in computer graphics and visualization. In order to display realistic images reflections, shadows and further realistic light diffusions is needed. To obtain these, ray tracing, view frustum culling as well as transparency sorting among others are commonly used techniques. Given the right acceleration structure, said procedures can be reduced to tree traversals, which it is often parallelized on the graphics hardware. In this thesis we focus on Bounding Volume Hierarchy (BVH) and Binary Space Partition (BSP) which are used as such acceleration structures. The problem with these structures is that their build time is often very high and the generation hardly parallelizable. The rising computational power and the highly parallel computation model of Graphics Processing Units (GPU) motivates to improve upon the parallelization of BVH and BSP algorithms. Among other algorithmic exploration during the implementation phase of this thesis, possible foundation for simplifying the general problem of BSP-Tree generation in parallel has been made. A hybrid algorithm is introduced to bypass the long construction time of BSP-Trees by reducing the problem size to a small amount. The scene is split via the usage of an uniform grid so that every cell contains only a small amount of triangles. Then a BSP-Tree is built in each of the grid-s nonempty cells in parallel. Thus transparency sorting can be done by first sorting the cells and then the small BSP-Trees. Evaluation showed that increasing the number of grid cells only leads to a decrease in build times up to a certain point. Also for sorting, the performance peaks around a grid size of 25 and decreases thereafter. The explained hybrid algorithm and its data-structure seem to theoretically overcome typical problems of the single BSP-Tree generation. However, limitations of the GPU still have a high influence on this procedure.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-91972
Library ID: AC13395604
Organisation: E186 - Institut für Computergraphik und Algorithmen 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

checked on Mar 1, 2021


checked on Mar 1, 2021

Google ScholarTM


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