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.
Assignment code
Download the skeleton code for the assignment here: A1.zip [Updated Feb 2 23:20]. 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/cube.pts. A window like this should pop up:
Use the mouse to rotate the view, and hold down Shift while dragging up/down to zoom in/out. Press 'B' to see the shape's bounding box, 'N' to show the point normals, 'F' to center and fit the shape in the window, and 'Esc' to quit.
Todo
In this assignment, you will write code to estimate planes in a point cloud using the RANSAC algorithm, using a kd-tree to accelerate plane-testing. Two sample point clouds with 50K and 200K points respectively are provided in the data subfolder (more data here: extra_data.zip). Here they are next to the meshes they were sampled from.
 |
 |
 |
 |
Each plane that you detect will be displayed in the viewer, in white with a yellow border by default, like so:
We recommend you approach the problem in two steps. First, implement RANSAC without using a kd-tree, just a linear iteration over all points for each candidate plane. Second, complete the kd-tree implementation, and make sure the results match those from linear iteration. (It can help to fix the random number seed to ensure the same candidate planes are tested by both variants.)
For extra credit, you can try implementing the following:
- (EC1) Use point normals (all the dataset point clouds have per-point normals) to sample better candidate planes and thereby reduce the required number of iterations. Remember that the provided normals may not point consistently in or out of the shape! Press 'N' to view the normals.
- (EC2) Adaptively downsample the point cloud: reduce the number of points in flat regions. This is trickier than it might appear since you have to maintain relatively high point density at the edges of the region where it transitions to sharper (non-flat) detail.
The relevant functions are marked with "TODO" in the code. They are:
- PointCloud::ransac (basic + EC1)
- Slab::contains (basic)
- Slab::intersects (basic)
- PointKDTree::build (basic)
- PointKDTree::rangeQuery (basic)
- PointCloud::adaptiveDownsample (EC2)
We recommend you implement them in this order (revisiting PointCloud::ransac after completing Slab and PointKDTree). Please follow all specs in the documentation exactly! In particular, study how the Point::enabled flag is used to handle detection of multiple planes -- all points matching a fitted plane are disabled for subsequent detections.
This skeleton is a basic template. You're free to add functions, add files, modify stuff etc. But please (1) do not change the signatures or specifications of any of the functions listed above, (2) do not change any print statements already in the code (we will use the information printed by them for evaluation), and (3) do not 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:
--ransac <N> <iters> <thickness> <min-pts> :
Extract N planes using RANSAC with the given parameters
--downsample : Adaptively downsample the points based on the planes
detected by the RANSAC operation (needs --ransac)
If you supply the options, the point cloud will be processed accordingly. If with --downsample you also supply <points-out>, the result will be saved to that disk file. Else, the downsampled 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. EC1 counts for 5%. EC2 counts for 10%.
Submission Instructions
You need to submit just 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-A1. E.g. if your roll number is 123456789, then the directory should be called 12345689-A1.
- Copy your src folder to YourRollNo-A1.
- Delete YourRollNo-A1/src/DGP. 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-A1. 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:
YourRollNo | +-- src | | | +-- Common.hpp | | | +-- Point.hpp | | | +-- PointCloud.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-A1.zip and submit it on Moodle. If you log in to Moodle, you should find an assignment called "A1: Point Clouds" set up.
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:- 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. -
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.