15-864 Assignment 1: Subdivision Surfaces

Overview

In this assignment you will get experience working with half-edge data structures and subdivision surface algorithms. Upon completion of the assignment, you will have produced a useful command-line tool for subdividing meshes stored in the OBJ file format.

Details

1. Read a mesh from an .obj file and put it in a half-edge data structure. Note that your data structure should support general polygons (not just triangles), and support geometry files with multiple (disconnected but manifold-with-boundary) mesh components. We will provide C++ code for parsing .obj files (see below), and some sample triangle-based and quadrilateral-based meshes.
2. Use your data structure to subdivide the mesh using one of the subdivision algorithms discussed in class; namely, Loop scheme or Catmull-Clark scheme (or even Butterfly scheme, Kobbelt scheme, or Doo-Sabin scheme) (note that some of these schemes require nontriangle meshes, or involve dual meshes).
3. "subdivide" command-line tool: Make command line tool to subdivide one obj file and produce a second, e.g., subdivide input.obj output.obj. It should provide an error message if the input file has the wrong kind of geometry, e.g., "expected only triangles but found a 6-gon." Be sure to write out normals for the subdivided vertices.
4. Displaying/debugging meshes: Feel free to use any third-party software to visualize your mesh, e.g., maya, or make a simple command line tool for displaying your untextured subdivision meshes with exported normals.
   
5. Hand in your full source code, and compiled executable tools. All code should run on the Weh5336 cluster--but feel free to work on your own machine in the beginning. Your command line tool (subdivide) should give meaning help when typed, or with the "--help" option. Include a README file that summarizes what you did, any special build instructions, and how to control the displayMesh UI (preferrably in the "--help" option).
   Turn-in directories have yet to be created, but are forthcoming.

.obj files

You can find an obj file reader and some example code that uses it here. It depends on both the vl and boost libraries, both of which have been installed in a convenient location in afs (the Makefile includes all the appropriate paths; take a look at it for details). If you are curious about the .obj file format, Roy Riggs has a great summary.

Here are some connected manifold-with-boundary test meshes (more to appear soon):

• polyCubeTris.obj A simple triangle-based cube (for Loop scheme, etc.)
• polyCubeQuads.obj A simple quad-based cube (for Catmull-Clark, etc.)
• dyrtManArmTris.obj DyRTMan's disembodied arm in triangle form.
• simpleIris_tri.obj A simple iris model (triangle format).
• simpleIris_quad.obj A simple iris model (quadrilateral format).

Also, check out Turbo Squid; it has a lot of free models. (Warning: Some of these models can have pretty gross mesh topology, since artists seldom care about the numerical properties of the meshes they create. Improving the error error checking of your code will be helpful.)

Other things to try:

• Make you subdivision algorithm interactive, so that you can load and subdivide meshes interactively. You might also try deforming the base mesh, and seeing how the subdivided mesh is affected.
• Provide a command line option to write out positions and/or normals on the limit subdivision surface. Formulae of limit positions and normals for Loop surfaces are given in the course notes, or in [Hoppe et. al 1994]. See references for other subdivision types.
• Include support for textured meshes by subdividing texture coordinates the same way that you subdivided points. Details are in [DeRose et al., SIGGRAPH 98]. Watch out for texture boundaries.
• Try implementing support for semi-sharp features, as in [DeRose et al., SIGGRAPH 98], and provide a simple example. You can save the edge sharpness value (-1=smooth, 0,1,2,3...) in your HalfEdge object. (To automatically specify edge sharpness for a complex example, you could also map edge-flap angles in the control mesh to sharpness values.)

Additional tips

• Take a look at this page for some useful library pointers.
• If you're having trouble logging into the lab machines, please see this page.

References

1. Tony D. DeRose, Michael Kass, and Tien Truong. Subdivision Surfaces in Character Animation. Proceedings of SIGGRAPH 98. pp. 85-94, 1998.
2. Hugues Hoppe, Tony DeRose, Tom Duchamp, Mark Halstead, Hubert Jin, John McDonald, Jean Schweitzer, and Werner Stuetzle. Piecewise Smooth Surface Reconstruction. Proceedings of SIGGRAPH 94. pp. 295-302, 1994.
3. Jos Stam. Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values. Proceedings of SIGGRAPH 98. pp. 395-404, 1998.
4. Joe Warren and Henrik Weimer. Subdivision Methods for Geometric Design: A Constructive Approach Morgan Kaufmann, 2001.
5. Denis Zorin, Peter Schröder, Tony DeRose, Leif Kobbelt, Adi Levin, and Wim Sweldens. Subdivision for Modeling and Animation. SIGGRAPH 2000 Course Notes. 2000.