@article {17977, title = {Generating levels of detail for large-scale polygonal models}, volume = {CS-1995-20}, year = {1995}, month = {1995///}, institution = {Department of Computer Science, Duke University, North Carolina}, abstract = {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. }, author = {Varshney, Amitabh and Agarwal,P. K and Brooks Jr,F. P and Wright,W. V and Weber,H.} }