Outline for Discussion Section 3

Discussion Section 3
TA: Peter Djeu (djeu@cs.utexas.edu)
October 26, 2003

Two Main Goals in Project 3

1. Use the 4 Point Scheme to subdivide Curves in 2-D
2. Use the Catmull-Clark Scheme to subdivide surfaces in 3-D

In both cases, you will be implementing a subdivision algorithm. Subdivision involves taking a set of control points that represent an object and then on each subdivision iteration adding new control points and possibly adjusting old control points. In general, because the number of control points is increasing on each subdivision iteration, the object will look smoother and smoother as it is further subdivided.

The 4 Point Scheme

Consider a closed 2-D curve which is represented as a sequence of vertices where each vertex is connected to its two immediate neighbors in the sequence (the last vertex in the sequence is also connected by an edge to the first vertex in the sequence). The vertices are treated as control points. When these control points are subdivided, additional control points are created.

Going from subdivision level j to subdivision level j+1 (also referred to in these notes as iteration j to iteration j+1), we add one new control points to each edge between existing control points (you can think of this process as adding the new control point onto the edge, although it is unlikely that the new control point will lie exactly on the edge). In the 4 Point Scheme, we will also be keeping all of our old control points (i.e. all control points in iteration j are in iteration j+1, unchanged). Thus, since we are adding one control point to each edge, and we are keeping all of our old control points, we will be doubling the number of control points each time we subdivide.

Transforming Pixel Locations to Viewing Frustum Coordinates

The glut mouse routine in the starter code returns the pixel coordinates when the user clicks the mouse in the glut window. The pixel origin is located at the upper left corner of this window. We need to transform these pixel coordinates (within the window) to viewing frustum coordinates, which are what we use to specify objects to OpenGL. Let the screen be (window_width x window_height) and let the viewing frustum be (world_width x world_height). Let world_left be the leftmost clipping plane of the frustum and let world_bottom be the bottommost clipping plane of the frustum. To transform a point (window_x, window_y) in pixel coordinates, we use:

world_x = [(window_x + 0.5) / window_width] * world_width + world_left
world_y = [(window_height - window_y) + 0.5) / window_height] * world_height
+ world_bottom

The "0.5" term is related to the dimensions of a pixel, which have a padding distance of 0.5 from their edges to their centers. Also notice since the pixel origin is in the upper left hand corner of the screen, we reverse the y axis by calculating (window_height - window_y) before applying the scaling.

The Weighting Rule

The location of the new control point is defined by the location of the four contiguous control points that are closest to an edge (the 2 control points immediately to the left of an edge, and the 2 control points immediately to the right). Let Pa be the new control point that will appear "on" edge (P1, P2), and let P0, P1, P2, P3 be the control points closest to edge (P1, P2). The weighting rule is:

Pa = (-1/16) * P1 + (9/16) * P2 + (9/16) * P3 + (-1/16) * P4

This weighting scheme is derived from the interesting row in the local subdivision matrix for the 4 Point Scheme in the Lecture notes. Basically, all control points that are not coincident with an existing control point (i.e. that will appear on edges) are derived using these weights.

A Word on Vector Notation

We are working with 2-D points for the 4 Point Scheme, so you can think of the point P1 as a 2x1 vector, such that P1 = (P1_x, P1_y). Let a and b be scalar constants. The formula:

P = a * P1 + b * P2

... is shorthand notation for the two scalar equations:

P_x = a * P1_x + b * P2_x
P_y = a * P1_y + b * P2_y

The weighting equation for the 4 Point Scheme is in this form. The weighting equations for the Catmull-Clark scheme is the analogous case for 3-D (where there are now 3 corresponding scalar equations for every equation using point notation). Notice no x coordinate appears in the same equation as a y coordinate, so we can handle all subdivision calculations on x coordinates first, then all subdivision calculations on y coordinates, and then put the x and y results back together.

Overview of Implementing the 4 Point Scheme

The basic algorithm for subdividing:

curr_points[] = iteration0_points[];

foreach subdivision level {
    allocate an array for the new points that we generate (this should be the
      size of curr_points[])
    let this new array be stored in variable new_points[]

    foreach set of 4 contiguous control points in curr_points[] {
        find the new control point by the weighting rule on the current 4 points
        add this new point to new_points[]
    }

    curr_points[] = merge curr_points[] and new_points[] by interleaving
                    (i.e. picking from array 1, array 2, array1, array 2...)
}

Possible Optimizations to the Basic Algorithm

When the user increases the subdivision level by 1, perform one level of subdivision from the current subdivision level's control points, rather than performing subdivision starting from iteration 0's control points. If the user adds a new control point, you will need rebuild the current level's control points from the iteration 0 control points.
When the user decreases the subdivision level by 1, remove every other point in the current set of control points (depending on how you represent your control points, you may need to remove every other control point starting from the first control point or starting from the second control point). If the user removes a control point, you will need to rebuild the current level's control points from the iteration 0 control points.

Drawing the Curve

You need to draw 2 different parts for the curve:

The location of the iteration 0 control points. These are the control points the user has entered with the mouse. One way of doing this is to use: glPointSize(5.0f), followed by glBegin(GL_POINTS), and then iterating through the control points and drawing each one with a glVertex3f(), and then call glEnd().
The subdivision curve, which is defined by the control points at the current subdivision level (aka iteration level). These points should be stored in a separate location than the iteration 0 control points. To draw the curve that is defined by these points, you should call glBegin(GL_LINE_LOOP) and iterate through the points, just like for VRML objects in Project 1. You should not draw the actual control points here, just the edges that connect them.

The Catmull-Clark Scheme

We are now working on a closed surface in 3-D that is represented as set of control points, which will also be refered to as a control point mesh. Just like the VRML objects in Project 1, the control point mesh is really a set of vertices and the polygon faces that our formed out of these vertices (specified using a face-index set). New vertices are generated by 3 rules:

Vertex Rule - adjusts the location of old control points as they are moved from iteration j to iteration j+1.
Edge Rule - adds a control point "kind of" to the middle of each edge ("kind of" because the control point does not necessarily lie on the edge or in the middle). This rule increases the number of control points in iteration j+1.
Face Rule - adds a control point to the center of each face. This rule increases the number of control points in iteration j+1.

Note that a big difference in Catmull-Clark subdivision is that control points shift (via the Vertex Rule) when the subdivision level increases. This is different from the 4 Point Scheme, where control point locations were fixed going from iteration j to iteration j+1.

The Vertex Rule

All shapes you will be working with are closed, so you should be able to apply the vertex rule to all vertices. If the control mesh had borders, control points on the border would not have enough neighboring vertices for the vertex rule and would need to be handled specially. Please see the Lecture 10 notes for the exact specification of the Vertex Rule.

The vertex rule is used to define the new location of a control point when going from iteration j to iteration j+1. It does not add a new vertex to the control mesh; it simply redefines the location of an existing control point. One thing to be careful of when using the vertex rule is to store new iteration j+1 control points in a completely separate mesh. Do not overwrite the control points of iteration j on the fly since these control points (and not the iterations j+1 control points) are the ones that will be used for computing the location of other neighboring control points.

The Edge Rule

Every edge in the control mesh is shared by exactly 2 faces of the object. Using these two faces and their vertices, you can determine the location of the new control point that is generated "on" the edge. The new control point that is generated does not necessarily lie on the edge, although it usually roughly lies somewhere in the region between the two endpoints of the edge. Please see the Lecture 10 notes for the exact specification of the Edge Rule.

The Face Rule

A new control point is generated near the center of the face, based on the average of the control points that define the face. Please see the Lecture 10 notes for the exact specification of the Face Rule.

Extraordinary Points

The degree of a vertex refers to the number of edges that are directly connected to the vertex. For a regular surface composed of quads, the degrees of all of the vertices are 4. However, if we have an irregular mesh of quads where some vertex has a degree that is not equal to 4 (either higher or lower), than we can still refine with some modification to standard Catmull-Clark. Change the weights in the vertex rule as follows:

Old              New
----             -------------------
1/64      ->     1 / (4n^2)
3/32      ->     3 / (2n^2)
9/16      ->     1 - 3/(2n) - 1/(4n)

Note that for an extraordinary point, the edge rule is still the same (each edge is still shared by exactly 2 faces) and the vertex rule is still the same (since all faces are still quads). The extraordinary points algorithm applies to any irregular quadrilateral surface, but keep in mind that the surface is still composed entirely of quads (this is slightly different from the case where we have triangles in our mesh, which is discussed next).

Catmull-Clark Subdivision on a Triangulated Surface

The 3-D surfaces you have been given for Project 3 are composed either entirely of quads or entirely of triangles. For surfaces composed entirely of quads, the regular subdivision scheme, combined with the technique for handling extraordinary points, handles all cases that may come up. However, for a triangular mesh, we need to split all triangle faces into quadrilateral faces before we can begin subdividing.

Given a control mesh with triangular faces, split each face (which are all triangles) into 3 quad faces. Note that this is a preprocessing step rather than a subdivision step since we are simply finding an alternate representation for the existing mesh topology.

Turning a triangle into 4 quads

A, B, and C are vertices from an existing triangle face. We calculate the new control points:

1, 2, 3 - by taking the midpoints of AB, BC, and AC, respectively.
4 - by taking (1/3) * A + (1/3) * B + (1/3) * C.

After generating these 4 new points, we discard the old face and create 3
new faces, which are all quads:

New Face 1: A, 1, 4, 3
New Face 2: B, 2, 4, 1
New Face 3: C, 3, 4, 2

Once this preprocessing step has been performed on all triangle faces, we have our subdivision level 0 control points. Now these subdivision level 0 control points can be subdivided using normal Catmull-Clark subdivision (with support for extraordinary points).

As an interesting side note, notice that this algorithm applies not only to triangles, but also generalizes to a mesh of arbitrary k-gons (and there could be multiple k-gons with different values of k in the mesh). If we find the center of each face, find the midpoint for each edge, and then create quadrilaterals everywhere (where each k-gon is turned into k quads), we will have created a full quadrilaterlization of the original mesh. This quadrilaterlization can then be refined using Catmull-Clark subdivision.

Overview of Implementing the Catmull-Clark Scheme

1. Perform a preprocess on the face-index set, creating:

Lookup table 1 such that, given a vertex, the table returns all faces that the vertex belongs to.
Lookup table 2 such that, given an edge, the table returns both of the faces that share the edge.
A face-to-new-vertex array, which has the size of the number of faces in the current iteration level.
A edge-to-new-vertex array, which has the size of the number of edges in the current iteration level.
Create new_vertices[], an array large enough to store the locations of all control points in iteration j+1. The number of control points in iteration j+1 should be: [number of control points in iteration j] + [number of edges in iteration j] + [number of faces in iteration j].

2. Perform the vertex rule on each vertex in the surface. Use lookup table 1 to find the n faces that include the current vertex, and perform the vertex rule (using the extraordinary vertex rule if n does not equal 4). Store all of the new vertices generated by the vertex rule in new_vertices[].

3. Perform the face rule on each face in the surface. For each face, get the vertices in the face and perform the face rule to generate a new vertex. Add the new vertex to new_vertices[], and set the value of the current face's element in the face-to-new-vertex array to be the unique vertex number for the vertex that was just generated.

4. Perform the edge rule for each edge in the surface. This step can be done in the middle of iterating through the faces in Step 3., or it can be done completely separately. In any case, for each edge in the surface, use lookup table 2 to find the 2 faces to which the edge belongs, and then perform the edge rule to generate a new vertex. Add the new vertex to new_vertices[], and set the value of the current edge's element in the edge-to-new-vertex array to be the unique vertex number for the vertex that was just generated.

5. All of the vertex locations have been generated, so replace iteration j's vertex locations with these new vertex locations. Cycle through iteration j's faces, and now, using the face-to-new-vertex array and the edge-to-new-vertex array, generate 4 iteration j+1 faces for each of iteration j's faces. We are basically quadrupling the number of faces (aka quads) on each iteration step. Now, replace iteration j's face array with this new face array. Having created a new vertex array and a new face array for iteraion j+1, we have now generated a face-index set for iteration j+1.
One iteration j face to 4 iteration j+1 faces

One iteration j face to 4 iteration j+1 faces

Drawing the Surface

Draw the surface either using GL_POLYGON with different colors at different vertices or using GL_LINE_LOOP for a wireframe. Pick the drawing method that best showcases the subdivision process.