This little tool is my implementation of the paper Surface Simplification Using Quadric Error Metrics by Michael Garland et al.
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.
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:
See my github.
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.