Two GPU Algorithms for Raytracing

Srinath Ravichandran (homepage)

Raytracing has been primarily used for generating photo-realistic imagery. Once considered as an offline algorithm, raytracing has primarily become realtime or near realtime with the advancement in computer hardware power. GPU computing has enabled the general purpose usage of graphics cards which were primarily designed for for graphics rendering purposes. Raytracing could be considered as a very embarrassingly parallel process in which each pixel's contribution to the final image is computed independent of one another. The tremendous power of GPUs has been been utilized for vastly improving the performance of almost all the functions in a raytracing pipeline.

The raytracing pipeline for rendering images fundamentally consists of three phases. The first is an acceleration structure construction phase which involves creating a data structure. It provides very fast results for intersection queries for the rays traced within the scene and all the objects contained within the scene. The second is the traversal phase in which each ray is traced within the scene employing the aforementioned data structure. The final optional phase is shading in which each hit point is shaded based on a shading algorithm. The shading algorithm determines the color of the pixel of the image for which a particular ray was traversed and the shading performed for all the rays for all the pixels computes the final rendered image. In this thesis we examine two problems associated with the GPU raytracing pipeline and provide two new approaches for them.

In the first work, we develop a novel parallel algorithm for performing raytracing without constructing any explicit acceleration structure on the GPU. This decouples the long standing notion of creating and storing a separate acceleration structure followed by tracing rays through the structure. Our algorithm creates an implicit hierarchical acceleration structure and traverses the implicit structure at each phase of the algorithm in tandem. Parallel construction algorithms for acceleration structures are difficult to implement on the GPU and also have a large memory footprint to store the resulting structure. Compared to CPUs the amount of memory available to GPUs is limited and hence methods that work on very small memory footprints are of utmost importance. Our algorithm is conceptually very simple, utilizing efficient parallel GPU primitives such as sort and reduce. Further our algorithm has small memory requirements compared to methods that construct acceleration structures thereby making it a suitable candidate for the GPU. Since our method employs a traverse-while-construct method, it is particularly very useful for animated scenes in which the acceleration structure has to be created for each frame in a traditional raytracing pipeline. We implement our algorithm on a CUDA enabled machine and show that our algorithm can perform much better than the serial CPU version of the algorithm.

Our second work is targeted towards the problem in the shading phase of the raytracing pipeline. Traditional renderers employed in the production rendering are primary unidirectional path tracers which traces rays from the camera into the scene. However the path tracing algorithm has difficulty in rendering scenes with complicated lighting scenarios which provide very good aesthetic value to certain kinds of scenes. Bidirectional path tracing on the other hand traces rays from both the camera and the lights within the scene and hence able to render scenes with complicated lighting scenarios much more effectively than path tracing. Current production renderers are primarily CPU based and only a few have started to employ GPUs for the entire pipeline. Limited memory compared to CPUs was the original factor for not employing GPUs. However with current generation GPUs having much more memory than earlier generations, GPUs have been slowly adopted for path tracing based pipelines. However bidirectional path tracers that are GPU based are yet to be fully employed in a full production rendering scenario. Our work is aimed providing a solution that tries to bridge the gap that enables bidirectional path tracing to be used in the production rendering scenario which involves complex materials. We specifically provide a new connection mechanism employed in the light vertex cache - bidirectional path tracing algorithm (LVC-BDPT) for improving shading efficiency as well as a sort based pipeline for improving the runtime performance of the algorithm on the GPU. We show that we perform much better than the unoptimized version of the algorithm as well as providing much better quality for the same amount computations performed.


Year of completion:  July 2015
 Advisor :

P. J. Narayanan

Related Publications