Submission date: Friday, 10/10/08, 23:59

Objective:

Implement a quadric-based mesh simplifier. Experience the difference between understanding a geometry processing algorithm on a theoretical level and actually implementing it.

Tasks:

1. Implement a quadric error metric based simplifier.

2. Develop a user friendly API for your simplifier

3. Develop an effective visualization mechanism for your algorithm.

4. Bonus: Combine your simplifier with a progressive data-structure to allow mesh restoration to any size (15%).

Instructions:

1. Implement a mesh simplifier based on edge collapse with the quadric error metric described in class. It should compute the metric for each edge and store the edges in a queue based on the metric. Based on a user input (see item 3 below) it should simplify the mesh as instructed by collapsing as many edges as necessary, in an order determined by the metric. The error metric should be updated as explained in class to reflect the "history" of each vertex. Disallow edge collapses if they create illegal topology.

• Pay attention to efficiency and robustness.

• Bonus: implement a progressive mesh data structure allowing you to restore the mesh to any size.

2. You can make the following assumptions in your work:

• Your simplifier should be restricted to edge collapse operations, no need to merge together vertices which do not share edges.

• Your simplifier should work on closed manifold meshes.

• You can use any available GRAPHITE code for your assignment (including the progressive mesh bits).

3. Your API should support the following mesh operations, performed repeatedly and in any order:

• Initialize the simplifier (compute error and order edges in queue).

• Perform a single simplification step, collapsing one edge.

• Simplify the mesh to a user specified size (number of vertices).

• Bonus: Restore the mesh to any previous size (number of vertices). Allowed sizes should be between the current and the original ones.

4. To visualize the simplification process and ensure correctness you should provide the following visualization tools (similar to the demo in class). You should provide an interface option (e.g. menu button) allowing the user to switch the visualization on and off.

• Once the simplifier is initialized you should visualize the top 10 edges candidates for collapse, coloring them on the scale from blue to red depending on the size of the error , with red being the top candidate for collapse. The color should be updated on the fly after each simplification operation.

• You should highlight the current top candidate edge to be collapsed.

• You should provide an option to select any edge in the mesh (click on it) and print out the error associated with this edge and the coordinates of the vertex that would replace it if it were collapsed.

• You should provide an option to find the current sizes (numbers of faces, edges and vertices) in the mesh at any point.

• Please provide any additional useful visualizations you can think of.

5. Test for illegal operations (e.g. running simplification when no mesh is loaded) and issue an appropriate error message if one is performed.

6. Provide a README explaining clearly how to run your method & activate all the different features it has. Note though that ideally your code should be self-explanatory...

7. By default the assignment should be done separately by each student. If you want to do the assignment together with another student, you would need to implement the bonus part to get full marks.

8. While you should work independently, it is a good idea to compare your results with other students, to verify code correctness.

Submission:

Send an email to Alla (sheffa@cs.ubc.ca) with the subject “DGP assign2” containing a zip file with your code. Submit your sources only – you must include the entire source-tree for your quickStart module. (If you submit a MeshMaker code, provide an executable and the modified source files).

Don't forget to include a README file explaining how to run your code.

In the email write your name and contact e-mail address.

All email should be received by Friday, 10/10/08, at 23:59.

No late submissions will be accepted.

This assignment is 15% of your final grade.