Midterm exam answers

1.1. How would you represent a temperature field using polyhedra, voxels, and a 3D Voronoi diagram? For each of the three, mention: (i) the data structure you would use, and (ii) where the temperature would be stored in this data structure.

Many data structures are possible. Some good options below.

Answers were marked based on whether the data structures were suitable for the stated purpose, taking into account a good balance of efficiency/compactness and navigability. For instance, storing a 3D Voronoi diagram as a set of polyhedra without the original points was bad, storing it as a DT was good. The same applies to the temperature. For instance, storing the temperature in every face of a polyhedron was bad, storing it once per polyhedron together with its ID was good.

1.2. Describe in your own words the difference between a 1-manifold and a 2-manifold. Give a practical example of each and where it is used.

Any clear definition that explained the key differences was okay. Any valid example of their use was okay.

One possibility: a manifold is a shape that looks like the unbounded (infinite) space of a certain dimension. A 1-manifold locally looks like a line and a 2-manifold like a plane. In boundary representation, 1-manifolds are used to describe the boundary of polygons, whereas 2-manifolds are used to describe the boundary of polyhedra.

Note the unbounded part in the definition above.

2.1. Using also the knowledge you gained from Homework 1, explain the changes in your code that would be required to use a sparse voxel representation in your assignment.

This depended on how you implemented the assignment, but if you used the VoxelGrid struct, it was one key part that needed to be changed. One possibility is to store each voxel as a tuple of x,y,z,v, where v is the value of interior/exterior/boundary. The other key part to change was the iteration over the voxel grid, since the optimisation we discussed (bbox of triangle) doesn’t work anymore. One possibility would be to use a (hash) map to quickly know if the voxel is in the grid or not.

Full marks if you mention both of these elements.

2.2. In Section 1.3 of Handout 2.2, a building reconstruction method is described. Could the mesh shown in this image be an output of this method? If not, explain why.

No. The building that is shown in the image is not 2.5D: it has overhanging structures on the sides. The output of the reconstruction method in the book will always be 2.5D due to how the extrusion is performed from a 2D planar partition of the building footprint (ie the roof-partition). Those overhangs could therefore not have been reconstructed. Notice that 4 structures on the top surface could have been reconstructed just fine, because those are all completely 2.5D.

3.1. Imagine you have a set of 10 points in the 3D Euclidean space, all lying inside a cube; thus you have 10 points + 8 points (corners of the cube). For further processsing, you want to create the Delaunay tetrahedralisation of the 18 points (not the constrained/conforming, simply of the DT). How many tetrahedra will the DT contain?

The number depends on the configuration. In 2D the insertion steps are flip13+flip22, so we know the number (if we know how many are on the boundary of the convex hull). But in 3D, the flips are a series of flip23 and/or flip32 depending on the configuration of the points.

50% => depends 50% => the reason

3.2. You obtained from your municipality a building footprint (see below, it has 1 interior boundary) and you extrude it to a height of 16m to create a 3D model. Characterise the 3D shape you obtain, using the ISO19107-terminology. What type? how many surfaces? Their orientation? Is it valid?

              ┌──────────────────────────────────────────────────────┐
              │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
              │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
              │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
              │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
              │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
┌─────────────┼───────────┐■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
│■■■■■■■■■■■■■│           │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
│■■■■■■■■■■■■■│           │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
│■■■■■■■■■■■■■│           │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
│■■■■■■■■■■■■■│           └────┐■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
│■■■■■■■■■■■■■│                │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
│■■■■■■■■■■■■■│                │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
│■■■■■■■■■■■■■│                │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
│■■■■■■■■■■■■■│                │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
│■■■■■■■■■■■■■└────────────────┘■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
└───┐■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
    │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
    │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
    │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
    │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
    │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
    │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
    │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
    │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│
    │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■┌────────────────────────────────┘
    │■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■│                                 
    └───────────────────────────────┘

You obtain a:

4.1. In the handout, it is stated that a given CityJSON file will be on average 6X compacter than an equivalent CityGML file. Give 2 reasons and explain them.

  1. vertices are indexed and listed once and not repeated (à la OBJ)
  2. “transform” can compress the floats over integer and the shift makes coordinates smaller
  3. JSON generally less verbose than XML

Flattening of the hierarchy doesn’t really help to compress, same information stored differently. Might even increase, since we need to index and keep IDs between the parts… But if you said this could avoid several spaces/tabs/returns, I gave half points (I felt generous).

4.2. Imagine the voxel CSG engine briefly mentioned in Section 1.4 of the handout. What do you think should be stored in the leaf nodes in the CSG tree? Justify your choice. Based on this, how would you implement Boolean set operations?

There are many possibilities, from half-spaces to arbitrary voxel grids in the leaves. Any well-argued solution was okay. Full marks if you mentioned the key steps to implement Boolean set operations on those primitives.

A simple solution was to state that you stored the values of a voxel grid in the leaves. Then, since the grids represented are the same, Boolean set ops are simply Boolean operations on the values.

Hw1. Using voxels made it possible to compute the volume of the faculty buildings even when the input data had some validity problems. Explain in your own words why is possible and whether there are any limits to voxelisation-based “fixing”.

There are a few different good answers here, but ideally you mentioned something about filling gaps (up to a certain size) and ignoring duplicates/self-intersections. The limits are with regards to filling gaps, since this only works if whole voxels can’t get inside the gaps due to a small voxel size. At the same time, large voxels reduce the accuracy of computations, which can be a problem. Full marks if you hit most of those points (or if you made a valid alternative argument).