Optimal triangulation and quadric-based surface simplification

Many algorithms for reducing the number of triangles in a surface model hav e been proposed, but to date there has been little theoretical analysis of the approximations they produce. Previously we described an algorithm that simplifies polygonal models using a quadric error metric. This method is fa st and produces high quality approximations in practice. Here we provide so me theory to explain why the algorithm works as well as it does. Using meth ods from differential geometry and approximation theory, we Show that in th e limit as triangle area goes to zero on a differentiable surface, the quad ric error is directly related to surface curvature. Also, in this limit, a triangulation that minimizes the quadric error metric achieves the optimal triangle aspect ratio in that it minimizes the L-2 geometric error. This wo rk represents a new theoretical approach for the analysis of simplification algorithms. (C) 1999 Elsevier Science B.V. All rights reserved.