Fast Polygonal Approximation of Terrains and Height Fields
Michael Garland and Paul S. Heckbert
Technical Report CMU-CS-95-181
Computer Science Dept., Carnegie Mellon University
Abstract
Several algorithms for approximating terrains and other height fields
using polygonal meshes are described, compared, and optimized. These
algorithms take a height field as input, typically a rectangular grid
of elevation data H(x,y), and approximate it with a mesh of triangles,
also known as a triangulated irregular network, or TIN. The
algorithms attempt to minimize both the error and the number of
triangles in the approximation. Applications include fast rendering
of terrain data for flight simulation and fitting of surfaces to range
data in computer vision. The methods can also be used to simplify
multi-channel height fields such as textured terrains or planar color
images.
The most successful method we examine is the greedy insertion
algorithm. It begins with a simple triangulation of the domain and,
on each pass, finds the input point with highest error in the current
approximation and inserts it as a vertex in the triangulation. The
mesh is updated either with Delaunay triangulation or with
data-dependent triangulation. Most previously published variants of
this algorithm had expected time cost of O(mn) or O(n log m + m^2),
where n is the number of points in the input height field and m is the
number of vertices in the triangulation. Our optimized algorithm is
faster, with an expected cost of O((m+n)log m). On current
workstations, this allows one million point terrains to be simplified
quite accurately in less than a minute. We are releasing a C++
implementation of our algorithm.