ISPRS, Vol.34, Part 2W2, "Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
368 
corresponding to a triangle at a certain level and a triangle at 
the next level if these triangles intersect. An example of such a 
hierarchy is the Delaunay pyramid [De 89], which is obtained 
by always adding the data point with the maximal error and 
retriangulating using the Delaunay criterion. Unfortunately, the 
hierarchies of the second category also have a serious 
drawback: because they do not have a tree-like shape it 
seems di_cult to combine the triangles of different levels into 
one representation. This is illustrated in Figure 2. Left in this 
_gure is the Delaunay triangulation of a subset of the points, 
and in the middle is the Delaunay triangulation of the whole set. 
The corresponding graph structure is also shown on the right. 
The idea behind our hierarchy is the following. We start with 
the initial terrain that forms the most detailed level of the 
hierarchy. To go from one level to the next, coarser level, a 
number of non-adjacent vertices of the terrain is removed, and 
the terrain is retriangulated. (This idea was introduced by 
Kirkpatrick [Kir83].) We allow the user some control over this 
process. In particular, it is possible to _x vertices that are 
relevant for the shape of the terrain and should not be 
removed, such as pits, peaks and passes. These 'important' 
vertices can either be speci_ed explicitly by the user, or they 
can be computed using existing methods [Lee91], Which of the 
non-_xed vertices are removed to go from one level to the next, 
coarser level is decided according to different heuristic 
strategies [Ede87, CG88, Lee89]. The hierarchy and how it is 
constructed are described in Section 2. The fact that the 
vertices we remove are non-adjacent allows us to combine 
different levels into a single representation. This is done by 
selecting small groups of triangles from the levels, instead of 
individual triangles. 
The hierarchical representation is a sequence DT k ; ... ; 
DTi ; ... ;DT 0 of Delaunay triangulations at progressively finer 
levels of detail; the finest level has index 0, and the coarsest 
level the index k. It is stored as a directed acyclic graph, 
whose nodes correspond to the triangles of the Delaunay 
triangulations DT 0 up to DT k . The leaf nodes correspond to 
triangles of the initial Delaunay triangulation DT 0 . There is an 
arc from a triangle t in DT i+ i to a triangle t’ in DT if their 
interiors intersect. We call t a parent of t’, and t ‘a child of t. A 
triangle can have several parents and children. 
The bottom-up construction of the hierarchical representation 
starts with the finest level, which is the Delaunay triangulation 
DT 0 of the given set of n data points. The set of vertices \A +1 of 
the Delaunay triangulation at the next coarser level is obtained 
from Vi by removing a maximal independent subset I i of 
vertices of V that have degreeat mostd, where d is a constant 
(general d = 12). Two vertices of Vi are independent if they are 
not adjacent. The union of the triangles incident to such a 
vertex v of li forms a star-shaped polygon whose number of 
edges equals the degree of v. 
Fig.4 A two-level hierarchy 
Fig. 5a Oringinal Triangle Mesh 
Fig 5b Generating the next level by retriangulation 
But such method still has serious problem in considering the 
terrian features. Although we may fix the terrain feature points 
in above model, the more fixed points, the lower deleting 
points in hierarchical model. That is also a key issue in practice. 
This paper suggest applying based on HOOM(Hypergraph 
Objected-oriented Model)[ Jin ZHANG, 2001] 
3.3. hierarchical dynamic simplification [ Luebke,97] 
Hierarchical dynamic simplification (HDS) is dynamic, 
retessellating the scene continually as the user’s viewing 
position shifts, and global, processing the entire database 
without first decomposing the environment into individual 
objects. The resulting system enables real-time display of very 
complex polygonal models consisting of thousands of parts 
and millions of polygons. HDS supports various preprocessing 
algorithms and various run-time criteria, providing a general 
framework for dynamic view-dependent simplification. 
Briefly, HDS works by clustering vertices together in a 
hierarchical fashion. The simplification process continually 
queries this hierarchy to generate a scene containing only 
those polygons that are important from the current viewpoint. 
When the volume of space associated with a vertex cluster 
occupies less than a user-specified amount of the screen, all 
vertices within that cluster are collapsed together and