Multiresolution analysis of arbitrary meshes

Multiresolution analysis of arbitrary meshes
Matthias Eck, Tony DeRose, Tom Duchamp, Hugues Hoppe, Michael Lounsbery, Werner Stuetzle.
ACM SIGGRAPH 1995 Proceedings, 173-182.
Semi-regular remeshing for wavelet-based representation of surfaces.
Abstract: In computer graphics and geometric modeling, shapes are often represented by triangular meshes. With the advent of laser scanning systems, meshes of extreme complexity are rapidly becoming commonplace. Such meshes are notoriously expensive to store, transmit, render, and are awkward to edit. Multiresolution analysis offers a simple, unified, and theoretically sound approach to dealing with these problems. Lounsbery et al. have recently developed a technique for creating multiresolution representations for a restricted class of meshes with subdivision connectivity. Unfortunately, meshes encountered in practice typically do not meet this requirement. In this paper we present a method for overcoming the subdivision connectivity restriction, meaning that completely arbitrary meshes can now be converted to multiresolution form. The method is based on the approximation of an arbitrary initial mesh M by a mesh Mj that has subdivision connectivity and is guaranteed to be within a specified tolerance.
The key ingredient of our algorithm is the construction of a parametrization of M over a simple domain. We expect this parametrization to be of use in other contexts, such as texture mapping or the approximation of complex meshes by NURBS patches.
Hindsights: Novel technique for parametrizing an arbitrary triangle mesh over a simpler triangular domain of the same topological type. Subsequently, two enhancements to this paper were presented: Vertex-based Delaunay triangulation (to improve the mesh partition) and Hierarchical computation of PL harmonic embeddings (to speed up harmonic maps).

The approach of remeshing a model to have subdivision connectivity was made more practical by the MAPS scheme of Lee et al in SIGGRAPH 1998.

The paper is often cited for introducing the harmonic map in the context of mesh parametrization. This harmonic/conformal map has been generalized to allow free boundaries, in LSCM and DCP, which are in fact equivalent, and also identical to harmonic maps for fixed boundary.