I have implemented Quadric Metric suggested by Garland and geomorph suggested by Hoppe.
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:
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.
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 . 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 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 is implemented by linearly interpolating the vertex positions in between a vertex transformation (both edge collapse and vertex split) as Hoppe suggested . 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
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 - -