In this project, I first learned to tesselate bezier patches to generate triangular meshes from bezier curves. Then, I implemented the ability to modify those meshes by flipping and splitting edges, or "upsampling" to increase the amount of triangle faces that represent the mesh. Finally, I wrote some cool GLSL shaders. My favorite was the reflection shader, which maps each pixel on the surface to a place on a reflection texture.

Part 1: Fun with Bezier Patches

The first thing I needed to do was generate a triangle mesh from an input Bezier Surface. A Bezier surface is specified by control points (16, in this case). The control points specify curves, and the convex hull of the control points contains a surface. That surface is the mesh I am trying to represent.

In order to represent the surface as a triangular mesh, I need to tesselate the Bezier surface specified by the control points into triangles. I accomplished this using the Bernstein Polynomials.I wrote some helper functions to help me evaluate the Bernstein Polynomials, used them to evaluate each control point. Once I determined which triangles I needed, I added them to a halfedge data structure to represent the mesh.

My Rendering of the teapot.bez Mesh

Part 2: Average normals for half-edge meshes

Next, I computed per vertex normals that were an average of the normals of their faces. This results in a nicer, smoother shading effect than when normal vectors are just computer per face. To accomplish this, I traversed the faces that the vertex belonged to in the half edge data structure, computing the normal for each face along the way. First I got the half edge that the vertex was attached to. Then, I saved it as h_original so I could keep track of where I started. Then I got the halfedge's twin and next half edge, and computed the vectors those half edges represented. I computed the normal of that face by crossing those two vectors before advancing to the next face. Once I reached h_original again, indicating I had tranversed all of the faces of that vertex, I returned the unit vector of the sum of all of the normal vectors as the normal vector for that particular vertex.

Each vertex is shaded uniformly according to the normal vector of one face.
This shows the teapot shaded according to per vertex normal vectors.
Initially I was calculating the vectors for the first face incorectly, which gave this cool swirly effect.

Part 3: Edge Flip

Next, I implemented the abillity to flip edges in the mesh. As I mentioned before, the mesh is represented as a half edge data structure. A half edge data structure is mostly a few key components: vertices, halfedges, edges, and faces. Vertices, edges, and faces each keep track of a single half edge. Halfedges each keep track of a twin halfedge (the one on the other side of the edge), a next halfedge (the next one on the face), an edge (made up of the half edge and its' twin), and a face.

In order to accomplish the edge flip, I just needed to reassign the pointers of all of the elements involving the edge before and after the flip.

Bug: Every edge I tried to flip poked a hole in my mesh!

Initially I was only reassigning pointers for the elements on the inside of the two faces between the edge I was trying to flip. Can you imagine why this would poke holes in my mesh? I was neglecting to reassign pointers for the halfedges on the outside of the borders of the faces. So while the edge may have been flipped correctly, the halfedges in the rest of the mesh weren't informed of the changes, and lost track of (could no longer traverse) that part of the mesh!

Once I assigned the pointers to the outside half edges too, I got the desired result.

A Torus mesh before any edges are flipped.
Torus mesh after flipping some edges.

Part 4: Edge Split

Next, I implemented the ability to split edges of the mesh. This was somewhat similar to flipping edges in that it involved a lot of reassigning of pointers. However, splitting became a little more complicated because it involved adding some new edges, faces, and a new vertex to the mesh.

Bug: Whenever I attempted an edge split, I punched a huge dent in my teapot! This shows a bunch of split-attempts near eachother, resulting in one giant heart dent.

This initial error was caused by an error calculating the position of my new vertex. In fact, I wasn't calculating the position of the vertex at all. So everytime I split an edge, I was adding a new vertex at the origin. That's why when I split, all of these dents were getting punched toward the same spot!

Once I updated the position of the new vertex to be the midpoint between the other corner vertices, I achieved the desired result.

Bean mesh before edges are split.
Bean mesh with some split edges in the middle.

Part 5: Upsampling via Loop Subdivision

Upsampling was the most challenging part of the project for me. There were quite a few issues to be debugged, but at a high level the approach is pretty straight forward.

  • First I marked all of the existing vertices as "old", indicating they were part of the mesh before it was upsampled.
  • Next I calculated new positions for all of the old vertices according to the vertex subdivision rule.
  • n = vertex degree

    u = 3/(8*n)

    (1 - 3/8) * original_position + u * neighbor_position_sum

  • Then I calculated positions for all of the new (to be added) vertices according to:
  • 3/8 * (A + B) + 1/8 * (C + D)

    where A and B are the vertex positions on the edge that the new vertex will lie, and C and D are the vertex positons on the adjacent edges of the faces on either side of the edge that the new vertex will lie.

  • Next, I split every "old" or prexisting edge in the mesh.
  • Finally, I flipped any edge that connected a new vertex and an existing vertex, and then updated all of the vertex positions.
  • Teapot mesh before upsample
    Teapot mesh after upsample

    Some times a little pre processing before upsampling a mesh can help significantly. A good example of this is the simple cube mesh. The way the edges are oriented can cause some irregularity when then mesh is upsampled. The upsampling behavior can be improved significantly if the edges that cross the faces of the cube are split prior to upsampling. This gives a more symmetrical mesh, which helps the upsampling give a symmetrical result.

    Here you can see a side by side comparison of the upsampling of two cubes. The left cube is the original mesh being upsampled. The right cube had each of the face crossing edges split before it is upsampled.

    Regular cube mesh before upsample
    Cube mesh with each face of cube split before upsample
    Regular cube after upsample (1X). Note the irregularity
    Pre-split cube mesh after upsample (1X).
    Regular cube after multiple upsamples. The irregularity has propagated.
    Pre-split cube mesh after multiple upsamples. Looks like a nice smooth cube!

    Part 6: Fun with Shaders

    Part 6 was my favorite! I wrote GLSL shaders which specify how OpenGL should light the scene. I implemented a simple Blinn Phong shader, and a really cool reflection environment map shader.

    Cow With Pink Phong Shader

    For the Phong shader, I followed the following procedue:

  • Calculate the light vector, l
  • Calculate the vector to my "eye position", v
  • Normalize the sum of the vectors l and v
  • Return a linear combination of the ambient, diffuse, and specular lights:

    LightVec = ambient_light + diffuse_light*max(dot(normal_vector, l), 0) + specular_light*(max(dot(n,normalize(l+v)), 0)^shininess_factor

    </p>
    Cow With Default Shader
    Cow With Grey Phong Shader

    Beetle With Default Shader
    Beetle With Phong Shader

    I liked the environment map reflection shader the best. This is what I did to accomplish this effect:

  • Calculate the vector to my "eye position", v
  • Calculate the reflection vector using v and the normal vector of the vertex
  • Convert the reflection vector into polar coordinates
  • Convert the polar coordinates into uv coordinates
  • Retrieve the colors for the vertex from the environment map using the uv coordinates. </p>
    Cow With Reflection Map Shader
    Beetle With Reflection Map Shader
    </div> </body> </html>