Hierarchical triangulation for multiresolution surface description
Authors:
Open Access
- 1 October 1995
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 14 (4) , 363-411
Abstract
A new hierarchical triangle-based model for representing surfaces over sampled data is proposed, which is based on the subdivision of the surface domain into nested triangulations, called a hierarchical triangulation (HT) . The model allows compression of spatial data and representation of a surface at successively finer degrees of resolution. An HT is a collection of triangulations organized in a tree, where each node, except for the root, is a triangulation refining a face belonging to its parent in the hierarchy. We present a topological model for representing an HT, and algorithms for its construction and for the extraction of a triangulation at a given degree of resolution. The surface model, called a hierarchical triangulated surface (HTS) is obtained by associating data values with the vertices of triangles, and by defining suitable functions that describe the surface over each triangular patch. We consider an application of a piecewise-linear version of the HTS to interpolate topographical data, and we describe a specialized version of the construction algorithm that builds an HTS for a terrain starting from a high-resolution rectangular grid of sampled data. Finally, we present an algorithm for extracting representations of terrain at variable resolution over the domain.Keywords
This publication has 27 references indexed in Scilit:
- Horizon computation on a hierarchical triangulated terrain modelThe Visual Computer, 1995
- Computing optimal triangulations using simulated annealingComputer Aided Geometric Design, 1993
- An implementation of triangular B-spline surfaces over arbitrary triangulationsComputer Aided Geometric Design, 1993
- Hierarchical triangulation using cartographic coherenceCVGIP: Graphical Models and Image Processing, 1992
- A hierarchical spatial data structure for global geographic information systemsCVGIP: Graphical Models and Image Processing, 1992
- Comparison of existing methods for building triangular irregular network, models of terrain from grid digital elevation modelsInternational Journal of Geographical Information Science, 1991
- Minimal roughness property of the Delaunay triangulationComputer Aided Geometric Design, 1990
- Modified multiquadric methods for scattered data interpolation over a sphereComputer Aided Geometric Design, 1990
- Triangular Bernstein-Bézier patchesComputer Aided Geometric Design, 1986
- A hierarchical structure for surface approximationComputers & Graphics, 1984