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.
- Overview
- What you are given to start
- How to compute triangle-line segment intersections
- Performance considerations
- Data structure to use
- Tips
- Deliverables
- Marking
- What to submit and how to submit it
- Extra: exporting map to Minecraft
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
This zip file contains three files:
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.TUDelft_campus.obj
is a larger model of the whole campus area with semantics (created using 3dfier).3dfier.mtl
is a materials definition file from 3dfier. It defines the materials used inTUDelft_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:
- the two endpoints of the segment are on opposite sides of the plane passing through the triangle, and
- the three planes passing through the line segment and a vertex of the triangle have the two other vertices of the triangle on opposite sides of it.
Test: endpoints on opposite sides
Test: two other vertices on opposite sides (x3)
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
- Always use integer coordinates to refer to the voxels (eg [12, 34, 56]). Repeatedly adding up floating point numbers will cause precision issues.
- Use integer numbers for the voxel values too. Then, use an index to map the voxel values to objects/materials (ie 12 -> “Water”). You might want to have another dictionary to do the reverse mapping.
- With small models, the output will look nicer if the input model is centred on the voxel grid.
- It is often easier to make a slightly bigger voxel grid and keep the boundary voxels empty.
- The bounding box of a triangle is easy to compute and can be used to skip many possible intersection tests.
- Voxelisation is a problem that is very easy to do in parallel. If you want to try it, have a look at the concurrency modules in Python.
- You might not even need to read the contents of the MTL file.
- For the report, Blender can make nice renders of your OBJ files.
- If you want to get nicer-looking results with a particular model (eg the campus one), you can set up a hierarchy of semantic classes to decide which class to use when multiple ones are in a single voxel. For instance, it is nice when the top voxels of a building are all marked as roof voxels.
- There are easy ways to avoid exporting duplicate surfaces (one for each of the two voxels on either side of it)
Deliverables
You have to submit one zipped file (or another compressed format) containing:
- Your code. The main file (the one that I will run) needs to be named
geo1004_hw02.py
and follow the specifications below. - Report in PDF format (please no Word file).
- 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]