Building a Mesh Editor
Glenn Wysen - Spring 2020
Overview
This project revolved around how to model and represent 3D objects on a screen. The underlying concept is that all shapes can be composed of a collection of triangles in a mesh. Modeling shapes like this allows for several benefits including the ability to split edges, flip edges, and use loop subdivision to create smoother meshes with more triangles. This project also implements a basic de Casteljau's algorithm to draw curves in 2D space and surfaces in 3D space.
Bezier Curves With 1D de Casteljau Subdivision
De Casteljau's algorithm is a way of creating a Bezier curve through the linear interpolation of a set number of "anchor points". To start, all the points are connected, forming a series of lines. The basic idea of de Casteljau's algorithm is to take these lines and iterate through them with each pass reducing the number of points (and subsequently lines) by one every time. Eventually, after many interpolations, we will end up with a single point. This point lies on our final Bezier curve. The way that an iteration removes a point/line is to interpolate between the first and second point with a weight t (which ranges from 0 to 1) to get a new starting point. Next, we interpolate between the second and third points to get our second new point. This process continues until the n-1th and nth point get interpolated to get the n-1th point of our new series. Now we repeat the same algorithm over and over using the previously created points as our new reference until n reaches 1, leaving us with one point. If we go through with every value 0-1 for t all of the final points will trace out the Bezier curve.
Average Normals for Half-Edge Meshes
I implemented the area-weighted vertex normals for each vertex by doing the following. First, I found any one half-edge pointing away from the vertex. Then using that half-edge to navigate around the local mesh, I found the area of the triangle it lay in and the normal vector of said triangle. After weighting each normal vector by the area of its triangle, I stored them in a vector and iterated around each triangle surrounding the vertex until I reached the first half-edge. I then added all of the weighted normal vectors to get a large vector pointing in the right direction. The last step was to normalize that large vector to be unit length. This process was repeated for every vertex in the mesh to obtain a smoothed out image (Fig.5).
Half-edge Flipping and Splitting
I implemented the an edge flip by carefully assigning every element (vertex, edge, half-edge, and face) that interacted with the edge I was flipping to a variable. I then went through where each element would end up after the flip and re-assigned them to the right ending elements. This involved re-assigning 21 total elements (ten half-edges, five edges, four vertices, and two faces).
I implemented edge splitting in a similar way to that of edge flipping. I drew out how all the elements in a two triangle mesh section would change and carefully kept track of which half-edges pointed where. The difference in this method was that it involved creating new elements, rather than only rearranging old ones. An issue I ran into while debugging was that I was calculating the center point of the split by averaging all four x, y, and z values from the four points surrounding the edge instead of simply interpolating between the two ends of the edge. This caused some slight confusion but was easy enough to fix with some quick edits.
Loop Subdivision for Mesh Upsampling
I implemented loop subdivision using the following steps: First I marked every vertex and edge in the mesh
as an "original element" by setting their isNew value to false. I then iterated through each
vertex and found their new position according to the loop subdivision weights. I then did the same for the
new vertices which would be halfway through each edge and set those positions in the newPosition
variable in each edge iterator. Then I began the splitting and flipping process where every original edge was split,
then certain edges were flipped to create an isotropic triangular mesh. Lastly, I updated each vertices new
position according to what I calculated before. I ran into an infinite looping issue that was caused by not
making sure I only split the original edges in the mesh. This was quickly remedied by checking breakpoints
and fixing my iterator to advance past the edge I was splitting before splitting said edge. After running
a few loop subdivisions, it appears that sharp edges get smoothed out into rounded points as can be seen in
the cube that gets subdivided throughout Fig.10-Fig.13. Additionally, this cube looks to be
slightly skewed, which is due to the shape of the edges in the original cube being only along certain diagonals.
The skew in the cubes above can be fixed by splitting each edge on each face of the cube before running the mesh subdivisions (Fig.14-Fig.17). The reason why this works is because now the subdivision starts with a symmetric base instead of diagonals across each face of the cube.
Lastly, I wanted to show some examples of how loop subdivision can smooth out a more complex triangle mesh. Notice how by the second round of subdivision the model is already mostly smooth and eventually the benefits of additional smoothness are outweighed by the computational complexity of that much subdivision.
