Assignment #2:
Mesh Simplifier

Submission date: Friday, 10/21/16, 23:59

Objective:

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.

Tasks:

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 Cartel, 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:
• Combine your simplifier with a progressive data-structure to allow mesh restoration to any size. Note that in this case you would need to store enough information to undo each vertex removal. In this case your API should support a restore operation that reverts the mesh to any previous size (number of vertices). Allowed sizes should be between the current and the original ones.
• Replace the basic vertec simplification metric with a volumetric error or other "smart" metric.
• Develop a method for smart hole triangulation which ensures that triangle normals do not flip (decide what to do if no such traingulation exists)

Instructions:

1. Download the latest version of Cartel which includes  UI support for your simplifier.
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. 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 and what you need to do is: compute the new poistion/error metric per edge; use this value to order edges in a queue; colapse the top edge (if the collapse is valid, i.e.does not create illegal topology); and update the queue accordingly.
4. In both simplifiers:
• Use the visualization functionality discussed blow to help you debug and test your code.
• Pay attention to efficiency and robustness.
• Try to support as many removal/collapse operations as possible without violating validity (crashing).
• While you should work independently, it is a good idea to compare your results with other students, to verify code correctness.
5. You can make the following assumptions in your work:
• Your simplifier should only work correctly on closed manifold meshes.
• You can use any available Cartel code for your assignment.
6. Your API should support the following mesh operations, performed repeatedly and in any order:
• Initialize the simplifier (compute error and order vertices in queue).
• Perform a single simplification step, removing one vertex and triangulating the hole (test triangulation validity).
• Simplify the mesh by a user specified amount (or alternatively to a user specified size).
7. To visualize the simplification process and ensure correctness use the visualization tools provided in Cartel to visualize the top 10 vertex/edge candidates for removal/collapse. Make sure that the color is updated on the fly after each simplification operation 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.

Submission:

• Write a README file containing your name and how to run your code.
• Send an email to Giorgio with the subject "[CPSC 524] Assign2" containing a zip file with your code and your readme file. Submit all and only the source files you changed.
• In the email write your name and contact e-mail address.
• All emails should be received by Friday, 10/21/16, at 23:59.

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.

Visualization:

First of all, make sure you download the latest version of Cartel (1.4) which contains the new visualization functionality. "EditMesh.cpp" contains a function "get_draw_colors" which populates an array of vertex colors. Change it for your purposes. A few notes:
• The default negative color (-1.0, -1.0, -1.0) just instructs the renderer to do normal shading with lighting.
• Colors are represented in RGB, where each value is between 0 and 1
• You have face index, vertex index and halfedge index of the halfedge starting at the vertex on the current face, use any of those to decide the vertex color
• Colors are per-vertex, and interpolated throughout the face: you can visualize faces, vertices, or even halfedges.
• Do not change the structure of the iteration, you need to preserve the index-based matching of vertices