CS 184: Computer Graphics and Imaging, Spring 2018

Project 2: Mesh Editor



This project explores two different methods for producing smooth surfaces: constructing them from Bezier curves using the de Casteljau method and editing existing COLLADA meshes systematically. For the first method, producing Bezier curves involves layers of linear interpolation. For the second method, we explore methods for producing more realistic shading with existing vertex data. Loop subdivision will come into play for increasing the complexity of a mesh, effectively smoothing out the structure by supersampling.

Section I: Bezier Curves and Surfaces

Part 1: Bezier curves with 1D de Casteljau subdivision

de Casteljau's algorithm is a method for designing Bezier curves that uses linear interpolation to determine the location of a point in space at time t. For the sake of a 2D Bezier curve such as the ones shown below, the algorithm forms a pyramid of vectors of height D, where D is the polynomial degree of the curve. Every point on this curve is the "top" of a de Casteljau pyramid.

The following is the progression of de Casteljau evaluation for a degree 6 Bezier curve.

Step 0.
Step 1.
Step 2.
Step 3.
Step 4.
Step 5.

The value of t and of the control points can also be tweaked:

Increased t for more interesting interpolation.
Changed control points.

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

The next part uses the same pyramid algorithm, but this time to generate a surface. For a point (u, v) on a plane and with a 4x4 grid of bezier curves, the algorithm generates a temporary Bezier curve using a set of interpolated vectors from the "u" axis, and then generates a final interpolated vector using v and the temporary curve. By this method, we have a systematic way to determine the exact location of any point on the surface along the u-v plane.

Below is the famous Bezier teapot generated from this algorithm:

Teapot using Bezier surfaces.

Section II: Sampling

Part 3: Average normals for half-edge meshes

To find the normal of a face from vertex v, we take the two edges connected to v. EDGE1 is the half-edge corresponding to v (pointing away from it), and EDGE2 is the halfedge corresponding to EDGE1's next next halfedge (pointing towards v).

By the right-hand rule where we have two vectors u and v, EDGE1 is like v and EDGE2 is like u. So, EDGE2 X EDGE1 is the area-weighted normal.

The smoothed normal is the sum of all area-weighted normals around the vertex. Below is the before and after screenshots for smoothed normals.

Without smoothed normals.
With smoothed normals.

Part 4: Half-edge flip

The flip operation wasn't so much a debugging journey for me as it was my being lazy... and then my having to not be lazy. I approached the flip initially by preserving the edge's halfedge and twin halfedge.

Seems like a good approach, since that means you don't need to worry about the twin attribute, and you just have to rearrange the next attribute for all 6 halfedges.

However, some of the faces were disappearing, so I decided to make a detailed map of the two triangles, and then yes, it was like solving a puzzle in a Zelda dungeon (is that epic enough?). In the end, I modified all pointers for halfedges, faces, and vertices (but not twin or edge attributes or edges themselves).

Original, no flips.
One flip alters the shape/shading.
I freaked since I thought the face was gone.
Turns out it was just blocking a lot of light.

For a hopefully thorough test of the flip functionality, I tried to make a dent in the side of the teapot.

Dent level 1.
Dent level 2.
Dent level 3.
Final flip from a different perspective.

Part 5: Half-edge split

Because of the increased complexity of the split algorithm and the need to allocate additional memory, I decided to draw out a detailed diagram. This is pretty much what guided all of my logic in implementing the split operation, and surprisingly enough, it worked on the first try, with a slight bit of tweaking (e.g. forgot to position the new vertex properly and had a typo in the edge allocations).

Cube before.
Cube after significant splitting.

Finally, to put our triangle operations to the test...

Teapot before.
Teapot after many operations.

Unfortunately (?) I did not have an epic debugging adventure, but it did certainly feel like an epic puzzling adventure.

Part 6: Loop subdivision for mesh upsampling

The implementation of loop subdivision was far more difficult since it exposed a subtle, hidden bug in the split operation. The structure of the upsample function itself closely follows the recipe given by part 6:

  1. Compute new positions for old vertices.
  2. Compute new positions for new vertices.
  3. Split every edge.
  4. Flip every "new" edge. (There was a major bug here that I'll explain shortly.)

That was the successful implementation, along with some bool storage and manipulation. There were 3 primary bugs in the original implementation that I had to scout out and fix:

Here is an example teapot after loop subdivision:

No loop subdivision.
One loop subdivision.

As hinted, it does seem as if the sharp edges of the original, especially on the handle, get smoothed out.

Original handle.
Subdivided handle.

Presplitting one layer around the handle has a slightly different effect, though there is still smoothing.

Pre-split one layer.
Subdivision with pre-split.

Inspecting 4 different splits on the cube...

No loops.
One loop.
Two loops.
Three loops.

The result looks asymmetric because, although the geometry is symmetrical, the topology is not. Let's pre-split every edge on every square face and try again.

Pre-split symmetric.
Three loops.

Now that the topology is symmetric, so is the subdivision. At least, it's symmetric in every way that the original cube was.

Section III: Mesh Competition

Part 7: Design your own mesh!

Again, really wish I could have done this part! Ran out of time.