= Assignment 8 - Subdivision Surfaces =

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

~+Questions? Check out the [wiki:self:Assignment8Discussion 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 [http://graphics.stanford.edu/courses/cs148-07/assignments/assignment8/assignment8.zip 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}}}.  

http://graphics.stanford.edu/courses/cs148-07/assignments/assignment8/facediagram.png

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}}}:
  * {{{SubdivFace::VertexPos}}}
  * {{{SubdivFace::NextFace}}}
  * {{{SubdivFace::NextVertex}}}
  * {{{SubdivFace::OtherVertex}}}

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.  



http://graphics.stanford.edu/courses/cs148-07/assignments/assignment8/splitdiagram.png