Mesh Simplification and Progressive Mesh Implementation

Wanze (Russell) Xie
Jun 8, 2018 · 8 min read

Introduction

This project implemented the mesh simplification algorithm based on on the Quadric error metric paper by Garland and Heckbert in SIGGRAPH 97. We also created a demo of progressive meshes based on [Hoppe, SIGGRAPH 96]. The data structure of our mesh simplification system is based on modified face-vertex adjacency list. This write-up will introduce the different ways of interactions to control the rendered model and the process of mesh simplification and progressive mesh.

Download executable for Windows:

https://drive.google.com/file/d/1mxp_eVIqSCOR8zZetuYorufShCpmXZYI/view?usp=sharing

Compilation and Run

Compile:

Our program is implemented with C++ and OpenGL in Visual Studio. Therefore, we provided a visual studio solution that can directly be compiled by setting the “Solution Configuration” to Release and “Solution Platform” to x86.

After compilation, the executable will be stored in the folder named “Release”. Double click “GLFWStarterProject.exe” to execute the program. Otherwise, feel free to download the executable provided above, which comes with the models to use.

Run:

There are two ways you can run the program:

Double click on the executable file (recommended):

  • Easiest way to run the demo program
  • This way the program will open by loading the default sphere.off model
  • All the Mesh Manipulation function works the same way

Execute the program using terminal (command line):

  • This way you will be able to load the any model by specifying the path
  • Recommend gitbash or similar to execute by inputting:
$ ./MeshSimplification.exe <model_file_path>
  • For example, to load the torus.off file we can do
$ ./MeshSimplification.exe ./models/torus.off

Note: if the windows prompt out and closed automatically, it means that the file path is incorrect, or the file format is incorrect

Mesh Viewer

3.1.1 Mesh Viewer Overview

After the program window prompt out, either by double clicking or using command line, all the interactions and manipulations can be done using keyboard control, which will be introduced in the section below.

If the loaded model is the sphere, it will be centered in the screen with a size of 1. We recommend making it larger by pressing “Shift+S” to make it larger, and press “L” to toggle the rendering mode from “Triangle” to “Wireframe”. Then feel free to use mouse to rotate the model.

Following is a sample scene of a loaded model after performing certain manipulation

3.1.2 Model Manipulation and Controls

Keyboard:

  • “S”: scale down the model
  • “Shift+S”: scale up the model
  • “Z”: move the model further from the camera
  • “Shift+Z”: move the model closer to the camera
  • “N”: toggle on/off the normal coloring
  • “C”: press and hold to start quick mesh simplification
  • “B”: press to perform slow mesh simplification
  • “V”: press to perform progressive mesh reconstruction
  • “A”: start/stop automatic mesh simplification animation
  • “M” / “Shift + M” to adjust the shininess of the material
  • “Esc”: to shut down the program and close the window

Mouse:

  • Hold left mouse button to freely rotate the model
  • Hold right mouse button to translate the model up/down/left/right
  • Scroll the mouse wheel to move the model further/close.
  • To control the lighting, press “1” on the keyboard, then drag the scene with mouse
  • To go back to model control, press “0” on the keyboard.

Note: Please make sure that you are not in “N” mode when trying to control the lighting. Also, the function of “A” and “C” will be disabled when “V” is pressed in order to ensure the performance.

Mesh Connectivity and Data Structure

3.2.1 advanced partial adjacency list

(1) Structure of Face, Vertices, and Edge

To make the implementation concise and organized , our implementation of the data structure is based on the partial adjacency list. However, our design is more light-weighted. We only keeps an adjacency list for vertices so that vertices will know the adjacent vertices around it. For edges, it will only have the information of two vertices that it connects. And for faces, they will only have the information of the three vertices that it connects.

The data structure used for face to store vertices are “std:vector” for quick accessing vertices. And the the adjacent list in each vertex uses “std::list”, this is because during mesh simplification, we will need to to sort out the duplicate vertices.

(2) Other structures used

In the general structure, we are keeping track of the vertices, faces with two lists. Their data structure are both std::vector. Note that since we would barely actually delete any vertices. So our performance are in O(1) if not considering keeping track of the error quadric precedency. To keep track of the quadric error of each edge so that we make sure we are collapsing the edge that has the smallest error, we use a binary search tree (“std::set”) data structure, which would result to a run time of O(log(n)) when updating the edges in our tree.

3.2.2 Build Mesh

To render our mesh, we used the OpenGL to render the mesh. Since we are render using VAO, VBO and EBO, we keep track of the vertices, faces and edges using a vector. Every time when we update our mesh structure due to mesh simplification, we will repopulate the elements in these three arrays to make sure that the correct triangles or the wire frame is rendered. Also, note that if the model size is large, it would take a while to load the model. After loaded, the manipulation will be easy and smooth.

Mesh Decimation

3.3.1 Keyboard Control

To perform mesh decimation, use ‘c’ key or ‘b’ key on your keyboard. Short pressing ‘c’ key will collapse 5 edges at a time. Long pressing ‘c’ key will keep collapsing 5 edges until the key is released. Short pressing ‘b’ key will collapse 1 edge at a time. Note that by default the program uses Quadric Error Matrices (QEM) to calculate which edge to collapse next, thus with very large models, long pressing the ‘c’ key might slow down the program significantly because the runtime is of O(log(N)).

3.3.2 Algorithm Explained

For each edge collapsed, the two vertices forming that edge are labeled invalid in the vertices list, and a new vertex is generated at the midpoint of those two old vertices. As a result, some faces will become degenerate, thus we also remove them from the faces list. Next, we update the adjacent vertices and faces to contain information related to the new vertex. Last but not least, we need to recalculate Quadric Error Matrices on adjacent vertices, as well as errors on the neighboring edges and update the edge tree. This is because we are using Quadric Error Matrices (QEM) to calculate which edge to collapse next, and thus when an edge is collapsed, the neighboring faces and vertices are all affected.

3.3.3 Efficiency — Complexity and Run Time

The manipulations for solely collapsing two edges have runtime of O(1). Since by default our program recalculates Quadric Error Matrices (QEM) and updates the edge tree after each edge collapse, this causes the runtime to be of O(log(N)).

Some example images during edge decimations of cow.off, sphere.off, and teapot.off are shown below.

3.3.4 Sample Pictures

Here we show some example images of edge collapse result from teapot.off:

And below here are some examples of the collapsing of the testpatch:

Quadric Simplification

3.4.1 Quadric Error Matrices (QEM) Implementation

The Quadric Error Matrices (QEM) measures the effect of moving a particular vertex around its original position on changing the geometry of the whole mesh. The QEMs take into account a vertex’s surrounding faces, computed as the sum of squared distances from this vertex to the planes of surrounding faces. In our implementation, we keep a matrix Q in each vertex (with position v); this Q is calculated as the sum of outer-product of vector p (a, b, c, d) with itself, where (a, b, c) is the normal n of each adjacent face, and d is -v·n. Then, for each edge, we calculate the error of collapsing the two vertices (with error matrices Q1 and Q2) to their midpoint with position p’ by adding Q1 · p’ and Q2 · p’.

3.4.2 Update Error for local edges

During mesh simplification and progressive mesh reconstruction, we sometimes will create or restore the edges. And in this process, we will need to update the errors in the edge. To maintain the edges in the binary tree structure in correct order, we will remove the modified edge from the tree and re-insert it into the correct position. Although this sacrifices the computation time, it ensures that when we perform mesh simplification, we can preserve the shape of the original model to the maximal extent.

3.4.3 The improvement after adopting QEM

Quadric Error Metrics enabled us to collapse the edge that has minimal affect to the general structure of the model. Before implementing QEM, if we just collapse the two vertices into the mid-point by random or sequential order, the mesh would lose it’s original shape comparing to the result after we adopted QEM into our algorithm. Unfortunately we didn’t preserve the version without QEM, otherwise we would be able to show a result of comparison in this section.

Progressive Mesh

3.5.1 Progressive Mesh Overview

The progressive mesh allows you to reconstruct from the collapsed mesh to the original mesh. During the process of edge decimation, our program saves information of removed vertices and faces along the way. Therefore, we can reconstruct the mesh splitting the merged vertices using these saved information.

3.5.2 Create Smooth Animation

Here is a smooth animation of collapsing a sphere with 482 vertices, the video demo is quite long but you can jump and click through to visualize the final result. You can also press “A” button to visualize the animation when running the demo program

3.5.3 Control

To perform progressive mesh, use ‘v’ key + shift key combination on your keyboard. Short pressing the ‘v’ key will reconstruct 2 edges at a time. Please note that once you pressed this key combination to perform progressive mesh, you cannot perform edge decimation further more.

3.6.1 Size and Shape Preservation

Our implementation of Quadric Error Metrics (QEM) ensures size and shape preservation of the meshes. Because each time the removed edge will cause the smallest error on the geometry of the whole mesh, a general shape and size of the original mesh is preserved along the way of edge decimation. Examples of the teapot model with different level of edge decimations are shown in section 3.3.4.

Some sample pictures below helps visualize this section:

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade