Computing visibility maps on hierarchical terrain models


Hierarchical terrain models describe a topographic surface at different levels of detail, thus providing a multiresolution representation as well as a data compression mechanism. Visibility problems on hierarchical terrain models present two aspects: visibility, related to a terrain representation at a certain resolution level, and visibility, as the required resolution changes. Here, we address the first aspect of the problem: the specific visibility problem considered consists of determining the portions of the surface of a terrain which are visible from a predefined viewpoint. In our solutions, visibility is computed through a of the multilevel structure of a hierarchical terrain model, thus avoiding a pre-computation of an explicit model representing the surface at the given resolution. We describe a hierarchical extension of two widely used approaches to visibility computation on polyhedral terrains: the method based a front-to-back traversal of the terrain, and the sweep-line method. We show how a procedure which traverses the structure of a hierarchical model can be incorporated into any algorithm working with one of these approaches without increasing its time or space complexity.

Proc. 2nd ACM Workshop on Advances in GIS