Homework 2: Meshedit
Colin Steidtmann
Overview
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)
Key Idea: Estimate derivative by using slope between previous point and next point, for each point. For the endpoints, estimate it how you think is best.
Bézier Curves: Defined by control points, offering flexibility and widely used in computer graphics and design.
Control points (used in Bezier curves): They define curve shape. They offer flexibility in shaping the curve independently of potential noise or errors in data. Cubic Bezier curves use four control points. The tangents at the beginning and end of the curve are determined by the first and last control points, respectively.
Data points (used in Hermite and Catmull): Represent actual measurements or observations you want the curve to pass through. Can be noisy or inaccurate depending on the measurement process.
De Casteljau Algo (Used to calculate points/pixel locations on Bezier curve) :
Start with the four control points of the curve.
Compute the midpoint of the curve.
Compute the two new control points for the two halves of the curve.
Repeat steps 2 and 3 until the desired level of accuracy is reached.
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.
Next, I moved to the control points to create a new curve and increased t to evaluate a point on the far right end.
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.
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.
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.
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:
Using the half-edge mesh to traverse all triangles directly surrounding the vertex (incident to it).
Calculating the normal vector for each surrounding triangle.
Weighting each normal vector by the area of its corresponding triangle.
Summing all the area-weighted normal vectors and normalizing the result (making its length equal to 1).
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:
Ambient Lighting: 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 Reflection: General, overall lighting you see on an object. It happens when light bounces off the surface in many different directions, creating a softer, more even illumination. Rougher surfaces diffuse light more evenly, while smoother surfaces create sharper highlights.
Specular Highlights: Specular highlights are those bright, shiny spots that appear on objects when they're hit by light. They occur when light reflects directly off the surface
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.
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.
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:
Vertices: 4 (a, c, d, b)
Half-edges: 10 ((bc, ca, ab); (bd, dc, cb); (cd, db, ba, ac))
Edges: 5 (e0, e1, e2, e3, e4)
Faces: 2 (f1, f2)
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.
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:
Faces: 2 new (f3, f4)
Vertices: 1 new (m)
Half-edges: 6 new
Edges: 3 new (e5, e6, e7)
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🙏.
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:
Subdivide each triangle in the mesh into four, this is called a 4-1 subdivision and it can be done via a series of split and flip operations we implemented earlier.
Update the positions of new vertices created by split operations and old ones.
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.
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.
Conclusion
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.