COMP 557 - Fall 2010 - Assignment 3
Catmull-Clark Subdivision Surfaces

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.

Provided Code

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.

• A3App

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

• PolygonSoup

  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.

• HalfEdge

  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.

• Vertex

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

• Face

  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 soup

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

• Sample Geometry

  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.

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 the siggraph 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.

1. 

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

2. 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 points.

3. 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 blue points.

   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 keyboard interface.

   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 child2.

   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.

4. 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.

5. Normals

   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.

6. 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 twin pointer.

   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.

7. Readme File

   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 question:

   1. 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 implementation!

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