ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
366 
indicates whether the algorithm is topology-tolerant, that is, 
whether the presence of non-manifold mesh regions will 
catastrophically affect the algorithm. An asterix (*) under 
fidelity-based or polygon-budget simplification indicates that 
the algorithm can be easily extended to support that use of the 
error metric, even though the algorithm’s original publication 
does not mention it. 
Tablel The feature of Simplification Algorithms[Luebke,97] 
Algorithm 
Reference 
Mechanism 
Use of 
Error Metric 
Topology 
Style 
Sampling 
Adaptive 
Subdivision 
Decimation 
Vertex 
Merging 
Fidelity-base 
d 
Polygon 
Budget 
Preserving 
Modifying 
Tolerant 
View-depen 
dent 
View-lndepe 
ndent 
Multi-Resolution 3D 
Approximation 
Rossignac 92 
V 
★ 
V 
Decimation of Triangle 
Mesh 
Schroeder 92 
V 
V 
* 
V 
V 
V 
Re-tiling Polygonal 
Surface 
Turk 92 
V 
V 
V 
V 
V 
Mesh Optimization 
Hoppe 93 
V 
V 
V 
V 
V 
Multiresolution Analysis of 
Arbitrary Meshes 
Eck 95 
V 
V 
V 
Voxel-Based Object 
Simplification 
He 95 
V 
V 
V 
Simplification Envelopes 
Cohen 96 
V 
V 
Pregressive Meshes 
Hoppe 96 
V 
V 
V 
Model Simplification Using 
Vertex Clustering 
Low 97 
V 
V 
V 
V 
View-Dependent 
Refinement of 
Progressive Meshes 
Hoppe 97 
V 
V 
V 
V 
V 
Progressive Simplicial 
Complexes 
Popovic 97 
V 
V 
V 
V 
V 
Surface Simplification 
Using Quadric Error 
Metrics 
Garland 97 
V 
V 
V 
V 
V 
Dynamic View-Dependent 
Simplification 
Xia 96 
V 
V 
V 
V 
Hierarchical Dynamic 
Simplification 
Luebke 97 
V 
V 
V 
V 
V 
V 
Note: An asterix means that the algorithm could easily be extended to include the specified use of error metric. 
3. MULTIRESOLUTION TERRAIN MODEL THEORY 
3.1. Hierarchical tin model (htin) [leila de floriant, 97 ] 
A terrain is a surface in three dimensions, which can be 
characterized as the graph G of a continuous bivariate function 
z=f(x,y), defined over a compact and connected subset D of 
the xy-plane: 
G={(x, y, f(x,y)) | (x,y)e D} 
Set D is called the domain of the terrain. In practice, a terrain 
G is known at a finite set s cG of data points. Based on 
such points, DEMs are built. A DEM consists of a plane 
subdivision £ , with vertices at the projections of the data 
points, and a family of functions which f locally, on each region 
of X ■ An approximation terrain model is a model that does not 
interpolate all data available, but only a subset. An 
approximation error is associated with each triangle ti of a TIN 
D. Such error is defined as the maximum approximation error 
measured at those points of S-R whose vertical projection lies 
inside or on he boundary of t 
Err(ti)=max{Err(P) | P=(x,y,x)e S-R | (x,y)s tj 
HTIN organize several TINs at different levels of resolution in a 
compact structure. Let e 0 . e R<zS e h be a 
predefined decreasing sequence of tolerances on the 
approximation error( e ¡>e l+1 for all 0<i<h). A constructive idea 
of an HTIN is the following: starting from an initial coarse TIN 
Do, whose approximation error is withine 0 , any triangle tj of D 0 , 
with Err(tj)>=e iis separately refined into a local TIN Dj, whose 
domain covers tj, and such that Err(Dj)<= e 1; the process is 
recursively iterated on the triangles of Dj, until the finest 
resolution levels h is reached. 
In HTIN, how to guarantee the consistency of edge or 
boundary is a keypoint for constructive HTIN. [Leila de Foriant 
and Paola Magillo,97] give us follow suggestion. 
An HTIN is consistent if, for each pair of adjacent triangles t 
and tj of H, sharing an edge e, one of the following conditions 
holds: 
Rule 1: The death errors oft and t are equal, and both t and tj 
are simple triangles (i.e., tand tare both unrefined); 
Rule 2: The death errors of t and t are equal, both t and t are 
macro-triangles, (i.e., t and t are refined at the same step), 
and the direct expansions of t and tj insert the same vertices 
on edge e;