Assignment 1

Triangulating a polygonal mesh with generalised maps

Deadline is 04 March 2021 at 11:59 pm

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

For this assignment you are allowed to work in a group of 3 (and thus to submit only one solution for all of you). If you prefer to work alone or in pairs, it is also fine.

The assignment is worth 20% of your final mark.

• Overview
• What you are given
• Input assumptions and file format
  • The OBJ file format
• How to implement a generalised map
  • How to output the generalised map to CSV
• How to triangulate
  • Tips
• Marking
• What to submit and how to submit it

Overview

For this assignment you will implement the generalised map. You will write a program that will

1. read a 3D polygonal mesh from an OBJ file,
2. store the polygonal mesh in a generalised map,
3. output all the darts and cells from the generalised map to .csv files, and finally
4. output a triangulation of the polygonal mesh to a new OBJ file.

You will hand in the program and the generated files. You do not need to write a report.

Introduction video:

What you are given

In the geo1004 gitlab repository you will find everything you need to start with this assignment in the hw/01 folder.

• The cpp contains a code skeleton to get you started. It consists of:
  • Point.h: 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).
  • Gmap.h: defines the basic structures of the gmap, ie. Dart, Vertex, Edge, Face, Volume. You need to complete them.
  • main.cpp: the main file were the execution of the program starts and were you can implement the main operations (reading/writing OBJ, creating and storing the structures from Gmap.h, etc).
• The data/*.obj folder contains a number of example input files.

This assignment needs to be implemented in C++. Apart from the standard C++ libraries, no additional libraries are allowed. Otherwise you are free to modify the code to your liking. We encourage you to write brief comments on each major part of your code: what does it do, and how does it work? You can earn a point for this.

Input assumptions and file format

You may assume that the input OBJ file contains

• a single valid polygonal mesh (so only one volume),
• whose faces are all convex and contain no holes.

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 5 7 3
f 4 3 7 8
f 8 7 5 6
f 6 2 4 8
f 2 1 3 4
f 6 5 1 2

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 5 7 3 means that there is a face that consists of the 1st, 5th, 7th and 3rd vertices of the vertex list. Note that OBJ thus uses 1-based indexes, unlike most C++ data structures (eg std::vector) that use 0-based indexes (ie. the first element is 0, not 1).

Face normals are implicit from the vertex order. The orientation of the vertices of the faces in relation to the face normal follows the right-hand rule:

How to implement a generalised map

First of all read chapter 8 of the book. Then have a look at the image below. It gives you a 2D example with all the elemements (darts and cells) and their references to other elements.

As stated in the book, you can either use integer IDs or pointers to identify and reference the elements. You are free to choose whatever you find most convenient.

How to output the generalised map to CSV

Your code needs to output the tables with the darts and cells of the generalised maps including their attributes similar to the figure above. You should generate

1. one CSV file for the darts (filename ends on darts.csv) with at least the columns ID, a0, a1, a2, a3, v, e, and f. And then
2. one CSV file for the 0-cells (ending on vertices.csv) with at least the columns ID, dart, x, y, and z,
3. one CSV file for the 1-cells (ending on edges.csv) with at least the columns ID, dart,
4. one CSV file for the 2-cells (ending on faces.csv) with at least the columns ID, dart,
5. one CSV file for the 3-cell (ending on volume.csv) with at least the columns ID, dart.

This is a total of 5 csv files. Don’t forget to include the header row and use a space or a (semi-)colon as delimiter. Here is an example of a vertices.csv based on the figure above:

id;dart;x;y
v0;8;0;0
v1;10;4;0
v2;12;4;4
v3;0;2;6
v4;3;0;4

How to triangulate

As suggested in the book we can triangulate the surface of the polygonal mesh by using the barycenters of the cells. The vertices (0-cells) already have x,y,z coordinates, which leaves you to compute the barycenters of the edges (1-cells) and faces (2-cells). Once you have done this you can easily derive one triangle from each dart, with the three triangle vertices being the barycenters of the dart’s 0, 1, and 2-cells.

Here is an example input (left side) and triangulated output (right side):

Tips

• std::unordered_map might come in handy while building the gmap.
• add print statements to verify that your datastructures are what you expect them at different points in the code (can remove them in the final version ofcourse).
• You can use the MeshLab software or Blender to visualise the OBJ files.

Marking

What to submit and how to submit it

You must hand in one ZIP containing:

1. your code (everything that is needed to run/compile it). Add a README.txt that very briefly explains how to run/use your program.
2. torus_triangulated.obj: OBJ output for the torus.obj dataset.
3. the 5 CSV files torus_darts.csv, torus_vertices.csv, torus_edges.csv, torus_faces.csv, torus_volume.csv.

Do not submit your assignment by email, but use this Dropbox link.

[last updated: 2022-02-10 15:05]