UCT CS Research Document Archive

A Low Dimensional Framework for Exact Polygon-to-Polygon Occlusion Queries

Haumont, Denis, Otso Makinen and Shaun Nirenstein (2005) A Low Dimensional Framework for Exact Polygon-to-Polygon Occlusion Queries. In Bala, Kavita and Philip Dutre, Eds. Proceedings Eurographics Symposium on Rendering, pages 110-120, Konstanz, Germany.

Full text available as:
PDF - Requires Adobe Acrobat Reader or other PDF viewer.


Despite the importance of from-region visibility computation in computer graphics, efficient analytic methods are still lacking in the general 3D case. Recently, different algorithms have appeared that maintain occlusion as a complex of polytopes in Plücker space. However, they suffer from high implementation complexity, as well as high computational and memory costs, limiting their usefulness in practice. In this paper, we present a new algorithm that simplifies implementation and computation by operating only on the skeletons of the polyhedra instead of the multi-dimensional face lattice usually used for exact occlusion queries in 3D. This algorithm is sensitive to complexity of the silhouette of each occluding object, rather than the entire polygonal mesh of each object. An intelligent feedback mechanism is presented that greatly enhances early termination by searching for apertures between query polygons. We demonstrate that our technique is several times faster than the state of the art.

EPrint Type:Conference Paper
Keywords:Exact, From-Region, Visibility, Culling, Occlusion, Plucker Space
Subjects:I Computing Methodologies: I.3 COMPUTER GRAPHICS
G Mathematics of Computing: G.4 MATHEMATICAL SOFTWARE
ID Code:207
Deposited By:Nirenstein, Shaun
Deposited On:22 June 2005
Alternative Locations:http://www.ulb.ac.be/polytech/sln/team/dhaumont/exact.htm, http://people.cs.uct.ac.za/~snirenst/cv.html