Overview

In this project I implemented Bezier Curves and Bezier Surfaces using de Casteljau's algorithm, splitting and flipping of edges in meshes, and upsampling of meshes through Loop Subdivision. I learned about how to use de Casteljau's algorithm in code, navigate meshes using the Half-edge data structure, and using splitting and flipping edge operations to upsample meshes. It was interesting to see how to go from a single curve to a surface and then to a teapot. I also discovered how easy it is for bugs in the flipping and splitting processes to cause upsampling to fail in strange ways that are hard to debug. Some bugs I could not figure out why they were occurring and I ended up having to rewrite my splitting and flipping operations to remove bugs and to get upsampling to work successfully.

Section I: Bezier Curves and Surfaces

Part 1: Bezier curves with 1D de Casteljau subdivision

De Casteljau's algorithm is a way to create a Bezier Curve from some number of control points. In the following screenshots, I start with six control points and draw five lines connecting the control points. Based on the value of t (1/2 in the screenshots), for each of the lines, I place a point at t * (line length) on each line. This results in five new control points and the process repeats until I end up with one final point which is on the Bezier Curve. To get the whole Bezier Curve, I just sweep t from 0 to 1 using the process explained previously. I implemented the algorithm in a function by calculating each level of control points using \((1-t)p_i + tp_{i+1}\) where i is from 0 to number of control points - 1 and pushing them into a vector of points that is returned from the function. The returned vector is passed back into the function and the process repeats until a vector with a single point is returned.

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

The de Casteljau algorithm extends to Bezier Surfaces by using a n * n grid of control points. For each row of this n * n grid, the 1D de Casteljau algorithm is used to obtain a single point for each row parameterized by u. Then for the n final points, the 1D de Casteljau algorithm is used to get the final point that is on the Bezier Surface parameterized by v. To get the entire surface, u and v are swept from 0 to 1. I implemented this process by writing the evaluateStep function that evaluates each step of the 1D de Casteljau for a vector of 3D points. Then I wrote another function (evaluate1D) that calls the evaluateStep function until it returns a vector with a single point in it. Finally, I implemented the evaluate function that calls evaluate1D with u on each row of the grid to get a vector of new control points which is then passed to evaluate1D with v to get the final point that lies on the Bezier Surface which is then returned.

Section II: Sampling

Part 3: Average normals for half-edge meshes

I implemented the Area-Weighted Normals by first implementing an area method in the Face class. To calculate the area of a face, I computed the area vector using the cross product of two vectors pointing from the A vertex of the triangle to the B and C vertices. I took the norm of the resulting area vector and divided it by two because the norm of the cross product computes the area of the parallelogram formed by the two vectors and dividing it by two gives the area of the triangle. Then, I implemented the normal method of the Vertex class by iterating over the neighboring faces around the vertex, calling the normal method to get the normal vector and multiplying the normal vector with the result of calling the area method on the face. The weighted vectors are then summed up and normalized to get the final normal vector.

Part 4: Half-edge flip

I implemented the edge flip operation by calling the setNeighbor method on each existing half-edge to reassign their next, twin, vertex, edge, and face members to the correct element based on the diagram in the spec. I also made sure to reassign the halfedge member of the existing faces, edges, and vertices to point to the correct half-edge to avoid bugs like disappearing triangles.

A bug I ran into was a triangle would disappear after three flips of the same edge. I first tried using the GUI information overlay to debug the problem but it was not that helpful because when the triangle disappeared, I could no longer select the half-edges of the missing triangle anymore. Next, I tried using the check_for method to print out some information about the edge that was being flipped and the half-edges being modified but I did not see any problems in the debug output. Then, I checked Piazza to see if other students encountered the same bug and sure enough some students had the same bug. One student managed to solve the bug by making sure to update the half-edge member of the four vertices that surround the two triangles. I tried that solution first since I was not updating some of the vertices but it did not solve the problem. Even though the solution did not fix the problem it eventually helped me solve the bug in the end because the bug was very similar to forgetting to update the surrounding vertices. I forgot to update the faces to point to a correct half-edge which caused the bug because one half-edge in each triangle would have to switch to the opposite face on an edge flip. After making sure to update the half-edge member of the faces, the problem was solved.

Part 5: Half-edge split

I implemented the edge split operation by creating three new edges, one new vertex, six new half-edges, and two new faces. Next, I connected everything up by assigning their members to point to the correct element. I also calculated the position of the new vertex by using the Midpoint Formula so that the new vertex would be located at the midpoint of the original edge that was being split.

Initially I did not have much problems with this part due to using experience (making sure to assign everything) from part 4 to avoid problems with disappearing triangles. But I still had to rewrite this part for part 6 due to edges disappearing during the splitting phase of upsampling. I tried debugging the disappearing edge problem but it did not really help so I decided to draw a new diagram of a different mesh and rewrote the code based on the new diagram which worked perfectly. I also defined variables to record all the original half-edges, faces, edges, and vertices to be used later on in reassignment process which I think helped me avoid bugs.

Part 6: Loop subdivision for mesh upsampling

I implemented Loop Subdivision by first iterating over all edges of the mesh to calculate the final position of each new vertex to be created by using the formula given in the spec (\(\frac{3}{8} * (A + B) + \frac{1}{8} * (C + D)\) where A, B, C, and D are the vertices surrounding the new vertex). I stored the final position inside the edge's newPosition member. Next, I iterated over all vertices of the mesh to calculate the final position of each old vertex using the equation from the spec (\((1 - n * u) * position + u * neighbors\_sum\) where n is the vertex degree, u is \(\frac{3}{16}\) if n == 3 else \(\frac{3}{8n}\), position is the vertex's position, and neighbors_sum is the sum of the positions of the neighboring vertices around the vertex). Then, I iterated again over all edges of the mesh and called splitEdge on each old edge and flipEdge on each new edge making sure to call flipEdge only if the edge connects an old and new vertex. Finally, I updated the position of each old and new vertex in the mesh to the new position that was calculated in the beginning of the upsampling process.

A debugging trick I used for this part was to comment out stages of the upsampling process to be sure my splitting and flipping methods were working currently. I discovered when I commented everything out but my splitting call, I could tell in the GUI when I split all edges of the cube that my splitting method was not working properly since there were missing edges. I ended up redoing part 5 and also part 4 to be on the safe side and my cube looked correct with only the splitting and flipping parts of the process enabled. Then, part 6 started working after I fixed another bug by adding .0 after all integers in the equations I used to force floating point division.

After upsampling some meshes, I noticed that some meshes seem to noticeably shrink on the first upsample. This effect is most noticeable for the cube but can also be seen for the torus. For sharp edges, they become noticeably rounder after upsampling. For the sharp corners of the cube, I can still see them after several upsamplings but they were not as sharp as before. I tried pre-splitting edges to keep the sharp edges but I could not achieve any good results. I think this is due to the implemented Loop Subdivision algorithm not treating sharp edges any differently. According to the Spring 2019 Lecture 8 slides on Mesh Representations and Geometry Processing, sharp edges can be marked so that the subdivision algorithm uses different equations that do not depend on neighboring vertices for the vertices along sharp edges, resulting in keeping the selected edges sharp.

I think the cube becomes asymmetric after a few subdivisions because the subdivision starts from a cube that only has one edge going across each surface. The unevenly split surfaces causes the cube to become asymmetric after subdivision with an extraordinary vertex appearing on each corner of the cube. To make the cube subdivide symmetrically, I simply split the one edge in the middle of each surface of the cube such that each surface looks like it has a X on it. Since each surface is now pre-divided evenly, the cube will subdivide symmetrically with an extraordinary vertex appearing in the center of each face.