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

  • Generic error metric signature: Defines the interface to a geometric error metric.
  • Garland/Heckbert quadrics, 3-Dimensional: Implementation of the GH quadric error metric in three dimensions
  • Garland/Heckbert quadrics, N-Dimensional: Implementation of the GH quadric error metric for N-dimensional data (allows simplification of points with color or texture data attached)
  • Signature for a surface simplifier: Specifies a transformation on simplicial complexes
  • Greedy edge reduction simplifier: Given an error metric and a model, greedily contract edges (or non-edge vertex pairs) which induce the lowest geometric error
  • MakeSimplifier.sml: Demonstrates linking the various functors into a cohesive application
  • Simple file->simplicial complex parser signature: Interface to various parsers for loading test data
  • Simple simplicial complex->file export signature: Interface for writing simplicial complexes in common file formats
  • Parser for subset of Garland's SMF format
  • Exporter for subset of Garland's SMF format
  • Exporter for Geomview's OFF format


    Acknowledgements

    The PSCICO project is supported by NSF under the title "Advanced Languages for Scientific Computation Environments" as part of the Experimental Software Systems program within CISE. The grant number is 9706572.
    Back to the PSciCo homepage.