A simple mesh-editing tool for DAE files with support for mesh upsampling.

Overview

For the first part of the project, I implemented Bezier curves and surfaces through the de Casteljau algorithm so these elements could be correctly drawn in the provided rasterizer. In the second part of the project, the provided starter code had the ability to load DAE files, load information about the meshes according to the half-edge data structure, and draw meshes as triangles in 3D space. For these parts, I added the ability to view a model with Phong shading, flip edges, split edges, and subdivide the polygon mesh with the loop subdivision algorithm.

This project was interesting to me as a 2D and 3D artist since I use many of these tools (Bezier curves and mesh-editing tools) regularly for a wide variety of tasks. Working with the code behind these tools was a fascinating look at how algorithms and math translate to tools that can be used for art.

Section I: Bezier Curves and Surfaces

Part 1: Bezier Curves with 1D de Casteljau Subdivision

de Casteljau’s algorithm represents a polynomial curve as a linear interpolation between control points over different points in time. With each step of the algorithm, for a given time t, the algorithm linearly interpolates between control points to produce intermediate control points, continuing to take steps until it reaches a single interpolated vector that represents the position on the curve for time t. This is implemented as a for loop through a vector of control points, which applies the lerp function to consecutive control points to output a vector of intermediate control points. This function is evaluated until the size of the output vector is 1 and the vector contains only the final point on the curve. The process is repeated for values of t between 0 and 1 to draw out the full curve.

I created a Bezier curve with 6 control points. The steps of the evaluation from the original control points to the final point can be seen below. The final curve is shown at the end.

I modified the curve slightly. Below is an animation showing the steps of evaluation for this curve from t=0 to t=1.

Part 2: Bezier Surfaces with Separable 1D de Casteljau

Whereas a Bezier curve is defined as a linear sequence of control points, a Bezier surface is defined as a grid of control points. When evaluating a Bezier surface, we view the n x m grid as n three-dimensional Bezier curves, each with m control points. Rather than interpolating solely across a linear variable t, we now interpolate across the u direction and the v direction. After evaluating the location for each of the n Bezier curves with lerp parameter u, we use the resulting n points as control points for a new Bezier curve. We then interpolate across this new Bezier curve to find the final point on the Bezier surface.

Section II: Triangle Meshes and Half-Edge Data Structure

Part 3: Area-Weighted Vertex Normals

I implemented area-weighted vertex normals for use in smoother Phong shading. In order to calculate the approximate unit normal for a vertex, I initialized an empty vector to hold the summed contribution from each face’s normal and area. Calculating the area of a triangle requires the three vertices of the triangle. To traverse the surrounding triangles, I based my code on the provided example, which demonstrated how to traverse neighboring vertices. Since the vertices for neighboring triangles would be located in a loop around the center vertex, I used a diagram of the half-edge structure to process the triangles one at a time.

Part 4: Edge Flip

I based my code for the edge flip operation from this resource linked on the course website. I named each half-edge, vertex, edge, and face according to the diagram, then updated the mappings for each half-edge, vertex, edge, and face based on the desired end-result for the flip.

Below is a comparison of a teapot before and after some edge flips

While working on the flip operation, I spent a short while trying to figure out why certain edges would disappear while flipping nearby edges. Ultimately, it turned out to be a typo when updating the neighbors for a certain half-edge.

Part 5: Edge Split

Similar to the previous part, I based my code for the edge split operation from this resource linked on the course website, though less guidance was provided for edge splitting. I first drew a new diagram demonstrating my desired before and after for the edge split operation.

I named each half-edge, vertex, edge, and face according to the diagram, then updated the mappings for each half-edge, vertex, edge, and face based on the desired end-result for the split.

Below is a comparison of a teapot before and after some edge splits, and before and after a combination of both edge splits and edge flips.

Part 6: Loop Subdivision for Mesh Upsampling

I implemented loop subdivision in three phases. First, I looped through every vertex to pre-compute where it would be moved to after the subdivision, marking each vertex as an old vertex and saving the pre-computed values for each vertex. Similarly, I looped through each edge to pre-compute where the new vertices corresponding to each edge would be placed. Next, I performed the splitting operation on each edge, flipping any edges that were marked as new edges connecting a new vertex to an old vertex. Any new vertices produced by splitting received their position values from their associated edges. Finally, I updated the positions of all vertices according to their pre-computed position values.

Sharp corners and edges are rounded out as we subdivide meshes. Pre-splitting edges near corners helps to preserve their shape.

Subdividing the cube repeatedly causes the cube to become asymmetric, as shown below. Since the loop subdivision algorithm divides every triangle into four new ones, the orientation of those original triangles will affect how the mesh subdivides. When the mesh is asymmetrical, the adjacent corners of the cube have different triangles oriented around them, so their calculated position after subdividing will be different. Proprocessing the mesh by splitting edges and making the topology symmetric ensures that dividing the triangles will maintain the same topology.