GAPS: General and Automatic Polygonal Simplification
I3D '99 Proceedings
Carl Erikson (eriksonc@cs.unc.edu), Dinesh Manocha (dm@cs.unc.edu)

We present a new approach for simplifying polygonal objects.  Our method is
general in that it accepts models that contain both non-manifold geometry and
surface attributes.  It is automatic since it requires no user input to execute
and returns approximate error bounds used to calculate switching distances
between levels of detail, or LODs.  Our algorithm, called General and Automatic
Polygonal Simplification, or GAPS for short, uses an adaptive distance
threshold and surface area preservation along with a quadric error metric to
join unconnected regions of an object.  Its name comes from this ability to
"fill in the gaps" of an object.  Our algorithm combines approximations of
geometric and surface attribute error to produce a unified object space error
metric.  GAPS can efficiently produce high quality and drastic approximations
of a wide variety of objects, including complicated pipe structures.  This
ability to perform drastic simplification allows us to create levels of detail
to accelerate the rendering of large polygonal environments, consisting of
hundreds of objects.  When viewing these models with LODs created by GAPS, we
achieve a 3.5 to 5 times average speedup with little loss in image quality.

The University of North Carolina at Chapel Hill
Department of Computer Science
CB#3175, Sitterson Hall
Chapel Hill, NC  27599-3175