Hierarchy of Surface Models and Irreducible Triangulation

Given a triangulated closed surface, the problem of constructing a hierarchy of surface models of decreasing level of detail has attracted much attention in computer graphics. A hierarchy provides viewdependent refinement and facilitates the computation of parameterization. For a triangulated closed surface of n vertices and genus g, we prove that there is a constant c ? 0 such that if n ? c \Delta g, a greedy strategy can identify \Theta(n) topology-preserving edge contractions that do not interfere with each other. Further, each of them affects only a constant number of triangles. Repeatedly identifying and contracting such edges produces a topology-preserving hierarchy of O(n + g ) size and O(logn + g) depth. In practice, the genus g is very small when compared with n for large models and the selection of edges can be enhanced by measuring the error of their contractions using some known heuristics