A Comprehensive Framework for Spatial Operations on Hierarchical Terrain Models

Abstract

In this paper we provide an overview of the state-of-the-art about data structures and algorithms for spatial operations on hierarchical models of terrains. Hierarchical terrain models provide a multiresolution description of a topographic surface based on a nested partition of the domain; they are different from quadtree-based terrain models, which are also based on the principle of a recursive decomposition, since the decomposition in hierarchical terrains is accuracy-driven, i.e., each level of refinement in the model corresponds to a terrain approximation within a predefined error tolerance. The tree-like structure of a hierarchical terrain model provides an effective support to processing spatial operations. Spatial operations can be classified into general-purpose and application-specific operations. General-purpose operations on hierarchical terrain models correspond to basic functions, which must be supported in any environment, and include the extraction of a terrain representation at a user-defined level of resolution, and answering interference queries (e.g., point location, segment and region intersection), at a certain resolution. Application-dependent operations considered in this paper are overlay computation and visibility determination. In this paper we overview the methods for solution of the above mentioned spatial operations, within the various types of existing data structures, proposed for representing hierarchical terrain models. Some experimental results from implementations within a prototype system are reported.