Assignment #2:
Mesh Simplifier

Submission date: Friday, 3/1/19, 23:59


Implement vertex-removal and edge-collapses based mesh simplifiers. Experience the difference between understanding a geometry processing algorithm on a theoretical level and actually implementing it.


  1. (50%)  Implement a vertex-removal based simplifier with a basic simplification metric (sum of incident angles over 2*pi) - here you will need to write the removal and hole triangulation code yourself, as well as provide all the data-structures/visualization necessary to run and debug your method. 
  2. (50%) Implement an edge collapse based simplifier  - use the basic collapse operation provided by minimesh (v1.3, Mesh_modifier::collapse_edge()), combine it with the QSLIM metric discussed in class and the rest of the features necessary for a complete simplifier. 
  3. To receive a bonus you can: The size of the bonus will be at the discretion of the marker.


  1. Download the latest version of minimesh which includes  support for edge collapse (you can use this link).
  2. Implement a mesh simplifier based on vertex removal. Use the basic sum of angles over 2 pi metric. Your code should compute the metric for each vertex and store the vertices in a queue based on the metric. Based on a user input (provided via the simplifier window) it should simplify the mesh as instructed, by removing as many vertices as specified, in an order determined by the metric. The error metric should be updated as explained in class to reflect the changes in the mesh around the removed vertex. You must disallow vertex removals if they create illegal topology.
  3. Implement an edge collapse based simplifier based on the QSLIM metric discussed in class. Note that the basic collapse functionality is already provided (except checking for operations that making the mesh invalid) and what you need to do is: compute the new position/error metric per edge; use this value to order edges in a queue; collapse the top edge (if the collapse is valid, i.e.does not create illegal topology); and update the queue accordingly. You must disallow edge collapses if they create illegal topology.
  4. In both simplifiers:
  5. You can make the following assumptions in your work:
  6. Your API should support the following mesh operations, performed repeatedly and in any order:
  7. To visualize the simplification process and ensure correctness use the visualization tools provided in minimesh to visualize the top 10 vertex/edge candidates for removal/collapse. You can call Mesh_buffer::set_XXX_colors() to color the mesh, where XXX can be faces or vertices. Make sure that the color is updated after the user specified number of simplification operations is finished and that the current top candidate vertex/edge is highlighted.
  8. Test for illegal operations (e.g. running simplification when no mesh is loaded) and issue an appropriate error message if one is performed.


You can use your grace days (if you still have them). No late assignments, beyond those, will be accepted.

This assignment is 15% of your final grade.


First of all, make sure you download the latest version of minimesh. The "Mesh_buffer" class contains two function "set_face_colors" and "set_vertex_colors" which sets the colors of vertices or faces. Note that Mesh_buffer expects the colors to be in a continuous order. Therefore, if the mesh is fragmented the color of vertex i must be inside the defrag_map.old2new_vertices[i]th column of the matrix that you pass to "set_vertex_colors".