COMP 557 - Fall 2010 - Assignment 3
Catmull-Clark Subdivision Surfaces
Due 12:00 Noon Wednesday 10 November
In this assignment you will build half edge data structures from
polygon soups, and subdivide meshes using the Catmull-Clark subdivision
scheme. The polygon soup loader has been written for you and is
very minimal. It will load the vertex and face data from an 'obj'
file (though these files can also contain lots of other information
too). We have also provided you with a number of sample meshes that
will be useful for testing your program.
Download the sample code from WebCT. It is a
working program that
will load one of the sample polygon soups and will draw it. You will
need to add the jogl, vecmath, and mintools jars to your project.
The sample code zip file has the following contents.
The main application loads a polygon soup, will make calls to try
to build a half edge data structure and will try to subdivide it
(these method calls will fail because you need to implement them).
The display call will draw the coarse polygon mesh by default, and
also draws a half edge of the coarsest half edge data structure.
You can use the keyboard interface to walk the half edge data
structure. Press space to go to the twin and N for the next half
edge. Left and Right arrows will take you to first and second child
(if they exist), while up arrow will take you to the parent (if it
exists). Home and end keys can be used to change the subdivision
level currently displayed, while page up and page down will allow
you to go forwards and backwards in the model list (the model is
loaded and subdivided each time).
Contains a vertexList and a faceList, and code to load these from
an obj file. There is also some simple drawing code used by the
A3App class to draw the loaded soup.
The half edge class is simple, and provided for you. It has 6
pointers (next, head, twin, child1, child2, parent), and a method
for drawing a half edge to help you verify that your program is
working. For your convenience, it also contains a prev
method to get the previous half edge.
The vertex class is simply a container to hold the position of the
vertex, the normal (if it has been computed), and a pointer to its
subdivision child (if it exists).
The face class is a simple container for the face normal
(for flat shading), a pointer to the half edge, and a pointer to
its subdivision child (a vertex) if it exists. The constructor will
compute the normal and set all the leftFace pointers of the
half edge loop appropriately.
HEDS (you need to finish this class)
HEDS is the Half Edge Data Structure, and simply contains a list
of faces (each face has a half edge loop). You will need to
implement the constructor which builds the structure given a polygon
CatmullClark (you need to finish this class)
This class has one method called subdivide which takes a half
edge data structure and returns the half edge data structure for the
subdivided mesh. You will need to implement this method, and will
likely want to create several private static helper methods to
complete the objectives described below.
A number of sample obj files are included. All of the samples
are orientable manifolds, or orientable manifolds with boundary, and
work with the provided soup loader. Some consist only of
quadrilaterals, while others are a mix of triangles and
quadrilaterals. You should test with simple models such as the
torus and cube before trying out the money and human models.
Several are meshes that involve boundary and should only be used if
you decide to complete the 6th objective. Feel free to add your own
models or modify these as you please.
Steps and Objectives
In these first steps, assume that your mesh is a closed
orientable manifold, and as such, your half edges will always have a
non null twin pointer (i.e., assume no boundaries). For steps 2 and
3, refer to Figure 4.8 on page 76 of
2000 course notes on subdividion surfaces. For the normals in
step 5 refer to Equation 4.1 on Page 71. Many meshes will not be
exclusively quads. You should deal with these problem cases by
using a modification of the subdivision rules. See the description
starting at the bottom of page 76 and continuing on page 77. For
this assignment it is fine to use simplified versions of these rules
as discussed in class, and we can note that after one subdivision
all faces will have 4 sides.
Half Edge Data Structure (two marks)
Write code that builds the half edge data structure. You will
probably want to keep track of the half edges you create as you make
them so that you can easily connect each half edge with its twin. One
simple and somewhat inefficient approach would be to use
Map<String,HalfEdge> where "i,j" is the key for the edge from
vertex i to vertex j. An alternative mentioned in class would be to
maintain a list of half edges leaving each vertex and match up the
twins as you find them.
You can test that your structure is correct by using the interface
that the A3App provides for walking the data structure (space
for twin and N for next). Once you have your half edge data structure
working, set the default value of the drawCoarse parameter in
the A3App to false (so that you can avoid unchecking this
parameter in the interface on each subsequent run).
Even Vertices (two marks)
Write code to compute the new position of the existing vertices in
the subdivided model (i.e., compute the even vertices). You might do
this by visiting each face, and then computing the vertex child if it
has not already been computed.
You do not need to return a completed HEDS in
the CatmullClark.subdivide call. Instead, check that you are
getting the expected result by checking the "display child vertices"
checkbox in the controls. Code to draw the child vertices (if they
exist) is already in the provided code (see the bottom of the half
edge data structure class). Even vertices are drawn as red
Odd Vertices (two marks)
Write code to compute the odd vertices by subdividing the half
edges of every face. Odd vertices are created at each edge and in the
center of each face.
The face child vertex is easiest to compute (it is the average of
the vertices). Use the "display child vertices" to make sure that
these vertices are in the correct positions. They will be drawn as
The edge child vertices are slightly more involved. The head
of child1 should point to the new vertex, while
the head of child2 should point to the child vertex
of the half edge you are subdividing (i.e., one of the even
child vertices you created in step 2). Be sure to set the parent
pointers on the children that you create. In contrast, do not worry
about setting next pointers at this step (see step 4). As such, you
will not yet be able to display these new half edges using the A3App
Make sure that you also create children of the twin edge, hook the
children up to each other with their twin pointers. Be sure to get
the connections correct, i.e., child1's twin is its parent's twin's
Use the "display child vertices" checkbox to make sure that the
child vertices appear to be in the correct positions. Odd vertices
created by edge subdivision are drawn as green points.
Connectivity (two marks)
In this step you'll finish building the half edge data structure
for the subdivided mesh. To do this, you will need to create the 8
child half edges that fall into the middle of each face (their parent
is a face rather than an edge, so leave the parent pointer null). You
will need to set their head, next, and twin pointers, and also set the
next pointers of all the other child half edges in each face. You
will also need to create the child faces, each of which will be a
quad. Normally there will be 4 child faces, but if the source mesh
has n-gons, then you will be generating n child faces at this point!
Use the keyboard controls to walk between the parent and child half
edge data structures to make sure you have connected everything
correctly. Keeping your code as simple as possilbe and drawing
yourself pictures will likely help you succeed with connecting up all
the pointers correctly in this step.
Once you have a correctly connected data structure for the
subdivided mesh, you can compute normals of the limit surface. Refer
to Equation 4.1 on Page 70 of the siggraph 2000 course
notes on subdividion surfaces (note that vertex order is important
for getting your normal in the correct direction). When you set the
normal of a vertex, it will be used by the display method of the HEDS
class to draw the object with smooth shading.
Boundaries (optional, 5% bonus)
Quite often, we deal with meshes that have boundaries, and in these
cases you will have half edges that have no twin. Write code that
detects this, and implements the boundary subdivision rules. For
instance, before subdividing a vertex, you probably compute the
valence of the vertex by walking the half edges that arrive at that
vertex; use the boundary subdivision rule if you come across a null
You will also need to modify your code that computes the vertex
normals in a similar way. Refer to equation 4.2 on page 72 of the
subdivision course notes as a guide. Note the typo for k=3, and
modify the k>=4 case so that you compute a weighted sum of vectors (as
opposed to working with weighted points). Resolve any ambiguity with
respect to this on the WebCT discussion board.
Note again that this objective is optional. That is, you are not
required to complete this step. It is suggested that you only
complete this objective if you finished the others too quickly.
Create a readme.txt or readme.pdf file to
submit with your assignment. The readme should include any
comments you have with respect to the assignment, and describes
anything you deem to be noteworthy. Try to be brief! Your
readme should also contain a written answer to the following
The monkey head model has 32 triangles and 468
quadrilaterals for a total of 500 faces. How many faces will
there be after 2 levels of subdivision. Give a formula, or
clearly explain your computation. If you implement step 6,
then you can also check your answer with your
Great! Be sure your name and student number is in the window
title, in your readme, and in the top comments section of each of
your source files.
Submit your source code as a zip file via webCT. Include a
readme.txt or readme.pdf file with your
comments. Be sure to check that your submission is correct
by downloading your submission from WebCT. You can not
recieve any marks for assignments with missing or corrupt
Note that you are encouraged to discuss assignments with your
classmates, but not to the point of sharing code and answers.
All code and written answers must be your own.