## COS 526 - Advanced Computer Graphics |
## Fall 2003 |

Course home | Outline and lecture notes | Assignments |

- The Euler-Poincaré formula states that, for a polyhedral mesh
topologically equivalent to a sphere,
`V - E + F = 2`,`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. Also show that the average number of triangles touching a vertex is 6. - 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:
- Separate triangles
- Indexed face set
- Half-edge (remember to include space for vertex coordinates!)

- 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.)
- Given a candidate edge collapse between
vertices
*V*and_{i}*V*determine all faces that touch both of these vertices._{j} - Remove face
*F*from the mesh (and adjust the data structure to remain self-consistent)._{k}

- Given a candidate edge collapse between
vertices

Please submit the answers to these questions in an email to
`smr@cs.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:02:55 smr@cs.princeton.edu