Feb, 2024

CS 184/284A: Computer Graphics and Imaging, Spring 2024

Homework 2: Meshedit

Colin Steidtmann


This assignment focused on representing 3D objects and rendering them on computer displays. Digital 3D representations are widely used, from mountain terrains in video games to building and car prototypes in engineering, and even scientific simulations. 

Two common methods for representing 3D objects are Bézier surfaces and triangle meshes. Bézier curves are smooth curves defined by a set of control points using mathematical formulas. Software like Adobe Illustrator allows artists and font designers to work with them effectively. Bézier surfaces are the 3D counterpart of Bézier curves, existing in three-dimensional space. While they excel at defining the shape of 3D objects, directly rendering them is computationally expensive due to the complex calculations involved for each pixel. 

Triangle meshes offer an alternative approach. We can define 3D objects using a collection of triangles in 3D space, or even convert Bézier surfaces into triangle meshes. This method requires fewer calculations for rendering, making it more efficient. However, triangle meshes can demand more memory compared to Bézier surfaces. To achieve smoothness comparable to Bézier curves, triangle mesh surfaces require further processing. This involves efficiently splitting triangles into smaller ones and potentially rotating or flipping them as needed. 

This assignment challenged us to implement various operations required for rendering both Bézier surfaces and triangle meshes. Along the way, I encountered frustrating bugs that took days to resolve but it was all worth it because now I have this great write-up with images to share.

Vocab to be aware of 

Why Use Triangles? We only need 3 points to define one, all three points of a triangle always lie on the same plane, modern GPUs are specifically designed to process triangles efficiently, and any 3D shape, no matter how intricate, can be approximated by combining numerous triangles.

Mathematical Splines: These are abstract functions representing smooth curves

Catmull-Rom Interpolation: Generates smooth curves based on a series of points without requiring tangent information (aka derivatives)

Bézier Curves: Defined by control points, offering flexibility and widely used in computer graphics and design.

Meshes: Used to represent 3D shapes using collections of triangles.

Up-sampling: Increasing the number of triangles for finer detail.

Down-sampling: Reducing the number of triangles for efficient data transmission.

Regularization: Making triangles more uniform in size and shape.

Ambient: A constant, low-level of light that affects the entire object, regardless of its orientation. E.g. in a picture of a tea cup, the back of cup is lit despite the light source being on the other side.

Diffuse: The intensity of light reflected from the surface based on the angle between the light direction and the surface normal. Rougher surfaces diffuse light more evenly, while smoother surfaces create sharper highlights.

Specular: A concentrated highlight that appears where the reflected light hits the viewer directly. This is calculated based on the angle between the reflected light direction (the mirror image of the light direction reflected off the surface normal) and the view direction.

Phong shading: calculates lighting at each pixel based on surface normals and light sources, resulting in smooth shading and highlights. 

Flat shading: Applies a single color to the entire surface of a polygon. While faster to render, it produces a less realistic appearance.

Section I: Bezier Curves and Surfaces

Part 1: Bezier Curves with 1D de Casteljau Subdivision

This part had me construct 1D Bezier curves in 2D space by implementing de Casteljau's algorithm. This algorithm is recursive: given n control points, p1, p2, ... , pn and a parameter t, we can compute the next p1,p2,...p(n-1), control points via:

We do this recursively until we arrive at a single point, which indeed lies on the Bezier curve. By varying t, we can compute all points on the Bezier curve. Following is a helpful animation demonstrating how Bezier curves and the parameter t work together. It is followed by 5 iterations of the implementation of de Casteljau's algorithm, which reduces 6 coordinate points and the given parameter t to a single location on the Bezier curve.

Varying t evaluates different points on the Bezier curve
Step 0: 6 control points
Step 1: 5 control points
Step 2: 4 control points
Step 3: 3 control points
Step 4: 2 control points
Step 5: 1 point on the curve

Next, I moved to the control points to create a new curve and increased t to evaluate a point on the far right end. 

New curve, new point location

Part 2: Bezier Surfaces with Separable 1D de Casteljau

Building upon the 1D de Casteljau algorithm, we can extend it to generate 2D Bézier surfaces in 3D space. The concept is straightforward: instead of using a 1D array of control points, we employ a 2D array and the same parameter, t. To evaluate a point on the surface, we perform the 1D de Casteljau algorithm on each row of control points using the parameter t. This reduces each row to a single point. We then obtain a final 1D array containing the evaluated points from each row. Finally, we apply the 1D de Casteljau algorithm one last time to this array, resulting in a single point that lies on the surface.

Bezier Surface Teapot

The teapot and wavy cube were constructed using my 2D de Cateljau algorithm. To get each point on the surface, I used a 2D array of control points and parameter t to run the recursive 1D de Cateljau algorithm on each row, collapsing it to a point, and finally collapsed all row points to a single point which lied on the surface.

Bezier Surface Wavy Cube

Section II: Triangle Meshes and Half-Edge Data Structure

This section shifted focus to rendering 3D objects using triangle meshes instead of Bézier curves. While Bézier curves offer smoother results, triangle meshes are more memory-efficient and render faster, making them the preferred choice in many applications. However, instead of just storing a collection of triangles defined by three coordinates, we use a more sophisticated data structure called a "half-edge" mesh. This structure incorporates pointers or links that facilitate efficient traversal of the mesh and enable operations like splitting and flipping triangles.

Half-edge Data Structure

Part 3: Area-Weighted Vertex Normals

Before constructing 3D objects using triangle meshes, we must establish proper shading to achieve realistic lighting and shadows. Phong shading is the primary technique used for this purpose. It calculates lighting at each pixel based on surface normals and light sources, resulting in smooth shading and highlights. 

An alternative is flat shading, a simpler approach that applies a single color to the entire surface of a polygon. While faster to render, it produces a less realistic appearance. The steps involved in Phong shading begin by visiting each vertex and calculating an area-weighted normal vector. This vector, perpendicular to the surface and pointing outwards, is determined by:

Phong Reflection Model - Shaded 3D Objects using Surface Normals

Once a normal vector is calculated for each vertex, it's passed on to the 'phong reflection model' which takes the vertex normal vector, light direction, view direction, and material properties as inputs. It then calculates three main components of lighting:

By combining these components, the Phong reflection model determines the final color of each pixel, resulting in a realistic representation of lighting and shading effects on the 3D object.

Flat Shaded Teapot

For the assignment, I only had to calculate the vertex normals and the rest of the program took care of feeding the normals through the reflection model and assigning colors to each pixel. 

Phong Shaded Teapot

Part 4: Edge Flip

The triangle meshe representation of the teapot above isn't as smooth as the teapot rendered using Bezier surfaces earlier. To fix this, we'll need to a way to flip and split halfedges because smaller triangles can approximate smoother surfaces much better than larger ones. 

Flipping an edge in a half-edge data structure can be more challenging than it initially appears. There are numerous variables to manage and reassign, including:

While the concept is straightforward (involving assigning variables and reassigning them), it's easy to introduce errors during implementation.

A personal anecdote: I spent two days debugging my implementation due to an accidental variable rename in a reference drawing. In the left corner image, the vertex labeled "d" corresponds to the rightmost vertex, and "b" corresponds to the bottom vertex. However, in the bottom right corner, "b" is labeled as the rightmost vertex, and "d" as the bottom vertex. This inconsistency caused incorrect rendering and was difficult to debug because I was focused on code errors rather than the drawing mistake.

Edge flips let us reduce the degree (number of edges connected to it) of one vertex, while increasing the degree of another vertex. This is a primitive operation that will be needed later on when we do mesh upsampling.

Before Edge Flips
After Edge Flips

Part 5: Edge Split

The second primitive operation we need to implement before doing mesh upsampling is edge splitting. Splitting edges lets us break larger triangles into smaller ones. Splitting edges is done in a similar way as flipping edges, except that it creates additional components to keep track of and re-assign, specifically:

Edge Split Drawing

This is actually the part where my mistake in labeling vertices in my drawing caused my rendering to be incorrect. It caused black spots in my rendering (holes maybe?) that didn't give me much of a clue to help debug it. I even added assert statements to make sure each vertex, face, edge, and half-edge was connected to the other components I expected them to but the assert statements never triggered. I asked my friend for help and after an hour on zoom they saw the issue on my drawing🙏. 

Buggy Rendering
Before Edge Splits
After Edge Splits and Edge Flips

Part 6: Loop Subdivision for Mesh Upsampling

Edge flipping and splitting are the primitive operations needed for the loop subdivision algorithm that performs mesh upsampling. Mesh upsampling increasing the resolution of a 3D mesh. This means adding more vertices, edges, and faces to the mesh, resulting in a more detailed and smoother representation of the original object. Loop subdivision is similar to the de Casteljau algorithm in that its recursive and consists of two steps:

For a new vertex that sits in the middle of the split edge AB, between a pair of triangles (A,C,B) and (A,B,D) gets assigned the position: 3/8 * (A + B) + 1/8 * (C + D)

For an old vertex, it's updated position is: (1 - n * u) * original_position + u * (sum of all neighbor vertices positions) - u is a number and variable that depends on the vertex degree.

Performing these two steps recursively will make the object's surface more round and smooth. 

Step 1 - Split Every Triangle into 4
Splitting Triangles into 4 via Splits and Flips
Step 2 - Update Vertex Positions
Cube - Loop Subdivision Round 0
Cube - Loop Subdivision Round 1
Cube - Loop Subdivision Round 2
Cube - Loop Subdivision Round 3

The transformation of the cube above clearly shows loop subdivision making the 3D object more round and smooth, but note that it doesn't keep the cube's symmetry. We can try to preserve the symmetry by preprocessing the cube before doing loop subdivision iterations and manually splitting edges so that each corner of the cube has the same vertex degree.

Vertex degree before splitting
Vertex degree after splitting and making X pattern
Symmetrical Cube - Loop Subdivision Round 1
Symmetrical Cube - Loop Subdivision Round 3


This project provided valuable insights into the representation and rendering of 3D objects. However, I'm particularly interested in learning more about Bézier surfaces and their applications in computer graphics. The project provided a file containing control points for rendering the teapot. While I understand their role, I'm curious about the process of creating such a file and the initial construction of the teapot model. Manually defining these control points seems highly improbable, suggesting the existence of specialized software to facilitate this process. Overall, this experience has sparked my interest in exploring Bézier surfaces and 3D meshes, and their practical applications in 3D modeling.