The 3D visibility complex
Authors:
Open Access
- 1 April 2002
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 21 (2) , 176-206
Abstract
Visibility problems are central to many computer graphics applications. The most common examples include hidden-part removal for view computation, shadow boundaries, mutual visibility of objects for lighting simulation. In this paper, we present a theoretical study of 3D visibility properties for scenes of smooth convex objects. We work in the space of light rays, or more precisely, ofmaximal free segments. We group segments that "see" the same object; this defines the3D visibility complex. The boundaries of these groups of segments correspond to thevisual eventsof the scene (limits of shadows, disappearance of an object when the viewpoint is moved, etc.). We provide a worst case analysis of the complexity of the visibility complex of 3D scenes, as well as a probabilistic study under a simple assumption for "normal" scenes. We extend the visibility complex to handle temporal visibility. We give an output-sensitive construction algorithm and present applications of our approach.Keywords
This publication has 29 references indexed in Scilit:
- A VISIBILITY-BASED PURSUIT-EVASION PROBLEMInternational Journal of Computational Geometry & Applications, 1999
- Fast and accurate hierarchical radiosity using global visibilityACM Transactions on Graphics, 1999
- Casting Light on Illumination: A Computational Model and Dimensional Analysis of SourcesComputer Vision and Image Understanding, 1997
- THE VISIBILITY COMPLEXInternational Journal of Computational Geometry & Applications, 1996
- The visual hull concept for silhouette-based image understandingIEEE Transactions on Pattern Analysis and Machine Intelligence, 1994
- An Integral Geometry Based Method for Fast Form‐Factor ComputationComputer Graphics Forum, 1993
- Ray shooting on triangles in 3-spaceAlgorithmica, 1993
- The geometry of view space of opaque objects bounded by smooth surfacesArtificial Intelligence, 1990
- Computing the aspect graph for line drawings of polyhedral objectsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1990
- On the classification of views of piecewise smooth objectsImage and Vision Computing, 1987