Survey of Multiresolution Modeling

A multiresolution model is a model which captures a wide range of levels of detail of an object and which can be used to reconstruct any one of those levels on demand. Surface simplification is a restricted form of multiresolution modeling. In polygonal surface simplification, the goal is to take a polygonal model as input and generate a simplified model (i.e., and approximation of the original) as output. This is in contrast to the more general goal of constructing a new representation of the original model which can be used to extract a wide range of approximations.

      The basic concept of multiresolution modeling for use in rendering is not particularly new; Clark discussed similar ideas in 1976. However, with the exception of work done on multiresolution raster images, most research in this area has been done fairly recently.

Survey of Past Research

Image Pyramids Image pyramids are the simplest and most common type of multiresolution model used in computer graphics today. They are a successful and fairly simple multiresolution representation of raster images.

Multiresolution Image Processing and Analysis. A. Rosenfeld.

Volume Methods
  • Truly multiresolution
  • Best on volume data only

Some work has been done on volumetric approaches to multiresolution modeling. For instance, volume pyramids are a natural generalization of image pyramids. Generally speaking, if the models in question are acquired as volumes and will be rendered as volumes, volume simplification is a good approach. However, if the simplified volumes must be converted into a polygonal form before rendering, volume methods become significantly less attractive.

Voxel-based object simplification. T. He, L. Hong, A. Kaufman, A. Varshney, and S. Wang. [ps] [abstract]

Vertex Decimation
  • Good quality
  • Manifolds only
  • Preserves topology
Vertex decimation is an iterative surface simplification algorithm. In each step, a vertex is selected for removal, all the faces adjacent to that vertex are removed from the model, and the resulting hole is retriangulated. These methods can only be applied to manifold surfaces. The removal of a non-manifold vertex does not create a hole which can be retriangulated. Because these algorithms were developed to reduce the density of acquired meshes, they are careful to preserve topology.

Decimation of triangle meshes. W. Schroeder, J. Zarge, and W. Lorensen. [software]

Multiresolution surface modeling based on hierarchical triangulation. M, Soucy and D. Laurendeau. [software]

Vertex Clustering
  • Fast & General
  • Hard to control
  • Poor quality
Uniform vertex clustering is a simple method which makes very few assumptions about the input geometry. First, the object's bounding box is subdivided into a grid. All the vertices falling within a single cell a clustered together and replaced by a single representative vertex. The layout of the grid controls the resulting simplified model. Unfortunately, this is a rather indirect means of controlling the output. It can also suffer from rather severe loss of detail and distortion of the model. These are primarily aliasing effects caused by using a discrete grid for clustering.

Multi-resolution 3D approximations for rendering complex scenes. J. Rossignac and P. Borrel.

Edge Contraction
  • Smooth transitions
  • Good quality

An edge contraction (or edge collapse) takes the two endpoints of the target edge, moves them to the same position, links all the incident edges to one of the vertices, deletes the other vertex, and removes any faces that have degenerated into lines or points. Typically, this removes two triangular faces per edge contraction.

      These algorithms work by iteratively contracting edges of the model. The primary difference lies in how the particular edge to be contracted is chosen.

Mesh optimization. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. [software] [html]

Progressive meshes. H. Hoppe. [ps/pdf/html]

Full-range approximation of triangulated polyhedra. R. Ronfard and J. Rossignac.

Surface simplification inside a tolerance volume. A. Guéziec. [ps]

Surface Simplification Using Quadric Error Metrics. M. Garland and P. Heckbert. [paper/software]

Progressive simplicial complexes. J. Popovic and H. Hoppe. [ps/pdf]

Simplification Envelopes
  • Global error guarantee
  • Oriented manifolds only
  • Preserves topology
  • Difficult to construct
Simplification envelopes are something of a meta-method. They provide a technique for establishing a global error guarantee on the distance of the approximate model from the original. This is accomplished by offsetting the original surface both outwards and inwards. This defines an outer and inner envelope. By generating an approximation that lies between these envelopes, we can have a maintain an error guarantee. This naturally preserves the original model topology.

      In order to construct the envelopes, the original model must be an oriented manifold. The envelopes can also be difficult to construct if the surface has many very sharp corners where the envelopes might fold back upon themselves.

Simplification envelopes. J. Cohen, A. Varshney, D. Manocha, G. Turk, H. Weber, P. Agarwal, F. Brooks, and W. Wright. [software] [ps]

Wavelet Surfaces
  • Truly multiresolution
  • Smooth manifolds only
  • Topology cannot change
The final approach to surface simplification is the use of wavelet methods. Essentially, this requires that the surface be reconstructed using a wavelet representation. This is typically difficult. Eck et al. developed a method for constructing wavelet representations of arbitrary manifold surfaces. However, it suffers from some serious drawbacks. Before the wavelet representation can be built, the surface must be remeshed so that it has subdivision connectivity. This process alone introduces error into the highest level of detail. In addition, the topology of the model must remain fixed at all levels of detail. The wavelet representation is also unable to adequately preserve sharp corners and other discontinuities on the surface.

Multiresolution Analysis of Arbitrary Meshes. M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsberry, and W. Stuetzle. [html] [ps]

[Table of Contents]

Michael Garland
Last modified: Tue Oct 28 10:50:44 EST 1997