Overview

In this project, we explore curve and mesh representations. It's interesting to see how we can define a Bezier curve using 4 points and how we can operate meshes by flipping, spliting, and loop subdivision to change their shapes. The mean idea that we utilize for generating Bazier curve is called de Casrekjau Algorithm, and it takes recursive linear interpoliations. The mean idea that we utilize for mesh operation is called halfedge, and we can use it to traverse all triangles, edges, and vertices in a mesh.

Section I: Bezier Curves and Surfaces

Part 1: Bezier curves with 1D de Casteljau subdivision

De Casteljau's algorithm finds points on curve by recursive linear interpolation. We connect neighboring points, and find new n-1 points on every line at a fixed relative position (with ratio t) as points for next loop, until there is only 1 point left. Changing the value t continuously, we can get a smooth curve.The equation for every point position with parameter t is as below:

Below is an example with 6 control points. We do recursion step by step. We can also move control points to change the curve shape or change parameter value t to change the final point on the curve.

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

To get 2D Bezier surfaces, we first use de Casteljau to evaluate Bezier curves at fixed v values. Then we find corresponding points on those curves as control points for another Bezier curve at a fixed u value.

Below is an example of generating Bezier surface of a teapot.

Section II: Sampling

In this section, we use notations as below. For a specific healfedge, we have attributes: vertex, twin(halfdege), edge, next(halfedge), face.

Part 3: Average normals for half-edge meshes

Phone shading provides smoother shading by shading every pixel compared to flat shading by shading every triangle, and it's implemented by interpolating area-weighted normals across each triangle. The normal at a vertex is calculated by normalized sum of all area-weighted normals of faces incident to the vertex. Starting from the root half edge of the vertex, we find the face of the half-edge and its three vertices to calculate its normal and area used as weight. Then we traverse all incident faces utilizing next and twin attribute of halfedges until we find the new half-edge is the root half-edge of the vertex. Finally we return normalized sum of all area-weighted normals.

Below is an example of smooth Phong Shading on the teapot.

Part 4: Half-edge flip

To flip an edge, we collect all the elements that related to the edge(e0), including halfedges, vertices, edges, and faces. During the implementation, we found out it would be easy if we draw out the graph and just follow the graph to update all attributes. See the following graph: we have h0 to h9, v0 to v3, e1 to e4, and f0 to f1. Then, we update pointers that are affected by the edge flip operation for all elements. Notice boundary edges can't be flipped.

Below is an example of performing random edge flips on the teapot.

Part 5: Half-edge split

To split an edge, we collect all the elements that are related to the edge and those two triangles containing the edge, including halfedges, vertices, edges, and faces. For splitting, we add 6 halfedges, 1 vertex, 3 edges, and 2 faces to the mesh. The new vertex is put in the middle of the splited edge on default (which should be changed for loop subdivision in part 6). Similar to edge flip, we update pointers for every element based on the following graph.

We also want to updated isNew attribute for edges, which is useful for part 6. The two edges we got from breaking the original edge are considered old (e0 ane e5), and the other two newly added edges (e6 and e7) are considered new. e1, e2, e3, e4 should have unchanged isNew value. During our first implementation, we wrongly set e1, e2, e3, e4 all to be false and e0, e5, e6, e7 all to be true, which cause infinite loop in part 6, because the algorithm will keep spliting new edges.

Extra Credit: Boundary Split

We draw the helper that split the boundary and write the function base on that. When we select a boundary edge e1, we make sure that halfedge h1 is on side that would be split to 2.

Part 6: Loop subdivision for mesh upsampling

To improve the mesh quality, we implement mesh upsampling by loop subdivision. To make sure every triangle is divided evenly into subtriangles, we follow the following 5 steps.

1. Compute new positions for old vertices. Traverse all existing vertices in any order, and mark them as old. For every vertex, the equation for the new position is: \((1-n*u)*V_{pos}+\sum(u*U_{pos})\), where Us are neighbor vertices of V, and \(u=\frac{3}{16}\) if \(n=3\), else \(u=\frac{3}{8n}\)
2. Compute new positions for new vertices. Traverse all existing edges in any order, and mark them as old. Because we will split every existing edge in step 3, there will be a new vertex on every existing edge. The position of the new vertex on an edge is: \(\frac{3}{8}*(A_{pos}+B_{pos})+\frac{1}{8}*(C_{pos}+D_{pos})\), where A and B are vertices on 2 ends of the edge, and C and D are another vertex of the two triangles containing the edge.

3. Split every old edge. Transverse all edges in any order, and perform edge split on every original old edge. Check if an edge is originally old by checking if the two vertices on two sides of the edge are both old. Mark vertices created during spliting process (blue ones on image) as new. Mark the two newly created edges (blue ones) as new, and mark the two edges (black ones) on original edge as old. Notice "original old edge" and "old edge" are different here! At the end of this step, there should be no more original old edge, and every original old edge has been splited into 2 old edges.

4. Flip any new edge that connects an old and new vertex. Traverse all new edges (blue ones) and flip it if it has a new vetex (blue ones) on one end and an old vertex (black ones) on the other end.

5. Update all vertices to new positions. Traverse all vertices, and update their positions calculated in step 1&2.

Below is an example of loop subdivision. Every time we perform one loop subdivision, the sharp edges and corners become smoother. This effect can be reduced by performing pre-splitting. If we split edges around a corner before loop subdivision, the corner will not be averaged by original nerighbor vertices as much as it would be before.

Below is another example of loop subdivision on a cube. We can notice that the subdivision result is not symmetric. That's because the edges on every cube face causes there to be different number of edges on every vertex, and different partterns cause the subdivision algorithm to produce different results. In order to fix the asymmetric problem, we can split the edges on every face, so there are diagonal edges on every square face. In this way, the pattern on every vertex corner will be same, and subdivision wil produce symmetric result.

Extra Credit: Dealing with Boundary

To deal with boundaries, we need add equations for boundary vertices and edges in step 1&2. The equation for bounary old vertice position is: \(\frac{1}{8}*(U1_{pos}+U2_{pos}+\frac{3}{4}*V_{pos})\), where U1 and U2 are neighbor vertices of V on the boundary. The equation for bounary new vertice position is: \(\frac{1}{2}*(A_{pos}+B_{pos})\), where where A and B are vertices on 2 ends of the edge.

Because we have succesfully implemented boundary split, we can just split boundary edges in the same way as we do for normal edges. For edge flip, it gets nothing to do with boundary edges. Finally, we can update position for all vertices.

Below is an example of boundary loop subdivision on beetle. We can see the boudaries are more smoother with more triangles after loop subdivision.

Section III: Optional Extra Credit

If you are not participating in the optional mesh competition, don't worry about this section!

Part 7: Design your own mesh!