CS 184: Computer Graphics and Imaging, Spring 2018

Project 2: Mesh Editor

Michael Lu, CS184-aaz


Give a high-level overview of what you implemented in this project. Think about what you've built as a whole. Share your thoughts on what interesting things you've learned from completing the project.

Section I: Bezier Curves and Surfaces

Part 1: Bezier curves with 1D de Casteljau subdivision

de Casteljau's algorithm is a recursive algorithm that uses linear interpolation to generate a smooth curve between two points by using a sequence of control points. I computed the locations of the intermediate points of the algorithm in each step using the relative t parameter until one point is left, which becomes the point on the Bezier curve. The entire Bezier curve is generated by running de Casteljau's on all t from 0 to 1.

Step 0 of de Casteljau's
Step 1 of de Casteljau's
Step 2 of de Casteljau's
Step 3 of de Casteljau's
Step 4 of de Casteljau's
Step 5 of de Casteljau's
Different Bezier curve with different t parameter

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

For Bezier surfaces we can apply de Casteljau's along one axis of the control points to obtain a set of Bezier curves. Then interpolating between the curves along the second axis using de Casteljau's obtains the Bezier surface. I implemented this by computing the Bezier curve points along the u axis corresponding to the parameter u. Then using those points as the new control points, I computed the Bezier surface point with the parameter v.

Bezier Surface: teapot

Section II: Sampling

Part 3: Average normals for half-edge meshes

First, I obtain the other two vertices of the face using twin() and next(). Then I compute the normal vector by taking the cross product and add it to a collective sum. Repeat for the other faces, using a do-while loop because I couldn't get the conditioning right using a for or while loop with this implementation.

Teapot with face normals shading
Teapot with average vertex normals shading

Part 4: Half-edge flip

I essentially stored all the pointers into variables and remapped all the references in the halfedges using setNeighbors. I also set the halfedges for the faces and the vertices just to make sure everything is correct. The edges stay the same so I am confident enough to not reassign them.

My eventful debugging journey started with 11 minutes and 40 seconds of hand drawn diagrams and mappings on a sheet of paper. And then it ended because everything worked out xD.

Modified Cube: pre edge flips
Modified Cube: post edge flips

Part 5: Half-edge split

I did the same thing as the last part: stored all the pointers and carefuly remapped all the halfedge references using setNeighbors. Then I made sure to also set all the halfedge properties to the appropriate halfedge in the new diagram.

This epic debugging journey started with 17 minutes and 22 seconds of hand drawn diagrams and mappings on a sheet of paper. And then it ended because everything also worked out.

Modified Cube: pre edge splits
Modified Cube: post edge splits
Modified Cube: post edge splits/flips

Part 6: Loop subdivision for mesh upsampling

I basically just did what the spec told me to do. I first compute the positions of the vertices in the input mesh, as well as the vertices associated with every edge, based on the weighting formula. Then split all the edges in the mesh and mark which halfedges are new and which are old. Then we flip all the edges that connect new vertices to old ones so that we generate the correct mesh pattern. Then finally, we copy the value of the new position of the new vertices into its position field to finalize the mesh.

Sharp corners and edges of meshes are smoothed out when upsampled. If we pre-split some of the nearby edges, we can preserve the general shape of the sharp edge as we upsample. The more edges we pre-split, the less the sharp corner or edge is affected or smoothed out by upsampling.

Default cube mesh
Cube mesh after 3 iterations of upsampling
Cube mesh with several pre-split edges
Pre-split cube mesh after 3 iterations of upsampling

The reason that the cube does not subdivide symmetrically is that the triangles that make up the mesh are not symmetric around the cube's axes of symmetry. One way to solve this issue is to pre-split each of the edges that run along a face so that the face consists of 4 triangles. This way the mesh's triangles become symmetric along the axes of symmetry that runs through opposite faces. Another way is to flip some of the edges so that the mesh triangles are symmetric along the cube's diagonal.

Default cube mesh
Cube mesh after 4 iterations of upsampling
Cube mesh with split edge faces
Pre-split cube mesh after 4 iterations of upsampling
Cube mesh with flipped edges
Pre-flipped cube mesh after 4 iterations of upsampling

Section III: Mesh Competition

If you are not participating in the optional mesh competition, don't worry about this section!

Part 7: Design your own mesh!