Parallelization of BVH and BSP on the GPU

Abstract

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.