(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/.
- Linux: Run make -f Makefile.linux
- OS X: Run make -f Makefile.osx
- Visual Studio: Create a new project and add the relevant source files (plus the GL, GLU and GLUT libraries) to it.
(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:
- MeshVertex::updateQuadric()
- MeshEdge::updateQuadricCollapseError()
- Mesh::decimateQuadricEdgeCollapse()
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:
- (EC1, 10%) Use a priority queue or similar data structure, stored with the mesh, to accelerate the search for the edge with the minimum collapse error instead of a brute force loop over all edges. Note that you can't recreate this queue every time Mesh::decimateQuadricEdgeCollapse() is called, since the construction time will outweigh the cost of the loop. Also remember that you will need to hack Mesh::collapseEdge() and Mesh::mergeEdges() to remove edges from the queue as they are removed from the mesh. To see if you're actually getting any speed gains, I suggest trying to (non-interactively) simplify bunny_40k.off to say 500 faces. This might yield smaller speedups than you expect. Can you figure out why? [EC1 seems relatively straightforward but is not. It's very easy to accidentally include a linear-time step somewhere. E.g., how do you remove an element from a priority queue in sublinear time?]
- (EC2, 20%) Try collapsing "virtual edges" between nearby vertices, to simplify meshes with disconnected components. You can choose any appropriate threshold, based on the overall size of the shape, to define "nearby". See the paper for details. [This can be quite challenging.]
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.
- Do a 'make clean'. You should submit NO binary files.
- Create a new directory somewhere called YourRollNo-A2. E.g. if your roll number is 123456789, then the directory should be called 12345689-A2.
- Copy your complete src folder for the basic part of the assignment to YourRollNo-A2. This should be your submission for the BASIC part of the assignment and nothing else (no EC's).
- Copy your complete src folder for EC1 to YourRollNo-A2 as src_EC1. This should be your submission for the EC1 part of the assignment, if you have completed it. Do not include solutions for EC2 here.
- Copy your complete src folder for EC2 to YourRollNo-A2 as src_EC2. This should be your submission for the EC2 part of the assignment, if you have completed it. Do not include solutions for EC1 here.
- Delete the DGP subfolder from src, src_EC1 and src_EC2. We will use our copy of DGP for evaluation, don't submit this along with your own code.
- Add a file called Readme.txt to YourRollNo-A2. This file should list: (a) whether you did EC1, and a sentence or two describing the algorithm you used, (b) whether you did EC2, and a sentence or two describing the algorithm you used, (c) what parts of the basic assignment (not the ECs) you could not do.
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
-
What format are the meshes in? What's .off?
OFF is a simple and standard format for storing 3D meshes. It's extremely limited (e.g. it can't store different parts of an object as individual components), but is very easy to read and write, and is good enough for our purposes.
It's fully documented here: http://segeval.cs.princeton.edu/public/off_format.html. It's a useful exercise to write an OFF file (e.g. for a cube or tetrahedron) by hand in a text editor.
-
I'm getting vertex positions in crazy places even though my math seems correct.
Do recheck your math carefully, but also make sure you're not suffering from problems with limited numerical precision. I faced problems when using single-precision floats for the quadric terms. Switching to double-precision fixed matters.
-
How can I check if a matrix is invertible?
The magnitude of the determinant should not be too small.
-
Can we do assignments in pairs/groups?
Nope, sorry. Assignments are individual exercises.
-
What's the ethics code?
A common sense notion of fairness. As rules of thumb:
- Copying: Don't copy code from anywhere. Any code you submit must be written by you (but see Question 3). I won't stop you looking at other people's solutions to similar problems online, but I encourage you to at least try to figure out the solution for yourself. If the goal is to learn something from the course, you're doing yourself a disservice by not giving it a fair shot.
- Discussion: It's ok to discuss approaches with classmates, but I again strongly encourage you to first try to figure it out yourself. And again, you must write your code yourself without looking at your peers' code. We will penalize copied code (and we have good ways to detect this so don't try changing variable names etc).
- What do "look" and "discuss" mean? "Look" and "discuss" are probably more restrictive than you think. I am on the departmental academic disciplinary action committee (DADAC), and we have already heard several cases of people clearly, and possibly unknowingly, abusing the right to discuss with peers. You can discuss or look at approaches at the broad algorithm level. You can look at published source code on the web. You CANNOT look at each other's code, or copy even a single line of code from anywhere. Do not show or email others your code. It is extremely easy to detect copying (from your peers or from the web), even if you think you've covered your tracks well. If you were not caught copying in an earlier class, it's because the instructor was too busy to run the necessary checks, not because you did a good job obfuscating your actions. To consistently fool an automated plagiarism checker (plus manual grader spot checks), you'll have to put in as much work as to just write the code by yourself.
- Acknowledgments: If you refer to a resource (website, person, program...) other than the lectures, please acknowledge it in the README you submit along with your assignment. You will not be penalized for the reference -- background research is always good -- and we should get into the habit of acknowledging our sources.
- Penalties: If you're caught violating the ethics code, the penalty for a first offence is typically zero on the assignment and a one-letter-grade reduction. Penalties for second and subsequent offences are considerably more severe. Both the giver and receiver of code are penalized equally. For more, see "Procedures for handling acts of academic malpractices by students" and "Academic Malpractices - punishments".
- But what if I need, say, some heavy-duty but standard-issue math code which would be a total pain to write from scratch?
If you need something like this for any assignment (e.g. a good sparse solver) that's ok, you can use an existing library (as long as it doesn't need to be separately installed but can be compiled in one step along with your own code, without external dependencies). But check with us first. Email me (Sid) giving particulars of what you want to use and why. I'll try to respond quickly.
That said, you're unlikely to need anything extra for this assignment.
-
Is there a coding style guideline?
Nothing set in stone, but please please please write your code in good style. Which means: proper and consistent naming conventions; proper indentation; reasonable limits on line length; judicious use of spaces etc. It also means proper comments and documentation. Otherwise it's hell for others to read, and most likely also hell for you to maintain.
My coding style is pretty obvious from the skeleton code and DGP, but you don't have to follow it. Just pick something that's neat, consistent and readable and stick with it.
That said, if you're editing a file written by someone else, it's usually a good idea to follow their style, just to keep the whole file consistent. For the assignment, feel free to reformat any source file according to your own conventions. I like astyle for this purpose.
-
Can I approach the course staff if I am stuck/have a question?
Yes, of course, that's what we're there for! You can also talk to your peers, see above.