Mesh Simplifier

This little tool is my implementation of the paper Surface Simplification Using Quadric Error Metrics by Michael Garland et al.

The Algorithm

The simplification works by selecting vertex-pairs with minimum contraction cost, which is measured by a Quadric Error Metric, and contract them iteratively until target faces number is reached. For more details, please refer to the original paper.

The algorithm requires extensive edges traversal and faces traversal around a certain vertex, and in my implementation, I use the half-edge mesh structure to make such operations efficient. The drawback is that the half-edge cannot handle non-manifold edges. In the original paper, the vertex-pair can be an edge or two vertices that are very close, my implementation only supports edge contraction.

Handling Mesh Boundaries in Half-Edge

Typically half-edge structure doesn't work with mesh with boundaries, and I didn't found much valuable information on this from the Internet. So I came up with a method for handling boundaries on my own. A half-edge is created for every boundary edge, i.e. those edges not bordering faces. The tricky part is how to link the boundary half-edges together to ensure consistent traversal of vertices, edges and faces. My method works as follows:

Results

Stanford Bunny, faces: 10K -> 1K -> 500 -> 100
Hand, faces: 3.1K -> 310
Head, faces: 18K -> 5K -> 500
Horse, faces: 6K -> 760

Source Code

See my github.

Acknowledgments

The bunny model is from Stanford 3D Scanning Repository; the hand model and horse model are from Princeton Shape Benchmark Repository; the head model is from Infinite Realities. The screenshots were generated by MeshLab.

Reference

  1. Garland, Michael, and Paul S. Heckbert. "Surface simplification using quadric error metrics." Proceedings of the 24th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 1997.
  2. The Half-Edge Data Structure, by Max McGuire, 2000.

Last updated 12/9/2014