Assignment 8 - Subdivision Surfaces

Due Date: Thursday March 15th, 11:59PM

Questions? Check out the Assignment 8 FAQ and discussion page.

In this assignment you will implement subdivision of a triangle mesh using a technique referred to as loop subdivision. Conceptually, this is very simple. In each stage of subdivision, every triangle of in the mesh is split into 4 triangles and every edge in the mesh is split into two edge connected by a new vertex. The difficulty in this assignment arises from the need to efficiently manipulate a mesh data structure to perform successive subdivision operations.

Download and build the starter code

1. Begin by downloading the Assignment 8 starter code and latest version of the libST source here. Libst has changed in this assignment. We've added a new class STVector, that should assist you with operations on 3-vectors. You will be performing many such operations in this assignment.

2. Build the code. In this project, you will be modifying assignment8/subdiv.cpp. In the assignment8/ subdirectory we have placed two sample meshes tetra.shp (a tetrahedron) and sphere.shp (a sphere) for you to test your code on. Run the program using the command subdiv mymeshfilename.shp and you will see an image of the mesh rendered in wire frame on your screen. Notice that we've added some mouse controls that move the camera in this assignment, making it easier to view a 3D object. Dragging while holding the left mouse button rotates the camera around the object. Dragging with the right mouse button depressed zooms, and dragging with the center button depressed will dolly (translate) the camera.

Mesh Representation

The most important part of this assignment is understanding how the mesh is represented. We will be working with triangle meshes in this assignment, so each face contains exactly three vertices: They are labeled v0, v1, and v2 in the diagram below. In this assignment we will only be working with "closed" meshes, so each face is connected to another face on each of its three edges. The adjacent faces are labeled f0, f1, and f2. Lastly, we've labeled the edge between vertex i and (i+1) mod 3 edge i.


Take a close look at the SubdivFace class defined in subdiv.h which represents a triangle face. You will see fields in this structure corresponding to points to 3 vertices, pointers to 3 adjacent faces. SubdivVertex, also defined in subdiv.h, represents mesh vertices. Vertices contain information about their position, a pointer (adjFace) to one face that uses the vertex, and a flag describing whether or not the vertex is extraordinary. Recall from lecture that extraordinary vertices are vertices that DO NOT have valence 6.

Before going further, you should take a look at and understand the following useful routines in SubdivFace:

Then understand how the complete mesh is represented in the SubdivSurface class. Original face and vertex data is read from disk in SubdivSurface::LoadGeometry. SubdivSurface::ProcessBaseGeometry then analyzes the geometry information to determine adjacent faces as well as to determine which vertices are extraordinary. The resulting mesh with face adjacency information is then stored in mOrigFaces and mOrigVerts.

The finer resolution mesh after subdivision is stored in mSubdivFaces and mSubdivVerts. The following section describes how that mesh is computed.

Mesh Subdivision

When a face is subdivided, the face is split into 4 faces as shown below. These faces are referred to as child faces of the original face. Notice that the SubdivFace structure contains pointers to child faces. Also notice that subdivision creates a new mesh that contains all the vertices of the old mesh as well as a new vertex placed on every edge of the old mesh. The new vertices are called ODD vertices and are marked in red below. The old vertices carried over from the coarser mesh are denoted in black. They are called EVEN vertices. The childVert pointer of a SubdivVertex points to the EVEN vertex in a finer mesh.


last edited 2007-03-16 04:12:05 by rescomp-06-99712