Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation
maximize

Hierarchical Terrain Representation

Description

Multiresolution digital elevation models are getting more and more importance for a scale-sensitive modelling of elevation data. In principle, they allow the representation of the data at a variety of scales. Of special concern are adaptive methods, where the resolution does not to be uniform but may be variable.

Adaptivity is very important for error measurement and control. In general, equal distribution of points (or, for that matter, triangles) does not imply equal distribution of error. The error is usually measured by some norm. Popular examples are the L2-norm, which is the squared integral of the difference between the original or the approximation, or the maximum norm, which is the maximum difference. Applying adaptive refinement, the approximation error can be controlled and distributed as uniformly as possible for a given error norm.

However, some types of error cannot (or cannot easily) reflected by some norm. For example, in hydrological modelling and simulation, changes in the topology of the DEM may yield surprising and unwanted effects. Small changes in elevation values can lead to large changes in catchment size and structure. Luckily, adaptive refinement can control possible changes in topology as well. The necessary computation involves the determination and quantification of critical points (i.e. local minima, maxima and saddles).

We have developed a tool which allows a fast multiresolution construction of very large digital elevation models with error control and preservation of topology. Some examples are given below.

Examples

If below pictures appear scrambled, please increase the width of your web browser. Click on the pictures to see an enlarged version.

Above we show successive approximations of a digital terrain model of the North Sea area. The approximations are based on the L1 norm. From right to left, the error threshold increases. Although the approximations are quite satisfying for mountainous areas, coastlines are not preserved very well. In the Netherlands, for example, land is quite flat leading to a small approximation error. Note that the land/sea topology is also not preserved at all (e.g. in Northern Germany and Denmark).

Here we put a special constraint on coastlines forcing the error to be smaller in these areas. The resulting terrain models are still continous, though (the corresponding triangulations do not contain so-called hanging vertices). The numbers of triangles are comparable to the previous case, however, here coastlines are preserved much better and topological problems are less severe.

These images show adaptive grids for different error thresholds and corresponding DEMs of a crater lake (Laacher See) in western Germany. Note that in the leftmost image the lake in the foreground gets an opening at its upper border which would be disastrous for hydrological simulations.

Here we show the corresponding images with topology preservation. Note that the numbers of triangles is again not much higher than in the previous examples. Here, all isolines retain their original topological structure (not only the isoline surrounding the crater lake). This implies that the connectivity and number of components of the isolines are identical to the original fine-resolution elevation model. Their exact geometric position does not have to be preserved. The geometrical error of the isolines can controlled by a gradient-type norm.

References

Related projects


Thomas Gerstner