Assignment 1

Triangulating the faces of a polyhedron

Deadline is 03 March 2023 at 11:59 pm

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

This is an individual assignment.

The assignment is worth 10% of your final mark.

cover

Changelog

Overview

For this assignment you will implement a method to triangulate the faces of a polyhedron by performing a constrained triangulation in CGAL. This method should support faces with holes (also known as inner rings) and will involve the following steps:

  1. read the input polyhedron from a file and load it into a data structure;
  2. for each face of the polyhedron, compute its best-fitting plane;
  3. for each face of the polyhedron, create a constrained triangulation containing all of its the edges as constraints projected to 2D using the best-fitting plane;
  4. for each face of the polyhedron, label its triangulation using the odd-even rule;
  5. for each face of the polyhedron, extract its triangulated interior back in 3D using the best-fitting plane;
  6. output all the faces of the triangulation to an OBJ file.

You will hand in the program and the output triangulated OBJ file. You do not need to write a report.

What you are given

The file that you have to triangulate is the station.hw1 file that is available here. There you can see a couple more hw1 files that you can use to test your code. hw1.cpp is bit of code to help you get started. You can use the image at the top of this page as a reference for how your output should look.

You are free to modify the provided hw1.cpp code as you see fit or to avoid it using entirely. Note that this file contains:

  1. A good set of CGAL headers and definitions for your code.
  2. A data structure to store each of your polyhedron’s vertices and faces while loading it, as well as its best-fitting plane and triangulated faces.
  3. Some sample code to parse the input file’s vertices.

This assignment needs to be implemented in C++. You can use any functions in the C++ standard library. From CGAL, you are only allowed to use functions in the packages 2D/3D Kernel, 2D Triangulations and Principal Component Analysis.

The input hw1 file format

The input file follows a custom hw1 file format which is structured as follows:

vertex header
vertices
faces header
faces

The vertex header starts with the number of vertices in the file (339 in station.hw1), just like the faces header starts the number of faces in the file (186 in station.hw1). You can ignore the other numbers in these lines.

The vertices are listed one after another and start with their id and then have their x, y and z coordinates. All of these elements are separated by a space and each vertex is stored in a separate line.

The faces are also listed one after another but use multiple lines. The first line of a face contains two elements: the number of its outer rings (always 1) and the number of its inner rings (ie holes). The next lines consist rings: first the face’s outer ring and then its inner rings (if any). Each ring is written in a separate line.

An (outer/inner) ring line starts with the number of vertices in the ring. Then each of its vertices is written in order and separated by a space. The vertices are represented by their ids, which correspond to those defined in previously in the vertices.

Some useful pieces of code

An example of an easy and fast iteration through all vertices of a face:

for (auto const &face: faces) {
  std::cout << "Face " << face.first << ": " << std::endl;
  std::cout << "\touter:";
  for (auto const &vertex: face.second.outer_ring) std::cout << " " << vertex;
  std::cout << std::endl;
  for (auto const &ring: face.second.inner_rings) {
    std::cout << "\tinner:";
    for (auto const &vertex: ring) std::cout << " " << vertex;
    std::cout << std::endl;
  }
}

How do I compute a best fitting plane? See this.

How to I project to 2D using this plane? See the to_2d function of CGAL’s Plane_3 here. For the opposite operation, check to_3d too.

How to I insert constraints in the triangulation? See the Constrained_triangulation_2 documentation.

How do I label the triangulation? A bit trickier, but see this from CGAL’s Triangulation_2 examples or this function from my code.

Odd-even rule?

Once you have triangulated a polygon, start from a triangle known to be outside the polygon and label it as part of the exterior. For this, you can use the triangulation’s infinite face. Starting from that triangle, the triangles that you can reach by passing through an odd number of constraints are part of the interior and those you can reach by passing through an even number of constraints are part of the exterior.

The OBJ file format

If you’re not familiar with it, see this Wikipedia article. You can use MeshLab or Blender to visualise OBJ files. Some Windows versions and all recent macOS versions come with OBJ viewers, but these aren’t as good as MeshLab.

You can find some sample OBJ files here.

Marking

In order to mark your assignment, I will run your code to ensure that is capable of producing the same station.obj output that you submitted and will then evaluate your results by viewing your submitted station.obj file.

Criterion Points
code runs without modifications 3
quality of the station.obj file 7

Here, quality defined as the geometry being correctly generated: no arfefacts, no weird/sliver/intersecting triangles, windows/doors visible in the triangulation, etc.

What to submit and how to submit it

You have to submit a ZIP file (or another compressed format) with the following files:

  1. your code (everything that is needed to run/compile it).
  2. a README that very briefly explains how to run/use your program, including what I need to do in order to set the path to the station.hw1 in my computer.
  3. station.obj with your triangulated output.

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

[last updated: 2023-02-16 14:07]