CS184/284A Spring 2025 Homework 2 Write-Up

Han Li & William Wu

Link to webpage: wu-yong-xuan.github.io/cs184/hw2/index.html
Link to GitHub repository: cal-cs184-student/sp25-hw2-_-3

Overview

In this assignment, we took a look at bezier surfaces to evaluate curved surfaces. We implemented 1d bezier curves, and then using that, we created 3d geometry using bezier surfaces. Additionally, we implemented some simple mesh geometry modification systems to flip edges and subdivide triangles. Using that, we implemented the loop subdivision algorithm in other to subdivide our mesh and create a better smooth surface.

The algebra is honestly so much easier to implement in code than to understand with math notation tbh.

Section I: Bezier Curves and Surfaces

Part 1: Bezier curves with 1D de Casteljau subdivision

So word's on the street that you're looking for the good stuff. Not the straight lines that everyone else seems to be smoking, but true, raw, unadultured, curvy bezier curves. Well, you've come to just the right place. We can get you sorted right on up, Casteljau's style.

A bezier curve consists of multiple control points, and through a series of interpolations, we can arrive at a point on our final curve. Let's start off with an example with 4 control points, \(b_0, b_1, b_2, b_3\). We can denote points \(b_0^1, b_1^2, b_2^3\) as the linear interpolation between the original first degree points. Expanding this interpolation recursively, we can then interpolate between \(b_0^1, b_1^2, b_2^3\) instead, and so on and so forth until we get to our final point \(p\). By graphing that point across all points of interpolation, we arrive at our final bezier curve.

To implement this programmatically, we take the ordered list of points of the bezier curve, and then loop through them. We can then interpolate between each pair of points in the array and save that to a return array. This will give us the 1 step interpolation of the bezier curve. Simply repeat this until you only have 1 point and voila! We got our bezier curve.

Part 2: Bezier surfaces with separable 1D de Casteljau

Those 1D bezier curves were no joke, just as good as you had dreamed, but still not enough. Despite their elegance and exquisiteness, your hunger remains unsated, your thirst unquenched. You began a journey on a quest to find the purest curve. After traveling on foot for what feels like an eternity, through hell and back, you've finally found it, the bezier surface.

A bezier surface is essentially just a 2D array of control points in which each row of the array defines a single 1D bezier curve. Taking all the 1D bezier curves defined by the rows, we then can interpolate between them and generate a new bezier curve using the points defined by the array of beziers.

More specifically, To find a point on the bezier surface, we had to consider two parameters \((u,v)\) to characterize the position of the point along the bezier curves. Using the de Casteljau algorithm with the parameter \(u\), we can generate a point along each bezier curve defined by the rows of the array. Using the points from each row as control points of another bezier curve, we can use de Casteljau again to get the point at position \(v\) to get our point on the bezier surface. Do this for each point along the curve and voila! Your very own bezier surface.

Section II: Triangle Meshes and Half-Edge Data Structure

Part 3: Area-weighted vertex normals

Once you've tasted 2 dimensions, you're gonna be craving for 3 dimensions. Unfortunately, most of the cheap stuff you get nowadays is all tessellated. We want the smooth stuff for your smooth brain. Here, we want to be able to average vertex normals based on the surrounding face normals, weighted based on the size of those faces.

To implement it, by using a combination of the twin and next operators for the half edges, we can go through all the adjacent faces of any given vertex.

For each adjacent face, calculating the cross product between any 2 half edges of the face will give you the face normal vector with a magnitude of \(2 * \text{the area of the triangular face}\). Simply dividing it by 2 will give you a normal vector with the correct magnitude. Doing this for each triangular adjacent face, we can then sum the vectors and normalize the final vector.

One thing to note is that since the half-edges are organized counterclockwise, taking the cross product will always give you a positive normal vector, ensuring that our normal is pointing in the right direction.

Part 4: Edge flip

I'm sure you're very familiar with edges in the present progressive tense. Putting your behavior aside though, let's talk about flipping! Instead of flipping people off, let's use those skills to flip other things as well. No, not burgers even though you might need the practice as a CS major. I'm talking about flipping edges.

To flip an edge is actually pretty simple, albeit kinda annoying. Essentially, you just follow this diagram. For example, for h0, you can have it point towards v3 instead. Then you can go and fix everything else. Yeah�c it's kinda simple but also very tedious to do. :D

Part 5: Edge split

Man, all those flipping edges are a flipping pain. I don�ft want to point fingers but all those pointer reassignments are flipping annoying. You must want to utterly rip them apart and split them in half. Well have I got news for you! Now introducing edge splits, for the cost of only a ton more pointer assignments, you can split the flipping edges in half.

Splitting an edge is very similar to flipping one, it�fs a long long list of pointer reassignments, but before that you have to create a couple new elements. Specifically, one new vertex (whose position is just the average of the positions of the vertices connected by the edge), three new edges, and six new half edges. When creating the new vertices and edges, we set a parameter isNew to true (except for e5 in the diagram, where it�fs set to false because it�fs part of the original edge that was split) which will make Loop subdivision easier later. After saving references to each relevant object (all vertices, edges, faces, and half edges), we reassign all the pointers accordingly to the following diagram (ie. h5->next() = h10).

Part 6: Loop subdivision for mesh upsampling

Now that we can split the flipping edges, we can be absolutely diabolical and split every flipping edge. Turns out we can do this ethically using a mesh upsampling algorithm called Loop Subdivision for some computer graphics applications that don�ft involve vengeance against edges.

Loop subdivision involves two steps: a 4-1 subdivision of each triangle in the mesh, followed by updating each vertex position. To do this, we actually calculated the new vertex positions first and stored them for later use so we wouldn�ft have to traverse more triangles. We iterated through each vertex in the triangle and calculated the new position using the following formula:

Where \(n\) is the vertex degree, \(u\) is equal to \(\frac{3}{16}\) if \(n=3\) and \(\frac{3}{8n}\) otherwise, \(\text{original_position}\) is the original position of the vertex, and \(\text{original_neighbor_position_sum}\) is the sum of positions of all neighboring vertices. This gives us the new position which we saved to a variable in the vertex object. We also set isNew to false for each vertex as we iterate through.

Then, we iterated through all the edges of the mesh and calculated the positions of all the new vertices to be created when doing the 4-1 subdivisions using the following formula where the capital letters denote the positions of the corresponding vertex:

We saved these new positions to a variable in the corresponding edge to be cut. We also set isNew for each edge to be false as we do this.

We then split every edge in the mesh. We do this by iterating through every existing edge in the mesh, opting to iterate using a counter with the max being the current number of edges. Because the mesh implementation adds new items to the end of a list, any new objects made using split will not be iterated through this way. As we iterate through, if isNew for an edge is false (should always be true, but just in case a new edge somehow gets iterated over we included the statement), we split the edge and save the adjusted position of the new vertex that we stored previously in the edge into a variable in the newly made vertex. We already set isNew to true for the new vertex and new edges in our split function so we do not have to worry about that.

Then, we iterated through the edges again and flipped any new edge that connects an old and new vertex. Finally, we iterated through every vertex and set the vertex�fs position to the stored adjusted position. After all that, we get a Loop subdivided mesh!

When subdividing a mesh, sharp corners and edges get smoothed out. We can reduce this effect by pre-splitting edges near the edges and corners that we want to stay sharp.

We can notice how if we subdivide a default cube using the Loop algorithm, it comes out assymetrically. This is the expected behavior for the Loop algorithm as with a low poly cube like this especially, the asymmetry of the direction of the edges across each face creates a skew in the direction of the location of the newly created vertices.

To remedy this, we can instead split all the face edges first so that they form X's. This will ensure symmetry before we subdivide

(Optional) Section III: Potential Extra Credit - Art Competition: Model something Creative

Here is Mel-chan, UCBUGG's mascot!