Real-Time GPU Algorithms: Parallel Primitives and Rendering of Participating Media

Sammanfattning: Modern graphics processing units, GPUs, present an immense resource of computational power, that however remains challenging to fully harness. This thesis explores four algorithms and methods that attempt to take full advantage of the resources provided by a GPU. The algorithms focus on efficient implementations that perform well enough to be considered for real-time applications. Two of the papers focus on using GPUs to accelerate general purpose algorithms by leveraging general purpose GPU, GPGPU, techniques. First, general purpose parallel primitives such as parallel stream compaction, reduction, prefix sums and sorting are presented. The second paper applies these techniques to efficiently build a two-level hierarchical grid from scene geometry. The two-level grid is then used to accelerate ray tracing. While ray tracing is related to computer graphics, it is outside of the traditional scope of GPUs, which are built to mainly accelerate rasterized graphics. In the third paper, the rasterization specific parts of a modern GPU are leveraged to render shafts of light and other effects that single scattering of light in a participating medium gives rise to. The method presented in the third paper relies on shadow maps to generate polygonal geometry enclosing space that is directly illuminated by a light source. It is inside this geometry that single scattering takes place. The final paper explores the combination of GPGPU techniques with traditional graphics operations. The method augments the single scattering algorithms presented in the third paper with support for multiple scattering and indirect illumination of geometry by light scattered in the participating medium. It uses light propagation volumes, LPVs, which are efficiently implemented using GPGPU programming techniques to propagate light using a modified propagation scheme that accounts for scattering in the medium.