Mesh Editor

For this project, I implemented a simple mesh viewer & editor in C++ that can open .dae files and perform simple mesh operations. It was really interesting to get an inside look into how 3D applications work, and this whole project gave me even more appreciation for the engineers behind the tools I use daily.

2D Bezier Curves with 1D subdivision

First, I needed a way to represent curved surfaces. Before I could do this for 3D surfaces, I had to start with a 2D plane. And to do that, I needed a function that takes a set of points and draws a curve between them. 

For this function I used the 1D De Casteljau 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 midpoints of adjacent segments.

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. 

3D Bezier Curves with Separable 1D Subdivision

Now it's time to move on 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.

I now had the ability to read NURBS meshes, since they're represented using curves rather than a series of triangles. Here is a NURBS teapot, visualized with my program:

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 half-edge 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. 

Flipping Mesh Edges

Next, I started implementing some simple mesh operations with my editor. First 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. 

Splitting Mesh Edges

Next I implemented a way to split mesh edges. This was 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 mesh edges:

Mesh Smoothing

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, which made some somewhat interesting results:

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.