Assignment A2: Subdivision Surfaces

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

Revision 3: 19 Feb. 2001.

Overview

Reading

• Part 1 consists of three documents:
  • Cover page for reader ( ps , pdf )
  • I suggest you print pages 13-21, 65-89, and 99-102 of the PDF course notes of the: Subdivision for Modeling and Animation, course at the SIGGRAPH 2000 conference, Pages 69-73 are the most important for this assignment.
  • Addendum page ( ps , pdf ) that I wrote for the above.
  You'll have to print these three documents yourself.
• 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. This was distributed in class 13 Feb.

Requirements

• Read in OBJ files for closed, triangulated polyhedra.
• 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 technical 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).
• Model an interesting, curved shape of your choice using subdivision surfaces. Perhaps a finger, hand, car, airplane, or fish. 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. Start simple and work your way up.
• On the demo date, show us your code and demonstrate all of the above. We'll ask you to read in an OBJ or two and see if your program generates the correct surface, among other tests.
• By the animation deadline, create an animation in which your creation changes shape (flexes, twists, etc -- something more than an affine transformation). Create the animation by animating the level 0 control points and then generating a higher level subdivision surface from them. Animating the camera and lighting are optional. Put your 640x480 resolution pictures in a2/anim/f???.tif , e.g. f000.tif, f001.tif, ... 60-180 frames is about right.
• We expect that you will want to change your code after your demo but before the animation is due, so there is no penalty for this.

Tips

• Implement subdivision using the basic butterfly rule first, not worrying about extraordinary vertices or normals (calculate face normals instead). 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/a2/cell as your subdivision surface representation.
• Start from the user interface code we've provided (see classdir/pub/src/a2/subsurf/subsurf.cc).

  As of 18 Feb, subsurf is working with FLTK, the recommended user interface library. Please work from this version (the one in a2/subsurf/). As of 16 Feb, an Xforms version of subsurf that compiles on Suns is available in a2/subsurf.xforms. You can write your program using either the Xforms version or the FLTK version of subsurf, but we recommend the latter because of better portability.

  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.
• You'll probably find it very handy to have a button that writes out the currently displayed surface in OBJ format.
• 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 A3 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 A2, so perhaps think ahead about what you might want to do (a chrome car, a glass hand, ...).

Grading

• 3 points for interesting shape (preferably not a formless blob)
• 2 points for animation
• 4 points for correct modified butterfly
• 2 points for good Gouraud shading, and display during interaction
• 1 point for good karma

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.

Change log:
18 Feb: FLTK version of subsurf ready
16 Feb: where to find Xforms version of subsurf

15-463, Computer Graphics 2
Paul Heckbert