Large multi-resolution terrain data sets are usually stored
out-of-core. To visualize terrain data at interactive frame rates,
the data needs to be organized on disk, loaded into main memory
part by part, then rendered efficiently. Many main-memory
algorithms have been proposed for efficient vertex selection and
mesh construction. Organization of terrain data on disk is quite
difficult because the error, the triangulation dependency and the
spatial location of each vertex all need to be considered.
Previous terrain clustering algorithms did not consider the
per-vertex approximation error of individual terrain data sets.
Therefore, the vertex sequences on disk are exactly the same for
any terrain. In this paper, we propose a novel clustering
algorithm which introduces the level-of-detail (LOD) information
to terrain data organization to map multi-resolution terrain data
to external memory. In our approach the LOD parameters of the
terrain elevation points are reflected during clustering. The
experiments show that dynamic loading and paging of terrain data
at varying LOD is very efficient and minimizes page faults.
Additionally, the preprocessing of this algorithm is very fast and
works from out-of-core.