Efficient real-time visibility testing

Sammanfattning: Visibility testing is an integral part of many computer graphics algorithms. For example, algorithms that generate images with shadows, ambient occlusion, environment lighting or transparency all require an efficient means of establishing the visibility between two or more points in a virtual scene. Algorithms designed for interactive applications, in particular, require these queries to be very fast and highly parallelizable. This thesis is based on six papers that present a number of novel algorithms which perform efficient visibility testing in virtual scenes in order to generate high quality images at interactive frame rates. The two most famous algorithms for shadows are shadow maps and shadow volumes. Shadow maps can only approximate the result, while shadow volumes are typically fill-rate limited due to huge overdraw. The first paper in this thesis modifies the shadow map algorithm to be exact per view sample and extends it to handle area or volumetric light sources. The second paper shows how to overcome the overdraw problems inherent in the shadow volume algorithm and extends it to support textured and transparent shadow casters in real time for complex geometry with no restrictions on topology. The three papers that follow focus on rendering of transparent geometry with shadows. The first of these describes a method for approximately sorting primitives to improve the speed at which alpha blending and opacity mapping can be used to render hair. Then, a method is described with which visibility functions can be generated and stored efficiently in a fixed size texture. We show how the equations for alpha blending transparent geometry can be expressed in such a way that the order in which the terms are accumulated is not important (given that the visibility between two points on a view ray can be established). Finally, we present an algorithm that provides a unified approach to estimate order independent transparency, transparent shadows and antialiasing. The final paper considers shadows in participating media and suggests a very simple to implement algorithm which can generate images with single-scattering and volumetric shadows at very high frame rates.