Part 1: Bezier curves with 1D de Casteljau subdivision

de Casteljau's algorithm is a divide-and-conquer algorithm that allows us to compute Bezier curves by simply performing multiple linear interpolations between different control points. Our implementation of de Casteljau's algorithm involves evaluating different levels of the curve; the control points of one level is use to compute new control points for the next level, by linearly interpolating two consecutive points together to create one new control point. We continue subdividing into new levels until there are no more control points left.

A custom Bezier curve with six points. No levels are currently evaluated.

A custom Bezier curve with six points, evaluated at level 1.

A custom Bezier curve with six points, evaluated at level 2.

A custom Bezier curve with six points, evaluated at level 3.

A custom Bezier curve with six points, evaluated at level 4.

A custom Bezier curve with six points, evaluated at level 5. The final curve is drawn out with differing values of t.

The same final custom Bezier curve with a higher t value.

The shift of one point changes all the levels and the resulting curve.

A different Bezier curve by modifying multiple points.

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

We can use de Casteljau's algorithm to evaluate Bezier surfaces as well as Bezier curves. Bezier surfaces are defined with 3D control points; a surface is then created with two parameters (u and v), where as a 2D Bezier curve only has one parameter (t). Thus, we can split the surface into two separate de Casteljau calls - one to interpolate the u parameter to create multiple Bezier curves, and another to interpolate those resulting points through the v parameter to create a Bezier surface.

This teapot has Bezier surfaces that define its shape.

The same teapot, but with more emphasis on the curve. The geometry of the curves are not drawn.

Part 3: Average normals for half-edge meshes

To average the normals, we first start on our source vertex and choose a random half-edge (and thus random face). Then we note the vertex and the vertex that the half-edge points to. By computing the cross-product of these two vertices, we get a resulting normal vector, that is already bounded by the shape created by the two vectors. We add this cross product to a vector that will describe the totals of all of the normals. Then we set the half-edge to the next half-edge of the twin, in order to select a different face. We continue doing this until we reach our original half-edge again - then we have traversed through all of the triangles that are centered on our source vertex. Then we return the unit vector of our total normals to create a valid normal vector for that vertex. These kinds of recursive algorithms are commonplace for operations on meshes defined with half-edges.

The same teapot rendered with a GLSL shader and averaged normals.

Part 4: Half-edge flip

Creating the edge-flip involves creating two models that describe two triangles before and after the edge-flip. We then label these two diagrams with half-edges, edges, vertices, and faces. To carry out the actual edge flip, we simply reassign the previous components of the triangles to the respective components in the post-edge-flip diagram.

Not much occured during the implementation of the edge-flip. The initial implementation only led the program to crash due to invalid pointers; specifically, the half-edges outside the two triangles were assigning faces and next half-edges erroneously to itself.

The teapot with a pattern of edge flips on a part of the surface.

The regular teapot after being rendered with the GLSL shader.

The edge-flipped teapot after being rendered with the GLSL shader.

Part 5: Half-edge split

Similarly to the half-edge flip, we first create two diagrams of two triangles, one before the edge-split and one after the edge split. With so many new elements (one vertex for the midpoint, two faces, three edges, and six half-edges), the labelling of the half-edges in the after diagram is not very important; the only requirement being that the half-edges outside the two triangles remain the same, so that their faces and next half-edges don't change as well. Then we reassign all the half-edges to fit the post-edge-split diagram.

One pointer reassignment led to the edge split forgetting to mark an edge. Redoing the pointer assignments to ensure that edge stored in a half edge is equivalent to the half edge stored in an edge solved the issue.

A basic cube without any edge operations on it.

A basic cube with edge splits on both a side face and a top face.

A basic cube with edge splits and some flips on both a side face and a top face.

Part 6: Loop subdivision for mesh upsampling

Loop subdivision allows us to upsame models and thus make them appear more smoother. We first start loop subdivision by weighting vertices according to a special rule. For every vertex, we count all of its neighbors and add the sum of their positions. Then we weight the sum according to a certain number (either ³⁄_8n for n > 3 or ³⁄₁₆ for n = 3 for degree n), and add that to the original vertex, but with a weighted (1 - un) vertex position. Then the midpoints are calculated from both the vertices that make every edge but also the two vertices that flank the edge as well. These are weighted according to ³⁄₈ (A + B) + ¹⁄₈ (C + D) where A and B are vertices on the edge, and C and D are vertices flanking the edge. Then the vertices on the original mesh are split, where all the new vertices and the new split edge are marked as new. Finally, all new edges that touch an old and new vertex are flipped to correctly triangulate the surface.

Some minor implementation issues came into surface. Faces were incorrectly rendered until only two - not three - edges were marked as new and not old. Special care was also needed by assigning "new positions" to vertex, to ensure that all vertex operations calculated neighbor positions that weren't already updated. These new positions were then assigned to the vertex after all operations were finished.

A torus without any Loop subdivision performed.

The torus with one step of Loop subdivision applied. The sharp edges of the torus have been more smoothed out, giving the impression that it is more rounded. (The size of the Torus also slightly shrank, as the weights of the vertex and edge midpoints are reduced.)

The torus with four steps of Loop subdivision applied. The sharp edges of the original model are barely noticeable; the torus has converged into a round ring. (The torus also shrunk more from the previous subdivision.)

A cube with no Loop subdivision. No edge operations have been performed.

A cube with one step of Loop subdivision. The cube is winded such that some of the corner vertices only have degree 3, while others have degree 4 or 5. As such, the cube appears to be slightly more weighted in only some of the corners, and not the others. The resulting subdivision of this supposedly symmetric cube produces an assymetric result. (Also note how the Loop subdivision made the mesh appear smaller.)

The cube with four steps of Loop subdivision. The abnormal stretching on the top-left and bottom-right of the picture showcases the assymetric result of the subdivision.

We'll try splitting all the diagonal edges of the cube faces to make sure all of the corners have the same degree of 8.

The resulting four iterations of loop division creates a symmetric subdivided cube.

Side note: we can reduce the smoothing effect that occurs on corners and edges by continuing to split the edges. This creates neighboring vertices that can be very close to the original vertices, reducing the difference between the original vertex and the midpoint vertex. This front face is split multiple times; the side face is not split.

The resulting 4-level Loop subdivision creates a smooth surface on the side, but with a relatively sharper surface on the front that mostly maintains the original's shape (and size).

Final Overview

Working with various algorithms involving interpolation - whether for Bezier curves, Bezier surfaces, or Loop subdivision, involves simplifying down complex structures into simpler instructions. Whether the instructions involve linear interpolation or various edge splits and edge flips, we can represent curves and heavily-detailed models — both essential in any form of computer graphics.

CS184 MeshEdit