﻿ Mesh Simplifier

# 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:

• Store all boundary half-edges in a set, sorted first by the starting vertex, then by the angle that the edge makes with a chosen vector on the starting vertex's tangent plane.
• For a boundary half-edge (let's call it BHE), to find its next edge:
• First, compute an angle (the angle on tangent plane, let's call it CUR_ANGLE) by treating its ending vertex as starting vertex;
• Locate all the boundary half-edges in the set with BHE's ending vertex as starting vertex (this can be done efficiently by the lower_bound() and upper_bound() function);
• Binary-search this edges list (already sorted by angle) to find the first one with angle that's greater than CUR_ANGLE.

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

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