~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~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. 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. 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:

``````
ab    b^2   bc   bd
ac    bc    c^2  cd
``````

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

``````
-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

• Downsampling preserves shape well (with quadric error metrics).
• Be cautious of how you iterate through the edges.

## Results      #### Simplification using edge length.      #### Regularization    ## References

• Botsch, Mario, and Leif Kobbelt. "A Remeshing Approach to Multiresolution Modeling." Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing - SGP '04 (2004): 185-92.
• Garland, Michael, and Paul S. Heckbert. "Surface Simplification Using Quadric Error Metrics." Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '97 (1997): n. pag.
• Gelas, Gouaillard, and Megason. “Surface Meshes Incremental Decimation Framework”. In: Insight Journal July-December (2008).
• The cmu code and specs

Solo project.