Written Exercise 1

Questions

1. We are learning about several different 3D object representations, including polygonal meshes, multiresolution meshes, spline surfaces, subdivision surfaces, constructive solid geometry, BSP trees, voxels, points, and image-based representations. Of course, no one of these representations is best for describing every type of object, for every operation, in every application. For each of the following situations, please describe which object representation(s) you think is best for the object written in capital letters, and give a one or two sentence explanation why.
   1. Rendering images of a CLOUD for a movie.
   2. Checking for accessibility to different parts in a proposed AIRPLANE engine design (e.g., whether or not a repair person can reach a part with his/her hand)
   3. Finding interferences (intersecting parts) in a proposed AIRPLANE engine design (e.g., finds pipes passing through one another).
   4. Manipulating a "CLAY OBJECT" interactively, where the user can: "push" to make dents in the clay (perhaps creating a hole through to the other side), "pull" parts of the clay to make extrusions (perhaps pulling off a piece completely), and "smush" two pieces together (perhaps merging them into one).
   5. Animating a CHARACTER made out of JELLO that will deform according to physical laws as it moves.
   
   
2. 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.
   1. Use this formula 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.)
   2. Show that the average number of triangles touching a vertex is 6.
   
   
3. Compute the total number of bytes expected to represent the following data structures for a 1,000-triangle mesh, assuming that point coordinates are represented with 3 4-byte floats and that all indices or pointers are represented with 4 bytes (remember to include space for vertex coordinates!):
   1. Separate triangles
   2. Indexed face set
   3. Half-edge

Submitting

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