Michael Garland

This page contains a short synopsis of the contents of my Ph.D. thesis. The complete text is available in the following formats:

• PDF (10 MB) for print output
• PDF (2.5 MB) with images downsampled and JPEG-encoded for on-screen viewing
• PostScript (110 MB)

I strongly recommend downloading the PDF version of my thesis. The final image quality should be identical to the PostScript version, at one tenth the size.

I have made my experimental implementation of the algorithms described in this dissertation publicly available. I also have a collection of sample data and related papers that you might find useful.

Abstract

Many applications in computer graphics and related fields can benefit from automatic simplification of complex polygonal surface models. Applications are often confronted with either very densely over-sampled surfaces or models too complex for the limited available hardware capacity. An effective algorithm for rapidly producing high-quality approximations of the original model is a valuable tool for managing data complexity.

In this dissertation, I present my simplification algorithm, based on iterative vertex pair contraction. This technique provides an effective compromise between the fastest algorithms, which often produce poor quality results, and the highest-quality algorithms, which are generally very slow. For example, a 1000 face approximation of a 100,000 face model can be produced in about 10 seconds on a PentiumPro 200. The algorithm can simplify both the geometry and topology of manifold as well as non-manifold surfaces. In addition to producing single approximations, my algorithm can also be used to generate multiresolution representations such as progressive meshes and vertex hierarchies for view-dependent refinement.

The foundation of my simplification algorithm, is the quadric error metric which I have developed. It provides a useful and economical characterization of local surface shape, and I have proven a direct mathematical connection between the quadric metric and surface curvature. A generalized form of this metric can accommodate surfaces with material properties, such as RGB color or texture coordinates.

I have also developed a closely related technique for constructing a hierarchy of well-defined surface regions composed of disjoint sets of faces. This algorithm involves applying a dual form of my simplification algorithm to the dual graph of the input surface. The resulting structure is a hierarchy of face clusters which is an effective multiresolution representation for applications such as radiosity.

Contents

The following is a high-level overview of the content of my dissertation:

• Chapter 1: Introduction.
• Chapter 2: Background & Related Work. In this chapter, I provide a detailed discussion of surface simplification and a review of the prior work in the field.
• Chapter 3: Basic Simplification Algorithm. This chapter introduces the core material of the dissertation. It contains a description of the quadric error metric and the simplification algorithm which I have built around it.
• Chapter 4: Analysis of Quadric Metric. The quadric error metric is the central component of my simplification algorithm, and this chapter is devoted to analyzing its behavior. For example, the quadric metric has an interesting geometric interpretation; in particular, the isosurfaces of the error function are (possibly degenerate) ellipsoids. In this chapter, I discuss this interpretation and also demonstrate a mathematical relationship between the eigenvalues of the quadric metric and the principal curvatures of the surface.
• Chapter 5: Extended Simplification Algorithm. The algorithm described in Chapter 3 considers surface geometry exclusively. In this chapter, I discuss the extension of the quadric error metric to surfaces with material properties (e.g., color and texture).
• Chapter 6: Results & Performance Analysis. This chapter illustrates the results of my algorithm. The emphasis is on empirical performance, although I also present some theoretical analysis of the complexity of the algorithm.
• Chapter 7: Applications. In this chapter, I examine some of the applications of my simplification algorithm. In particular, I review the progressive mesh and vertex hierarchy structures developed by others. I also describe the close connection between simplification and minimum spanning tree algorithms.
• Chapter 8: Hierarchical Face Clustering. This chapter outlines my hierarchical face clustering algorithm. I perform hierarchical clustering by applying what is essentially the dual of my simplification algorithm to the dual graph of the surface. The resulting structure can be quite useful in hierarchical computations for applications such as radiosity and collision detection.
• Chapter 9: Conclusion. This chapter summarizes the content of all the previous chapters. I also discuss some of the more interesting directions for future work.
• Appendix A: Implementation Notes. To highlight certain design choices and techniques, I have included Appendix A, which contains details on my implementation of the simplification algorithm described in Chapter 3.