Assignment 2

Unordered mesh to a CityJSON model

Deadline is March 22 at 10:00 am

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

The assignment is worth 20% of your final mark.

wireframe

Changelog

Overview

For this assignment you are given a ‘triangle soup’ as input. The order and orientation of the triangles in the soup is random and they are not grouped in any way. The triangle soup does contains a number of meshes that do not touch or intersect each other.

In this assignment you will write a program that converts this triangle soup to a valid CityJSON file with polygonal faces. And you will do this by using the DCEL datastructure (see Lesson 1.2).

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 and store them in a DCEL,
  2. group the triangles into meshes,
  3. determine the correct orientation for each mesh and ensure all its triangles are consistent with this correct orientation (ie. all the triangle normals are pointing outwards with respect to the mesh).
  4. merge adjacent triangles that are co-planar into larger polygonal faces, and
  5. write the meshes with their faces to a valid CityJSON output file.

You are allowed to work in a group of 2 (and thus to submit one solution for both of you). If you prefer to work alone it is also fine.

Discussing your solution with your classmates outside your group is very much encouraged. In other circumstances, this would be done in the (Geo)lab, but since this is not an option, you are asked to have at least one meeting with another group. In this meeting, each group should describe how they’re attempting to solve the problem, the results that they’re getting (so far) and provide feedback to the other group. Just take this into account: high-level discussions are a great way to improve your solution, but copying/pasting significant parts of the code from other groups will be considered as cheating.

What you are given to start

hw2.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.
  5. soupchef, which is a folder containing some initial code (including a DCEL implementation) to help you get started.

You can visualise OBJ files with MeshLab where you will immediately notice any incorrectly oriented triangles due to the darker shading.

In the folder soupchef you will find:

  1. DCELElements.hpp, which contains the classes to represent the vertices, half-edges and faces of the DCEL
  2. DCEL.hpp, contains the main DCEL class that keeps the lists of vertices, half-edges and faces.
  3. main.cpp, the main file that you can write/run. There are some functions that you might want to fill out (or not).
  4. CMakeLists.txt, to make it easier to open the project in an IDE like CLion

Read through all the source files before you begin, there are comments and examples that explain how The DCEL works.

Working with the DCEL

This assignment is all about the DCEL data structure. Every major operation consists of interactions with the DCEL and the DCEL elements. In the DCEL that we use every half-edge has 6 links (implemented as pointers in the provided code). Faces store one link to a half-edge of their exterior ring and one half-edge for each hole/interior ring.

DCEL

The code provides an example that constructs the DCEL example shown in the image above. It also shows how you can iterate around the vertices of a face in the DCEL. Do check it out, and also checkout the DCEL.hpp and DCELElements.hpp to understand how the DCEL implementation works.

Importing the OBJ file into the DCEL

The triangles in the soup OBJ files are randomly oriented and ordered. Importing them into the DCEL you can first import all the vertices (ie. create a Vertex Element for each). And then import the triangles themselves (edges+faces). You may want to use a map (std::map or std::unordered_map, it is similar to a python dictionary) to link the id’s from the OBJ file to DCEL elements that you create. A map will make it easy and fast to look up eg a DCEL element that you created based on the corresponding id from the OBJ file.

Finding the correct orientation of a mesh

Once you have figured what triangles belong to what mesh you need to figure out the proper orientation of each mesh. A mesh is correctly oriented when all its faces have the correct orientation. A face 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).

You can find the correct mesh orientation by intersecting the mesh with a ray that originates from the exterior of the mesh. The first triangle that you find (ie closest to the ray origin) should be flipped towards the origin of the ray. Luckily you already know how to do triangle-ray intersections from homework 1 and you can re-use that code.

Grouping triangles into polygonal faces

The obvious way to implement this is to remove edges between faces that are co-planar (they have an identical normal vector). Just make sure that the links of the surrounding DCEL Elements (ie the ones that link to the edge that you remove) are updated accordingly. It’s recommended that you draw this out on a piece of paper before you implement it.

Be aware that faces can also contain holes.

Tips

Deliverables

You have to submit one zipped file (or another compressed format) containing:

  1. Your code.
  2. Report in PDF format (please no .doc file).
  3. The CityJSON output bk.json produced by your code.

Code

You should submit all the files that I need to run your code. The code should read an OBJ file with a triangle soup and write your resulting meshes to a valid CityJSON file

You are free to modify and add files as you see fit. Everything should be implemented in C++ using only libraries from the C++ Standard Library.

Report

You need to submit a simple report outlining your work. It should document how you perform the 5 main tasks. Explain briefly how you implemented the key parts 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 correctness of your results. We don’t expect perfect results—just document honestly what works well and what doesn’t.

Use a small section of your report to describe how the other group you met was progressing (at the time you met). Focus on what they’re doing differently.

We expect maximum 5 pages for the report (figures and graphs included). Don’t forget to write your names and the names of the people from the other group you met.

CityJSON output

Your end result should be written to a CityJSON file.

The CityJSON format is explained in Lesson 4.1.

The requirements for the CityJSON output are

You do not need to specify a CRS.

You can visualise CityJSON files with a viewer like ninja.

Marking

Criterion Points
code compiles/runs without modifications 1
mesh grouping 1
correct mesh orientations 1
correct polygonal faces with holes 2
CityJSON valid 1
report (quality/clarity) 3
discussed with another group 1

What to submit and how to submit it

Submit your single compressed file by uploading it here.

[last updated: 2021-03-03 11:15]