[an error occurred while processing this directive] COS 526, Fall 2004: Written Exercise 1 [an error occurred while processing this directive]

# COS 526 - Advanced Computer Graphics

### Fall 2004

 Course home Outline and lecture notes Assignments

## Written Exercise 1

Due Thursday, Sep. 23
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 Vi and Vj determine all faces that touch both of these vertices.
2. Remove face Fkfrom 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.

Last update 29-Dec-2010 12:01:30
smr at princeton edu