Cornell CS 466: Computer Graphics Practicum

Subdivision Surfaces Project

Overview

In this practicum component you will get experience working with adjacency data structures for representing polygon meshes, and subdivision surface algorithms for modeling and animation.

Project Steps

1. OBJ file format:  Familiarize yourself with the OBJ file format. Build an OBJ file parser to read vertex and polygon face data, e.g., into temporary arrays.  Error handling is recommended to handle a variety of OBJ files that might be used.  For example, 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." Some sample triangle-based and quadrilateral-based meshes are provided below.
2. Mesh adjacency datastructure: Build an object-oriented mesh datastructure with adjacency information to represent the input mesh:
   
• You may use any number of adjacency datastructures, such as:
• Half-edge
• Winged-edge
  
• You should support geometry files with multiple (disconnected) manifold-with-boundary mesh components. Feel free to implement boundaries as you see fit. 
• Your data structure can support general polygons (not just triangles or quads).  However, although you can load arbitrary meshes, you can assume (but check!) that only a particular face type is present for subdivision.
  
3. Subdivision: Use your data structure to subdivide the mesh using one subdivision algorithm, e.g., 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).  Augment the adjacency datastructure to support parent and child relationships to navigate the multi-level subdivision mesh hierarchy. For example, vertex objects can point to their child (finer) and parent (coarser) vertex relations;  faces can point to their children (finer) and parent (coarse) relations;  edges can point to their parent edge, or odd-vertex child (in cases where they are bisected);  mesh objects might provide access to mesh components, and support access to refined or coarsened variants.
   
4. Interactive modeling: Integrate subdivision surfaces inside your geometric modeling assignment so that you can interactively model and deform the surfaces. You should integrate the OBJ file loading, and subdivision kernels into the modeler GUI, and allow interactive selection of subdivision levels of detail.  Scenegraph transformations act on the control points of the subdivision mesh. Support interactive picking of base-mesh control points to interactively deform the surface.
5. Mesh export: Implement exporting of subdivided polygon meshes within the modeling program.  For example, a typical usage would be to subdivide and modify a loaded OBJ mesh, then write the new mesh (at some level of detail) out to disk as a new OBJ file complete with vertices, faces, normals, etc.
   
6. Hand in your full source code, and compiled executable tools. 

Other things to try:

• Subdivision surfaces can be very beautiful when rendered nicely.  Integrate subdivision surfaces in your final Ray II ray-tracing project. 
  
• 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.)
• 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.
• 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.

.obj files

Here are some connected manifold-with-boundary test meshes:

• 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.)

Mesh-related Pre-Submission (due Fri Nov 16)

• OBJ file format parser capable of parsing either triangle or quad meshes, and that works on the test OBJ files above.
• Mesh adjacency datastructure that works with the (tri or quad) test meshes.
• To illustrate that the mesh has been constructed properly, render the mesh datastructure's contents using OpenGL--performance is not a factor.
• Submit your pre-submission materials via CMS for CS 466.
  

Additional tips

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.