Fast and High-Quality Visibility Determination

Sammanfattning: Computer generated imagery is vital to the entertainment industry in the production of games and films, for example. It is also increasingly important for visualization in design, architecture, engineering, and medicine, to name a few. Improvements to rendering techniques come from a combination of improved algorithms and more powerful hardware. Typically, hardware developments introduce new challenges and opportunities for algorithms that better fit the platform. Recently, these developments involve a widening gap between memory bandwidth and compute capabilities, wide SIMD units, and shared memory between CPU and GPU. The focus of this thesis is on improved algorithms for visibility queries that are used in graphics, motivated by challenges introduced by recent hardware developments. Geometry sampling lies at the core of rendering techniques, both for real-time and offline rendering, and generating images of higher quality generally involves taking more samples. Performance and quality improvements for visibility samples can thus enable higher quality rendering within a smaller time budget. This thesis presents five published papers with new solutions for visibility queries in the two major rendering paradigms in use today: rasterization and ray tracing. Two-dimensional rasterization is common in real-time graphics because of its computational efficiency. Multiple point samples are usually taken for each pixel to get high-quality images without aliasing artifacts. When rendering thin curves, many samples will typically be required to achieve acceptable quality. In this context, we propose that thin curves can be rasterized in high quality on a graphics processor using spatial line samples and curve-specific intersection tests. Further, we propose that the recent advent of shared memory between CPU and GPU can allow for MSAA computations to be offloaded to idle CPU cores. In three-dimensional rasterization, specifically rasterization with motion blur, we introduce a way to render practically noise- and alias-free images with competitive performance using semi-analytical line-based visibility queries on a multi-core CPU. Ray tracing, common in offline rendering, is a flexible rendering technique that can model how light propagates in a scene. Challenges in ray tracing include how a ray can be efficiently tested against a scene. Tests are accelerated by building a spatial hierarchy over the scene and our work in ray tracing specifically targets the process of traversing rays against a bounding volume hierarchy (BVH). The first contribution involves a flexible BVH traversal algorithm that executes without storing the traversal state in a stack, which may be beneficial in cases where storing a stack is expensive. The second contribution is an efficient algorithm for traversing large streams of rays against a BVH while making use of wide SIMD.