3 Out-of-core Multiresolution Terrain Modeling
45
is supported through a compressed pyramid of images that can be handled in main
memory. Fast decompression algorithms and an effective use of a graphics processing unit (GPU) allow traversing the pyramid, by extracting data at the appropriate
resolution, and rendering them on the fly.
In most cases, however, multiresolution models require use of adaptive representations in the form of TINs, even when full-resolution data come in the form of a
DEM. For this reason, we consider here techniques that process and produce TINs
at all intermediate levels of resolution. If a DEM at high resolution is given as input,
most of the techniques developed in the literature consider a TIN built as follows.
The DEM is interpreted as a regular grid where elevation values are attached to the
vertices (usually placed at the center of pixels) and each rectangular cell is subdivided
into two triangles through one diagonal. This model carries the same information as
the DEM but is fully compatible with the structure of a TIN. Lower resolution models are TINs obtained adaptively from the full-resolution model through some terrain
simplification procedure, as described in the following section.
3.3 Out-of-core Terrain Simplification
Dealing with huge amounts of data is often a difficult challenge. An obvious
workaround is to reduce the data set to a more manageable size. Simplification algorithms take a terrain model as input and produce a simplified version of it, which provides a coarser (approximated) representation of the same terrain, based on a smaller
data set.
Many simplification algorithms have been proposed in the literature (see, e.g. [16]
for a survey of specific methods for terrain, and [32] for a survey of more general
methods for polygonal 3D models). Most methods are based on the iterated or simultaneous application of local operators that simplify small portions of the mesh by
reducing the number of vertices. Most popular techniques are based on the following:
• Clustering. A group of vertices that lie close in space, and the submesh that they
define, are collapsed to a single vertex, and the portion of mesh surrounding it is
warped accordingly.
• Vertex decimation. A vertex is eliminated, together with all its incident triangles,
and the hole is filled by a new set of triangles.
• Edge collapse. An edge is contracted so that its two vertices collapse to a single
point (which may be either one of them or a point at a new position computed
to reduce approximation error), and its two incident triangles collapse to edges
incident at that point; the portion of mesh surrounding such two triangles is
warped accordingly.
Classical techniques require that the model is completely loaded in main memory. For this reason, such techniques cannot be applied to huge data sets directly.
Simplification of huge meshes requires a technique that is able to load and process
at each step a subset of the data that can fit in main memory. Existing out-of-core
45
is supported through a compressed pyramid of images that can be handled in main
memory. Fast decompression algorithms and an effective use of a graphics processing unit (GPU) allow traversing the pyramid, by extracting data at the appropriate
resolution, and rendering them on the fly.
In most cases, however, multiresolution models require use of adaptive representations in the form of TINs, even when full-resolution data come in the form of a
DEM. For this reason, we consider here techniques that process and produce TINs
at all intermediate levels of resolution. If a DEM at high resolution is given as input,
most of the techniques developed in the literature consider a TIN built as follows.
The DEM is interpreted as a regular grid where elevation values are attached to the
vertices (usually placed at the center of pixels) and each rectangular cell is subdivided
into two triangles through one diagonal. This model carries the same information as
the DEM but is fully compatible with the structure of a TIN. Lower resolution models are TINs obtained adaptively from the full-resolution model through some terrain
simplification procedure, as described in the following section.
3.3 Out-of-core Terrain Simplification
Dealing with huge amounts of data is often a difficult challenge. An obvious
workaround is to reduce the data set to a more manageable size. Simplification algorithms take a terrain model as input and produce a simplified version of it, which provides a coarser (approximated) representation of the same terrain, based on a smaller
data set.
Many simplification algorithms have been proposed in the literature (see, e.g. [16]
for a survey of specific methods for terrain, and [32] for a survey of more general
methods for polygonal 3D models). Most methods are based on the iterated or simultaneous application of local operators that simplify small portions of the mesh by
reducing the number of vertices. Most popular techniques are based on the following:
• Clustering. A group of vertices that lie close in space, and the submesh that they
define, are collapsed to a single vertex, and the portion of mesh surrounding it is
warped accordingly.
• Vertex decimation. A vertex is eliminated, together with all its incident triangles,
and the hole is filled by a new set of triangles.
• Edge collapse. An edge is contracted so that its two vertices collapse to a single
point (which may be either one of them or a point at a new position computed
to reduce approximation error), and its two incident triangles collapse to edges
incident at that point; the portion of mesh surrounding such two triangles is
warped accordingly.
Classical techniques require that the model is completely loaded in main memory. For this reason, such techniques cannot be applied to huge data sets directly.
Simplification of huge meshes requires a technique that is able to load and process
at each step a subset of the data that can fit in main memory. Existing out-of-core