CS283 Assignment 1: Mesh Simplification and Progressive Meshes

I have implemented Quadric Metric suggested by Garland[1][2] and geomorph suggested by Hoppe[3].

Project Video

Implementation Details

Mesh Viewer and .OFF file loading

Figure 1: Screenshot of the mesh viewer

My mesh viewer supports the following basic functions: Translate, rotate, scale and wireframe rendering. In addition, by calculating their bounding boxes, models are automatically positioned in the center of the screen with appropriate scale. For simplicity, only diffuse shading is used.

In my .OFF loader, vertex normal is calculated by averaging normals of adjacent triangles. Assuming counter-clockwise orientation, triangle normal is computed by taking cross product of the edges.

Mesh Connectivity Data Structure

I chose 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:

  1. 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.
  2. Merge the triangle list of v1 and v2.
  3. Update the position of v1 to the merging point.
  4. Recalculate normal of v1 by taking the average of the normals of all triangles adjacent to v1.

Figure 2, 3: plane.off

Merging the circled vertex into the vertex being pointed at.

The triangle count is 200 before edge collapse, and 198 after because the 2 degenerate triangles are removed. This is an evidence that my edge collapse is updating the data structure correclty





Figure 4, 5: testpatch.off

Merging the circled vertices into their midpoint.

The triangle count is 16 before edge collapse, and 14 after because the 2 degenerate triangles are removed. This is another evidence that my edge collapse is updating the data structure correclty. Careful readers should notice that there is only 12 triangles in the second figure; it is because I did not attempt to remove the triangle fins.

Quadric Simplification

Figure: armadillo.off 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 closely [1][2]. 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

Compile and Run

The program uses OpenGL 3.3, GLEW, glfw, GLM, OpenMP and Boost C++ libraries. The makefile included is only written for my linux machine; users may need to edit the makefile to link the appropriate libraries.

To generate the sequence file, run
./mesh gen [.OFF file path] [output path]

To play the sequence file with my mesh viewer, run
./mesh play [.OFF file path] [sequence file path]

To control the mesh viewer,
Switch Transform Axis - x / y / z / a (all axes only available for scaling) Translate - t
Rotate - r
Scale - s
Control sequence player - m
Wireframe - w
Quit - Esc
Increase Sensitivity - =
Decrease Sensitivity - -

Top Arrow - Fast forward / increase
Left Arrow - Forward / increase
Bottom Arrow - Fast backward / decrease
Left Arrow - Backward / decrease

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.