This is an archive of a past semester of this course. Go to the current semester.
Assignment 2: GeoMenagerie

Due Date

Mon Feb 29th, 11:59pm


In this project you will explore a subset of the geometric topics covered in lecture. You will tesselate Bezier patches, manipulate half-edge meshes, implement Loop subdivision, and write shaders for your own meshes! When you are finished, you will have a tool that allows you to load and edit basic COLLADA mesh files that are now used by many major modeling packages and real time graphics engines. For the last part of the assignment, you'll be creating your own COLLADA file using free software like Blender!

Project Parts

  • Part 1: Fun with Bezier Surfaces (20 points)
  • Part 2: Average normals for half-edge meshes (10 points)
  • Part 3: Edge flip (10 points)
  • Part 4: Edge split (10 points)
  • Part 5: Upsampling via Loop Subdivision (20 points)
  • Part 6: Fun with Shaders (20 points)
  • Part 7: Design your own mesh (10+ points)
  • NEW: Website guidelines and deliverables for each part

As with the first assignment, all your deliverables should be documented in the website/index.html webpage. Your art competition submission should be saved in the root directory as competition.png.

Quick links

Getting set up

You can either download the zipped assignment straight to your computer or clone it from GitHub using the command

git clone

Please consult this article on how to build and submit assignments for CS 184.

A debugging note: Check out this page on how to set up gdb to work with recent OS X releases. Please use gdb to debug, particularly if you get a seg fault that you can't track! Turn on debug symbols by toggling this line at the top of the CMakeLists.txt file in the root directory:

    option(BUILD_DEBUG     "Build with debug settings"    ON)

You'll have to rerun cmake to update the Makefiles after doing this.

Using the GUI

When you have successfully built your code, you will get an executable named meshedit in the build directory. The meshedit executable takes exactly one argument from the command line. You may load a single COLLADA file by specifying its path. For example, to load the example file dae/quadball.dae from your build directory:

./meshedit ../dae/quadball.dae

After Part 1, you will be able to load Bezier surfaces by running a command such as:

./meshedit ../bez/teapot.bez

When you first run the application, you will see a picture of a mesh made of triangles. The starter code that you must modify is drawing this mesh. The editor already supports some basic functionality, like moving vertices around in space, which you can do by just clicking and dragging on a vertex. You can also rotate the camera by right-clicking and dragging (or dragging on the background), and zoom in and out using the scroll wheel or multi-touch scrolling on a trackpad. Hitting the spacebar will reset the view. As you move the cursor around the screen, you'll notice that mesh elements (faces, edges, and vertices) under the cursor get highlighted. Clicking on one of these elements will display some information about the element and its associated data.

In this assignment, you will add additional functionality to the program that allows you to modify the mesh in a variety of ways. Each of these methods is exposed through the viewer. There will be two basic types of operations:

  1. Local flip and split operations, which modify the mesh in a small neighborhood around the currently selected mesh element.
  2. Loop subdivision, which refines and smooths the entire mesh.

Each operation will be executed with a key press (A table of all the keyboard controls in the meshedit application is provided in the appendix).

Command Key
Flip the currently selected edge F
Split the currently selected edge S
Subdivide the mesh U

Notice that currently, nothing happens when keys are pressed - this is because you haven't yet implemented resampling! Unlike the previous assignment, no reference solution is provided. However, we will provide several examples of correct input/output pairs for each remeshing operation.

Note that each COLLADA file may contain multiple mesh objects; more generally, a COLLADA file describes a scene graph (much like SVG) that is a hierarchical representation of all objects in the scene (meshes, cameras, lights, etc.), as well as their coordinate transformations. Global resampling methods will be run on whichever mesh is currently selected.

Getting Acquainted with the Starter Code

Before you start, here is some basic information on the structure of the starter code. Your code for all parts except shading will be contained inside student_code.cpp. (For shading, you'll have to edit the shader/frag file.)

For Bezier patches, you'll be filling in member functions of the BezierPatch class, declared in bezierPatch.*. We have put dummy definitions for all the Bezier patch functions you need to modify inside student_code.cpp, where you'll be writing your code. You may additionally need to add member variables to the class definition in bezierPatch.h.

For half-edge meshes, you'll be filling in member functions of the HalfedgeMesh class, declared in halfEdgeMesh.*. We have put dummy definitions for all the half-edge functions you need to modify inside student_code.cpp, where you'll be writing your code.

For shaders, you'll be editing the shader/frag file.

Before you attempt parts 2-5 (the half-edge sections), you'll want to quickly consult these lecture slides as a half-edge refresher and then read this in-depth article with more detail about the half-edge data structure and its implementation in the starter code.

Part 1: Fun with Bezier Surfaces

We'll begin with a warmup problem to introduce you to working with triangle meshes before jumping into the half-edge data structure. The goal for this part is to tessellate a Bezier surface into triangles. The input Bezier surface is represented by 16 control points in 3D space. These points are stored as a 4x4 Vector3D array called controlPoints, which can be accessed from inside the BezierPatch class. You need to tessellate the given Bezier surface uniformly on a 8x8 grid in parameter space, which should produce 8x8x2=128 triangles. You'll want to consult this slide for the proper formula to evaluate each point, remembering the definition of Bernstein polynomials as well.

To implement this, you may need to add some member variables to the BezierPatch class (by modifying bezierPatch.h). The BezierPatch::preprocess function allows you to do some precomputation. For example, you might initialize your own member variables here based on the 16 control points. The BezierPatch::addTriangle function (defined inside bezierPatch.cpp) helps you add triangles to the output mesh. If your implementation is correct, you will be able to see a teapot by passing bez/teapot.bez as the input argument.

These are the functions inside student_code.cpp that you will need to modify:

  1. Bezier::preprocess
  2. Bezier::evaluate
  3. Bezier::add2mesh

Part 2: Average normals for half-edge meshes

Next, we move on to working with the full half-edge data structure. Again, read this article before you start working with the HalfedgeMesh class in this and subsequent parts of the assignment. Make sure you understand the code given for a printNeighborPositions function in particular.

In this part, you will implement the Vertex::normal function inside student_code.cpp. This function returns the area-weighted average normal vector at a vertex. This slide depicts this graphically.

In order to compute this value, you will want to use a HalfedgeIter to point to the Halfedge you are currently keeping track of. A HalfedgeIter (analogously VertexIter, EdgeIter, and FaceIter) is essentially a pointer to a Halfedge (respectively Vertex, Edge, and Face), in the sense that you will use -> to dereference its member functions. Also, you can test whether two different iterators point to the same object using ==, and you can assign one iterator to point to the same thing as another using = (this will NOT make the pointed-to objects have the same value, just as with pointers!).

Caveat: For this part only, you're implementing a const member function, which means you need to use HalfedgeCIters instead of HalfedgeIters. These merely promise not to change the values of the things they point to.

The relevant member functions for this task are Vertex::halfedge(), Halfedge::next() and Halfedge::twin(). You will also need the public member variable Vector3D Vertex::position.

How you might use these to begin implementing this function:

Vector3D n(0,0,0); // initialize a vector to store your normal sum
HalfedgeCIter h = halfedge(); // Since we're in a Vertex, this returns a halfedge
                             // pointing _away_ from that vertex
h = h->twin(); // Bump over to the halfedge pointing _toward_ the vertex.
               // Now h->next() will be another edge on the same face,
               // sharing the central vertex.

At this point, you should

  1. Save a copy of h's value in another HalfedgeCIter h_orig.
  2. Start a while loop that ends when h == h_orig.
  3. Inside each loop iteration:
    • Accumulate area-weighted normal of the current face in the variable n. You can do this by using the cross product of triangle edges (since the cross product of two vectors has a norm equal to twice the area of the triangley the define, so these vectors are already area weighted!). We've defined the cross product for you, so don't re-implement it yourself!
    • Once you've added in the area-weighted normal, you should advance h to the halfedge for the next face by using the next() and twin() functions.
  4. After the loop concludes, return the re-normalized unit vector n.unit().

If you are still feeling confused about how to use iterators, reread the halfedge article or take a look at the extensive comment at the top of the halfEdgeMesh.h file.

Part 3: Edge Flip

Now you should be a little more comfortable traversing the half-edge pointers. In this task, you will implement a more substantial method: a local remeshing operation that "flips" an edge, implemented inside the method HalfedgeMesh::flipEdge in file student_code.cpp.

More precisely, suppose we have a pair of triangles $(a,b,c)$ and $(c,b,d)$. After flipping the edge $(b,c)$, we should now have triangles $(a,d,c)$ and $(a,b,d)$:

Your solution should:

  • Never flip boundary edges (just return immediately if either neighboring face is a boundary loop). Every object has a useful boundary() function that can tell you if it is or is not on the boundary.
  • Perform only a constant amount of work -- the cost of flipping a single edge should not be proportional to the size of the mesh!
  • Not add or delete any elements. Since there are the same number of mesh elements before and after the flip, you should only need to reassign pointers.

The biggest challenge in properly implementing this operation (as well as split) is making sure that all the pointers still point to the right place in the modified mesh. An easy recipe for ensuring that all pointers are still valid after any general remeshing operation is:

  1. Draw a picture and/or write down a list of all the elements (vertices, edges, faces, halfedges) that will be needed from the original mesh.
  2. Draw a picture and/or write down a list of all the elements that should appear in the modified mesh.
  3. Allocate any new elements that are needed in the modified mesh, but do not appear in the original mesh (only relevant for the next part).
  4. For every element in the "modified" picture, set all of its pointers -- even if they didn't change. For instance, for each halfedge, make sure to set next, twin, vertex, edge, and face to the correct values in the new (modified) picture. For each vertex, edge, and face, make sure to set its halfedge pointer. A convenience method Halfedge::setNeighbors() has been created for the purpose of setting all pointers inside a halfedge at once.

The reason for setting all the pointers (and not just the ones that changed) is that it is very easy to miss a pointer, causing your code to fail. Once the code is working, you can remove these unnecessary assignments if you wish.

Tip: you can check which other objects in the mesh point to a given object by using the debug functions check_for inside HalfEdgeMesh. There's more information about these functions at the bottom of the halfedge documentation article.

Part 4: Edge Split

This time, you will make a different local modification to the mesh in the neighborhood of an edge, called a split. In particular, suppose we have a pair of triangles $(a,b,c)$ and $(c,b,d)$. The edge $(b,c)$ is split by inserting a new vertex m at its midpoint and connecting it to the opposite vertices $a$ and $d$, yielding four triangles:

This task is a bit tricker than "flip" because there are more pointers to keep track of, and you will have to allocate new mesh elements this time (e.g., two new triangles, three edges, some halfedges...). Your implementation should:

  • Ignore requests to split boundary edges, unless you are trying for extra credit (just return immediately if either neighboring face is a boundary loop). Note that splitting a boundary edge does make sense, but flipping a boundary edge does not make sense.
  • Assign the position of the new vertex to the midpoint of the original edge, i.e., the average of its two endpoints (see Vertex::position).
  • Perform only a constant amount of work -- the cost of splitting a single edge should not be proportional to the size of the mesh!
  • Allocate only as many new elements as needed; there should be no "orphaned" elements that are not connected to the rest of the mesh.

To obtain a correct implementation, you might try following the same "recipe" given in the previous task (though clever, clean, and simple alternatives are of course always welcome). To verify that your implementation works correctly, try flipping some edges that you've split, and splitting some edges that you flipped.

  • Extra credit: support edge split for edges on the boundary. For this, you will need to carefully read the section about the "virtual boundary face" in the halfedge article. In this case, you will split the edge in half but only split the face that is non-boundary into two. Give screenshot examples if you do this.

Part 5: Upsampling via Loop Subdivision

Now, we can leverage the previous two parts to make implementing the mesh topology changes in Loop subdivision very simple! In this task, you will implement the whole Loop subdivision process inside the MeshResampler::upsample in student_code.cpp.

Loop subdivision is somewhat analogous to upsampling using some interpolation method in image processing: we may have a low-resolution polygon mesh that we wish to upsample for display, simulation, etc. Simply splitting each polygon into smaller pieces doesn't help, because it does nothing to alleviate blocky silhouettes or chunky features. Instead, we need an upsampling scheme that nicely interpolates or approximates the original data. Polygon meshes are quite a bit trickier than images, however, since our sample points are generally at irregular locations, i.e., they are no longer found at regular intervals on a grid.

Loop subdivision consists of two basic steps:

  1. Change the mesh topology: split each triangle into four by connecting edge midpoints (sometimes called "4-1 subdivision").
  2. Update vertex positions as a weighted average of neighboring positions.

4-1 subdivision does this to each triangle:

And the following picture depicts the correct weighting for the new averaged vertex positions:

Written out, the new position of an old vertex is

(1 - n*u) * original_position + u * neighbor_position_sum

where n is the number of neighboring vertices, u is a constant as depicted in the figure above, original_position is the vertex's original position, and neighbor_position_sum is the sum of all neighboring vertices' positions.

The position for a newly created vertex v that splits an edge AB connecting vertices A and B and is flanked by opposite vertices C and D across the two faces connected to AB in the original mesh will be

3/8 * (A + B) + 1/8 * (C + D)

If we repeatedly apply these two steps, we will converge to a smoothed approximation of our original mesh. In this task you will implement Loop subdivision, leveraging the split and flip operations to handle the topology changes. In particular, you can achieve a 4-1 subdivision by applying the following strategy:

  1. Split every edge of the mesh in any order whatsoever.
  2. Flip any new edge that touches a new vertex and an old vertex. Note: Every original edge will now be represented by 2 edges, you should not flip these edges, because they are always already along the boundary of the 4 way divided triangles. In the diagrams below, you should only flip the blue edges that connect an old and new vertex, but you should not flip any of the black new edges.

The following pictures (courtesy Denis Zorin) illustrate this idea:

Implementation Walkthrough

For Loop subdivision, we have also provided some additional data members that will make it easy to keep track of the data you need to update the connectivity and vertex positions. In particular:

  • Vertex::newPosition can be used as temporary storage for the new position (computed via the weighted average above). Note that you should not change the value of Vertex::position until all the new vertex positions have been computed -- otherwise, you are taking averages of values that have already been averaged!
  • Likewise, Edge::newPosition can be used to store the position of the vertices that will ultimately be inserted at edge midpoints. Again, these values should be computed from the original values (before subdivision), and applied to the new vertices only at the very end. The Edge::newPositionvalue will be used for the position of the vertex that will appear along the old edge after the edge is split. We precompute the position of the new vertex before splitting the edges and allocating the new vertices because it is easier to traverse the simpler original mesh to find the positions for the weighted average that determines the positions of the new vertices.
  • Vertex::isNew can be used to flag whether a vertex was part of the original mesh, or is a vertex newly inserted by subdivision (at an edge midpoint).
  • Edge::isNew likewise flags whether an edge is a piece of an edge in the original mesh, or is an entirely new edge created during the subdivision step.

Given this setup, we strongly suggest that it will be easiest to implement subdivision according to the following "recipe" (though you are of course welcome to try doing things a different way!). The basic strategy is to first compute the new vertex positions (storing the results in the newPosition members of both vertices and edges), and only then update the connectivity. Doing it this way will be much easier, since traversal of the original (coarse) connectivity is much simpler than traversing the new (fine) connectivity. In more detail:

  1. Mark all vertices as belonging to the original mesh by setting Vertex::isNew to false for all vertices in the mesh.
  2. Compute updated positions for all vertices in the original mesh using the vertex subdivision rule, and store them in Vertex::newPosition.
  3. Compute new positions associated with the vertices that will be inserted at edge midpoints, and store them in Edge::newPosition.
  4. Split every edge in the mesh, being careful about how the loop is written. In particular, you should make sure to iterate only over edges of the original mesh. Otherwise, you will keep splitting edges that you just created!
  5. Flip any new edge that connects an old and new vertex.
  6. Finally, copy the new vertex positions (Vertex::newPosition) into the usual vertex positions (Vertex::position).

If you made the requested modification to the return value of HalfedgeMesh::splitEdge() (see above), then an edge split will now return an iterator to the newly inserted vertex, and the halfedge of this vertex will point along the edge of the original mesh. This iterator is useful because it can be used to (i) flag the vertex returned by the split operation as a new vertex, and (ii) flag each outgoing edge as either being new or part of the original mesh. (In other words, Step 3 is a great time to set the members isNew for vertices and edges created by the split. It is also a good time to copy the newPosition field from the edge being split into the newPosition field of the newly inserted vertex.)

You might try implementing this algorithm in stages, e.g., first see if you can correctly update the connectivity, then worry about getting the vertex positions right. Some examples below illustrate the correct behavior of the algorithm.

Possible Extra Credit Extensions:

  • Support surfaces with boundary. To do this, you will first need to make sure your edge split operation appropriately handles boundary edges (you do not need to change your edge flip function). You will also need to use a different weighted average for boundary vertices; see Boier-Martin et al, "A Survey of Subdivision-Based Tools for Surface Modeling" for more information.
  • Implement additional subdivision schemes. There are many alternatives to Loop subdivision. Triangle subdivision schemes include Butterfly and modified Butterfly (which are interpolating rather than approximating) and Sqrt(3) (which refines the mesh at a "slower" rate); the most popular subdivision scheme for quadrilateral meshes is Catmull-Clark. There are also special subdivision schemes for handling meshes with high degree vertices, e.g., extraordinary vertices, called polar subdivision.

Part 6: Fun with Shaders

For this part, you will implement Phong shading and environment map reflection shading. Take a look at these slides to review the basic concepts and variables used in shading equations.

The necessary variables for you to compute shader values are already defined in the shader file. In the meshedit program, you can press 0-9 to switch between different shading effects. Initially only shader #0 is implemented as reference. Shader #1 and #2 are the two shading effects you will need to implement. Shaders #3-#9 are for extra credit. You can try your own shading there -- be creative!

For both shader #2 and #3, you'll need to figure out the reflection direction of a given input direction. The figure below shows you how to do this.

Suppose the blue arrow in the figure is the normal direction $\vec{n}$ of a surface point. The reflection direction $\vec{o}$ of the input direction $\vec{i}$ shown in red can be obtained by $\vec{o} = 2(\vec{i}\cdot \vec{n})\vec{n} - \vec{i}$.

Tips on Environment Mapping

First compute the reflection direction in $(x, y, z)$ coordinates. Then, figure out $(\theta,\ \phi)$ in spherical coordinates as shown in the figure below.

Once you have $\theta$ and $\phi$, simply use $(\ \theta/(2\pi),\ \ \phi/\pi\ )$ as texture coordinates to access environment texture.

In shader/frag, a macro called USE_AUTO_MIPMAP is defined as 0 by default. If you want to enable auto mipmap to antialias, set the macro to be 1. However, when you enable it, you will see a seam on the object due to angle wrap.

GLSL Tutorials

Here is a short tutorial on GLSL. It should have everything you need to know about this part of the assignment. If you want to try some really fancy shaders for extra credits or learn more about GLSL, please refer to this link.

  • Extra Credit: Create your own shading using shaders #3-9. Some interesting shading effects include bump mapping, 3D texture mapping, Perlin Noise to make marble...

Reference Images

Phong Shading

Environment Map Reflection Shading

Here is a list of functions you will need to modify inside shader/frag:

  1. shadePhong
  2. shadeEnvmapReflection

If you want write any additional shaders to try for extra credit, you will append those functions to the same file.

Some examples are here:

Bump Mapping

3D Texture Mapping

Part 7: Design your own mesh!

For this part, we'd like you to design your own COLLADA .dae file format mesh using the free program Blender. Our suggestion for a baseline starting point is to design a humanoid mesh with a head, two arms, and two legs. We've created a Blender video tutorial and a modeling tips article to guide you through the basics of making a simple humanoid mesh.

Once you make your mesh, you should load it into meshedit and use what you've implemented! Subdivide it to smooth and use your custom shaders from part 6.

Here are some examples of Weilun's mesh-man before and after subdivision and also with the environment map applied:

  • Open Ended Extra Credit: Make a super cool or super detailed mesh! Write fancy shaders and apply them to your mesh. Implement additional geometric operations and demonstrate them on your mesh. The sky is the limit! Describe anything you do beyond the ordinary in detail in your writeup.

Art competition ideas

You'll submit your favorite screenshot of your mesh as competition.png in your root project directory. Here are some suggestions...

  • Add additional detail to your mesh - fingers, facial features.
  • Google "box modeling" (images and videos) to get inspired.
  • Investigate additional functionality in Blender to design an alternative shape.
  • Programmatically generate a mesh that approximates a 3D fractal or other complex shape.
  • Write a super cool custom shader that makes your mesh look awesome.

Website writeup

The goals of your write-up are for you to (a) think about and articulate what you've built and learned in your own words, (b) have a write-up of the project to take away from the class. Your write-up should include:

  • An overview of the project, your approach to the various parts, what problems you encountered and how you solved them. Strive for clarity and succinctness.
  • On each part, make sure to include the results described in the Deliverables section for each Part. If you failed to generate any results correctly, provide a brief explanation of why.
  • The last Part is where you have the opportunity to be creative and individual, so be sure to provide a good description of what you were going for and how you implemented it.
  • Clearly indicate any extra credit items you completed, and provide a good write-up and illustration.

The writeup is our main method of evaluating your work, so it is important to spend the time to do it correctly. Plan ahead to allocate time for the writeup well before the deadline.

Friendly advice from your GSIs

  • Start early. Once again, this is a multi-part assignment, and you should manage your time appropriately. Remember that pernicious bugs can sap your time like no other, and always keep in mind Hofstadter's Law.
  • Parts 1 and 2 should be straightforward to code once you understand the concepts.
  • Parts 3 and 4 will be trickier to write correctly, since they involve pointers (exposed to you as iterators). Make sure you test these parts together on a few meshes -- alternately flip and split edges at least ten times in nearby and far apart regions of the mesh as a first test. Obviously, correct behavior does not imply correct code, but incorrect behavior does imply incorrect code :)
  • In Part 6 you'll have to use the GLSL shader language. The syntax is very similar to C, but you might be tripped up by the small differences. It is a language designed for writing shaders, so there should be a way to do most mathematical operations you'll want to do fairly elegantly.
  • Part 7 involves learning how to use a 3D modeling tool. Weilun's step-by-step directions will help, but it will be another new experience. We recommend getting started early in case you have questions. A good first milestone would be creating a simple box mesh in Blender and loading it into the meshedit application as a .dae file. This doesn't depend on any other part of the assignment, so you can do it anytime (perhaps as a nice from chasing pointers...).
  • Allocate time for your writeup before the deadline. Again, it's our main method of evaluating your work, so submitting something you patched together at the last minute is not in your best interest.

Submission Instructions

As with the first assignment, log in to an instructional machine, navigate to the root directory of your project, and run

zip -r .
submit hw2

This indicates you have succeeded:

Looking for files to turn in....
The files you have submitted are:
Is this correct? [yes/no] yes
Copying submission of assignment hw2....
Submission complete.

There are more detailed instructions (including how you can use scp to copy your files onto the s349 machines) here.


Keyboard Controls

Command Key
Flip the selected edge F
Split the selected edge S
Upsample the current mesh U
Toggle information overlay I
Select the next halfedge N
Select the twin halfedge T
Switch to GLSL shaders W
Switch between GLSL shaders 0-9
Toggle using area-averaged normals Q
Recompile shaders R
Reset camera to default position SPACE
Edit a vertex position (click and drag on vertex)
Rotate camera (click and drag on background, or right click)