Multiresolution terrain modeling using level curve information

摘要

The core of the presented multiresolution method is an algorithm for removing recursively the level curves according to some error criterion. This allows us to obtain a sequence of approximations of the terrain where the difference between two consecutive approximations is only one curve: the less “important”. In other words, the input curves are sorted in such a way that the n most relevant curves are contained in the n-th resolution level. For a given curve, the relevance criterion is the error computed using a function interpolating the remaining curves. Hence, to fully formulate the multiresolution algorithm a function interpolating the contour lines of the terrain is necessary. We note that a contour line representation has a higher density in the horizontal direction than in the vertical. To alleviate this problem, a horizontal simplification algorithm for each curve is proposed. Computational efficiency concerns arising from the size of the datasets, such as the computation of the distance from a point to a polygon (with a huge number of vertices), and the point location problem, are addressed. To obtain an efficient implementation of the proposed method, it was necessary to use adequate data structures and computational geometry algorithms, in order to solve several subproblems, for instance: the computation of the distance from a point to a polygon (with a huge amount of vertices), the simplification of the level curves and the point location problem. Finally, we show how to visualize the interpolant corresponding to the n-th resolution level.