Out-of-core multiresolution terrain modeling

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 multiresolutionmodel 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 virtualmemory 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 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. © Springer-Verlag Berlin Heidelberg 2007. All rights are reserved.