Variable Resolution Triangulations
E. Puppo
Abstract
A comprehensive study of multiresolution decompositions of planar domains
into triangles is given.
A general model is introduced, called a
Multi-Triangulation (MT), which is based on a collection of fragments
of triangulations arranged into a directed acyclic graph.
Different decompositions of a domain
can be obtained by combining different fragments of the model.
Theoretical results on the expressive power of the MT are given.
An efficient algorithm is proposed that can extract a triangulation
from the MT, whose level of detail is variable over the
domain according to a given threshold function. The algorithm works in
linear time, and the extracted representation has minimum size among all
possible triangulations that can be built from triangles
in the MT, and that satisfy the given level of detail.
Major applications of these results are in real-time rendering of
complex surfaces, such as topographic surfaces in flight simulation.
|