[Back]

M. Imre:
"Parallelization of BVH and BSP on the GPU";
Supervisor: W. Purgathofer; Institut für Computergraphik und Algorithmen, 2016; final examination: 2016-06-15.

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.

http://publik.tuwien.ac.at/files/publik_253534.pdf