Visibility preprocessing for interactive walkthroughs
Seth J. Teller, Carlo H. Séquin · ACM SIGGRAPH Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH) · 1991
The number of polygons comprising interesting architectural models is many more than can be rendered at interactive frame rates. However, due to occlusion by opaque surfaces (e.g., walls), only a small fraction of a typical model is visible from most viewpoints.We describe a method of visibility preprocessing that is efficient and effective for axis-aligned or axial architectural models. A model is subdivided into rectangular cells whose boundaries coincide with major opaque surfaces. Non-opaque portals are identified on cell boundaries, and used to form an adjacency graph connecting the cells of the subdivision. Next, the cell-to-cell visibility is computed for each cell of the subdivision, by linking pairs of cells between which unobstructed sightlines exist.During an interactive walkthrough phase, an observer with a known position and view cone moves through the model. At each frame, the cell containing the observer is identified, and the contents of potentially visible cells are retrieved from storage. The set of potentially visible cells is further reduced by culling it against the observer's view cone, producing the eye-to-cell visibility. The contents of the remaining visible cells are then sent to a graphics pipeline for hidden-surface removal and rendering.Tests on moderately complex 2-D and 3-D axial models reveal substantially reduced rendering loads.
Cited by 401 works. doi:10.1145/122718.122725
Authors
References
- Multidimensional binary search trees used for associative searching
- Computational Geometry--An Introduction.
- Art gallery theorems and algorithms
- Shadow algorithms for computer graphics
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- On visible surface generation by a priori tree structures
- Space subdivision for fast ray tracing
- Towards image realism with interactive update rates in complex virtual building environments
- On visible surface generation by a priori tree structures
- An algorithm for constructing the aspect graph