Assignment #2:

Mesh Simplifier

# Submission date: Friday, 2/17/12, 23:59

Objective:

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

1.      Implement a vertex removal based simplifier.(65%)

2.      Develop a user friendly API for your simplifier (10%)

3.      Develop an effective visualization mechanism for your algorithm (10%)

4.      Alternatively (15%):

Combine your simplifier with a progressive data-structure to allow mesh restoration to any size

OR Use knowledge acquired in class to minimize the simplification error (measured as distance to original model). The grade for this part will be given on a competitive basis by ranking your result against your peers.

Instructions:

1.      Implement a mesh simplifier based on vertex removal with the distance to plane metric described in class. It should compute the metric for each vertex and store the vertices in a queue based on the metric. Based on a user input (see item 3 below) it should simplify the mesh as instructed by removing as many vertices as necessary, 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 each vertex.  Disallow vertex removals if they create illegal topology.

Pay attention to efficiency and robustness.

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

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

Your simplifier should work on closed manifold meshes.

You can use any available MeshLab code for your assignment.

2.      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 a vertex and triangulating the hole (test triangulation validity).

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

3.      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.

HINT:To set the color of a vertex, you can simply do this

`m.vert[0].C() = vcg::Color4   (255,0,0,255);`
` `

4.      In order to visualize the colors, in Render|Color switch to Per Vertex.

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

You should highlight the current top candidate vertex.

You should provide an option to select any vertex in the mesh (click on it) and print out the error associated with this vertex.

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.      The assignment so far will give you 85% of the grade. To get the remaining 15% (and a potential bonus) you can either:

Implement a progressive mesh data structure allowing you to restore the mesh to any size. In this case you 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.

Improve upon the basic simplification through the use of a better error metric as well as sophisticated hole triangulation strategies.  To measure result quality use METRO (http://vcg.isti.cnr.it/activities/surfacegrevis/simplification/metro.html).  The grading for those who choose this option will be on a competition basis, by evaluating METRO error on a set of random models and different amounts of simplification. The student with the best score will get a 10% bonus, the runners up will get 6% and 3% respectively, the rest will be distributed based on relative score and improvement above the basic method.

7.      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...

Submission:

Send an email to Mikhail (bmpix@cs.ubc.ca) with the subject “DGP assign2” containing a zip file with your code. Submit your sources only.

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, 2/17/12, 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 17% of your final grade.