Final exam

1.1. Give an example of a 3D model (eg something from the homework assignments or from the BIM lesson). Using that model as an example, write three sentences, one for each aspect of: (i) its geometry, (ii) its topology, and (iii) its semantics. The sentences can refer to specific parts of the model or to the model as a whole.

Many, many possible answers here. Here’s a minimal example using the 3D model of the faculty buildings from Homework 1.

• geometry: it is composed solely of triangles
• topology: it is not guaranteed to be 2-manifold
• semantics: its faces are grouped into 4 objects (the o marker)

1.2. Figure 1.5(c) of Lesson 1.2 in the handout shows an undesirable representation of a non-manifold polygon (due to the creation of a disconnected structure). Give an example of an application where this can be a problem. Explain your reasoning.

Also many possibilities here. Any kind of algorithm that involves navigating the structure of the polygon would be a nice example, such as finding out the number of vertices of a polygon. A naive implementation that counts vertices from an initial one would say that the polygon has only 4 vertices.

2.1. Let’s say we want to voxelise a mesh (like Homework 1), but it is a mesh with semantics. So, there are triangles labelled as roof, wall, floor, etc. (i) How would the process differ from that which you did in Homework 1? (ii) What would you store in the voxel grid (in memory)? (iii) What would the OBJ output be like?

The answer here would depend on your particular implementation. That being said, here are some typical expected things:

(i) Parsing triangle groups (g marker) or similar, having different values in raster grid to represent each group, assigning those values to a voxel based on the semantics of the triangle being tested, creating obj output with groups or materials.

(ii) One possibility would be different integer values for each class, which could be combined with a list that says which values refer to which classes.

(iii) Something with groups, objects and/or materials to show each class.

2.2. In Assignment 2 you had to merge co-planar faces on a building model using a DCEL. (i) Explain the major benefit of using a DCEL to implement this task. (ii) Explain why Assignment 2 would have been much more difficult if the input would not have been 2-manifold and illustrate this with a concrete example.

(i) the main benefit are the explicit topological links that allow you to navigate very easily and efficiently to eg adjacent faces, and incident elements. This makes it easy to know if a given edge needs to be removed (to merge two faces) since you can very easily get access to the two adjacent faces through the incidentFace and twin links.

(ii) the method to find the correct orientation strongly depends on the assumption that the input mesh is 2-manifold. If it is not, eg due to a hole, there is no guarantee it will still work.

3.1. Given the following 4 points: a=(3, 4, 17) b=(5, 11, 17) c=(22, 1, 17) d=(5, 5, 5), what results Orient(a, b, c, d) return? Positive, negative, or zero? Explain your calculation/reasoning to obtain the result.

▲                                   
│                                   
│                                   
│                                   
│                                   
│                                   
│         b                         
│                                   
│                                   
│                                   
│                                   
│                                   
│   a                               
│                                   
│                           c       
└──────────────────────────────────▶

• No need to calculate anything, a, b, and c are on the same plane z=17.
• using left-hand rule, up is above (since abc are CW), but z=5 is below
• so NEGATIVE

3.2. Download the file CityJSON cube.json (download link), which is meant to represent a simple cube. You will notice that it is not a valid CityJSON file and its geometric representation contains errors. Fix the file, and describe in details all the operations you did to obtain a valid CityJSON representation of the cube.

Three errors:

1. “vertices” is wrong [3]
2. surface #3 (0-based) is wrong direction; [5, 1, 2, 6] [3]
3. one surface is missing, should be added, and how: +[5,4,7,6] [4]

The order of the JSON properties does not matter in JSON!

4.1. The specifications of the Assignment 3 state that “the geometry of the building must be a solid valid according to ISO 19107”. Why was that asked? Describe 3 reasons why you think this was asked (instead of the simpler MultiSurface) and/or why in practice practitioners would want this.

• buildings are generally solids, so should be modelled as such
• MS is just a collection of surfaces, and doesn’t represent the “true” geometry of a building, and doesn’t mean that topological relationships between the surfaces are verified (they could intersect),
• orientation of the surfaces is easier to obtain then with a MS
• useful for applications where volumes are calculated
• useful for applications where Boolean operations (union/intersection)
• can help “clean” the geometry: easily finding dangling pieces, intersections, etc
• saying that Solid is a int’l standard and ISO19107 is true, but MultiSurface is also one…

4.2. Imagine the voxel CSG engine briefly mentioned in Section 1.4 of the handout (and in the midterm exam). We have decided to use half-spaces as leaf nodes. (i) How would you evaluate whether a voxel is part of a half-space? (ii) How would you perform Boolean set operations at the voxel level?

(i) One possibility: using a plane equation of the form Ax+By+Cz=D and a direction (up or down), it is possible to evaluate whether a point in the centre of each voxel is in/out the half-space.

(ii) If you evaluate the child nodes, then it becomes a simple Boolean operation (ie AND, OR, NOT, etc).

5.1. What is the difference between a geometric simplex (point, line segment, triangle, tetrahedron, etc) and a dart?

In short, darts are abstract simplices, so their vertices (except for the ones marked with 0) don’t have a location in space. Also, darts in an n-dimensional map are n-simplices, whereas in the same map you can have geometric simplices of any dimension up to n.

5.2. (i) For what shapes does the MAT consist only of a single interior part? (ii) Give an example of a solid for which the exterior MAT consist of a single part with a maximum medial radius that is smaller than the maximum medial radius of the solid’s interior MAT.

(i) any convex shape (ie, no exterior parts possible)

(ii) Solid with convex exterior boundary and one small cavity. Eg outer boundary a sphere with a radius of 100m, with in the center a cavity in the the shape of sphere with a radius of 10m.

6.1. Say we have a quadratic Bézier curve with point coordinates (0, 0), (0, 1), (2, 0). What coordinates do we obtain when we evaluate it at t = 0.5?

For this, you could use the weights given by the Bernstein polynomials for quadratic curves OR you could directly check the ready-made equation (1.5). Following the first option, the values are in Figure 1.9(c) in the handout, which tells you that at t = 0.5, they are respectively 1/4, 1/2 and 1/4.

The result is thus 1/4 * (0, 0) + 1/2 * (0, 1) + 1/4 * (2, 0), which is (1/2, 1/2).

6.2. It is stated in the lesson 6.2 that “Triangulating a Voronoi cell is easily performed since it is a convex polyhedron”. Explain in details one method.

• It’s easy because it’s convex, and each surface is convex.
• Take the Voronoi vertex, and for each surface triangulate it (easy it’s convex), and then form tetrahedra.

7.1. For a 3D modelling application of your choice, explain: (i) briefly what the application is, (ii) what input it needs (eg particular geometric representations), (iii) what are the steps to carry it out, and (iv) what is the output.

Exactly what is stated in the question :-).

7.2. How are IFC elements grouped in spatial structures within a BIM? (i) Explain what is prescribed by the IFC data model, and (ii) comment on how these are found in practice.

(i) They can be grouped by means of IfcSpatialStructureElements (eg Site, Building, Storey, Space, Zone, etc), as well as IfcSpaces.

(ii) In practice, they are grouped in an irregular way: multiple buildings in one project are grouped as only one building; sometimes the site includes everything and sometimes only the terrain; the storeys can include elements spanning across many storeys or wrong assignments; etc.