Generating levels of detail for large-scale polygonal models

We present an e cient algorithm for generating various levels-of-detail approximations for agiven polygonal model. Our algorithm guarantees that all points of an approximation are within a
user-speci able distance from the original model and all points of the original model are within a
distance from the approximation. Each approximation attempts to minimize the total number of
polygons required to satisfy the previous constraint. We show how the problem of generating levels-
of-detail approximations reduces to the classic set partition problem. The various approximations
are guaranteed to be topologically consistent with the input polygonal model. The approximations
can be constrained by the user to preserve any desired edges of the input model. We also propose
a method to compute an estimate of the quality of the approximation generated by our algorithm
with respect to the optimal approximation satisfying the same constraints. We have implemented
our algorithm and have obtained experimental results of multiresolution hierarchy generation on over a thousand polygonal objects from a CAD model of a notional submarine.