44
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
algorithms and data structures explicitly control how data are loaded and how they
are stored. Here, we review methods and models proposed in the literature for simplification and multiresolution management of huge datasets that cannot be handled
in main memory. We consider methods that are suitable to manage terrain data, some
of which have been developed for more general kinds of data (e.g. triangle meshes
describing the boundary of 3D objects).
The rest of this chapter is organized as follows. In Sect. 3.2, we introduce
the necessary background about digital terrain models, focusing our attention on
triangulated irregular networks (TINs). In Sect. 3.3, we review out-of-core techniques for simplification of triangle meshes and discuss their application to terrain
data to produce approximated representations. In Sect. 3.4, we review out-of-core
multiresolution models specific for regularly distributed data, while in Sect. 3.5, we
describe more general out-of-core multiresolution models that can manage irregularly distributed data. In Sect. 3.6, we draw some conclusions and discuss open research issues including extensions to out-of-core simplification and multiresolution
modeling of scalar fields in three and higher dimensions, to deal, for instance, with
geological data.
3.2 Digital Terrain Models
There exist two major classes of digital terrain models, namely digital elevation models (DEMs) and triangulated irregular networks (TINs).
A DEM consists of a regular tiling of a planar domain into rectangular cells,
called “pixels” with elevation values attached to pixels, that provide a piecewise
constant approximation of terrain surface. DEMs are most often defined over rectangular domains encoded just as two-dimensional arrays of elevation values, which
are easily geo-referenced by defining an origin, an orientation, and the extent of the
cells in the tiling.
A TIN consists of a subdivision of the domain into triangles (i.e. a triangle mesh).
Triangles do not overlap, and any two triangles are either disjoint or may share exactly either one vertex or one edge. Elevation samples are attached to vertices of
triangles, thus each triangle in the mesh corresponds to a triangular terrain patch interpolating measured elevation at its vertices. Linear interpolation is usually adopted
at each triangle, hence the resulting surface is piecewise-linear. More sophisticated
interpolation models can also be used without changing the underlying domain subdivision. Data structures used to encode TINs are more sophisticated and expensive
than those used for DEMs, but TINs have the advantage of being adaptive. A high
density of samples may be adopted over more irregular portions of a terrain, while
other portions that are relatively flat may be represented at the same accuracy with a
small number of samples.
Multiresolution DEMs usually consist of a collection of grids at different resolutions. Well-known multiresolution representations for DEMs are provided by region
quadtrees or pyramids [40]. One recent example in computer graphics is provided in
the work of Losasso and Hoppe [31], where fast rendering of a large area of terrain
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
algorithms and data structures explicitly control how data are loaded and how they
are stored. Here, we review methods and models proposed in the literature for simplification and multiresolution management of huge datasets that cannot be handled
in main memory. We consider methods that are suitable to manage terrain data, some
of which have been developed for more general kinds of data (e.g. triangle meshes
describing the boundary of 3D objects).
The rest of this chapter is organized as follows. In Sect. 3.2, we introduce
the necessary background about digital terrain models, focusing our attention on
triangulated irregular networks (TINs). In Sect. 3.3, we review out-of-core techniques for simplification of triangle meshes and discuss their application to terrain
data to produce approximated representations. In Sect. 3.4, we review out-of-core
multiresolution models specific for regularly distributed data, while in Sect. 3.5, we
describe more general out-of-core multiresolution models that can manage irregularly distributed data. In Sect. 3.6, we draw some conclusions and discuss open research issues including extensions to out-of-core simplification and multiresolution
modeling of scalar fields in three and higher dimensions, to deal, for instance, with
geological data.
3.2 Digital Terrain Models
There exist two major classes of digital terrain models, namely digital elevation models (DEMs) and triangulated irregular networks (TINs).
A DEM consists of a regular tiling of a planar domain into rectangular cells,
called “pixels” with elevation values attached to pixels, that provide a piecewise
constant approximation of terrain surface. DEMs are most often defined over rectangular domains encoded just as two-dimensional arrays of elevation values, which
are easily geo-referenced by defining an origin, an orientation, and the extent of the
cells in the tiling.
A TIN consists of a subdivision of the domain into triangles (i.e. a triangle mesh).
Triangles do not overlap, and any two triangles are either disjoint or may share exactly either one vertex or one edge. Elevation samples are attached to vertices of
triangles, thus each triangle in the mesh corresponds to a triangular terrain patch interpolating measured elevation at its vertices. Linear interpolation is usually adopted
at each triangle, hence the resulting surface is piecewise-linear. More sophisticated
interpolation models can also be used without changing the underlying domain subdivision. Data structures used to encode TINs are more sophisticated and expensive
than those used for DEMs, but TINs have the advantage of being adaptive. A high
density of samples may be adopted over more irregular portions of a terrain, while
other portions that are relatively flat may be represented at the same accuracy with a
small number of samples.
Multiresolution DEMs usually consist of a collection of grids at different resolutions. Well-known multiresolution representations for DEMs are provided by region
quadtrees or pyramids [40]. One recent example in computer graphics is provided in
the work of Losasso and Hoppe [31], where fast rendering of a large area of terrain