Efficient algorithms for occlusion culling and shadows
No Thumbnail Available
Doctoral thesis (article-based)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Helsinki University of Technology publications in telecommunications software and multimedia. A, 11
AbstractThe goal of this research is to develop more efficient techniques for computing the visibility and shadows in real-time rendering of three-dimensional scenes. Visibility algorithms determine what is visible from a camera, whereas shadow algorithms solve the same problem from the viewpoint of a light source. In rendering, a lot of computational resources are often spent on primitives that are not visible in the final image. One visibility algorithm for reducing the overhead is occlusion culling, which quickly discards the objects or primitives that are obstructed from the view by other primitives. A new method is presented for performing occlusion culling using silhouettes of meshes instead of triangles. Additionally, modifications are suggested to occlusion queries in order to reduce their computational overhead. The performance of currently available graphics hardware depends on the ordering of input primitives. A new technique, called delay streams, is proposed as a generic solution to order-dependent problems. The technique significantly reduces the pixel processing requirements by improving the efficiency of occlusion culling inside graphics hardware. Additionally, the memory requirements of order-independent transparency algorithms are reduced. A shadow map is a discretized representation of the scene geometry as seen by a light source. Typically the discretization causes difficult aliasing issues, such as jagged shadow boundaries and incorrect self-shadowing. A novel solution is presented for suppressing all types of aliasing artifacts by providing the correct sampling points for shadow maps, thus fully abandoning the previously used regular structures. Also, a simple technique is introduced for limiting the shadow map lookups to the pixels that get projected inside the shadow map. The fillrate problem of hardware-accelerated shadow volumes is greatly reduced with a new hierarchical rendering technique. The algorithm performs per-pixel shadow computations only at visible shadow boundaries, and uses lower resolution shadows for the parts of the screen that are guaranteed to be either fully lit or fully in shadow. The proposed techniques are expected to improve the rendering performance in most real-time applications that use 3D graphics, especially in computer games. More efficient algorithms for occlusion culling and shadows are important steps towards larger, more realistic virtual environments.
computer graphics, shadow algorithms, occlusion culling, 3D graphics hardware, order-independent transparency
- T. Aila, V. Miettinen, and P. Nordlund. 2003. Delay streams for graphics hardware. ACM Transactions on Graphics 22, number 3, pages 792-800.
- T. Aila and T. Akenine-Möller. 2004. A hierarchical shadow volume algorithm. In: Proceedings of the Eurographics Symposium on Graphics Hardware 2004, Eurographics Association, pages 15-23.
- T. Aila and V. Miettinen. 2004. dPVS: an occlusion culling system for massive dynamic environments. IEEE Computer Graphics and Applications 24, number 2, pages 86-97.
- J. Arvo and T. Aila. 2003. Optimized shadow mapping using the stencil buffer. Journal of Graphics Tools 8, number 3, pages 23-32.
- T. Aila and S. Laine. 2004. Alias-free shadow maps. In: Proceedings of the Eurographics Symposium on Rendering 2004, Eurographics Association, pages 161-166.