Overview

For project 2, I implemented geometric algorithms to edit curves, 3D meshes and surfaces. The number one takeaway from this project was how difficult it is to perform mesh operations. It gives me even more appreciation for the engineers behind all of the graphics applications I use daily. My mesh editor was extremely slow, running at maybe 20fps for a simple .dae mesh, so it boggles my mind that applications can run very quickly while rendering multiple complex meshes at once.

NOTE: this writeup contains multiple GIFs - please view in html at rachel.pt/mesh-editor

Part 1: Bezier Curves with 1D De Casteljau subdivision

For part 1, I implemented the 1D De Casteljau's algorithm to evaluate bezier curves between points. De Casteljau's algorithm calculates a curve given a set of control points by recursively drawing lines between points along the lines it's given.

My implementation is recursive - each iteration is given a series of points, and constructs lines between the adjacent points. It then calculates a point interpolated linearly between these lines at percent T, and feeds these points into the next iteration of the algorithm. It terminates when it there is only one point - this is the final evaluated point for value T.

Below, you can see me stepping through each part of the algorithm with 6 control points, until we get the final curve.

Below: moving around the control points changes the evaluation of the curve.

As you can see below, changing the value of t between 0 and 1 evaluates the curve at different points (the final evaluation is given by the red dot). The curve is fully evaluated when all steps between t=0 and t=1 have been evaluated.

Part 2 - Bezier Curves with Separable 1D de Casteljau Subdivision

De Casteljau's algorithm doesn't only work on 2D curves - it can be extended to 3D surfaces! All we need to do is apply this same algorithm in another dimension - calculating multiple evaluations of the algorithm along one dimension, and then linearly interpolating between those. The image below illustrates this well:

My implementation was a function that evaluated the bezier surface at point (u,v). It first created four evaluations of a helper function that, given 4 input points, evaluates the Bezier curve at parameter t using the 1D de Casteljau algorithm. It then performs a chain of linear interpolations at parameter u, and finally interpolates between these last evaluations at parameter v, generating the final point.

the algorithm was used to render this beautiful teapot below:

Part 3 - Average Normals for Half-Edge Meshes

In this part of the project, I implemented a way to visually "smooth" a polygon surface by altering the vertex normals of the mesh. Vertex normals are vectors pointing away from the surface of the mesh that allow the shader to evaluate how the mesh will show up on the screen.

The data structure we're using to store the mesh is a series of vertices connected by edges, which each have two "half-edges." Each half-edge has a twin() pointer, which indicates the other half-edge that shares its edge, and a next() pointer, which indicates the next halfedge in the triangle.

My algorithm does the following: For each vertex in the mesh, it iterates through all the vertices adjacent to the vertex, adding their area-weighted normals together and normalizing the result.

Part 4 - Half-Edge Flips

For part four, I implemented an algorithm to take any triangle edge and flip it:

If we think about any given non-border edge in a triangle mesh, it will be joining two triangles. If we draw out these two triangles, we can see that there are four vertices in the image, with our edge at the center.

I flipped the edge by first copying down the values associated with all the edges, vertices, faces and half-edges in the figure, and then re-assigning the pointers of each element so that the edge in question connects the two outer vertices in the figure. I had a bug early on that I missed, but revealed itself later in the project when I was attempting part 6. My mistake was not re-assigning pointers for the outer four half-edges of the figure - this was the final bug in my project and was wonderful to finally fix!

Below is a gif showing me flipping a few edges on a mesh. Pretty cool!

Part 5 - Half-Edge Split

This is a more complicated version of the above problem. To understand it, I had to use some diagrams (second one is my own):

For this part, I couldn't just re-assign pointers like before; I had to create mesh elements. Luckily, with the help of my diagram, it wasn't too hard. I had to use pre-existing helper functions to create the new vertex, edges, faces, and half-edges. I then reassigned all the pointers (for every element) like before, returning the new vertex. This required multiple re-draws of the diagram - I made the mistake of moving around the outer edges in my first iteration of the drawing, which created some fun segmentation faults. There were also another bug with my final drawing that I'll explain below... stay tuned!

Here is a gif of me splitting some edges in the same bean mesh:

Part 6 - Mesh Upsampling

The final and most daunting task: subdivision surfaces! This time we used the combined powers of parts 4 and 5 to implement a mesh subdivision smoothing algorithm. By splitting every edge, and then flipping every edge that connects an old and new vertex, we can essentially insert a new smaller triangle inside each old triangle. The following image (courtesy Denis Zorin) illustrates what is happening here:

My implementation did the following: I first iterated through every vertex in the mesh, setting a "new" flag to false, to mark the vertex as "old". I then stored the updated position of each old vertex using the smoothing rule:

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

Here, u is 3/16 if the vertex degree is 3, and 3/8*degree otherwise.

I then stored the updated position of the vertices that would be inserted along each edge using the following rule, where A, B are the vertices attached to our vertex and C, D are the opposite vertices:

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

Next, I split every old-marked edge in the mesh, and iterated over the edges to flip any edge that connects an old-marked and new-marked vertex. Finally, I copied the saved positions from earlier into the actual positions of the vertices.

I had multiple errors while implementing this part, all caused by issues with parts 4 and 5. Below, you can see the error produced when I tried to up-sample without re-assigning pointers correctly from part four. Additionally, I re-assigned pointers wrongly in part 5, and ended up having to switch the positions post-split of edge 0 and edge 5.

Also, at one point I had a bug that made everything take on a cloud-like, swirly appearance (I am still unaware what actually caused this, but it was beautiful) - the image below shows a cube up-sampled multiple times:

Below are some screenshots showing me stepping through different levels of subdivision. As you can see, mesh features get smoothed out with each step, and sharp details are lessened in intensity.

Below is a demo of me up-sampling a cube mesh multiple times. As you can see, on the left, the cube is asymmetrical after up-sampling. This is because the edges dividing each face are not symmetrical. In the second gif, you can see that splitting every edge keeps the mesh symmetrical after sub-division. Although the mesh looks the same geometrically, the better topology makes for a better subdivision.

Part 7 - My own mesh

Now comes the exciting part - actually putting my own mesh into the program! I spent about two days making the following dragon sculpt in ZBrush and Substance Painter: