Overview

The goal of this project was to create a program that could correctly display geometric meshes. Using concepts learned in class like Bezier curves and surfaces, I was able to visualize curves from given control points. For the geometric mesh, I implemented mesh subdivision which divides the mesh into smaller triangles, averaging the original mesh positions to accurately reflect an upsampled mesh. I also implemented area averaged normals for half-meshes that allows for GLSL shaders to be used in "smooth mode". Finally, I wrote a couple shaders to change the appearance of the input geometric mesh.

I've been using 3D modeling software (Autodesk Maya) for a while now and did not understand how subdivision works. I think I've gotten much better understanding of it at this point, leading me to marvel at how quickly the 3D modeling software is able to do it on complicated meshes. I'm also quite happy to know how to write my own shaders as I can texture objects as I please instead of relying on commercial services.

Section I: Bezier Curves and Surfaces

Part 1: Bezier curves with 1D de Casteljau subdivision

de Casteljau's algorithm is used to calculate a Bézier curve. The algorithm recursively linear interpolates, each time decrementing the number of control points by 1. Given n+1 control points, this method calculates one step at a time until 1 control point is returned. The last control point is equivalent to the t parameter. All intermediate control points influence the curve but the curve does not necessarily touch those points.

I implemented 1D de Casteljau subdivision by first implementing a method that linearly interpolation between 2 points (x,y) and a parameter t. In my method, I checked the number of control points I have access to. If I have access to only one, my job is done as the control point corresponding to paramater t has already been found. If not, then I linearly interpolate each pair of consecutive control points with t (so lerp(p0, p1), lerp(p1, p2), etc.. This newly calculated set of control points is added to the overall list of evaluated control points so that the method can access them if called again.

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

One way to represent a Bezier surface is as a 4x4 grid of points (x,y,z). Divying up the array of points to 4x1, we can treat each of the 4x1 arrays as a 1D Bezier curve. After calculating the parameter u for these 4 1D Bezier curves individually (getting 4 individual control points total), we can compose a final Bezier curve (whose control points were calculated by lerping in the u direction) parameterized with the input v.

To implement this step, I created a method that lerps two given points with an input parameter t (between 0, 1). Looping through the 4 vectors of the given 4x4 grid, I calculate the final control point for each 1D Bezier curve using the input u as the parameter. These 4 control points (of the 1D Bezier curves) now make up the control points of a 2D Bezier curve parameterized by the given v. I evaluate the Bezier curve parameterized on v and return the final control point.

Section II: Sampling

Part 3: Average normals for half-edge meshes

First, I initialized an empty vector to store the sum of all my normals. I also instantiated a HalfedgeCIter object to keep track of my initial halfedge (to prevent the program from looping infinitely). Each halfedge object has a pointer to a face. In this project, each face is triangular and thus has 3 vertices. In order to access the position of these 3 vertices, I followed my current halfedge's next() pointers to get the face's other 2 vertices. In order to utilize the given cross-product method (which takes in two vectors), I subtracted the face's consecutive vertices from each other (Vertex2 - Vertex1, Vertex1 - Vertex0). Then, I calculate the cross product of the edge vectors and added it to my ongoing sum. Finally, I move on to the next halfedge by setting my current halfedge to its twin and following the twin's next() pointer. I continue calculating the area-weighted average for every triangle in the mesh until I return to my original halfedge. The normalized sum is then returned.

My Mistakes:

Part 4: Half-edge flip

I drew out some lovely diagrams and charts in order to orient myself and figure out what pointer reassignment was needed. For my method, I first check if the current edge's halfedge was attached to a boundary face. If it is, I return the input edge. Otherwise, I check the twin's face and return if it is a boundary face. After ensuring that both current halfedge and twin halfedge are not attached to boundary faces, I proceeded to create references to all the pointers for the left and right face (all halfedges, vertices, edges, and faces).

After storing the references to every halfedge, vertex, edge, and face, I reassigned the pointers to every reference (even if no change was made during the flip). While working in lab, I received a tip about using clear naming conventions for my references. I can see how that could save alot of headache when chasing pointers. Please see image below for detailed breakdown of how items were associated with each other, diagrams, etc. I went through my diagram and for each halfedge, found the correct halfedge pointer reference in the right diagram (with the horizontal edge).

Luckily, I didn't have to do too much debugging. My biggest bug was not updating the face references causing holes in my mesh after flipping an edge. This was quickly fixed after perusing Piazza.

Part 5: Half-edge split

I once again drew out the diagram for the splits and determined that I needed to add a couple new mesh elements: 2 faces, 3 edges, 1 vertex, 6 halfedges. After checking that the passed in edge does not lie on a boundary (like the FLIP method above), I added the new elements to the mesh. I then rereference all of the pointers for every data structure to ensure uniformity. Please see diagram below for reassignments.

Debugging: I did not realize there was a setNeighbors method so I had 100+ lines of code dedicated to setting each pointer for the 12 halfedges individually. After finding it, I rewrote the method and it was much cleaner. The second issue was that I did not realize that the elements needed to be added to the mesh (for some reason, I believed that it would be automatic). Whenever I ran the command, the program would segfault, leading me to believe that I had a typo. After perusing Piazza, I found a similar question and corrected my ways.

Part 6: Loop subdivision for mesh upsampling

To implement this method, I edited both the UPSAMPLE method and the SPLIT method.

To begin, I iterate through all the vertices of the mesh and calculate the updated vertex positions of the existing vertices. This was calculated by first finding the sum of all the neighbor positions, the degree of the vertex, and calculating our ratio u (either 3/(8 * degree) or 3/16 if the vertex degree is 3. The updated position of the existing edge is then:

(1 - n * degree) * originalPosition + u * neighborPositionSum

To make sure I can distinguish between old and new vertices (not yet created), I set these vertices' isNew property to false as they are part of the original mesh.

Next, I iterate through all the edges of the mesh and compute the positions of new vertices. The new vertices would be created by splitting the existing edges of the mesh (no splitting occurs during this step). I store this within the current edge's newPosition variable. The new position is calculated by weighting the two vertices of the edge we plan to split and the two vertices that will later be connected via the formula:

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

Then, I iterate through all the edges of the mesh and split all original mesh edges. In order to determine if it's logically and physically part of the original mesh, I check that the edge is not new and that the two vertices of the edge are also not newly created from the subdivision. If all the conditions are met, I split the current edge and set the returned vertex's newPosition to the current edge's newPosition (as I had calculated the position in the last step).

Next, I iterate through all the edges of the mesh and only flip the newly created edges if exactly one of the edge's vertices is new and exactly one of the edge's vertices is old.

Finally, I iterate through all the vertices and reassign each vertex's positions to the stored newPositions as we no longer need to reference the old positions

After a loop subdivision, the sharp corners and edges are averaged and look rounder. As I subdivide more, some points become more defined while other points recede back into the mesh. For example, after a few subdivisions, the cube becomes asymmetrical and non-cube-like. To improve this, I can split all the diagonal edges and all the border edges so that the entire cube is initially symmetric in every direction.

To get the cube to subdivide symmetrically, I split each diagonal edge. Originially, subdivision creates faces with different areas as the diagonals are non-uniform. By splitting the diagonal, we can ensure that each face is the same in terms of area and direction and thus all subdivisions will lead to smaller symmetric faces.

Mistake

I ran into a mistake where I did not use floats when calculating my ratios for u and got some bumpy models:

Section III: Shaders

Part 7: Fun with shaders

Section IV: Mesh Competition

I had some experience with 3D modeling in the past and so I made this mesh (instead of mesh man). Some of the edges in the cottage were not manifold which caused some issues when subdividing. The non-manifold edges came from combining my geometric mesh and applying a mesh cleanup tool. This leads to polygons that are non-triangular which the program does not deal with particularly well.

Part 8: Design your own mesh!