Assignment 1-resit

Voxelisation with semantics

Deadline is June 17 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 implement a program that voxelises triangular mesh models while keeping their semantics. In order to do this, you are provided a model of the TU Delft campus as an OBJ file, which you will use as a use case. The model has semantics defined using objects (o) and materials (usemtl), which are stored in a separate MTL file. The output file should also be in the OBJ format, and it should keep the objects and materials from the input.

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 MTL file to get the available materials and their properties, which you can store in memory and assign each material an ID as you do so;
  2. parse and read the OBJ file into memory, keeping track of individual objects and storing a mesh for each;
  3. create a grid of empty voxels of the right size;
  4. voxelise the model using the three targets for 26-connectivity (Figure 1.7 in the handout), assigning each voxel the ID of the object present in it.

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, but copying/pasting significant parts of the code from other groups will be considered as cheating.

What you are given to start

hw1-resit.zip

This zip file contains:

  1. TUDelft_campus.obj, which is a model of the campus with semantics (created using 3dfier).
  2. 3dfier.mtl is a materials definition file from 3dfier. It defines the materials used in TUDelft_campus.obj.

In addition, you are welcome (and encouraged) to use the voxeliser code from Homework 1, in which 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.

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 TUDelft_campus.obj which was produced by your code.

Code

You should submit all the files that I need to run your code. 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 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.

We expect maximum 5 pages for the report (figures and graphs included). Don’t forget to write your names.

Voxelised model

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

Marking

Criterion Points
code compiles/runs without modifications 1
code outputs the voxelised/filled model 3
quality of model 2
report (quality/clarity) 4

What to submit and how to submit it

Submit your single compressed file by uploading it here.

[last updated: 2021-05-13 05:15]