woodblock

25 January 2014 by Woody Chow on mesh simplification | progressive meshes | geomorph | edge collapse

Mesh Simplification and Progressive Meshes

Introduction

This was written for my first project for the graduate level Computer Graphics Course at Berkeley. I implemented the algorithm described in Garland's paper [1], which uses a greedy algorithm to calculate the best split with respect to the model's geometry, recursively reducing a 3D model's polygon count by edge contraction. I also implemented geomorph, granting smooth transition between different polygon resolutions.

Video Demonstration

Implementation Details

Mesh Connectivity Data Structure

I decided to use Indexed Face to represent triangle meshes. In Indexed Face, vertices are stored in an array. Then, there is an array of triangles, where vertices of a triangle is store as indices to the vertex array.

The most obvious reason for choosing Indexed Face over other representations is its affinity with OpenGL. Vertex array is read as array buffer, and triangle array is read as element array buffer. Unlike other data structures like half edge or winged edge, there is no conversion is required for OpenGL to read the data. In addition, due to the simplicity and compactness of Indexed Face, very few updates are needed when performing an edge collapse. Last but not least, .OFF is an Indexed Face file format. Initializing the data structure in C++ is just trivial.

Atomic Operations: Edge Collapse

An edge collapse of v1<->v2 into vertex v1' with an updated position consists of the following steps:

For each triangle adjacent to v2, count the number of vertices which is v1 or v2. If the number is 1, it denotes only v2 is in the triangle; only overwriting v2 with v1 in the triangle list is needed. If the number is 2, it denotes both v1 and v2 are in the triangle. It logically follows that it is a degenerate face, because v1 and v2 are going to merge into a single position v1'. The triangle is to be removed from the triangle list.
Merge the triangle list of v1 and v2.
Update the position of v1 to the merging point.
Recalculate normal of v1 by taking the average of the normals of all triangles adjacent to v1.



Figure 2, 3: Edge Collapse Example 1
Merging the circled vertex into the vertex being pointed at.


Figure 4, 5: Edge Collapse Example 2
Merging the circled vertices to the midpoint.

Quadric Simplification


Figure 6: Armadillo in different resolution
The polycount is 172974(full model without simplification), 75000, 10000, 5000, 2000 and 500 respectively from left to right, from top to bottom.

I followed Garland's papers on Quadric Simplification [1][2] closely. Specifically, I have implemented his Normalized Quadric Metric specified in his PhD thesis, which weights the metrics of adjacent triangles at a vertex by their angles at that vertex and their areas. Specifically, the weight is area times the angle divided by pi. This allows the simplified model to resemble the original model more closely. However, it has its compromises too. Calculating the angles and area of a triangle require lots of calculations. The normalized versaion runs significantly slower than the non-normalized version. Parallel optimization is necessary for acceptable performance on models with high polygon count. Therefore, I used OpenMP to speed up Quadric Metric calculation.

The main implementation challenge was to correctly update the Quadric Metrics after an edge collapse in a reasonable time. Therefore, I have used STL Multimap as my primary data structure for the Quadric Metrics, and an array of STL vectors storing the Quadric Metric of each edge. When an update is required, I use the array of STL vectors to find the way in the multimap.

After iterating through all possible edge collapses, the sequence of edge collapse with Quadric Error minimized is written to the output. Each line in the output represents an edge collapse, with information about the original vertices, merge position, and triangle to be removed and updated. The mesh viewer can read this file, and illustrate the result.

Please watch the video at the top of this page for demonstration.

Progressive Mesh

Progressive mesh is trivial since the inverse of edge collapse is vertex split. After the model is simplified to a certain extent using the edge collapse sequence specified, the model is progressively expanded by reading the sequence file in reverse order.

Geomorph

Geomorph is implemented by linearly interpolating the vertex positions in between a vertex transformation (both edge collapse and vertex split) as Hoppe suggested [3]. I also utilized Spherical Linear Interpolation (Slerp) on transforming vertex normal. However, I suspect any users will actually notice the difference between linear interpolation and Slerp unless carefully inspected.

Geomproh is used throughout the video demonstration.

References

  1. Michael Garland and Paul S. Heckbert. 1997. Surface Simplification using Quadric Error Metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques (SIGGRAPH '97). ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 209-216
  2. Michael Garland. 1999. Quadric-Based Polygonal Surface Simplification. Ph.D. Dissertation. Carnegie Mellon Univ., Pittsburgh, PA, USA.
  3. Hugues Hoppe. 1996. Progressive meshes. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques (SIGGRAPH '96). ACM, New York, NY, USA, 99-108.

First published at http://woodychow.com/berkeley/cs283/mesh/ in Jan 2013.