~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Hugh Chen~~~~~~~~~~~~

Abstract

For this project, I implemented three algorithms. Two for mesh simplification and one for mesh regularization.

The first two algorithms addressed mesh simplification. Mesh simplification is an important problem because the level of detail required for applications in computer graphics can vary greatly. In order to control computation time it is important to be able to upsample as well as downsample our meshes. The first algorithm uses quadric error metrics based off the surfaces of the mesh to determine which edges to contract. The main reference for this is Garland and Heckbert 09. The second algorithm is much simpler. It uses edge lengths to determine which edges to contract. The main reference is Gelas, Gouaillard, and Megason 2008

The third algorithm addressed mesh regularization. Mesh regularization is an important problem because the shapes and sizes of particular elements influences interpolations, simulation, shape approximation, and more (Shewchuck). A few simplistic heuristics of "good" triangle meshes are consistent triangle shapes, adhering to delaunay conditions, and regular vertex degrees. In order to conform to these heuristics, we can performa an isotropic remeshing algorithm detailed in Botsch and Kobbelt 04.

Technical Approach

Edge Collapse

In implementing mesh simplification and regularization, the first step is to write the edge_collapse, edge_split, and edge_flip functions. Since edge_split and edge_flip were both part of homework two, I only discuss edge_collapse here.

Implementing edge collapse for the halfedge mesh data structure was primarily a matter of reassigning pointers to achieve the following local change:

There were two methods to accomplish this: creating a new vertex v_m or reassigning one of the prexisting to be v_m. In order to minimize the amount of pointer I would have to reassign, I chose to do the latter. I reassigned the remaining vertices keeping in mind that I would ultimately delete the following vertices, edges, faces, and halfedges:

This means that v_c becomes our new v_m and the half edge pointing from c to a he_ca becomes our new he_ma, and so on. The first step to the reassignments is to reassign all halfedges around v_d to v_c. Since there could be an arbitrary number of halfedges, it requires iterating around v_d and reassigning the appropriate halfedges. The seconds step is to simply reassign v_m, v_a, and v_b as well as he_ma, he_am, he_mb, and he_bm accordingly.

Apart from special cases for the boundaries (in this project I just ignore them), the final note of caution is to ensure that we keed the mesh manifold. The images for the following two issues were taken from here

The first issue is connectivity. In order to ensure that the mesh is manifold after collapsing, we only want to merge one pair of edges per side of our original edge. In order to ensure this, I implemented a check by doing BFS with a depth of two from one endpoint of our original edge to the other, making sure that there were exactly two paths of length two between the endpoints.

Here we collapse the red edge. One on side of our original edge we see both blue and orange pairs of edges.

The second issue is geometry. In order to ensure that our mesh is still manifold we want to ensure that we don't flip any triangles. In order to guarantee this, we check around both endpoints of our original edge to ensure that the new triangles formed with v_m are all valid. This is accomplished by iterating around the endpoints to confirm that the dot product of the normals before and after is positive.

Here we collapse the red edge. The green triangle ends up being flipped.

Simplification using quadric errors.

For this part, I primarily used the CMU specs here.

Essentially we compute quadric matrices K for all faces which allow us to calculate the distance from given planes that look like:


    a^2   ab    ac   ad
    ab    b^2   bc   bd
    ac    bc    c^2  cd
    ad    bd    cd   d^2
    

Here N=(a,b,c) is the normal vector of the plane and d=-N•p, where p is a point on the plane. In this way we can find the squared distances to the given planes by multiplying with our point in homogenous coordinates on either side of the matrix. Then in order to obtain estimates for the quadric matrices for each vertex, we simply add up all of the adjacent faces' matrices. Then we can estimate quadric matrices for edges by adding the matrices at each endpoint. In order to figure out the optimal point to collapse we solve the linear system: Ax=b, where the entries of A are just


    a^2   ab    ac 
    ab    b^2   bc
    ac    bc    c^2
    

and the entries of b are


    -ad
    -bd
    -cd
    

Then, the estimated cost of collapsing an edge is x^T K x.

Now that we understand how to find the cost of edges, we simply create a priority queue with all the edges sorted by their optimal collapse cost, and we collapse until we have a quarter of the number of edges we had prior, all the while reassigning the vertices to be at their optimal points.

Simplification using edge length.

This simplification is very easy. It is similar to the previous simplification method, except we simply collapse according to edge cost, with our optimal point being the midpoint of the edges. The performance of this algorithm is fairly strong, although it doesn't preserve the shape of the mesh nearly as well as the quadric error metric method does.

Regularization

For the mesh regularization, we simply implement the following:

  1. Compute the mean edge length L of the input.
  2. Split all edges that are longer than 4L/3.
  3. Collapse all edges that are shorter than 4L/5.
  4. Flip all edges that decrease the total deviation from degree 6.
  5. Compute the centroids for all the vertices.
  6. Move each vertex in the tangent direction toward its centroid.

The only thing to be cautious of is that edge collapse deletes the edge input as well as a couple other edges. In order to make certain the edge iterator doesn't throw errors, we make sure to increment the iterator if we encounter any of the deleted edges.

Lessons Learned

Results

Simplification using quadric errors.

Cow screenshot - no downsampling.
Cow screenshot - downsampled once.
Cow screenshot - downsampled twice.
Teapot screenshot - no downsampling.
Teapot screenshot - downsampled once.
Teapot screenshot - downsampled twice.

Simplification using edge length.

Cow screenshot - no downsampling.
Cow screenshot - downsampled once.
Cow screenshot - downsampled twice.
Teapot screenshot - no downsampling.
Teapot screenshot - downsampled once.
Teapot screenshot - downsampled twice.

Regularization

Bean screenshot - no regularization.
Bean screenshot - regularized.
Cow screenshot - no regularization.
Cow screenshot - regularized.

References

Contributions from each team member

Solo project.