Surface Approximation and Multiresolution Modeling

This page is a slight edit of Michael Garland's excellent page (see below); I have been slowly adding a few pointers. If you know of other links that should be added, send them to me at

Sites of Interest

Multiresolution Modeling.
Web page for Michael Garland, on which this page is based (copied).
Terra/Scape Terrain Simplification.
Web page for Garland's terrain software.
LOD Overview
This page from Mike Krus is another overview page of Level of Detail algorithms.
Simplification envelopes software
The simplification envelopes algorithm presented at SIGGRAPH 96.
Some decimation-based multiresolution stuff from Nick Torkos.
This is basically the Schroeder et al. decimation algorithm, with more focus on constructing a multiresolution model during the decimation process.
Mesh reduction
from the Shastra project at Purdue.
Unstructured Decimation of Tessellated Domains
This is a generalization of decimation to higher dimensions (i.e., tetrahedralized volumes).
Mesh generation links from Paul Heckbert
Mesh generation is loosely related to mesh simplification.
The Visualization Toolkit (vtk)
This is a large and comprehensive class library for scientific visualization. Of primary interest, it contains an implementation of the decimation algorithm of Schroeder et al..
Some papers on using wavelet representations of surfaces.
Automatic level-of-detail generation from IBM
IBM's Interaction Accelerator implements the model simplification algorithm due to Rossignac and Borrel.
3D Alpha Shapes
UNC Simplification Group
Another page of links to simplification-related information.
Geometric Modeling Group at the University of Genova
This is primarily terrain-related modeling work, with some volume modeling thrown in.
Visual Computing Group at CNR-Pisa
This is an actual large-scale virtual world. Just the sort of area where multiresolution models and model simplification would be most useful. They've done some work along these lines.
Alias/Wavefront polygon reduction
IMCompress from InnovMetric.

General Papers

Polygonal Simplification: An Overview,
by Carl Erikson, UNC TR96-016. An excellent overview document.
Multiresolution Modeling For Fast Rendering,
by Paul Heckbert and Michael Garland, Graphics Interface '94. The version published in Graphics Interface had certain errors that have been corrected in this online version.
Simplification of Objects Rendered by Polygonal Approximations
Michael DeHaemer and Michael Zyda
Surface reconstruction from unorganized points
Hugues Hoppe,
Progressive meshes (SIGGRAPH'96)
Hugues Hoppe,
Multiresolution Analysis for Surfaces of Arbitrary Topological Type
Michael Lounsbery
Generating Levels of Detail for Large-Scale Polygonal Models
Amitabh Varshney, Pankaj K. Agarwal, Frederick P. Brooks, Jr., William V. Wright, and Hans Weber
Simplex Meshes: a General Representation for {3D} Shape Reconstruction
Herve Delingette
Fast Multiresolution Surface Meshing
Markus H. Gross, R. Gatti, and O. Staadt
Surface Simplification Inside a Tolerance Volume
Andre Pierre Gueziec
SuperFaces: Polyhedral Approximation with Bounded Error (reference only)
Alan D. Kalvin and Russell H. Taylor
Voxel-Based Object Simplification
Taosong He, L. Hong, A. Kaufman, A. Varshney, and S. Wang
Multiresoultion modeling and visualization of volume data based on simplicial complexes
P. Cignoni, L. De Floriani, C. Montani, E. Puppo, and R. Scopigno

Terrain Papers

Fast Polygonal Approximation of Terrains and Height Fields,
by Michael Garland and Paul Heckbert (Technical Report CMU-CS-95-181).
A color plate is included separately.
Representation and Visualization of Terrain Surfaces at Variable Resolution
P. Cignoni, E. Puppo, and R. Scopigno
Hierarchical Triangulation for Multiresolution Surface Description
Leila De Floriani and Enrico Puppo
Multiresolution Models for Topographic Surface Description
Leila De Floriani, Paola Marzano, and Enrico Puppo
On Levels of Detail in Terrains
Mark de Berg and Katrin Dobrindt
Level-of-detail Management for Real-Time Rendering of Phototextured Terrain
Peter Lindstrom, David Koller, Larry F. Hodges, William Ribarsky, Nick Faust, and Gregory Turner
Real-Time, Continuous Level of Detail Rendering of Height Fields (plus Figures )
Peter Lindstrom, David Koller, William Ribarsky Larry Hodges, Nick Faust and Gregory Turner
Automatic Generation of Triangular Irregular Networks using Greedy Cuts
Claudio T. Silva, Joseph S. B. Mitchell, and Arie E. Kaufman
Surface Approximation and Geometric Partitions
Pankaj K. Agarwal and Subhash Suri
Separation and Approximation of Polyhedral Objects
Joseph S. B. Mitchell and Subhash Suri
Approximation Algorithms for Geometric Separation Problems
Joseph S. B. Mitchell
Approximating Polygons and Subdivisions with Minimum Link Paths
L. J. Guibas, J. E. Hershberger, J. S. B. Mitchell, and J. S. Snoeyink
Decimation of 2D Scalar Data with Error Control
D. Schikore and C. Bajaj
Hierarchical model for natural terrain using topographic triangular meshes
Reda E. Fayek, and Andrew K.C. Wong
Temporal Continuity of Levels of Detail in Delaunay Triangulated Terrain
Daniel Cohen-Or and Yishay Levanoni

Related Topics

Bibliographic Notes on Voronoi Diagrams
Javier Bernal
Bibliography of approximation algorithms
Eric Grosse
Geometric Compression through Topological Surgery
Gabriel Taubin and Jarek Rossignac
Optimal Surface Smoothing as Filter Design
Gabriel Taubin, Tong Zhang, and Gene Golub
Importance-Driven Progressive Refinement Radiosity
Philippe Bekaert and Yves D. Willems
Overview on Multigrid Algorithms

October 20, 1996

Joe Mitchell