Lecture 7 Quiz

Solution

A triangle mesh can be encoded as a list of vertex positions (x,y,z), together with a list of triangles specified as triples of indices (i,j,k) into the vertex list. For instance, the following data represents a square split along one of its diagonals (making two triangles):

VERTICES
0: 0, 0, 0
1: 1, 0, 0
2: 1, 1, 0
3: 0, 1, 0

FACES
0 1 2
0 2 3

In class we talked about normal vectors, which roughly speaking are vectors pointing "away" from the surface; more precisely, a vector is normal to the surface if it is orthogonal to all tangent vectors.

For a triangle (i,j,k), we can compute a surface normal by taking the cross product of the edge vector (i,j) with the edge vector (i,k). For instance, if we consider the first triangle in the mesh above, we would compute its normal as

$N = (v_1-v_0) \times (v_2-v_0) = (1,0,0) \times (1,1,0) = (0,0,1)$,

i.e., we get a vector pointing out of the plane. However, suppose in our file this triangle had instead been listed as

0 2 1

Then our normal vector would be flipped:

$N = (v_2-v_0) \times (v_1-v_0) = (1,1,0) \times (1,0,0) = (0,0,-1)$.

In practice, arbitrary flipping of normals can cause all sorts of nasty artifacts---for instance, lighting or shading might change dramatically as we go from one triangle to the next.

Therefore, we want to make sure our triangles are consistently oriented whenever we load a mesh.

Question 1

Argue that the direction of a triangle's normal is unchanged if we make a cyclic permutation of its vertex indices, but flips direction if the permutation is not cyclic. For instance,

$(i,j,k) \longrightarrow (j,k,i)$

preserves the normal direction, but

$(i,j,k) \longrightarrow (j,i,k)$

reverses it.

Question 2

Reorder the vertex indices in the following meshes so that triangle normals have a consistent orientation. (Does this activity suggest a general algorithm for orienting a triangle mesh?) Note that the vertex positions are not provided, because they do not matter!

MESH 1 FACES
4 0 1
4 0 2
3 1 4
4 3 2
2 1 3
1 0 2

MESH 2 FACES
3 1 4
5 4 1
4 0 2
2 5 4
3 2 1
0 1 2

To make grading easier, please apply a cyclic permutation to each face in your final solution such that the lowest index appears first.

Question 3

Which vertices and edges of the following mesh are nonmanifold? Which ones are on the boundary? (It may help to draw a picture.)

MESH 3 FACES
1 2 5
2 0 5
0 1 5
4 3 5
4 6 3
4 7 3
10 4 5
3 10 5
8 10 9