Assignment 02

Voxelisation

Deadline is 16 March 2020.

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

You’re allowed for this assignment to work in a group of 2 (and thus submit only one solution for both of you). If you prefer to work alone it’s also fine.

voxelised model

Overview

The aim of this assignment is implement a program that voxelises triangular mesh models while keeping their semantics. The input models will be in the OBJ format and can have semantics defined using objects and materials (in an MTL file). The output files should also be in the OBJ format, and it should keep the objects (o) and materials (usemtl) from the input.

For this, you will use the method described in Lesson 3.1, which uses intersections between the model and specially designed targets. Your output model should have 26-connectivity.

The exact steps to achieve this task are for you to figure out. But if you are unsure about the best way to approach this, feel free to discuss your methodology with us (lab/discussion forum)!

Everything should be implemented in Python. You can use anything in the Python Standard Library. The only external modules that you are allowed to use for your computations are numpy and scipy.

What you are given to start

hw02.zip

This zip file contains three files:

  1. bag_bk.obj is a model of the faculty building without semantics (courtesy of Ravi). It is similar to the one from Assignment 1, but we made no effort to make it valid/manifold.
  2. TUDelft_campus.obj is a larger model of the whole campus area with semantics (created using 3dfier).
  3. 3dfier.mtl is a materials definition file from 3dfier. It defines the materials used in TUDelft_campus.obj.

You probably want to start with very simple models (such as a single triangle or the cubes from Assignment 1), then get the bag_bk.obj model working, use parts of TUDelft_campus.obj to get semantics working, and only attempt the whole file once you have fast code.

If you want another challenge, there is an experimental LoD2 model of Delft here. Bear in mind that there are several validity problems in this dataset (which is typical of many files in practice).

Apart from these files, there are OBJ files all over the internet. You can also find some other city models here.

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 modified 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 tests per line segment-triangle intersection.

Performance considerations

With a good implementation, your triangle-line segment intersections can be quite fast, but the key to getting good performance is to minimise the number of intersection tests you have to make. Consider the order of iterations, do easy optimisations and avoid all unnecessary intersection tests (ie when you can know in advance that they are impossible).

Data structure to use

You are free to use whatever you want.

That being said, a good option is a 3D matrix from Numpy (numpy.ndarray) of a very compact type. A sparse representation would be nice considering all the empty voxels, but you will definitely need hashing/indexing to achieve good performance.

Tips

Deliverables

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

  1. Your code. The main file (the one that I will run) needs to be named geo1004_hw02.py and follow the specifications below.
  2. Report in PDF format (please no Word file).
  3. A voxelised version of TUDelft_campus.obj produced by your code.

Code

Your Python source file(s) need to have the following text at the very top:

#-- GEO1004.2020--hw02
#-- [YOUR NAME 1] 
#-- [YOUR STUDENT NUMBER 1]
#-- [YOUR NAME 2] 
#-- [YOUR STUDENT NUMBER 2]

The main file to run your code should be named geo1004_hw02.py. The first argument should be the input file, the second argument should be the output file, and the third argument should be the voxel size (in the same units as the OBJ input). I should thus be able to execute the code by calling the main file like this:

python geo1004_hw02.py <input OBJ> <output OBJ> <voxel size>

For example:

python geo1004_hw02.py bag_bk.obj bag_bk_voxels.obj 1.0

Apart from that you are free to organise your code to your liking.

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 magical results—just document what works well and what doesn’t.

We expect about 4-5 pages for this (figures and graphs included!)

Voxelised model

The voxelised model should be produced with your code using 10-meter voxels or smaller. 1-meter voxels would be great, if you can manage. Submit a cropped part of the model if you have serious performance problems.

Marking

Criterion Points
followed all rules and compiles/runs without modifications 1
voxel model (complexity and quality of result) 3
report (quality/clarity) 3
implementation 3

It is okay if you submit only part of the TU Delft campus file due to performance issues. However, please show us your insight into the problem by explaining (in your report) where your performance issues are and why they happen.

What to submit and how to submit it

Submit your single compressed file by uploading it here.

Extra: exporting map to Minecraft

While planning this assignment for you, we had the idea to have an optional task to export your map to Minecraft at the end. Unfortunately, this is more complex than we expected, so we decided to skip it. If you finish the assignment early and find it fun, maybe you want to try it? (no bonus points though)

Some libraries to read/write Minecraft files (not tested by us):

[last updated: 2020-02-21 19:05]