What's Wrong with That Mesh?!

In lecture we described a mesh in terms of two pieces of data:

• the connectivity, which says which mesh elements are next to/contained in which other mesh elements, and
• the geometry which says how mesh elements should get drawn in two- or three-dimensional space.

Something a lot of people struggle to understand (even seasoned graphics veterans...) is what it means for a mesh to be "valid." The main source of confusion is that just because a mesh "looks broken" does not mean its connectivity is invalid! Conversely, however, if the connectivity is broken, then it's impossible to meaningfully talk about the geometry. In short:

• Possible: valid connectivity, degenerate geometry.
• Impossible: invalid connectivity, well-defined geometry.

These exercises will (hopefully!) help us understand this stiuation a bit more clearly. The key concept is to think of mesh validity as a precise set of checks that can be performed on the digital data. You should never just try to "eyeball it" when checking if a mesh is valid!

In general, there are so many different ways a mesh can be "wrong," it's a surprise that anything can ever go right! But as long as we're aware of a few common problems, we can check for these errors systematically. However, before developing these checks we need to make sure we really understand what it means to be a mesh.

Some Basic Checks

To get warmed up, let's start with a simple data structure, and check some of its basic properties. In particular, suppose we have a vertex-face adjacency matrix given by an integer array f[n][3], where n is the number of faces. For simplicity, we will assume that there are no repeated entries in any row f[i] of this array. Your answers may assume any auxiliary data structure you like, but should only need very basic/standard data structures (i.e., not other mesh data structures!).

1. What kinds of polygons does this array encode?

2. Using only the array f, how can we count the number of vertices in this mesh?

3. Using only the array f, how can we count the number of edges in this mesh?

4. Give a simple algorithm to check if the mesh has boundary.

5. Give a simple algorithm to check if the faces of the mesh are consistently oriented, i.e., if all vertices of all faces are in clockwise order (or they're all in counter-clockwise order). Does your solution to this question change your answer to the previous question?

6. Give a simple algorithm to check if the mesh has any nonmanifold edges.

7. Give an algorithm to check if the mesh has any nonmanifold vertices. This one is slightly trickier than the last one.

8. Why didn't you need the list of vertex positions to perform these checks?

What Can Go Wrong with a Triangle?

Let's start by considering just a single triangle. It's not hard to imagine making a cone out of a single paper triangle: just pick up the triangle, and tape two of its edges together. The geometry of this triangle is not flat, but the connectivity is still that of a triangle mesh. In particular, there are two vertices i and j, three edges, from i to j, then j to j, then j back to i, and a single triangle with three corners: two at j and one at i.

1. Try encoding this mesh using the three connectivity data structures we've studied: vertex-face adjacency list, signed incidence matrices, and a halfedge mesh. For the moment, do not worry about the geometry---only the connectivity. Do all three data structures clearly describe this connectivity? Why or why not?

2. Is our one-triangle mesh manifold? Why or why not? (Notice that this question has nothing to do with the geometry! Only the connectivity.)

   Ok, now let's think about the geometry of this mesh. Traditionally, given three vertices in space, we draw a triangle by connecting these three vertices along three line segments (to form the edges) then "filling in" the three edges to make a flat triangle. More precisely, we can always think of the way we display a triangle in terms of a function f(b1,b2,b3) that takes the three barycentric coordinates b1, b2, b3 into space.

3. What does the set of all barycentric coordinates look like? I.e., what is the set of all triples (b1,b2,b3) such that b1, b2, b3 > 0 and b1 + b2 + b3 = 1?

4. Given coordinates x1, x2, x3 for the three vertices of a triangle, what is a function f(b1,b2,b3) that describes a flat triangle interpolating these three coordinates?

5. What does the mesh from Question 1 look like if we draw it using the function f? What implications does this drawing have for the connectivity of our mesh?

6. Suppose we always use the same function f from Question 3 to draw triangles. Is it possible for a "normal" triangle (with three distinct vertices i, j, k) to look degenerate? In other words, if we see a degenerate triangle on the screen, do we immediately know something about the connectivity of our mesh?

7. Nobody ever said that a mesh has to be made of flat triangles. Suppose you are given the barycentric coordinates b1, b2, b3 associated with the three corners of the triangle from our one-triangle mesh. How might you use these barycentric coordinates to more nicely draw this triangle in space?

8. Let's consider a more extreme situation, where all three vertices of a single triangle are the same. What can this figure look like? Is it possible for such a triangle to be part of a manifold triangle mesh?