Mesh Editor

Overview

Over the course of this project, I explored geometric modelling in the context of computer graphics, starting with an introduction to Bezier curves and surfaces and finishing with a mesh editor capable of loop subdivision. I learned that with a proper data structure, seemingly daunting implementation tasks such as that of triangle meshes can be translated into reality fairly efficiently, allowing us to produce increasingly complex graphical objects. Overall, the project was an very insightful foray into a fundamental concept of computer graphics, and one I enjoyed immensely.

Section I: Bezier Curves and Surfaces

Part 1: Bezier curves with 1D de Casteljau subdivision

Given n+1 control points, we can define a n degree Bezier curve using 1D de Casteljau subdivision. The key idea underlying de Casteljau subdivision is that of recursive linear interpolation. Let x be the relative location we want to evaluate the Bezier curve at. If we think of each recursive step as a level, given some level l with k points, level l + 1 can be computed by linearly interpolating of every sequential pair of points at x, giving us k-1 new points that can then be used to compute the level l+2. The recursion ends when we reach a level with only one point, which we subsequently return. By varying x between 0 and 1, we can construct the full Bezier curve.

Screenshots:

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

The 1D de Casteljau subdivision algorithm can be easily extended to 2 dimensions to create a surface. To evaluate the relative point (u,v) given an array of control points with dimensions n by m, the underlying idea is as follows:

• For each row in the control point array, perform the 1D de Casteljau subdivision algorithm as described in Part 1 with u as the relative location you want evaluated. Consequently, we'll get m points that we can use in the next step.
• Using the m points from previous step, perform the 1D de Casteljau subdivision algorithm with v as the evaluation point. The resulting value will be the Bezier surface evaluated at (u,v).

Section II: Sampling

Part 3: Average normals for half-edge meshes

For a given vertex, we can calculate the unit normal as follows:

• For each neighboring face, we find the cross product of two of the edges (making sure they conform to the winding order).
• We then add up all of the cross products found in the previous step and take the average to get our normal vector.
• Finally, we convert the normal vector to a unit vector to normalize it.

Details regarding traversal and edge calculation:

• Our starting edge will be the twin of the halfedge associated with the vertex.
• For a given face, we can find two of its edges as follows: First we collect the associated halfedge we know about and the halfedge that comes next. We now have the 3 vertices of the triangle (2 from the halfedges and the original vertex we're finding the norm of) that we can then subtract from one another to create the edges used to calculate the area of the face.
• Traversal to the next face can be done by just taking the twin of the next halfedge.

Part 4: Half-edge flip

Given two adjacent triangles, the half-edge flip takes their shared edge and flips it to connect the two previously unconnected vertices. Using the half-edge data structure, the half-edge flip became a matter of drawing an accurate picture and reassigning pointers accordingly. A resource I was quite inspired by was Correctly Implementing Edge Flip/Split/Collapse. An implementation tip that I found very useful was the assigning of all references, regardless if they changed or not. A major debugging debacle was that of an accidental getHalfedge() call that inexplicably crashed the editor when the function was called. After checking my reassignments numerous times, I finally switched my focus to the seemingly innocuous boundary check that contained the offender.

Part 5: Half-edge split

Given an edge between 2 triangles, the half-edge split introduces two new edges, one to split each face--each new edge starts from the midpoint of the given edge and ends in the opposite corner of its respective triangle. Using the half-edge data structure, the half-edge flip once again became a matter of drawing an accurate picture and reassigning pointers accordingly. In this case, however, we also had to introduce 3 new edges, 2 new faces, 6 new halfedges, and 1 new vertex whose pointers all also had to be properly assigned. A glimpse of my scratch work (emphasis on scratch): A truly great debugging quest was undertaken--having not realized I accidentally created an extra face, I spent an inconceivable number of hours figuring out what reassignment had gone wrong before I realized the rogue extra line of code.

Part 6: Loop subdivision for mesh upsampling

When given some low-resolution polygon mesh, there are times when we would benefit from upsampling, e.g., for displays and simulation. We can accomplish this through Loop subdivision, whose two steps are as follows:

• Split each triangle into 4 by connecting the edge midpoints together ("4-1 subdivision")
• Adjust vertex positions by taking the weighted average of neighbor positions

The weighted averages are calculated as follow:

• For an old vertex the new position is: (1 - n*u) * original_position + u * neighbor_position_sum where n is the number of neighbors and u is 3/16 if n=3 else 3/8n.
• For a new vertex created by splitting the edge with end vertices A and B and flanking vertices C and D, the new position can be calculated by 3/8 * (A + B) + 1/8 * (C + D).

"4-1 subdivision" can be achieved by splitting every old edge arbitrary and flipping any new edge that connects an old vertex to a new vertex, taking care to not accidentally flip any of the edges that comprise the original edge (since each original edge will now be represented by 2 edges).

A few implementation tricks I used were to compute new positions before doing any splitting, since the original connectivity is far easier to traverse than than the new upsampled connectivity. The traversal is not unlike what was done in Part 3, but instead of keeping track of faces, we kept track of vertices.

As the number of Loop subdivisions increases, the sharp corners and edges get rounded out. We can mitigate this effect slightly by pre-splitting edges as seen below. Notice the corners remaining after three Loop subdivisions.

In the case of the cube, notice a slight deformation as the number of Loop subdivisions increases. This effect result from the asymmetry of the mesh on the cube's faces--on some faces an edge goes from top left to bottom right, whereas on other faces an edge goes from from top right to bottom left. As subdivision occurs, these differences cause some corners of the cube become more subdivided than their surroundings, resulting in odd bumps on the ensuing surface.

We can increase symmetry of the mesh by once again pre-splitting the edges, specifically ones that cross faces. The result as we perform Loop subdivision is a far more symmetrical surface, as seen below.