Mixed semi-sharp cube example from [DeRose et al. 1998]

15-864 Assignment 1: Subdivision Surfaces

Due Monday, Feb 13 before midnight.


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.


  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):

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:

Additional tips


  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.