Assignment P3: Subdivision Surfaces

Computer Graphics 2, 15-463
Paul Heckbert
Carnegie Mellon University

Revision 2: 10 Mar. 1999.

Overview

Reading

• Part 1 consists of excerpts of the SIGGRAPH '98 Subdivision for Modeling and Animation course notes. Read the whole thing, but pages 68-70 are the most important for this assignment. The errata pages at the end of that reader contain important corrections to those pages.
• Part 2 is a reprint of the paper on the modified butterfly scheme, from the proceedings of SIGGRAPH 96. Read this too, particularly section 3.3.

Requirements

• Read in OBJ files consisting of triangles.
• Subdivide the surface to level 0, 1, 2, 3, 4, or 5, with interactive level selection. Level 0 means the original model (from the file), level i means each triangle has been split into 4^i sub-triangles. (this is the meat of the assignment)
• Display the model, subdivided to the selected level, with interactive option of filled polygons or wireframe, both with lighting.
• Do Gouraud shading so that the surface looks smooth, not faceted (you'll need to calculate vertex normals for this - use the method in the reader).
• Interactively move level zero control points, with redisplay of the subdivided surface.
• Spin it around interactively. (this might be slow for higher levels).
• Write out the currently displayed surface in OBJ format.
• Model an interesting, curved shape of your choice using subdivision surfaces. Perhaps a telephone handset (the part you speak into), a hand, a car, an airplane, or an insect. I suggest you design the level zero control mesh on paper (don't worry about the geometry too much; but try to get the topology right), type it into a file, and then use your interactive editor to adjust the geometry to make it look good.
• Make a nice picture (JPEG or TIFF format) of your creation. You can use the snapshot program for this. If you leave more than one picture file in your directory, add a README file telling us which to look at. Note that there is no animation requirement for this assignment.
• Put your code and your picture file in your p3 directory by the due date.
• Demonstrate your program during class on Thursday 18 March in Wean 5201/2/3/5/7.

Tips

• Implement subdivision using the basic butterfly rule first, not worrying about extraordinary vertices or normals (calculate face normals instead, as we did in P2). Get this working and visually check that it works.
• Then add extraordinary vertex handling and normal vectors.
• For modularity, put your butterfly code in a file, say subdiv.cc, separate from the main program, subsurf.cc.
• You'll probably want a tag field of some sort for marking edges and vertices as even (old) and odd (new). Feel free to modify the header files in the cell directory.
• Put lots of assert() calls in your code to check that your pointers are valid and point to what you expect. See the assert man page.
• Take advantage of the operator overloading (e.g. Vec3::Operator+) in the SVL library so that you can do vector arithmetic concisely.
• Use the quad-edge data structure code in the classdir/pub/src/p3/cell as your subdivision surface representation. This is unchanged from assignment P2.
• Start from the user interface code we've provided (see classdir/pub/src/p3/subsurf/subsurf.cc). This is a variant of the cellview code from P2.

  The interactive 3-D positioning scheme used is called a "mouse pole". Depending on which mouse button you click, a point can be moved in one of several planes. This allows points to be moved almost anywhere in 3-D space using a mouse and a single view. This interaction technique is much more intuitive than the use of x, y, and z sliders, say. You will probably not need to modify the mousepole code or viewing code.

  This program's user interface:

  • Left-mouse near a control point to pick it and move it in the plane parallel to the ground.
  • Middle-mouse near a control point to pick it and move it in the plane parallel to the screen.
  • Right-mouse does nothing useful at present.
  • Shift-left-mouse rotates the object. (hold down shift key while clicking with left mouse button). To rotate about a vertical axis, move the cursor horizontally across the center (equator) of the circle. To rotate about a horizontal axis, move the cursor vertically across the center of the circle (e.g. from N to S pole). To rotate something about an axis perpendicular to the screen, move the cursor outside the yellow circle that appears.
  • Shift-middle-mouse translates the object parallel to the screen.
  • Shift-right-mouse translates the object in and out (move mouse in y).

• Optimize your code for speed (but only after you get the basics working). You can optimize both at a high level (avoid redundant computation) and low level (precompute trig functions, see comments about compiling with -O and without -DVL_CHECKING in the Makefiles, remove assertions with -DNDEBUG). If you want to save memory and render fast using triangle strips, see the paper Fast Rendering of Subdivision Surfaces linked on the notes page.
• Note that the wireframe option above requires lighting for full credit. To do lighting on a wireframe model, simply send vertex normals before each line segment endpoint, as you would when drawing Gouraud shaded polygons. Try it - it works (and it looks very nice)! Making the lines more than 1 pixel wide helps, too.
• You'll probably want to run at level 2 or 3 most of the time, while moving control points. A nice trick to improve interactivity is to draw a cheaper approximation of the surface (drop by one level?) while the user is moving a control point, and then revert to the normal subdivision level when they complete the edit (let up on the mouse button).
• If your surface is too wiggly or has features that are too sharp, you could try smoothing your control mesh. The simplest method for this is Laplacian smoothing, where you move each vertex to the average of the positions of the neighboring vertices. If smooths too much, you could try linearly interpolating between the current position and this Laplacian location by some fraction.
• So far, our quad-edge code deals with manifolds (closed surfaces) only. If you want to extend it to work for manifolds with boundary, be our guest.
• Make the lighting nice (see figures in Zorin's paper for inspiration). You might want to use multiple colored lights. The code for this is currently in glrender.cc.
• You could associate a color with each vertex and interpolate those as well. Could be cool.
• Assignment P4 will be recursive ray tracing (specular reflection, transparency, ...) with the emphasis on image realism. In that assignment you might want to ray trace the objects you're designing in P3, so perhaps think ahead about what you might want to do (a chrome car, a glass hand, ...).

Extra Credit

• Interactive creases. Select an edge, somehow, and turn creases on and off there.
• Adaptive subdivision (split more where there's higher curvature, or polygons are big, or something like that).
• Interactive topological modifications to the control mesh.

15-463, Computer Graphics 2
Paul Heckbert