Lecture 8 Quiz

Question 1:

A very useful relationship to be aware of is that as the number of vertices in a manifold triangle mesh goes to infinity, the ratio of vertices to edges to faces becomes

V : E : F = 1 : 3 : 2

independent of the shape of the surface. A formal proof of this fact takes a bit of work (but is not beyond your ability!). For this quiz question, you should just give a very rough argument for why mesh elements might appear in this ratio. (Hint: think about the manifold property, the notion of regular valence, and the fact that we are only considering triangle meshes.)

Question 2:

In lecture, we compared the storage cost of three common polygon mesh data structures: polygon soup, incidence matrices, and halfedge meshes. On the slide, we said that the storage cost was about 3x, 33x, and 36x the number of vertices in the mesh.

In this quiz question, make your own estimate for the storage cost for each of these data structures, in terms of the number of integer values and/or pointers required to encode just the connectivity (since the vertex coordinates will always take the same amount of storage). You should assume that an integer index and a pointer have the same cost (which is true in many moden systems, e.g., both pointers and integers use 64 bits of storage). You will need to carefully specify (and think about!) exactly how each of these data structures is implemented. For instance, in an incidence list do we need to store, for each vertex, the number of adjacent edges? If so, that means we must add one additional integer per vertex. Etc. Do your estimates agree with the numbers mentioned in lecture? (It's ok if they don't, so long as they are consistent with the representation you describe!)