Animated Subdivision Surfaces

Subdivision surfaces are a common way to model realistic looking smooth surfaces like human skin and cartoon characters [1].  For this project we decided to implement a non-interpolating Loop subdivision scheme for subdivision surfaces to model the Pink Panther, and then import this model into the CSE557 animator project [5].  The goal was to animate a smooth looking character modeled by a subdivision surface.

Our work consisted of two distinct parts.  The first part involved taking the skeleton code for a MFC subdivision surface application, Sub, from the CSE557 subdivision surfaces project [6] and implementing a non-interpolating Loop subdivision scheme along with a means for users to modify the base subdivision mesh.   The second part involved extending the CSE557 animator project to read models exported from Sub and support rendering subdivision surfaces as well as interactively manipulating groups of control points in the base subdivision mesh.   Here is a more detailed description about each part.

In this part we built Sub, a MFC application used to create, edit, load and export a subdivision surface model.  To support this functionality, we added the following functionality to the original CSE557 subdivision surfaces project:

• non-interpolating Loop subdivision - This was implemented based on the class notes and Wavelets of Computer Graphics [2] [3].
• interactive addition of control points - The user can interactively add control points by holding SHIFT + CTRL while clicking with the left mouse button on 3 control points that share a common face.  While still holding SHIFT + CTRL, if the left mouse button is clicked again, a new control point is created equidistant from the clicked points.  The old face deleted and three new faces are created between the new control point and the clicked points.
• interactive grouping of base mesh control points - The user can group a set of points by first specifying a group name (an integer) and then drawing a bounding box around the points to be groups by holding SHIFT + CTRL and clicking/dragging with the right mouse button.  The division of the base control mesh into groups is used by the animator to move parts of the mesh in unison. Each group can be thought of as a "bone." The animator code is designed to work well with hierarchical models, so a scheme was needed to relate groups via a parent-child relationship. In order to invoke a hierarchy on the groups, we devised a integer naming convention. If group A is a child of group B, then the prefix of group A's name will be group B's name. Group A's name is completed by adding an indifying single digit integer. For example in our artifact the upper-arm has group name "1".  Every other group that starts with a 1 falls under group 1.  The lower-arm has group name "11", the hand "111", and the 3 fingers "1111", "1112", and "1113".  Moving the upper-arm moves the rest of the groups as well.  However, moving the hand, will only affect the hand and the fingers.
• interactive specification of group pivot locations - In the Animator, the user will mainpulate groups, or "bones", via rotation around the X, Y and Z axises. In order to keep a group's relative position to its parent and child groups, one must specify pivot locations, or "joints." The user can interactively specify a group's pivot location, by entering a group name, holding down the SHIFT + ALT keys and clicking on point already in the mesh with the center mouse button.  The current location of the poitn selected is recorded and saved as the pivot location for the group name entered. If the selected point is then move, the pivot location remains the same.  If no group pivot location is specified, the default value of (x=0, y=0, z=0) is used.
• inclusion of group information in exported model - Originally Sub exported base control mesh for subdivision surfaces in a file format similar to the OBJ format. The original file format was further extened to include information about the groups the user specified. In the exported file, each vertex is tagged with a group name. Also, for each group specified by the user an entry is included in the exported file that identifies the pivot location.

In this part we built Animator, a FLTK application used to animate the subdivision surface models that are exported from Sub.  The CSE557 animator can now:

• render subdivision surfaces - This involved taking the code that stored subdivision base meshes and rendered the surfaces from the subdivision surface project and integrating it into the animator project. Menu items were added to the view menu on the main animator window that allow users to specify a level of subdivision in the range [2,4,6,8].
• import models exported by Sub - In addition to reading vertex and face information into the internal data structures used by the subdivision surfaces code, the Animator also stores the hierarchy of the groups of control vertices. For each distinct group, a group object stores information about the group's current frame (orientation and origin) and the positions of the group's vertices as well as the positions of its children's vertices. Once all the groups are read, they are collected together into a hierarchical tree structure, determined via the naming scheme described above.
• automatically create X, Y, Z rotation control sliders for each group - Once a model is loaded, control sliders are created for each distinct group (or "bone") in the file and labeled with the group name. These control sliders allow the user to rotate a group about the group's pivot point (or "joint") around the X, Y and Z axis. Each group tracks the changes to its controls as the program runs. When a change is detected, the group repositions its vertices as well as its children's vertices and then the model is resubdivided. We found that dynamically adding controls when the model is loaded to be a very convenient because it freed us from having to hard code the addition control sliders to main animator window for every group in the model.

We found several issues and concerns in our project worth discussing.

• First, our original plan was to try and model the entire Pink Panther from our previous Animator project using subdivision surfaces.  This turned out to be an unreasonable goal since modeling such a complex model via directly editing a base control mesh is very difficult and time consuming.  So we settled on just modeling the Pink Panther's arm.  This is OK since we were more interested in how the triangle mesh would respond to bends and if something realistic looking can be modeled.  We were happy to find that this was the case for our arm, and that something more complex and realistic looking is feasible.
• In the beginning, we found the Quad-Edge data structure used to store the subdivision surface a bit tricky to understand.  After studying Paul Heckbert's notes (which was very useful) [4] and with Daniel Wood's help we were able to understand the data structure well enough to add control points in the middle of a selected face.
• We found the ability to interactively add control points less useful than we originally anticipated.  It is very difficult to model anything substantial by only adding points to the middle of a face in the base control mesh.  Most things that we wanted to model start off as a rough box, and creating a box from something non-box like, such as a simple tetrahedron (the most basic filled polygon one can create) is not straightforward. As a result, we ended up creating our base model by hand, editing the input file. This was very tedious and prone to errors, but in the end it was the better alternative.  The interactive version, was used to tweak the base model and to add little bumps here and there.
• Specifying the group pivot requires the user to click on an existing point.  This is not ideal since the desired location for the group's pivot may be somewhere else, where there is no point.  However, this can be simulated by first dragging an existing point to the desired location, choosing that as the group pivot, and then dragging back that point to its original location.  This seemed to be a reasonable solution since just clicking on the screen (which is in 2D) does not work well because the model is in 3D.  We didn't want to have the user try to guess the Z coordinate by typing in the location.
• Other issues arose from the fact that in the context of the subdivision surfaces code points are viewed more in terms of global coordinates whereas in the context of the Animator points are viewed more in terms of local coordinates (with respect to hierarchical models at least) In hopes to change as little about the data structures used to render and store subdivision surface in the Sub application, separate code was written in the Animator to commensate for these differences. The method implemented involved transforming and un-transforming points in order to reposition the base control mesh. This method is prone to numerical error (in the case of a singular transformation matrix) and often caused the model to "blow up." Future work should explore how to alter the subdivision surfaces data structures and rendering code to incorporate a notion of local and global coordinates. This may involve storing the original base control mesh positions relative to group pivot locations and keeping track of a matrix stack, much like in OpenGL.

For our artifact we modeled the Pink Panther's arm using subdivision surfaces.  We then imported this into animator, and animated the arm such that it picks up a ball and bounces it a few time.  After the ball deflates, the Panther's arm expresses it's frustration by pounding on the floor, arhhhhhh ....

Here is a link to the mini movie:

One Of Those Days [2.9 MB]

[1]        Tony DeRose , Michael Kass , Tien Truong, Subdivision surfaces in character animation, Proceedings of the 25th annual conference on Computer Graphics, p.85-94, July 19-24, 1998, Orlando, Florida, United States

[2]        Stollnitz, DeRose, and Salesin.  Wavelets of Computer Graphics: Theory and Application, 1996, section 6.1-6.3.

[3]        Class notes from CSE557 - Computer Graphics, Winter Quarter 2002.  Available:  http://www.cs.washington.edu/education/courses/557/02wi/lectures/14-subdivision-curves.pdf

[4]         Class notes by Paul Heckbert, Quad-Edge Data Structure and Library, March 2002. Available: http://www-2.cs.cmu.edu/afs/andrew/scs/cs/15-463/pub/src/a2/quadedge.html

[5]         CSE557 Animator Project - Winter Quarter 2002.  Available:  http://www.cs.washington.edu/education/courses/557/02wi/projects/animator/handout.html

[6]         CSE557 Subdivision Surfaces Project - Spring Quarter 1999.  Available:  http://www.cs.washington.edu/education/courses/557/99sp/projects/sub/handout.html