(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. 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) 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 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) 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 the 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);
I initially wanted you to write the Mesh::collapseEdge() function as well, but after going through the exercise myself, I thought I'd spare you the incredible pain of debugging all the pointer updates. Take a look at the function and try to understand how it works, it's good practice. By the way, I'm not 100% sure it's correct myself, so if you find it doing wonky things please let me know at once.
With this in mind, I've tried to avoid making you write any low-level code to tweak adjacencies in the mesh. You can call Mesh::collapseEdge() to directly collapse an edge. That said, it's good to be aware of how things are done, and you will need to roll up your sleeves and do the dirty work if you tackle EC2.
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
Please email your submissions to the course staff (Sid + both TAs, emails on main page) using EXACTLY the following format:
-
Subject: [CS749-A2] <LDAP-ID>, <Full Name>
For example, my subject line would be "[CS749-A2] schaudhuri, Siddhartha Chaudhuri". Please follow this format precisely else our mail filters won't work.
-
Body: Leave blank unless you have something very specific to add.
-
Attachments: Attach a single zip file, named <LDAP-ID>-A2.zip (lowercase). E.g. for me that would be schaudhuri-A2.zip The zip should contain:
- Your src subfolder, without any .o, .obj, pcloud or other executable files, and without the DGP folder. If you attach executables, mail servers are quite likely to reject them, and we'll have no record of your submission. Please don't send us any data files either.
- A README file documenting (a) The OS and compiler you used (but your code should be cross-platform), (b) the extra credit portions you did and how to run them (if not obvious), (c) which resources you used and/or people you discussed with, and (d) any other comments.
Yes, multiple submissions are ok, but only the most recent one will be considered (going by email timestamp).
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?
See if the magnitude of the determinant is 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:
- Don't copy code from anywhere. Any code you submit must be written by you (but see next question). 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.
- 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. We will penalize copied code (and we have good ways to detect this so don't try changing variable names etc).
- 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.
- 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.