The meshes produced by surface reconstruction, isosurface extraction, automatic tessellation, etc. are almost always wasteful. They’re wasteful in the sense that the vertex density and triangle shapes are often insensitive to the geometric complexity of the shape. They’re also wasteful in the sense that they can contain many more polygons than necessary for a particular run-time task. The aim of surface simplification methods is to automatically produce approximate surfaces that use far fewer triangles but yet still preserve the surface shape as closely as possible.
We’ll begin our discussion of simplification by studying the quadric-based simplification algorithm usually called QSlim. This is obviously a topic near and dear to my heart, as it got me a Ph.D..
M. Garland and P. Heckbert. Surface simplification using quadric error metrics. In Proceedings of SIGGRAPH 97, pp. 209–216, August 1997. [PDF]
M. Garland and Y. Zhou. Quadric-based simplification in any dimension. ACM Transactions on Graphics, 24(2), April 2005. Draft preprint available as Technical Report UIUCDCS-R-2004-2450. [Tech Rept]
We’ll continue our discussion of simplification with Hugues Hoppe’s work on progressive meshes.
There are a number of useful surveys of the simplification literature. Although it’s starting to get a little bit out-of-date, I personally like the one I wrote (surprise!)
there’s also all sorts of useful information in the following book:
One of the interesting aspects of the QSlim algorithm is that you can actually prove that it’s optimal (in a certain restricted sense). Specifically, you can show that, in the limit of infinitesimal triangles, if you minimize the quadric error of the approximation, the triangles will have the aspect ratio necessary for L_2-optimal approximation.
Our in-class presentation was delivered by Jerry Talton.