Overview

Conceptually, this project had three parts. The first part was about rendering smooth curves and surfaces using de Casteljau's algorithm. The second part was about editing a triangle mesh structure, with the main goal of being able to "smooth out" a structure by increasing the number of triangles. The third part was about shading an object, with the angles between the object, viewer, and light source being the key factors. The second part in particular was very fascinating, as it required learning how to use the halfedge data structure. Working with halfedge objects requires careful thought on which pointers need to be updated when changing the mesh stucture. The third part was also interesting, in that it allowed us to describe how the camera "sees" the object based on a sum of different parts, each dependent on a combination of of the orientations of the light source, object, and camera.

Section I: Bezier Curves and Surfaces

Part 1: Bezier curves with 1D de Casteljau subdivision

De Casteljau's algorithm is essentially recursive linear interpolation. For a given value t between 0 and 1, and a list of n points, the next list of n-1 points is the result of interpolating adjacent points from the previous list, with weights 1-t and t. We stop when we have a list with only one point. This point lies on the Bezier curve, and we can render the entire curve by letting t travel from 0 to 1 in very small increments.

Part 2: Bezier surfaces with separable 1D de Casteljau subdivision

We can extend deCasteljau's algorithm to work on 2d surfaces by performing the algorithm in two "orthogonal" variables. We start with a cage of sixteen points, arranged in a 4x4 array. For each list of 4 points in that array, and a value "u" between 0 and 1, we perform deCasteljau's algorithm in to get a new point. We then use these four new points as our control points, and another value "v" between 0 and 1, in another pass of de Casteljau's algorithm, to arrive at a single point on the Bezier surface. Letting u and v each vary from 0 to 1 gives us the entire 2d surface.

Section II: Sampling

Part 3: Average normals for half-edge meshes

We can assign a normal vector to the vertices of a triangle mesh by taking an area weighted sum of the faces surrounding it. These vectors can then be used to create a "smooth" rendering in the following manner: Normally (no pun intended) the shading (brightness) of a point on a triangle is based solely on the normal vector of that triangle (and its angle with respect to the viewer). We can use barycentric coordinates to instead define the shading at a point as the weighted sum of the normal vectors of the vertices of that triangle. This is very similar to the way we produced a continuous color gradient across a triangle in Project 1.

Part 4: Half-edge flip

To flip a given edge, I began by "naming" the different halfedge mesh elements around that edge that I knew would have to be modified, ignoring any that I knew wouldn't be effect by the operation. I drew a sketch of the "before and after" of the operation, with each element labeled. I then worked through the list of elements and their pointers, and if I could see from the sketch that a pointer needed to be updated (even only in special cases), I did so. I only had a few bugs, mostly from typos, but also from forgetting to update a couple pointers.

Part 5: Half-edge split

Splitting an edge was a bit more complicated. I wanted to implement the operation without deleting any mesh elements, as I knew this could potentially cause problems later on. Again, I drew a sketch of the "before and after," with each element labeled, including any new elements in the "after." For the six new halfedges, I knew that I would have to assign all five of their pointers, so I utilized the setNeighbors method to do so. However, I must have been especially sleep deprived while working on this part, as I got the order of operands confused, so that the new halfedge's "twins" and "nexts" were reversed. I couldn't get gdb to work, so I instead inserted calls to check_for(x) for each element x in my list (about 20 of them). What check_for(x) does is print a list of every object that points to x, and what type of pointer it is. However, it only shows the hexcode addresses of the objects, not the names I had assigned them. Thus I still couldn't tell what was going on until I noticed that 0x177d50 was the twin of 0x177efc, but 0x177efc was the twin of 0x177b14. Afterwards, I also implemented support for boundary edges.

Part 6: Loop subdivision for mesh upsampling

To implement Loop subdivision, I basically followed the "recipe" described in the project spec. I started by iterating through all the vertices, calculating their new postions, storing these seperately from their original positions. I also marked each vertex as "old." I then iterated through all the edges, marking each as "old" and calculating the positions of as-yet nonexistant "new" vertices, storing these for later. Next, I iterated through the edges again, splitting each. Here is where my implementation of splitEdge made life easier, as an edge that got split contained the position for the newly created vertex. However, simply checking if an edge was "old" didn't work, as I needed to mark the "new" second half of the split edge as "old" for the next step in the algorithm, which meant these new "old" edges would get split, and the process would continue ad infinitum. I found the solution on piazza: check if the edge is connected to two "old" vertices, then split it. I then marked the two "new new" edges as new. I then iterated through the edges one last time, flipping any edges marked "new" that were connected to one "old" and one "new" vertex, which required finding a hack for a boolean xor operator on stackOverflow (it was !A != !B). Finally, I iterated through the vertices, new and old, updating their positions to the ones newly calculated.

Loop subdivision "smooths out" sharp corners and edges. If we presplit some edges, the effected is much lessened.

If the original mesh is asymmetric, even if the geometric object is symmetric, the result of Loop subdivision will be asymmetric.

If we presplit some edges to make the underlying mesh symmetric, Loop subdivision preserves this symmetry.

I also implemented support for Loop subdivision on surfaces with boundaries. The basic idea is that vertices along boundaries get updated as if they formed a single curve, independent from the vertices in the rest of the mesh. The new position of an old vertex was 3/4 of its previous position, plus 1/8 of each of its neighbors. The new position of a new vertex formed from splitting a boundary edge was simply 1/2 of each of its neighbors.

Section III: Shaders

Part 7: Fun with shaders

Full Portfolio