Assignment 1

Voxelisation

Deadline is March 04 at 11:59 pm

Late submission? 10% will be removed for each day that you are late.

The assignment is worth 20% of your final mark.

voxelised model

Overview

The aim of this assignment is to calculate the total volume of the buildings of the Faculty of Architecture and the Built Environment (main building + bouwpub). In order to do this, you are provided a triangular mesh of the faculty buildings as an OBJ file, which you will have to voxelise and fill. For this, you will use the method described in Lesson 2.1, which uses intersections between the model and specially designed targets.

The suggested steps to achieve this task are:

  1. parse and read the OBJ file into memory
  2. create a grid of empty voxels of the right size
  3. voxelise the model using the three targets for 26-connectivity (Figure 1.7 in the handout)
  4. fill the interior of the model
  5. compute the volume based on the number of voxels

For this assignment, you are allowed to work in a group of 2 (and thus to submit one solution for both of you). If you prefer to work alone it is also fine.

Discussing your solution with your classmates outside your group is very much encouraged. In other circumstances, this would be done in the (Geo)lab, but since this is not an option, you are asked to have at least one meeting with another group. In this meeting, each group should describe how they’re attempting to solve the problem, the results that they’re getting (so far) and provide feedback to the other group. Just take this into account: high-level discussions are a great way to improve your solution, but copying/pasting significant parts of the code from other groups will be considered as cheating.

What you are given to start

hw1.zip

This zip file contains:

  1. bag_bk.obj, which is a model of the faculty buildings (courtesy of Ravi). We made no effort to make it valid/manifold.
  2. voxeliser, which is a folder containing some initial code to help you get started.

In voxeliser you will find:

  1. Point.h, which is a structure to store 3D points/vectors with some convenient functions to do simple operations (eg creation using Point p(x,y,z), accessing a coordinate as p[0], vector addition/substraction as p+q or p-q, multiplication/division with a scalar as p*s or p/s, dot/cross product as p.dot(q) or p.cross(q), and one to write the coordinates of a point using std::cout << p).
  2. Rows.h, which is a structure to store a triplet of rows representing a specific voxel in the voxel grid. It also has some convenient functions.
  3. VoxelGrid.h, which is a structure to represent/manipulate a voxel grid of a given size (as VoxelGrid voxels(rows_x,rows_y,rows_z)). It has a function to access and modify the value of a specific voxel (as unsigned int v = voxels(x,y,z) or voxels(x,y,z) = 1).
  4. main.cpp, which is the main file that you can write/run. There are some functions that you might want to fill out (or not).

How to compute triangle-line segment intersections

The key part of your implementation will be creating a function that can tell you whether a triangle and a line segment intersect. This can be done in different ways, and you are free to choose whatever method you prefer. For instance, you could use a version of the Möller–Trumbore intersection algorithm (with an additional condition to check for distance to the origin at the end).

However, our suggestion is to use instead a more robust method based on a series of orientation tests.

The signed volume of a tetrahedron with vertices a, b, c and d is given by 1/6 * dot(a-d, cross(b-d, c-d)). This volume is positive if d lies on the positive side of the oriented plane passing through a, b and c (right-hand rule), negative if d is on the negative side of the plane, and 0 if it is on the plane. This method works well as long as the tetrahedron is well-shaped (ie not a sliver).

Based on this knowledge, we know that a line segment intersects a triangle if and only if:

Test: endpoints on opposite sides

test 1

Test: two other vertices on opposite sides (x3)

test 2

So, that would be a maximum of four or five tests (depending on your implementation) per line segment-triangle intersection.

With a good implementation, your triangle-line segment intersections can be quite fast using this method, but getting good performance relies on minimising the number of intersection tests you have to make. A good heuristic for this is that a voxelised triangle can only have voxels (partly) within the bounding box of the original triangle. So, you can first compute the axis-oriented bounding box of a triangle (ie its minimum and maximum x,y,z coordinates), and then only compute the intersections for the voxels (partly) within the bounding box.

How to fill the interior of the model

This is easy. Start from a voxel that you know is in the exterior of the model, then recursively fill its neighbours that are empty (ie marked as 0 if you use the default in VoxelGrid.h). What is left empty at the end of this process is in the interior of the two buildings.

Tips

Deliverables

You have to submit one zipped file (or another compressed format) containing:

  1. Your code.
  2. Report in PDF format (please no Word).
  3. A voxelised version of bag_bk.obj produced by your code.

Code

You should submit all the files that I need to run your code. The code should output the final volume computed and write the final (ie filled) voxel model to an OBJ file. Everything should be implemented in C++ using only libraries from the C++ Standard Library.

Report

You need to submit a simple report outlining your work. It should document your volume calculation, explain briefly how you implemented the key parts of the algorithm and why you chose to implement them in this manner. Focus on high-level descriptions of how things work, not on explaining your code line by line. Discuss the pros and cons of your method, assess the quality of your results and the performance of your code. We don’t expect perfect results—just document honestly what works well and what doesn’t.

Use a small section of your report to describe how the other group you met was progressing (at the time you met). Focus on what they’re doing differently.

We expect maximum 5 pages for the report (figures and graphs included). Don’t forget to write your names and the names of the people from the other group you met.

Voxelised model

The voxelised model should be produced with your own code using 1-meter voxels or smaller.

Marking

Criterion Points
code compiles/runs without modifications 1
code outputs the voxelised/filled model 3
code computes the correct volume 2
report (quality/clarity) 3
discussed with another group 1

What to submit and how to submit it

Submit your single compressed file by uploading it here.

[last updated: 2021-02-15 02:34]