COS 526 - Advanced Computer Graphics

Fall 2004

Written Exercise 1

1. The Euler-Poincaré formula states that, for a polyhedral mesh topologically equivalent to a sphere, V - E + F = 2, where V, E, and F are the numbers of vertices, edges, and faces, respectively. Use this to show that for a large triangular mesh the ratio V:F:E is approximately 1:2:3. (Hint: it might make things easier if you think in terms of half-edges.) Also show that the average number of triangles touching a vertex is 6.
2. Compute the total size necessary to represent the following data structures for a 1,000-polygon mesh, assuming that point coordinates are represented with 3 4-byte floats and that all indices or pointers are represented with 4 bytes:
   1. Separate triangles
   2. Indexed face set
   3. Half-edge (remember to include space for vertex coordinates!)
3. You are implementing an edge collapse-based decimation algorithm, and are considering using either an indexed face set or a half-edge data structure. For these two possibilities, sketch how the following basic operations would be implemented. What is the relative performance of the two data structures? (Assume that the input is a closed orientable manifold triangular mesh.)
   1. Given a candidate edge collapse between vertices V_i and V_j determine all faces that touch both of these vertices.
   2. Remove face F_kfrom the mesh (and adjust the data structure to remain self-consistent).

Submitting

Please submit the answers to these questions in an email to smr@princeton.edu, with "CS526" in the subject line. Plain text email is preferred. Please see the general notes on submitting your assignments, as well as the late policy and the collaboration policy.