Mesh optimization using global error with . . .

This paper presents a linear running time optimization algorithm for meshes with subdivision connectivity, e.g., subdivision surfaces. The algorithm optimizes a model using a metric defined by the user. Two functionals are used to build the metric: a rate functional and a distortion (i.e. error) functional. The distortion functional defines the error function to minimize, whereas the rate functional defines the minimization constraint. The algorithm computes approximations within this metric using jointly global error and an optimal vertex selection technique inspired from optimal tree pruning algorithms used in compression. We present an update mechanism, that we name merging domain intersections (MDIs), allowing the control of global error through the optimization process at low cost. Our method has application in progres-sive model decomposition, compression, rendering, and finite element methods. We apply our method to geometry simplification and present an algorithm to compute a decomposition of a model into a multiresolution hierarchy in O(n log n) time usin