Well, this is embarrassing. There should be an image here. Great picture, too!
Curved Surfaces: How do They Work?

CS 184: Computer Graphics and Imaging, Spring 2017

Oliver O'Donnell, CS184-agh

Project 2: MeshEdit


Computers hold discrete information - ones and zeroes - so how can the likes of Pixar generate beautiful curved shapes? Bezier surfaces and polygon meshes are the data structures that allow programs to generate close estimations of smooth shapes. It was incredibly interesting to get into the details of these data structures.

The skeleton code that I started with was a 99% finished 3D graphics engine; as students we were only required to fill in a few particularly complex methods. It was eye-opening to see the visual impact of minor implementation bugs. In a mesh data structure, every pointer makes a difference, leading to some wacky shapes.

Section I: Bezier Curves and Surfaces

Part 1: Bezier curves with 1D de Casteljau subdivision (10 pts)

De Casteljau's algorithm is essentially repeated corner-cutting. We find the coordinates of a point that is a proportion of t along the curve by recursively halving (actually, breaking edges proportionally to t) and then creating new edges connecting each pair of mid-points.

We stop recursion when there is exactly one new edge. Now, the coordinates of the point corresponding to t are a linear interpolation of the endpoints of the final edge. This becomes clearer when you view my demonstration video.

Note to grader: I hope it's okay that I have provided a video rather than screenshots, as the spec requests. As you can see, the video contains frames that fulfil the purpose of each of the required screenshots.

Part 2: Bezier surfaces with separable 1D de Casteljau subdivision (15 pts)

De Casteljau's algorithm extends quite nicely to surfaces. Before we covered it in lecture, I had had no idea how a Bezier curve could ever relate to a surface.

Consider a situation with 16 control points along the u-axis and the v-axis, where we are trying to find the 3D point corresponding to (u,v). (u,v) performs the same purpose as t did in the 1-dimensional example.

As you can see in the image, the key is to first find where u would fall on the four bezier curves in the u direction. We can calculate these using the method from the 1D example.

Those four points constitute the control points that define the v curve. As we did before, we simply perform 1D De Casteljau with these 4 control points. The resulting 3D point is the point corresponding to (u,v).

Here is a screenshot of my rendering of bez/teapot.bez:

Section II: Loop Subdivision of General Triangle Meshes

Part 3: Average normals for half-edge meshes (10 pts)

In this section, I resolved an issue that occurs on edges and vertices regarding shading. As you will see with the following two screenshots, it is far superior to have triangles determine their color by using neighboring normal vectors to achieve greater smoothness.

I simply used the halfedge data structure to retrieve area-weighted average normal vector for each neighboring face. A complementary part of the code leverages the improved normal vectors at the vertices to create the smooth gradient you see in the screenshots.

Part 4: Half-edge flip (15 pts)

I implemented the halfedge flip operation essentially as recommended. I set out my "ingredients", an exhaustingly long list of pointers in the structure of the starting triangle, and reassigned the attributes of each of the halfedges, then the faces, then the vertices, using a whiteboard to help me visualize the geometry.

Here is the mesh before some edge flips:

And after some edge flips:

My eventful debugging journey centered around multiple misallocated pointers. After a while, AB and BA look like the same thing. A bug followed me all the way to part 6 - I had misallocated the pointer to a vertex and that was making some triangles very lopsided in the upsampling process.

Part 5: Half-edge split (15 pts)

I implemented the halfedge flip operation with the same "ingredients" approach as before. I reassigned the attributes of each of the halfedges, then the faces, then the vertices, and this time also the edges using a whiteboard as I thought through the geometry to determine what should go where.

Here are screenshots of a mesh before and after some edge splits:

Here are screenshots of a mesh before and after a combination both edge splits and edge flips.

I didn't go on much of a debugging quest for this section, thankfully!

Part 6: Loop subdivision for mesh upsampling (25 pts)

It is very challenging to explain loop subdivision briefly, but I will try. The core idea is to pursue a specific strategy of:

  1. Vertex location adjustments,
  2. Edge splitting, and
  3. Edge flipping.

The vertex location adjustments must be done in a way that approximates the underlying shape of the mesh. The edge splitting can simply be applied to all non-border edges while being careful to mark which edges you've just created so as to not recurse infinitely. The edge flipping needs to be done between only pairs of old and new vertices where the edge is also a "new" edge.

Since the instructions for this section were so helpful, I didn't encounter too many implementation issues; I ended up with a for-loop for each TODO.

Take some notes as well as some screenshots to record your observations of how meshes behave after Loop subdivision. What happens to sharp corners and edges? Can you lessen this effect by pre-splitting some edges?

Meshes after loop subdivision smooth over sharp corners and edges. But if you are careful about it, it's possible to lessen the smoothening by pre-splitting some edges.

dae/cube.dae has an asymmetric mesh, and therefore the smoothed approximation is more like a skipping rock than a sphere. This can be fixed by pre-processing the cube so that each face is symmetrical.

These effects occur because of the way that subdivision determines the new positions of vertices. When it computes a weighted average of points, the algorithm considers topology but not geometry, and provides too much weight to some vertices.

Section III: Shaders

Part 7: Fun with shaders (10 pts)

The Phong shader was an interesting taste of lighting algorithms!


Though at times challenging and certainly tedious when it came to reassigning pointers in the halfedge linked-list-style data structure, this was the second in a series of excellent graphics projects. I feel as though I am gaining useful insight into the way that the most impressive 3D projects are developed.