CS184 Project 2 (MeshEdit) Writeup

Spring 2023, Yunhao Cao and Yuqi Zhai

Overview

In this project, we implemented a mesh editing tool that allows users to edit a mesh in a 3D space. The tool supports the following operations:

  1. Bezier Curve/Surface visualization and editing
  2. 3D Vertex / Edge visualization and editing
  3. Vertex Normal visualization
  4. Mesh upsampling using Loop subdivision

The skeleton code for this project is basically a 99.9% complete 3d engine, we just need to fill in a few functions to make interpolations/editing work.

Part I: Bezier Curves with 1D de Casteljau Subdivision

De Casteljau’s algorithm recursively calculates the Bezier Curve through a series of linear interpolations.

  1. On each level, we do linear interpolation on the line segments between 2 points available through a predetermined parameter of t to find the new point that we would use to linearly interpolate for the next level.
  2. Eventually, we will end up with only 1 point, where this point is actually on the Bezier Curve that we want to find. Together with the starting and ending points (in our case of a cubic spline, b0 and b3), we could find the unique cubic function that passes through all three points, which will serve as the Bezier Curve for this section.

Each step-level of evaluation:

step images
1
2
3
4
5
6
with curve
hiding intermediate points

Scrolling t:

step images
before
after

Changing control points:

step images
before
after

Part II: Bezier Surfaces with Separable 1D de Casteljau

In this part we implemented Bezier surfaces.

  1. De Casteljau algorithm could easily be extended to Bezier surfaces by essentially doing the De Casteljau algorithm twice over the surface, once along the row direction, then using the interpolated curves in the row direction do once more to get the column direction, which combined to be the Bezier surface.
  2. More specifically for each (u,v) , We will interpolate each row in the n x n grid of control points at parameter u specified, which will get us one 3D point per row evaluated by the Bezier curve at parameter u. Then using those n points to do once more the de Casteljau algorithm with parameter v to get the point we want that corresponds to (u, v).

Rendering of teapot:

Part III: Area-Weighted Vertex Normals

Phong shading provides a better shading for smooth surfaces by taking into account the surface normal at each vertex. In this part, we implemented area-weighted vertex normals.

We implemented the area-weighted vertex normals through the following steps.

  1. First we find the vertices of the current face (triangle) that we are trying to calculate the area-weighted face normals. The vertex that we want to get the normal of (call it v0) for should always be one of the vertices, since we want the normals for faces that the vertex is incident to.
  2. Then the remaining 2 vertices we retrieve by using the vertex of the next halfedge of the halfedge initiated at v0 (call this vertex v1), and by using the vertex of the next halfedge of the next halfedge of the current halfedge starting at v0 (call this vertex v2).
  3. After that, we constructed 2 vectors, from v1 - v0 and v2 - v1. And we calculate the cross product of the 2 vectors without normalizing.
    1. We did not use the normal encoded in the Face structure because it is the same as multiplying the normalized normal with the area (only by a factor of 2, since area of a triangle is the norm of the cross product of 2 vectors of the sides divided by 2).
  4. Lastly, we add the cross product to the result 3D vector and normalize at the end.

It is clear that without vertex normals, the teapot appears to have clear boundaries for each triangle mesh. However, with the vertex normals implemented, the teapot looks like a round object.

Surface Normals Vertex Normals

Part IV: Edge Flip

We followed closely by the steps outlined in the spec, where we listed all mesh elements from halfedges, edges, vertices, to faces, number them in a way that we could visualize more clearly, and perform the flip.

  1. We check whether both faces involved are not boundaries, through calling is_boundary() for the face mesh.
  2. Then we begin the flip by modifying the halfedges 0 to 5 first by resetting the next, twin, vertex, face, and edge according to the graph we drew where I linked below.
  3. After that, we modify the halfedges associated with each vertex. We move on to modify the halfedges associated with edges and last for the faces.
  4. We did not use any interesting implementations, and the debugging tricks I used are mainly through check_for function and the graph we drew on our notebook to begin with (going over the assignments one by one to make sure the pointers are pointing to the correct mesh element).
Before After

The debugging journey was a tough one. First we fell into the pitfall where we thought similarly to the last few tasks, we have to create a new EdgeIter instance to return, which ends up with weird overlapping happening on the teapot. Then after carefully examining the spec, we noticed that and changed that.

After that, we failed on the point where I did not update the vertices and faces halfedges, and when I do flips on the teapot, there may appear some new edges after flipping (check_for returns weird number of meshes for the edge), where those new edges with black color filling in will disappear after 4 flips. Then we add in the full assignments of halfedges to all faces and edges (before we thought the halfedges assigned will not change, so we did not bother to reassign), the whole edge flip is complete. In order to make sure, we did flipping multiple times and it seems to be fine.

Part V: Edge Split

In this part, we are asked to implement the edge split operation: selecting an edge and spliting it into two edges, while preserving the mesh connectivity.

  1. We implemented this by first checking whether the edge is a boundary edge. If it is, then we process it with a special rule described in the EC section
  2. When we split one edge into two, we need to create a new vertex in the middle, the originall edge splits into two edges to connect the new vertex to two vertices that the edge is previously connected to.
  3. We also need to add in two more edges to connect the new vertex to two top vertices of the two faces that the edge is incident to.
  4. Then we need to add in two more faces to account for the original two faces splitting.
  5. Finally we add in corresponding halfedges into the mesh

Before and After Edge Splits

Before After

Edge Splits + Flip

Before Split Flip

Eventful Journey:

  1. It is extremely important for this part to be implemented correctly since the next part heavily depends on this part. I made sure that all halfedges have twins in the inverse direction, and all pointer relaitonships are correct between vertices, halfedges, edges, and faces.

EC: Splitting on boundary edge

  1. This case is actually relatively simpler than the general case, because instead of splitting two face into four faces, we only need to split one face into two faces.
  2. One thing special in the implementation is that we need to check which side of the halfedge lying on the splitting edge is inside the mesh and which is outside. Then we just draw out the diagram and figure out relationships between vertices, edges, halfedges, and faces before and after the split.
  3. Once we figured out that, we can simply add two new edges, four new halfedges, and one new face to the mesh.
Before After

Part VI: Loop Subdivision for Mesh Upsampling

In this part, we implemented the Loop subdivision algorithm for mesh upsampling. The algorithm calculates new positions for existing vertices and creates new vertices in the middle of each edge.

  1. I implemented the subloop algorithm by first iterating through the mesh and calculating the new position for each old and new vertex. For the new position of the new vertex, I store it in its corresponding splitting edge's newPosition attribute.
  2. Then I iterate through the mesh and start dividing each edge. The challenging point here is that we need to make sure we don't divide on new edges otherwise we will end up in an infinite loop.
  3. Then I iterate through the mesh again and flip new edges that connects an old vertex with a new vertex.
  4. Finally I update the position of all vertices in the mesh

Debugging thoughts:

  1. Once I was able to think about the algorithm throughly I was able to fix every bug I encountered. The tips on the project website was extremely helpful. I also have a screenshot of a bug I encountered.

Task 6 Bug

Some observations:

Beetle

Before After

Icosahedron

Before After

I think one important thing to notice is that on sharp corners after the split the corner will be more prominent than other corners. Depending on the number of neighbours a sharp corner has, the corner will be more or less prominent.

Subdivisions on cube

Step Image
1
2
3
4
5

Preprocess Ideas:

I think the asymmetric behavior of the subdivision algorithm is due to the fact that the edges on each surface of the cube is not symmetric, and our algorithm depends on the position of neighbouring vertices to calculate the new position of the vertex. So I did exactly that to make the subdivision symmetric

Step Image
1
2
3
4

Credit and site notes:

Webpage hosted at quantumcookie.xyz/Opensourced-Study-Notes-Berkeley/CS184/proj2-meshedit-writeup