Overview

The demand - and supply - of larger and larger meshes present some interesting problems. How do we store and share these meshes? How can we render them quickly in a real-time application? One solution is to simplify the mesh, reducing the number of faces while maintaining similar geometry.

One class of these mesh simplification techniques is to determine an energy function for each edge, then iteratively remove the edge with the least cost. Two seminal works in this area are Progressive Meshes by Hughes Hoppe and Quadric Error Metrics by Michael Garland. The progressive meshes technique introduced a means of storing each edge collapse so that the mesh simplification could be reversed; however, the quadric error meshes technique is much faster. This is a very high-level view of the two techniques - read the papers on the respective authors' websites for more information.

For this project, I implemented a quadric error metrics (QEM) mesh simplification program, and utilized an adaptation of the progressive error metrics structure to make the transformation reversible.

Design Decisions

I made two crucial design decisions when implementing this project. The first decision I made was to not collapse boundary edges; while this limits the number of possible edge collapses, it also allows the mesh to retain its structure and general geometry longer.

The second decision I made was regarding how to store the edge collapses. The primary difficult inherent is determining which faces belong to which vertices once the vertex split has been done (a vertex split is the opposite of an edge collapse). I originally stored the positions of both vertices, the vertex IDs, and the common neighboring vertices (labeled V_left and V_right). In the following diagram, V₀ and V₁ are the vertices of the edge to collapse; V_left and V_right are labeled for clarification.

A potential edge collapse, with relavant vertices labeled.

I then used the heuristic that all faces from V_right to V_left, clockwise, belonged to V₀. This worked well, except for meshes with edge boundaries and non-manifold meshes. Due to this - and in a rush to finish under the deadline - I also store the vertices of every face that belong to V₀. This technique is much more verbose, but also much more resilent.

Results

The following images show a gargoyle mesh, shunk down from 2,000 faces to 250. This transformation can be done in much less than a second.

2,000 faces	1,000 faces	500 faces	250 faces

Download

My program may be downloaded and used for educational purposes. The usage is as follows:
pm_njlynch.exe meshFile [shrinkToFaces]

• meshFile: The name of the *.m (or *.pm) file to load.
• shrinkToFaces: Optional; if presented, it will attempt to shrink the input mesh to shrinkToFaces faces.

• 1 - Toggle displaying faces
• 2 - Toggle displaying edges
• r - Removes one edge
• t - Adds one edge (if one or more have been removed).
• s - Saves the file as mesh.pm in the current directory, including all edge collapse data. Sorry about the hard-coded filename. :)
• x - Collapses the mesh to its most minimalist form (least faces).
• q - Quits

DISCLAIMER: This program was created under a deadline with conflicting priorities and last-minute implementation. There are known bugs, some of which will cause strange mesh states, some of which will actually crash the program. Sorry about that. It does work very well in a lot of cases, but it's by no means production-ready.