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.
In implementing mesh simplification and regularization, the first step is to write the
edge_flip functions. Since
edge_flip were both part of homework two, I only discuss
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_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_b as well as
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:
a^2 ab ac ad ab b^2 bc bd ac bc c^2 cd ad bd cd d^2
N=(a,b,c) is the normal vector of the plane and
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.
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.
For the mesh regularization, we simply implement the following:
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.