An Improved Refinement and Decimation Method for Adaptive Terrain Surface Approximation

Abstract

The development of methods for storing, manipulating, and rendering large volumes of data efficiently is a crucial task in terrain modeling. As an alternative representation to regular grid digital elevation models (DEM), we present an improved method for adaptively approximating terrain surfaces based on triangulated irregular networks (TIN). Alternate refinement and decimation steps are applied to the triangular model, incrementally determining a better distribution of the data points, while a specified error tolerance is preserved. This technique provides an effective compromise between fidelity and time requirements, producing high quality approximations with great flexibility. The method uses a Delaunay triangulation to maintain the topology of the data points, whose vertices lie at a subset of the input data. A new local error metric is used to select points from the original terrain data set, based on the maximum vertical error weighted by the standard deviation calculated in a neighborhood of the candidate point. Conversely, a measure of angle between surface normals is used to determine whether a vertex should be removed from the triangulation. Automatic procedures for construction of smooth terrain surfaces defined as a network of curved triangular patches are also investigated. The method has been implemented and tested on a number of real terrain data sets.