Project 3: Simplification

due: 04/19/2022
submission: push to GitLab and copy link to Canvas quiz


objectives

  • implement a mesh collapse (contraction) operator using half-edges,
  • implement a mesh simplification algorithm.


getting started

As with the previous projects, copy the project template stored in src/flux-base/projects/project3/ into your repository in src/projects/project3/. This includes CMakeLists.txt, main.cpp, simplifier.h and simplifier.cpp. Remember to uncomment add_subdirectory(project3) in projects/CMakeLists.txt.


part 1: implement a mesh simplification algorithm (17 points)

Please implement the mesh simplification algorithm described in the notes for Lecture 13. Recall that there are two important pieces to this algorithm: (1) calculating the vertex, edge and face data and (2) implementing the collapse (contraction) operator. We practiced with the first ingredient in class (see Lecture 13, slides) so please revisit the exercises we did. Many of the functions we wrote in class can be directly used in your project.

implementing the collapse operator

The second ingredient consists of implementing the collapse (a.k.a. contraction) operator, which collapses an edge (a HalfEdge), thereby removing one vertex of the edge, and relocating the other to the optimal location (stored in vbar of the edge). Implementing this requires attentive bookkeeping when updating the half-edge entities affected by the collapse. Here is a summary of what to implement:

  1. Given an edge you want to collapse (with the highest priority), retrieve any relevant half-edge entity pointers around this edge (vertices, edges, faces).
  2. Perform check #1 described in the notes. In other words, extract the one-rings of the two endpoint vertices p and q, and reject the collapse if the number of common vertices in the one-ring is not equal to 2.
  3. Pick one of p or q as the receiving vertex (which remains in the mesh after the collapse), and the other as the deleted vertex.
  4. Re-assign the coordinates of the receiving vertex to those stored in vbar of the edge.
  5. Update all the pointers of the half-edge entities affected by the collapse. This part has a lot of potential for bugs, so you should draw a sketch to visualize how the entities are updated. You will submit this sketch in your final report.
  6. Recompute vbar, Qbar and cost of any edge affected by the collapse (remember to assign the collapsed edge Qbar to the Q of the receiving vertex).
  7. Update the priority queue by removing edges in the one-ring of the receiving vertex (including twins) and re-inserting them. We need to do this because the cost of these edges changes during a collapse.

When a collapse is performed, some half-edge entities are removed. In particular, one HalfVertex is removed, six HalfEdge's are removed and two HalfFace's are removed. Each of these can be removed from the HalfEdgeMesh container using the remove function. For example, to remove the entity associated with a HalfVertex* called p, you can use halfmesh.remove(p). For further information, please see the three remove functions in the documentation.

ordering the edges to collapse

Finally, you should maintain a priority queue of edges to collapse, such that we remove edges with the lowest cost first (lowest impact of collapsing the edge on the underlying geometry). You can use a std::multiset<HalfEdge*,CompareCost>, as described in the notes. Some definitions are provided in the project template (in simplifier.h) to help with this, notably the CompareCost structure, as well as the definition of the CollapsePriorityQueue via a std::multiset. Therefore, you can create a CollapsePriorityQueue to keep track of which edges to collapse (in order). Useful functions will be insert (add a new edge with a cost into the queue), erase (remove an edge) and begin (an iterator to the edge at with the highest priority). When a collapse is rejected (e.g. for topological reasons), you should still remove it from the priority queue. For more information, see the C++ documentation for a std::multiset: https://www.cplusplus.com/reference/set/multiset/. Note that this is just a recommendation - you are free to use a different method to keep track of the order in which you want to collapse edges. But you should still prioritize collapsing edges with a lower cost first. As we practiced with in class, be careful when updating your priority queue and the HalfEdgeMesh container - you should first remove edges that you no longer need from the priority queue, and then the HalfEdgeMesh.

visualizing the simplified mesh

After your mesh has been simplified to some target number of faces (triangles) nf_target, you can call halfmesh.extract(mesh) where mesh is the connectivity-based mesh structure that will be filled with the simplified mesh. You can then pass this mesh to a Viewer to visualize your simplified mesh.

testing your implementation

I highly recommend starting by testing your implementation with a Sphere mesh as defined in the initial project template. You should then test your algorithm with a mesh of your choosing as described in Part 3 below. We are assuming that our meshes are closed (no boundary), so you should use the HalfEdgeMesh::nb_boundary() function to ensure that there are 0 edges on the boundary for your initial mesh.

development tip

Don't try to get everything working at the same time. I would suggest starting with a mesh (maybe a Sphere with $N = 10$), pick some arbitrary HalfEdge to collapse and write a function to collapse it. You can visualize the result and verify that the edge was collapsed. There might still be some bugs with updating the half-edge entities, but it's a good start. Then try collapsing a handful of edges. If that works, proceed to collapsing many more (e.g. hundreds). If everything still seems to work, proceed to setting up a priority queue of edges. There might still be some bugs to sort out, since this priority queue needs to be updated whenever a collapse is performed.


part 2: implement an additional check on the validity of a contraction (1 point)

In the notes, a second check is proposed to determine the validity of a collapse. In particular, we can check if the normals of the affected faces in the one-rings of the edge endpoint vertices flip directions as compared to the original normals (before the collapse). It will be hard to see a difference in the final meshes, so just print out the total number of edge contractions which are rejected by this check (print it out to the terminal at the end of the simplification).


part 3: report (2 points)

In the README.md file, please include the following:

  • Include a sketch that your group created to visualize all the half-edge entities affected by the collapse operator. It's okay if this is hand-drawn - you can take a picture of your work (a whiteboard, or your notebook). If you take a picture from your phone, try to make sure the image size isn't too large (phones sometimes create images that are several MB). Since you are committing this image to your repository, it would be best to keep the image small (while keeping a reasonable resolution). There are several online tools for reducing image size, e.g. https://www.imagereduce.com/.
  • Include pictures of your simplified sphere mesh for a target number of triangles of $1000$, $100$ and $10$. The initial sphere mesh should be generated with $N = 100$ (which contains 19800 triangles).
  • Include pictures of simplified meshes where the initial mesh is a mesh of your choosing. Make sure this initial mesh is closed (no boundary, like a sphere). Some sample meshes are posted here, if you'd like to use those. Perform the simplification to three target numbers of triangles of your choosing, e.g. $1000$, $500$ and $100$.

Please leave your code in a compilable and runnable state. When typing make project3 your code should simplify the mesh (of your choosing) and provide the ability to render the initial and simplified meshes.
submission

After completing the code and your README, please push to your GitLab repository. Then copy a link to your project commit to this Canvas assignment. All group members should submit this link in Canvas.