(Please check this page regularly for updates!)

Assignment 2: Mesh Simplification

Preliminaries

We'll again use the DGP toolkit for this assignment. Remember to keep your master copy up-to-date using git pull origin master regularly!

Assignment code

Download the skeleton code for the assignment here. Make sure you have GLUT installed, and copy the DGP/DGP subfolder to src/.

(For convenience, you can rename Makefile.<os> to Makefile, to avoid having to pass the -f argument each time.)

If the build succeeds, run ./simplify data/bunny_200.off. A window like this should pop up:



Use the mouse to rotate the view, hold down Shift while dragging up/down to zoom in/out, and press 'F' to center and fit the shape in the window. Press 'B' to see the shape's bounding box, 'E' to show the mesh edges, and 'Esc' to quit.

Todo

In this assignment, you will write code to simplify a mesh using quadric error metrics, following the Garland/Heckbert paper we studied in class.

Here is a video of what the process should look like, starting with the bunny above. The interface is set up so that by pressing the 'D' key, you can repeatedly apply exactly one simplification step -- a single edge collapse. The vertex resulting from the collapsed edge is highlighted in red.



NOTE: Your results need NOT look exactly like this, but they should look similar.

The program has the following usage:

Usage: ./simplify <mesh-in> [<target-num-faces> [<mesh-out>]]

You can do the simplification non-interactively by specifying a target number of faces on the command line. To save the result out to disk, add a third argument which is the path to the target file in the OFF format.

Note that the simplify executable functions as a standalone viewer: as long as you don't pass a target number of faces, it will load and display the mesh without changing it until you press 'D'. This is useful for checking the saved output.

The relevant functions you need to complete are marked with "TODO" in the code. They are:

I suggest you attack them in the above order. Remember to take full advantage of existing functionality in the classes, otherwise your life will be much harder.

This time, you should NOT change stuff in the code substantially, unless you're implementing the extra credit. Just flesh out the above functions. Definitely don't change DGP in either case (unless there's a bug, in which case please inform me).

For extra credit, you can try implementing the following:

Strategy

This assignment is trickier than it looks. Meshes are considerably harder to deal with than point clouds. I suggest you spend enough time at the beginning studying the Mesh class, which stores a mesh as a graph of adjacencies between vertices, edges and faces. This is an excellent learning exercise and will serve you well in the future.

Be careful, there are many pointers in there! It's incredibly easy to mess up and have dangling pointers/iterators, and C++ as a language doesn't make our job any easier. So be careful.

As an example of things that can go wrong, recall last year's midsem question on updating adjacencies after an edge flip. What would happen to the mesh if you forgot to correctly change even one of the pointers?

Also, the following C++ program is likely to crash. Can you see why?

std::list<int> numbers;

numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);

for (auto ni = numbers.begin(); ni != numbers.end(); ++ni)
  if (*ni == 2)
    numbers.erase(ni);

Always start with the documentation: run Doxygen in the doc subfolder and check out doc/html/index.html.

There are several test meshes in the data subfolder. Start with the simplest one: cube.off. There you can work out by hand how the simplification should proceed, and compare your results with this. Progress slowly to the more complex meshes.

Finally: the assert(...) statement (and similar checks) is your friend. Use it liberally to make sure invariants hold after any incremental change in the mesh.

Evaluation

We will evaluate your code on test meshes that we will not release with the assignment. So we encourage you to test on as much data as you can find before submitting! (We'll share more data soon.) Look for corner cases.

Submission Instructions

You need to submit your source code directories -- separate ones for the basic assignment and for the two EC's -- and a Readme. Please follow these instructions EXACTLY.

Be very sure that you have the following folder structure (src_EC1 and src_EC2 are optional):

YourRollNo
|
+-- src
|   |
|   +-- Common.hpp
|   |
|   +-- Mesh.cpp
|   |
|   +-- Mesh.hpp
|   |
|   +-- MeshEdge.cpp
|   |
|   +-- ...
|
+-- src_EC1
|   |
|   +-- Common.hpp
|   |
|   +-- Mesh.cpp
|   |
|   +-- ...
|
+-- src_EC2
|   |
|   +-- Common.hpp
|   |
|   +-- Mesh.cpp
|   |
|   +-- ...
|
+-- Readme.txt

Please do NOT include any other files! No data files, binary files, etc.

Now zip this folder (do NOT use .tar, .tar.gz, .rar, .7z or any other format), calling it YourRollNo-A2.zip and submit it on Moodle. If you log in to Moodle, you should find an assignment called "A2: Mesh Simplification" set up.

FAQ