COMP 557 - Fall 2009 - Assignment 3
Due 23:59 pm Monday 2 November
In this assignment you will build half edge data structures from
polygon soups, and subdivide meshes using the Loop 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.
The sample code is a working program that
will load one of the sample polygon soups and draws 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
build a half edge data structure and will try to subdivide it.
Display call Will display the coarse polygon mesh by default, and
also displays 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
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).
HEDS (you need to finish this class)
HEDS is the Half Edge Data Structure, and simply contains a list
of faces (where each face is implicitly specified by a half edge).
You will need to implement the constructor which builds the
structure given a polygon soup
Loop (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 consist only of triangles and work with the
provided soup loader. You should test with simple models such as
the tetrahedron before trying out the cow, rabbit, and monkey
models. Several are meshes that involve boundary and should only be
used if you decide to complete the 6th objective (e.g., triangle,
ico-hole, opentet, monkey). 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.3 on page 70 of the siggraph 2000
course notes on subdividion surfaces. Use Loop's original rules
(as opposed to those of Warren, or the modified scheme described on
Pages 70 and 71). For the normals in step 5 refer to Equation 4.1
on Page 71.
Half Edge Data Structure
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 (a
simple 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).
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).
Write code to compute the new position of the existing vertices in
the subdivided model (i.e., compute the even vertices using Loops
original scheme). 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 Loop.subdivide
call, but 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 points.
Write code to compute the odd vertices by subdividing the half
edges of every face (use Loop's original scheme as mentioned above).
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 child vertices you created in the
previous step). 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 the next step). As such, you will not yet be able
to display these new half edges using the A3App keyboard
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
are drawn as green points.
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 6
child half edges that fall into the middle of each face (their parent
is a face, 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.
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.
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.
Rational Curve Endpoint Derivatives
What are the derivatives of a cubic rational Bezier curve at its
endpoints in terms of its control points? Be careful! Hint: use
non-homogeneous coordinates to make sure you get the correct answer.
Show your work.
The code for this assignment largely involves three parts:
loading, subdivision, and display. The provided code, and the code
that you wrote, is likely not very optimized for speed or memory
usage. Come up with a list of optimizations that you would make to
improve each of the three parts (perhaps several for each part).
Describe for each how the code would need to be modified, explain
why it would be better, list any difficulties that might be involved
in making these modifications, and finally give your intuition on
what kind of improvement you might expect and under what conditions.
Write your answer in plain language (English or French), and give
each of your optimizations a short descriptive name. Be
thorough and brief. Use no more than 1 full page at 12 pt font (you
can probably get away with much less).
Marks for this written question are awarded with diminishing
returns, much like real optimizations, and also similar to the
process of subdividing meshes. You mark will be a geometric sum
where the number of terms is the number of real, clearly described,
distinct optimizations that you list. Specifically, 0.5 for one,
0.75 for two, 0.875 for three, 0.9375 for four, and in the limit,
converging to 1 full mark.
Great! Be sure your name and student number is in the window
title, and in the comments of the code. Submit your source code
as a zip file via webCT.
Include a readme.txt file with your comments. Note that your
written questions need to be submitted to a different
assignment box! DOUBLE CHECK BOTH of your submitted files by
downloading them from WebCT. You can not recieve any marks for
assignments with missing or corrupt files!
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.