Construction of multi-resolution terrain models using hierarchical Delaunay triangulated irregular networks

For land planning or visualization, we need to model a large area of digital terrain in a graphics workstation and then display the 3-D terrain model at a general frame rate. However, the geometrical complexity of terrain models is far exceeding the capabilities of a general graphics workstation. Using a multi-resolution terrain model is one way to fit the requirement of the applications. Simplification or decimation algorithms are used to generate multiple terrain models at different detailed levels and then the models are selected to display for different situations such as distance or view scope. In this study, we concentrate on the triangulation and the level-of-detail generation of terrain models. In triangulation, we improve the performance of Palacios-and-Renuad triangulation algorithm. In level-of-detail generation, we give a new criterion to improve the accuracy of sequential multi-resolution terrain models based on the Schroder-and-Robbach, Schroeder et. al., and Floriani-and-Puppo approaches. We also propose a new hierarchical structure of Delaunay triangulated models to represent multi-resolution terrain models. The hierarchical structure is a tree structure, and thus result in a better search performance than other approaches.