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.
| 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
|
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
|
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
|
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
|
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
|
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
|
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] |