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 also produced some reusable
command-line tools for subdividing (and displaying) meshes stored in
the OBJ file format.
Details
-
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.
-
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).
- "subdivide" command-line tool: Make command line
tool to subdivide one obj file and produce a second, e.g., subdivide
-loop 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.
- "displayMesh command-line tool: Make a simple
command line tool for displaying your untextured subdivision meshes
with exported normals. Note that you needn't use your half-edge data
structure for this step. To view multiple subdivision levels, support
loading of multiple meshes, e.g., displayMesh meshL0.obj meshL1.obj
meshL2.obj, and toggling which mesh is displayed using arrow
keys. Provide some capability for moving the camera around the scene
so we can view the entire mesh (and document this!).
- 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 tools (subdivide and
displayMesh) 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:
- 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
-
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 Jin, John 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, 1998.
-
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 Levin, and Wim Sweldens.
Subdivision for Modeling and Animation.
SIGGRAPH 2000 Course Notes. 2000.
Questions? Contact Christopher Twigg.