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