Multiresolution Modeling -- The Old Page

Sections: [ My Own Work | New | Sites of Interest | Papers | Terrain Papers | Related Topics ]


NOTE: This is an out-of-date page which I've kept around for purely historical reasons. There is a much more current and useful page available.

Multiresolution modeling (or multiresolution modelling for those fond of the letter L) is the main area of my research in computer graphics. The general theme can be summed up as "complexity is the bane of rendering" (because complexity makes things slow).

Currently, this page is a place to collect links to useful and relevant information out in the Web. If you know of any such links that aren't listed here, send them to me at garland@cs.cmu.edu.

My Own Work

This is my Web page, so I think it's fair that my personal links go first. For those of you just stopping by, looking around here should give you some idea of what I've done.

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.

We wrote this general paper a couple of years ago. It basically outlines why multiresolution modeling is important and useful. We also made some comments about possible different approaches for the representation and generation of multiresolution models.

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.

More recently, I spent quite a bit of time working on generating approximations of digital terrain models. This explains the fairly large number of terrain references below.

Terra/Scape Terrain Simplification.
This is my page for the terrain software I built. It's free and it's available. It might even be useful to you. But it's been a quite a while since I've had time to actively work on this software, so be warned: this is definitely not production-quality software.

Online Bibliography
This is the bibliography database that Paul Heckbert and I have compiled over the past couple of years.

Future work to be added.
I've pretty much wrapped up my foray into the world of terrains, and I'm now trying to focus on the real problem that interests me: How to produce multiresolution models of arbitrary 3D polygonal models. When I actually have something useful or interesting to look at, I'll put it here.

There. Now that you've seen what I've been doing, let's get on to what other people have been doing.

What's New

To make it easier to keep track of things, and for the benefit of people surfing through here, I've started collecting new links here. Eventually, they'll move off into their proper area.

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

Sites of Interest

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..
Wavelets
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
NPSNET
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

Simplification of Objects Rendered by Polygonal Approximations
Michael DeHaemer and Michael Zyda
Surface reconstruction from unorganized points
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

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

November 19, 1996

Michael Garland
garland@cs.cmu.edu