CS749: Digital Geometry Processing, Spring 2017

(Please check this page regularly for updates!)

Assignment 3: Shape Descriptors

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. Also, this project doesn't actually use OpenGL, but the capability to display meshes is there if you need it.)

Todo

In this assignment, you will write code to compute a shape descriptor of a mesh, and test it on the Princeton Shape Benchmark. Skeleton functions for two different descriptors are provided in main.cpp. You need to implement only ONE of them (you can do the other one for extra credit if you would like).

The program has the following usage:

Usage: ./meshdesc <mesh> [vol2bbox] [d2 <#points> <#bins>]

The relevant functions you need to complete are marked with "TODO" in main.cpp. Remember, you only need to complete ONE of the following sets for the basic portion of the assignment! The functions are:

• computeVolumeToBBoxRatio() [and its helper function computeVolume()]
• computeD2() [and its helper function samplePoints()]

You can add any other functions and code that you need, but do not change the signature or expected behaviour of the above functions.

For 20% extra credit (EC), implement both descriptors! If you make any errors in either, we will treat the function which is more correct as the basic portion of the assignment, and the less correct function as the EC.

Finally, test your descriptor(s) on the Princeton Shape Benchmark. This dataset has 907 training meshes from several classes, and 907 test meshes also divided into classes. You will work with only the test dataset (see the PSB paper).

• Generate features for each of the 907 meshes in the test dataset and save them either to one single text file or to multiple text files.
• Hold out each of the meshes in turn, matching it to the remaining 906. Find the top K = 1, 5, 10, 20 and 50 closest matches, using L2 distance between the descriptor of the query mesh and the descriptors of dataset meshes. You should not submit this code with the assignment, and you can use any language/tool you want (C++, Python, Matlab...).
• Measure precision and recall for the different values of K for all 907 possible queries.
• Report (in Readme.txt) the average precision and recall for each value of K. No need to plot it though you can do so if you want for your own benefit.

Submission Instructions

You need to submit your source code directory 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-A3. E.g. if your roll number is 123456789, then the directory should be called 12345689-A3.
• Copy your complete src folder to YourRollNo-A3.
• Delete the DGP subfolder from src. 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-A3. This file should list which descriptor(s) you implemented, and the average precision/recall values (for 5 different values of K) requested above.

Be very sure that you have the following folder structure:

YourRollNo
|
+-- src
|   |
|   +-- Common.hpp
|   |
|   +-- Mesh.cpp
|   |
|   +-- Mesh.hpp
|   |
|   +-- MeshEdge.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-A3.zip and submit it on Moodle. If you log in to Moodle, you should find an assignment called "A3: Shape Descriptors" 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.


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