3
Out-of-core Multiresolution Terrain Modeling
Emanuele Danovaro
1,2 , Leila De Floriani
1,2 , Enrico Puppo
1 , and Hanan Samet
2
1 University of Genoa, Genoa (Italy)
2 University of Maryland, College Park (USA)
3.1 Introduction
In this chapter we discuss issues about level of detail (LOD) representations for digital terrain models and, especially, we describe how to deal with very large terrain
data sets through out-of-core techniques that explicitly manage I/O operations between levels of memory. LOD modeling in the related context of geographical maps
is discussed in Chaps. 4 and 5.
A data set describing a terrain consists of a set of elevation measurements taken
at a finite number of locations over a planar or a spherical domain. In a digital terrain
model, elevation is extended to the whole domain of interest by averaging or interpolating the available measurements. Of course, the resulting model is affected by
some approximation error, and, in general, the higher the density of the samples, the
smaller the error. The same arguments can be used for more general two-dimensional
scalar or vector fields (e.g. generated by simulation), defined over a manifold domain,
and measured through some sampling process.
Available terrain data sets are becoming larger and larger, and processing them at
their full resolution often exhibits prohibitive computational costs, even for high-end
workstations. Simplification algorithms and multiresolution models proposed in the
literature may improve efficiency, by adapting resolution on-the-fly, according to the
needs of a specific application [32]. Data at high resolution are preprocessed once to
build a multiresolution model that can be queried online by the application. The multiresolution model acts as a black box that provides simplified representations, where
resolution is focused on the region of interest and at the LOD required by the application. A simplified representation is generally affected by some approximation error
that is usually associated with either the vertices or the cells of the simplified mesh.
Since current data sets often exceed the size of the main memory, I/O operations
between levels of memory are often the bottleneck in computation. A disk access is
about one million times slower than an access to main memory. A naive management
of external memory, for example, with standard caching and virtual memory policies,
may thus highly degrade the algorithm performance. Indeed, some computations
are inherently non-local and require large numbers of I/O operations. Out-of-core
Out-of-core Multiresolution Terrain Modeling
Emanuele Danovaro
1,2 , Leila De Floriani
1,2 , Enrico Puppo
1 , and Hanan Samet
2
1 University of Genoa, Genoa (Italy)
2 University of Maryland, College Park (USA)
3.1 Introduction
In this chapter we discuss issues about level of detail (LOD) representations for digital terrain models and, especially, we describe how to deal with very large terrain
data sets through out-of-core techniques that explicitly manage I/O operations between levels of memory. LOD modeling in the related context of geographical maps
is discussed in Chaps. 4 and 5.
A data set describing a terrain consists of a set of elevation measurements taken
at a finite number of locations over a planar or a spherical domain. In a digital terrain
model, elevation is extended to the whole domain of interest by averaging or interpolating the available measurements. Of course, the resulting model is affected by
some approximation error, and, in general, the higher the density of the samples, the
smaller the error. The same arguments can be used for more general two-dimensional
scalar or vector fields (e.g. generated by simulation), defined over a manifold domain,
and measured through some sampling process.
Available terrain data sets are becoming larger and larger, and processing them at
their full resolution often exhibits prohibitive computational costs, even for high-end
workstations. Simplification algorithms and multiresolution models proposed in the
literature may improve efficiency, by adapting resolution on-the-fly, according to the
needs of a specific application [32]. Data at high resolution are preprocessed once to
build a multiresolution model that can be queried online by the application. The multiresolution model acts as a black box that provides simplified representations, where
resolution is focused on the region of interest and at the LOD required by the application. A simplified representation is generally affected by some approximation error
that is usually associated with either the vertices or the cells of the simplified mesh.
Since current data sets often exceed the size of the main memory, I/O operations
between levels of memory are often the bottleneck in computation. A disk access is
about one million times slower than an access to main memory. A naive management
of external memory, for example, with standard caching and virtual memory policies,
may thus highly degrade the algorithm performance. Indeed, some computations
are inherently non-local and require large numbers of I/O operations. Out-of-core