CMSC 435/634: Introduction to Computer Graphics

Assignment 4
Loop Subdivision with a HalfEdge Data Structure
Due November 13, 2015 @ 11:59 PM

The Assignment

The assignment is to write a program that performs Loop subdivision using a half-edge data structure. Your program will read a file in a simplified obj format (you may use the parser from the previous assignment) and write an obj file with the subdivided mesh. Your program should support the following usage:

subdivide input.obj output.obj number_of_subdivision_steps

After parsing the file into a set of vertices and triangles, you should construct the half edge data structure. Beware: initializing all the pointers appropriately is non-trivial. I found it helpful to augment my vertex class with a boolean flag, which is true for vertices that were in the previous subdivision and false for vertices that are added along edges in the current subdivision; an integer index that I use when writing the mesh, and the current vertex position as well as the new position (after completing subdivision). I also found it helpful to store pointers to all vertices, halfedges, and faces in std::vectors. My subdivide routing first iterates through the vertices in the current mesh, setting the flag and computing the new vertex position (using the Loop subdivision rules and the halfedge data structure to find neighbors). Then I loop over the edges dividing each edge in four halfedges (I visit each edge twice, but I skip it if it has already been divided). This requires *carefully* updating pointers in the halfedge data structure and creating new vertices. I also found it convenient to compute the location of new vertices at this point. After dividing all edges, each face in the mesh is a hexagon. I then loop over the faces, triangulating the hexagons into four triangles, again by carefully updating pointers. Finally I loop over the verices updating positions. An executable of my program is at:

~adamb/public/Subdivide/subdivide

I have pushed some simple models to your git repositories. Tet.obj is a great model to start with.

Advice

Work smart. This is a tricky data structure to implement.
Incorporate debugging code from the start (I wish I had).
I found it helpful to augment the data structure (e.g. giving faces/vertices/edges unique id) to help analyze its current state.
Make heavy use of assert; there are quite a few invariants of the halfedge data structure.
Write functions that perform simple tasks (such as listing all the edges around a face) to help with analysis.
Work on simple analysis operations before moving on to the more difficult mesh update operations.
Draw pictures!

634 only

TBD

Extra Credit

For 20 additional points, extend your program to handle catmull-clark subdivision. You may assume the input is a quadrilateral mesh (a simple sample input, quadcube.obj, has been pushed to your git repository). Note that there are many ways to write the averaging rules. I set edge points points to be

(1/16) * sum old_neighboring_quad_vertices + (3/8) * sum old_edge_endpoints

face points to be

(1/4) * sum old_quad_vertices

and vertices to be

(6 * sum neighboring_vertices + 1 * sum diagonal_vertices + (4*n*n - 7*n) * old_position) / (4*n*n)

where n is the number of neighboring quads.

What to turn in

Turn in this assignment electronically by pushing your source code to your proj3 GIT directory by 1:00 AM on the day of the deadline. We will be looking for multiple checkins documenting your development process.

As always, double check that you have submitted everything we need to build and run your submission, but no generated files (.o's, executables, or images). Be sure to include a Makefile that will build your project when we run 'make', and a readme.txt file telling us about your assignment. Do not forget to tell us what (if any) help did you receive from books, web sites or people other than the instructor and TA.