Assignment 02-retake

Determination of interior using voxelisation

Deadline is 26 June 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
  • Code
  • Report
• Marking
• What to submit and how to submit it

Overview

The aim of this assignment is implement a program that voxelises the interior of imperfect triangular mesh models with some faces missing, which is a common problem in practice. The input models will be in the OBJ format. 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 a simplified version of the method proposed in Damien Mulder’s MSc thesis, which involves shooting rays from many points known to be in the exterior of the model towards the centre of every voxel. If almost all rays are blocked by triangles in the model, then the voxel is in the interior of the model. By extension, if a sufficient proportion of the rays do not pass through any triangles in the model, then the voxel is in the exterior.

In order to know whether a ray intersects a triangle, you can use the method described in Lesson 3.1 and implemented in the original Assignment 2, which uses intersections between the model and specially designed targets.

The exact steps to achieve this task are for you to figure out, including which rays to shoot and how many of them need to be blocked in order to define a voxel as part of the interior of the model. But if you are unsure about the best way to approach this, feel free to discuss your methodology with us (Discord/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

bk-city.zip

This zip file contains five files, which represent different parts of the faculty building (courtesy of Ravi). It is similar to the one from the original Assignments 1 and 2. Note that these files have no missing faces, so you need to remove some!

If you didn’t do so already, you probably want to start by getting the basic voxelisation method from the original Assignment 2 working, then implementing the methods to shoot rays from many directions, and finish by fine tuning the parameters (eg how many rays to shoot and how many rays need to be blocked). Do your best to get your method working with a decent number of faces missing (eg a random 10% subset).

How to compute triangle-line segment intersections

One important part of your implementation (which was previously implemented in the original Assignment 2) 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.

Tips

• Always use integer coordinates to refer to the voxels (eg [12, 34, 56]). Repeatedly adding up floating point numbers will cause precision issues.
• 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)
• You can reduce the number of rays you need to shoot by choosing well distributed origin points

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_hw02r.py and follow the specifications below.
2. Report in PDF format (please no Word file).

Code

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

#-- GEO1004.2020--hw02r
#-- [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_hw02r.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_hw02r.py <input OBJ> <output OBJ> <voxel size>

For example:

python geo1004_hw02r.py bag_bk.obj bag_bk_voxels.obj 0.5

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 5 pages for this (figures and graphs included!)

Marking

What to submit and how to submit it

Submit your single compressed file by uploading it here.

[last updated: 2020-05-19 22:42]