Objective:

Tasks:

1. Implement a vertex-removal based simplifier with a basic simplification metric (sum of incident angles over 2*pi). Have a UI in place to repeatedly remove one vertex at a time and triangulate the resulting hole (70%).
2. Develop an interface (and data structures) for your simplifier that allow the user to efficiently remove any number of vertices in one step (10%).
3. Develop an effective visualization mechanism for your algorithm to show the next 10 verts to be removed (5%)
4. Either develop a method for smart hole triangulation which ensures that triangle normals do not flip (decide what to do if no such traingulation exists) OR implement a more sophisticated eror metric such as distance to the approximating plane of the neighboring vertices or a volume metric. (15%)
5. 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.
   • Replace the basic simplification metric with a volumetric error.

Instructions:

1. Implement a mesh simplifier based on vertex removal. Start with a basic sum of angles over 2 pi metric and then (if you choose) replace with the distance to plane and/or volumetric metrics 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 the removed 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.
2. 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.
3. 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).
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. Following the assignment specification is some code to help you with visualizations.
   • Once the simplifier is initialized you should visualize the top 10 vertex candidates for removal. The color should be updated on the fly after each simplification operation. Please also highlight the current top candidate vertex.
   • 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. To receive a bonus you can implement a progressive mesh data structure allowing you to restore the mesh to any size. 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.

Submission:

Hints

Simplification amount

• Bind fixed intervals to, for example, the number keys. With suggested scales of powers of 10. (1, 10, 100, 1000, ...)
• Read in a user input from the command line. This would need to be triggered via a key press. Read in with your favorite user input method, (fgets, fread, scanf, etc.) and then processed. Be aware that anything waiting for input will likely stall the program until a number is provided.

Visualization

• "MeshUtils.h" has a function called drawGem that can be modified to take a color. You can render small octahedrons at the locations of the top ten verts. This is not pretty, but will be fast. Recommended for those unexperienced with graphics.
• You can pass a new array of colors to the shaders, per vertex. With each vertex's color specified. You would need to loop over all vertices in this case, decide what color they should be and specify it in the array. An example of this can be seen below:
  • Your code in main would resemble this:

  
        // create your array of colors
        glm::vec3 *color     = new glm::vec3[3*num_verts];
        // zero it
        memset(color,      0, 9*num_verts*sizeof(float));
  
        for(int i = 0; i < num_verts; i++) {
          /* populate the array */
        }
  
        r_state[0]->bindVAO();
  
        // bind the color array to shader slot 2 (which will be specified in the shader)
        r_state[0]->setBufferData(2, 3*num_faces*sizeof(color[0]), (unsigned char*)color);
        r_state[0]->setAttributeData(2, 3, 0, 3*sizeof(float));
        

  • inside mesh.vs.glsl you can change the second input binding to be:

  
        layout (location = 2) in vec3 Color;
        

  • you then need to pass it to the fragment shader, where the vertex color is determined in:

  
        if ((view_mode & 0x4) != 0) { // verts
            out_color = mix(vec4(1, 0, 0, 1.0), out_color, vertIntensity);
        }