Back to the PSciCo homepage

# Surface Simplification and Multi-resolution Modelling

## Overview

In many computer modelling applications, the input data is in the form
of a mesh of triangles. They have the advantages of being simple to
work with, always planar, and yet still able to represent a complex
shape with a fair degree of fidelity. Often, these meshes are highly
oversampled, either as an artifact of the creation process (three-dimensional
scanning, marching-cubes triangulations) or to capture very fine-grained
surface details. While this may be ideal for archival purposes, as well as
finite element methods or close-up rendering, it can place great stress
on even high-end graphics hardware. In many rendering applications, a
particular model may sometimes be rendered far off in the viewport,
so that much of
the detail captured by the dense mesh is lost in any case. In this
situation, it is ideal to be able to down-sample the mesh, maintaining
the shape of the object while drastically reducing the triangle count.

Michael Garland developed
a fast, reasonably high-quality algorithm for simplifying triangle meshes,
as outlined in his thesis and later papers (available from his web site).
He presents a reference implementation in C++. For this project, we have
undertaken a Standard ML implementation, using persistent data structures
and purely functional code. Thanks to the module system, we can easily
replace entire sections of the algorithm, whether the vertex-pair selection
strategy, the error metric itself, or the driving greedy loop, without
any re-coding of the other portions. It also allows us to implement his
extended algorithm (taking into account texture coordinates, RGB color
information, or arbitrary per-vertex data) while holding the vast majority
of the code-base constant.

## Relevant Files