ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
polygons filtered out. HDS maintains an active list of visible 
polygons for rendering. Since frame-to-frame movements 
typically involve small changes in viewpoint, and therefore 
modify this list by only a few polygons, the method takes 
advantage of temporal coherence for greater speed. 
Hierarchical dynamic simplification (HDS) is a framework for 
polygonal simplification via vertex merging. This operation, in 
which several polygon vertices are collapsed together into a 
single vertex, provides the fundamental mechanism for 
removing polygonal detail. When two vertices sharing an edge 
of a triangle are merged, that triangle becomes redundant and 
may be removed. Note the use of triangle rather than polygon. 
The constant memory requirements and guaranteed planarity 
of triangles make them preferable to generic polygons, and like 
most simplification algorithms, HDS assumes that polygonal 
models have been fully triangulated. 
As a polygonal simplification algorithm, HDS has some novel 
features. HDS is global: whereas traditional LOD algorithms 
represent the scene as a collection of objects, each at several 
levels of detail, HDS uses a single large data structure that 
constitutes the entire model. This structure is the vertex tree, a 
hierarchy of vertex merge operations that encodes a 
continuum of possible levels of detail across the whole model. 
Figure 6 shows a simple two-dimensional example model and 
its associated vertex tree. Applying a node’s vertex merge 
operation collapses all of the vertices within the node together 
to a single representative vertex. Triangles whose corners 
have been collapsed together become redundant and can be 
eliminated, decreasing the total triangle count. This is called 
folding the node. Likewise, a node may be unfolded by splitting 
its representative vertex into the node’s constituent vertices. 
Triangles filtered out when the node was collapsed become 
visible again when the node is expanded, increasing the 
triangle count. Figure 7 illustrates the result of folding and 
unfolding different nodes in the vertex tree. 
3.3.1. Constructing The Vertex Tree 
One of the simplest techniques is to classify the vertices of the 
model with a hierarchical space-partitioning structure. Recall 
the spatial binning approach introduced by Rossignac and 
Borrel, which clustered vertices according to a uniform grid 
[Rossignac 92]. The first versions of HDS used a 
straightforward extension of the Rossignac-Borrel algorithm to 
construct the vertex tree, clustering vertices in a top-down 
fashion with an octree. In this method vertices are first ranked 
by importance using local criteria such as edge length and 
curvature. The root node of the quadtree is an axis-aligned 
cube large enough to contain every vertex in the model. 
Beginning with this root node, the most important vertex within 
each node is chosen as that node’s repvert. The node is then 
divided exactly in half along the X, Y, and Z directions into 8 
cubical subnodes (hence the name “Quadtree”). The vertices 
are then partitioned among the node’s eight children and the 
process is recursively repeated for any subnode with more 
than one vertex. In this way vertices are clustered roughly 
according to proximity. Neighboring vertices are likely to get 
clustered near the leaves of the tree, whereas distant vertices 
tend to merge only at higher levels of the tree. 
For this method, its main disadvantage is that it is very 
difficulty to choice proper spatial subdivision. Another main 
problem is how to consider the terrain feature in this model. In 
fact, it is very difficulty. 
© 
© © ©i 
-©— 
— 
© © ! 
© 
1 
©tu) 
1 
1 
(12) (13) 
Quadtree 
© © © @© ©,© © © ¿A A?) d) 
^©®© © ©tB ©® 
Tight Quadtree 
© I 
© ® (|) 
-© 
© © 
(12) (13 
I ©©©@©©©®©®(ll)(l2).ffc) 
©®®©©)l©©®d ®('№)(ll) 
© 
—1 
1 
-<2r® 
-©— 
■®| 
© © 
1 • 
1 * 
© 
1 1 
1 * 
i ! ® in) 
! i-MJ 3 ) 
1 
<35 © ® © © ©0 @T@'® (Tl) (12) (T 
r*. ir*~ll ♦ I 
©(&© ©(11)1)2) (13) 
cznrmr±~ir—I 
©©© ©©© ®®@ ® (11) (12) (13) 
©! 
—I— 
-J& 
2)l 
I 
D 
D 
—in) 
(12) (3) 
©'® © ©© © © © ® '(H) (12) Q3) 
13 
d»2)fl3) 
©@© ©©© ©®® ®(11)(12)(13) 
AlJLai 
©®©©©®kz)®®© (11) (12) (¡3) 
iri"' II t 
□mnmriTi 
©@® ©©© ©®@ <®(11)(12)(13) 
“©-I 
-®—© 
© 
(D 
© 
PP 
I ®i (11 
(12) W 
©@®©©©£>©®®(11)(12)(13) 
•r~ -| rrr ri 
ËÏ, 
©@® ©©© ®©@ ®(11)(12)(13) 
Fig. 8 A 2-D example of octree vs. Tight-octree clustering.