365 
ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS", Bangkok, May 23-25, 2001 
2.1. Mechanism of Polygon Elision 
Nearly every simplification technique in the literature uses 
some variation or combination of four basic polygon elision 
mechanisms: sampling, adaptive subdivision, decimation, and 
vertex merging. 
Sampling schemes begin by sampling the geometry of the 
initial model. These samples can be points on the 2-D manifold 
surfaces in the model or voxels in a 3-D grid superimposed 
upon the model. The algorithm then tries to create a polygonal 
simplification that closely matches the sampled data. Varying 
the number of samples regulates the accuracy of the created 
simplification. 
Adaptive subdivision approaches create a very simple 
polygonal approximation called the base model. The base 
model consists of triangles or squares, shapes that lend 
themselves to recursive subdivision. This process of 
subdivision is applied until the resulting surface lies within 
some user-specified threshold of the original surface. 
Conceptually simple, adaptive subdivision methods suffer two 
disadvantages. First, creating the base model involves the 
very problem of polygonal simplification that the algorithm is 
attempting to solve. For this reason adaptive subdivision 
approaches have been more popular for the specialized case 
of terrains, whose base model is typically just a rectangle. 
Second, a recursive subdivision of the base model may not be 
able to capture the exact geometry of the original model, 
especially around sharp comers and creases in the mesh 
[Hoppe 96]. 
Decimation techniques iteratively remove vertices or faces 
from the mesh, retriangulating the resulting hole after each 
step. This process continues until it reaches a user-specified 
degree of simplification. If decimation algorithms do not permit 
a vertex or face removal that will change the local topology of 
the mesh, the decimation process may be unable to effect high 
degrees of simplification. 
Vertex merging schemes operate by merging two or more 
vertices of a triangulated model together into a single vertex, 
which can in turn be merged with other vertices. Merging two 
corners of a triangle makes that triangle degenerate. Such 
triangles can then be eliminated, decreasing the total polygon 
count. Vertex merging approaches do not necessarily require 
manifold topology, though some algorithms use a limited 
vertex merge called an edge collapse, in which only the two 
vertices sharing an edge are collapsed in each operation. 
These algorithms generally assume manifold topology 
implicitly. 
2.2. Use of Error Metric 
Simplification methods can be characterized by how they use 
an error metric to regulate the quality of the simplification. A 
surprising number of algorithms use no metric at all, but simply 
require the user to run the algorithm with different settings and 
explicitly select appropriate LOD switching distances. For large 
databases, however, this degree of user intervention is simply 
not practical. Those algorithms that utilize an error metric to 
guide simplification fall into two categories: 
Fidelity-based simplification techniques allow the user to 
specify the desired fidelity of the simplification in some form, 
then attempt to minimize the number of polygons, subject to 
that fidelity constraint. 
Polygon-budget simplification systems attempt to maximize the 
fidelity of the simplified model without exceeding a specified 
polygon budget. For example, adaptive subdivision algorithms 
lend themselves nicely to fidelity-based simplification, simply 
subdividing the base model until the fidelity requirement is met. 
Polygon-budget simplification is a natural fit for decimation 
techniques, which are designed to remove vertices or faces 
one at a time and merely need to halt upon reaching the target 
number of polygons. As mentioned above, however, topology 
constraints often prevent decimation algorithms from reducing 
the polygon count below a certain level. To be most useful, a 
simplification algorithm should be capable of either 
fidelity-based or polygon-budget operation. Fidelity-based 
approaches are crucial for generating accurate images, 
whereas polygon-budget approaches are important for 
time-critical rendering. The user may well require both of these 
possibilities in the same system. 
2.3. Preservation of Topology 
In the context of polygonal simplification, topology refers to the 
structure of the connected polygonal mesh. The local topology 
of a face, edge, or vertex refers to the connectivity of that 
feature’s immediate neighborhood. The mesh forms a 2-D 
manifold if the local topology is everywhere homeomorphic to 
a disc, that is, if the neighborhood of every feature consists of 
a connected ring of triangles forming a single surface. Every 
edge in a mesh displaying manifold topology is shared by 
exactly two triangles, and every triangle has exactly three 
neighboring triangles, all distinct (a 2-D manifold with boundary 
allows the local neighborhoods to be homeomorphic to a 
half-disc, which means some edges can belong to only one 
triangle). A topology-preserving simplification algorithm 
preserves manifold connectivity. Such algorithms do not close 
holes in the mesh, and they therefore preserve the genus of 
the simplified surface. Global topology refers to the 
connectivity of the entire surface. A simplification algorithm 
preserves global topology if it preserves local topology and 
does not create self-intersections within the simplified object 
[Erikson 96]. A self-intersection, as the name implies, occurs 
when two non-adjacent faces intersect each other. 
Topology-preserving algorithms preserve the genus of the 
simplified object, so no holes will appear or disappear during 
simplification. The opacity of the object seen from any distance 
thus tends to remain roughly constant. This constraint limits 
the simplification possible, however, since objects of high 
genus cannot be simplified below a certain number of 
polygons without closing holes in the model. Moreover, a 
topology-preserving approach requires a mesh with valid 
topology to begin with. Some algorithms, such as [Schroeder 
92], are topology-tolerant: they ignore regions in the mesh with 
invalid local topology, leaving those regions unsimplified. Other 
algorithms faced with such regions may simply crash. 
Topology-modifying algorithms do not necessarily preserve 
local or global topology. The algorithms can therefore close up 
holes in the model as simplification progresses, permitting 
drastic simplification beyond the scope of topology-preserving 
schemes. This drastic simplification often comes at the price of 
poor visual fidelity, however, and distracting popping artifacts 
as holes appear and disappear from one LOD to the next. 
Some topology-modifying algorithms do not require valid 
topology in the initial mesh, which greatly increases their utility 
in. real-world CAD applications. Some topology-modifying 
algorithms attempt to regulate the change in topology, but 
most are topology-insensitive, paying no heed to the initial 
mesh connectivity at all. 
2.4. Catalog of Important Papers 
The intent of this section is not to provide an exhaustive list of 
work in the field of polygonal simplification, nor to select the 
“best” published papers, but rather to briefly describe a few 
important algorithms that span the taxonomy presented above. 
Most of the papers chosen represent influential advances in 
the field; a few provide more careful treatment of existing 
ideas. 
Table 1 summarizes the catalog. Each algorithm is broken 
down according to which mechanism or combination of 
mechanisms it uses, whether it supports fidelity-based 
simplification or polygon-budget simplification, and whether the 
algorithm preserves or modifies topology. The final column