15-864 Assignment 1: Subdivision Surfaces
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.
- Read a mesh from an
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.
- 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, or Doo-Sabin
scheme) (note that some of these schemes require nontriangle
meshes, or involve dual meshes).
- "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
- Displaying/debugging meshes: Feel free to use
any third-party software to visualize your mesh, e.g., maya, or make a
command line tool for displaying your untextured subdivision meshes
with exported normals.
- 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
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
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
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
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.)
- Take a look at this
page for some useful
- If you're having trouble logging into the lab machines, please
- Tony D. DeRose, Michael Kass, and Tien Truong. Subdivision
Surfaces in Character Animation. Proceedings of SIGGRAPH
98. pp. 85-94, 1998.
- Hugues Hoppe, Tony DeRose, Tom Duchamp, Mark Halstead, Hubert
McDonald, Jean Schweitzer, and Werner Stuetzle. Piecewise
Smooth Surface Reconstruction. Proceedings of SIGGRAPH 94.
pp. 295-302, 1994.
- Jos Stam. Exact
Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter
Values. Proceedings of SIGGRAPH 98. pp. 395-404,
- Joe Warren and Henrik Weimer. Subdivision
Methods for Geometric Design: A Constructive Approach
Morgan Kaufmann, 2001.
- Denis Zorin, Peter Schröder, Tony DeRose, Leif Kobbelt, Adi
and Wim Sweldens. Subdivision
for Modeling and Animation. SIGGRAPH 2000 Course Notes.