Assignment 1

Triangulating the faces of a polyhedron

Deadline is 01 March 2023 at 01:45 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 will involve the following steps:

  1. read the input polyhedron from an OBJ 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 the face’s 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 a nice example with a pair of OBJ files: an input file that is not triangulated and an output file that is triangulated by your code. You should also write a very short report explaining what you did.

What you are given

Your code should be able to triangulate OBJ files that are structured similarly to those available here. There, you have many 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. Simple data structures 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 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.

Some tips

Test your code with different OBJ files. Develop it using a simple example and move on to increasingly complex ones.

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? Starting from a Face_handle f, you can label it with something like f->info().processed = true. For labelling the whole triangulation of a face, 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.

Marking

In order to mark your assignment, I will:

Criterion Points
code runs without modifications 2
code triangulates complex files correctly 4
report 4

Please choose a reasonably complex OBJ file. You won’t get all points if you submit a very simple building.

Deliverables

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

  1. your source code (everything that is needed to run/compile it).
  2. a pair of OBJ files that nicely showcase your code: an input OBJ file that is not triangulated and an output OBJ file that is triangulated using your code.
  3. a very short (maximum 3 page) report in PDF that briefly explains what you did, how to run/use your program (including what I need to do in order to set the paths to the input and output OBJ files in my computer), and a few screenshots of your OBJ files.

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

[last updated: 2024-02-27 14:07]