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.