CS 426 Exercises
  Polygonal Meshes

  1. The computers in MECA can draw triangle strips at faster rates than independent triangles. Why? <\li>
  2. If an object's surface is a closed 2-manifold, how many faces can share each edge? How many faces can share each vertex?
  3. Write the Euler-Pontcare formula for 3D polyhedra. Give values for V, E, and F for: a) a cube, b) an octahedron, c) a dodecahedron, d) an icosahedron.
  4. What is the computational complexity of an operation that changes the coordinates of a vertex V for each of the following mesh representations: a) list of triangles with explicit vertex coordinates stored redundantly (like the .ray representation)? b) triangle strip/fan? c) Vertex table and face table with references to vertices? d) winged-edge?
  5. What is the computational complexity of an operation that inserts a new vertex on the edge between two existing vertices V1 and V2 for each of the following mesh representations: a) list of triangles with explicit vertex coordinates stored redundantly (like the .ray representation)? b) triangle strip/fan? c) Vertex table and face table with references to vertices? d) winged-edge?
  6. Given a winged-edge data structure and a pointer to an edge E and a face F, write pseudo-code for the following functions: a) Return the face across E from F. b) Return the edge adjacent to E moving counter-clockwise around F. c) Return the vertex adjacent to E moving clockwise around F. What is the computational complexity of these operations?