Assignment 01

Orienting a mesh

Deadline is 27 February 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.

bk-soup

Overview

For this assignment you are given a ‘triangle soup’ as input. While this triangle soup contains a number of 2-manifold isolated meshes, the order and orientation of the triangles in the soup is random. It is your job to determine for each triangle 1) which mesh it belongs to and 2) its correct orientation.

The work you need to do for this assignment can roughly be subdivided in 5 tasks:

  1. read the triangle soup from the OBJ input file,
  2. put the triangles into a topological data structure,
  3. group the triangles into isolated meshes,
  4. determine the correct normal orientation for each mesh and ensure all its triangles have the correct winding order, and
  5. write the meshes to an OBJ output file. In this file the the triangles should be grouped by mesh and the triangles need to have the correct orientation. Your output should be valid according to val3dity.

The topological datastructure of task 2, will make tasks 3 and 4 a lot easier. You will have to implement everything from scratch in Python. Apart from the standard Python libraries you may only use numpy.

What we give you

hw01.zip

This zip file contains 4 OBJ files:

  1. bk_soup.obj example input file that contains a triangle soup.
  2. isolated_cubes.obj small example OBJ file that contains two isolated meshes.
  3. cube.obj OBJ example of a cube.
  4. cube_soup.obj OBJ example of cube.obj as a triangle soup.

You can visualise these files with MeshLab where you will immediately notice any incorrectly oriented triangles due to the darker shading (when viewed from the outside of the mesh).

Details on implementation

The topological data structure

You will have to implement a topological data structure for this assignment. Since we are dealing only with triangles here (and not general polygonal faces), a triangle-based data structure would be the simplest. However, you are free to choose any data structure described in handout 1.2.

Finding the correct orientation of a mesh

Once you have grouped the triangles into meshes, you need to figure out the proper orientation of each mesh. A mesh is correctly oriented when all its triangles have the correct orientation. A triangle is correctly oriented when its normal is pointing towards the exterior of the mesh and its vertices are winded counter-clockwise around the normal (when looking at the triangle with the normal pointed towards you). Indeed, this is according to the so-called right-hand rule.

right-hand rule

You could find the correct mesh orientation by intersecting the mesh with a ray that originates from the exterior of the mesh. The closest triangle that you find should be flipped towards the origin of the ray. To compute the ray-triangle intersections you could implement the Möller–Trumbore intersection algorithm. Notice that other (faster) methods do exist and are also allowed as long as they give the correct result.

Input assumptions

Geometric validity

Your output should be valid according to val3dity. Check the extensive list of possible errors to see what this means.

The OBJ file format

An OBJ file as we use it in this assignment is a plain text file composed of a list of vertices and one or more lists of faces. For example, below are the entire contents of the cube.obj file:

v 1.00 1.00 -1.00
v 1.00 -1.00 -1.00
v -1.00 -1.00 -1.00
v -1.00 1.00 -1.00
v -1.00 -1.00 1.00
v 1.00 -1.00 1.00
v 1.00 1.00 1.00
v -1.00 1.00 1.00
f 1 2 3
f 3 4 1
f 5 6 7
f 7 8 5
f 3 2 6
f 6 5 3
f 2 1 7
f 7 6 2
f 1 4 8
f 8 7 1
f 4 3 5
f 5 8 4

The lines starting with v denote the vertices. The v is followed by respectively the x, y, and z coordinates of the vertex. The lines starting with f denote the faces. The f is followed by a number of indices that refer to the vertex list at the beginning of the file. For example the line f 1 2 3 means that there is a face that consists of the first 3 vertices of the vertex list (top 3 lines). In this assignment all the faces have only 3 vertices, since we deal only with triangles.

You can separate meshes within one OBJ file using the o <id> tag, where <id> is a unique string. See the example isolated_cubes.obj file.

Deliverables

You have to submit 2 items:

  1. Your code. The main file (the one that I will run) needs to be named geo1004_hw01.py and follow the specifications below.
  2. Report in PDF format (please no Word file)

Code specifications

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

#-- GEO1004.2020--hw01
#-- [YOUR NAME] 
#-- [YOUR STUDENT NUMBER]

The main file to run your code should be named geo1004_hw01.py and the first argument should be the input file and the second argument should be the output file. I should thus be able to execute the code by calling the main file like this:

python geo1004_hw01.py <input OBJ> <output OBJ>

For example:

python geo1004_hw01.py triangle-soup.obj your-output.obj

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

The report to submit

You need to submit a report explaining briefly how you implemented the key parts (the topological data structure, grouping the triangles by mesh, finding the correct orientation of each mesh, etc.) and explain what works (and what not).

We expect maximum 1500 words for this.

Marking

  Marks
followed all specifications and runs without modifications 1
report quality/clarity 3
mesh grouping 2
correct orientation 3
output valid 1

Submission