Assignment 1: Point Clouds
Preliminaries
For the assignments in this course, you will be using a toolkit that contains basic classes and functions, including vector and matrix math, geometric transformations, binary and text file I/O, system utilities, and (optionally) an OpenGL-based display module. Visit http://github.com/sidch/DGP and check it out following the instructions. Then, read the Doxygen-generated HTML documentation, and subsequently dig into the code as needed. This toolkit is likely to be updated as the course progresses, so keep your master copy up-to-date using git pull origin master. (Recent bugfix, please update.)
Assignment code
Download the skeleton code for the assignment here: A1.zip, and additional data for testing here: PointClouds.zip. 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.
If the build succeeds, run ./pcloud data/teapot.pts. A window like this should pop up:
Use the mouse to rotate the view. Press 'B' to see the shape's bounding box, 'N' to hide the point normals, and 'Esc' to quit.
Todo
In this assignment, you will write code to estimate the surface normal at each point of a point cloud. In other words, given data/teapot_no_normals.pts, you should produce something like data/teapot.pts. You can use any method whatsoever, including those not discussed in class. Correctly implementing linear regression on local neighborhoods (as discussed in class) is enough for full credit. (Hint: the Matrix3 class has the eigenvalue function you need.) To find the points in a local neighborhood, you must complete and use the PointKDTree class.
For extra credit, you can try implementing the following:
- (EC1) Ensure the normals are consistently oriented (either all inside-to-outside, or all outside-to-inside).
- (EC2) Handle sharp edges correctly. The normal field should have a discontinuity at such edges, instead of getting smoothed out by standard regression.
- (EC3) Adaptively downsample the point cloud: reduce the number of points in smooth regions with similar normals
The relevant functions are marked with "TODO" in the code. They are:
- PointKDTree::PointKDTree() (basic)
- PointKDTree::rangeQuery() (basic)
- PointCloud::estimateNormals() (basic + EC1 + EC2)
- PointCloud::adaptiveDownsample() (EC3)
This skeleton is given only as a guidance. You're free to change anything you want in the code, add functions, add files, etc. Just don't change anything in DGP (unless something is broken, in which case let me (Sid) know ASAP).
The program has the following usage:
Usage: ./pcloud [OPTIONS] <points-in> [<points-out>] Options: --normals : Estimate the normal at each point --downsample : Adaptively downsample the points
If you supply either of the options, the point cloud will be processed accordingly. If you also supply <points-out>, the result will be saved to that disk file. Else, the processed points will only be displayed in the interactive window.
Evaluation
We will evaluate your code on test point clouds that we will not release with the assignment. So we encourage you to test on as much data as you can find before submitting! Look for corner cases. You may do any subset (including, obviously, zero) of the ECs. The first two ECs you do (any two) count for 10% each. The third counts for 5%.
Submission
Please email your submissions to the course staff (Sid + both TAs, emails on main page) using EXACTLY the following format:
-
Subject: [CS749-A1] <LDAP-ID>, <Full Name>
For example, my subject line would be "[CS749-A1] 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>-A1.zip (lowercase). E.g. for me that would be schaudhuri-A1.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
-
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. -
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.