mesh editor

Nadia Hyder, CS 184 Spring 2021

OVERVIEW

In this project, I explored several geometric modeling concepts; I built Bezier curves and surfaces using de Casteljaus algorithm, manipulated triangle meshes represented by the half-edge data structure (flipping and splitting edges), and implemented loop subdivision for upsampling. This project is split in two sections: 1. Bezier curves and Surfaces, and 2. Triangle Meshes and the Half-Edge Data Structure.

SECTION I: BEZIER CURVES AND SURFACES

Part 1: Bezier curves with 1D de Casteljau Subdivision

I implemented Bezier curves using de Casteljau’s algorithm. Bezier curves run from a start to end point, with its curvature influenced by intermediate control points. Bezier curves are the result of several linear interpolations over lines connecting these points.

De Casteljau subdivision is a divide-and-conquer algorithm for evaluating Bezier curves, recursively performing linear interpolation between two points to place new control points between edges. The base case is when there is only one point left.

More formally, the recursive step is a parametrized equation of the movement between two points. Given n control points p1, …, pn, and the parameter t, we use linear interpolation to calculate the n-1 control points in the next subdivision level:

I implemented this recursive step, which eventually brings us to a final, single point which lies on the Bezier curve given parameter t.

Here are the results:

Bezier curve with each step of the evaluation from original control points to final evaluated point

Bezier curve with modified parameter t

Part 2: Bezier surfaces with separable 1D de Casteljau

Next, I applied de Casteljau’s algorithm to Bezier surfaces. Instead of looking at n control points, a surface is defined by and nxn grid of control points, with curves going along the u or v direction. We move along the curves in the u direction and the v direction, both of which span from 0 to 1. A Bezier surface can be computed as a “sum of Bezier curves”.

More specifically, for nxn control points, each nx1 control point Pi in u defines a Bezier curve. These points, Pi, are found using the recursive step from part 1 at the parameter u. The corresponding points on the n Bezier curves define n control points for a “moving curve” in v. Again, using the recursive step from part 1, I evaluated the final, single point { on the Bezier curve at the parameter v. This point P lies on the Bezier surface at the given parameter u and v.

Here is an output: a teapot, with its surface rendered using de Casteljau’s algorithm:

SECTION II: TRIANGLE MESHES AND HALF-EDGE DATA STRUCTURE

In this next section, I worked extensively with the half-edge data structure to represent surfaces using triangle meshes. Triangle meshes are easier to render than Bezier surfaces.

Part 3: Area-Weighted Vertex Normals

I implemented area-weighted normal vectors at vertices to provide better shading for smooth surfaces (rather than flat shading). Given a vertex, I used its half-edge to iterate through faces incident to the vertex and weighted its normal by its area. Finally, I normalized the sum of all area-weighted normals, returning a unit vector (using the unit() function). I computed a given triangle’s normal vector by computing the cross product of 2 edges of the triangle.

Below is the teapot with and without vertex normals:

without vertex normals	with vertex normals

Part 4: Edge Flip

Next, I implemented a flip: a local remeshing operation on an edge.

Given an EdgeIter e0 to flip, I had to reassign its twin, next half-edge, vertex, edge, and face. This ended up being quite involved; I first retrieved all half-edges and their twins (for a total of 9 edges, including the given one), all 4 triangle edges, all 4 vertices, and the 2 triangle faces, from e0 and its neighbors. Next, I had to reassign the neighbors for all 9 half-edges, the half-edges corresponding to the edges and vertices, and the half-edges corresponding to the new faces, as appropriate for flipping. I dealt with quite a few bugs in the beginning, because I initially did not account for twin half-edges. I was able to finally come to the correct solution after a few diagram sketches.

Below is the teapot mesh before and after a few edge flips:

before flips	after flips

Part 5: Edge Split

The next local remeshing operation I implemented was an edge split. Splitting an edge inserts a new vertex at its midpoint and yields 4 triangles.

The splitting operation was similar to flipping but required reassigning old half-edge elements and creating new half-edges, vertices, edges, and faces. I first retrieved all half-edges and their twins (for a total of 9 edges, including the given one), all 4 triangle edges, all 4 vertices, and the 2 triangle faces, from e0 and its neighbors. Then I created 6 new half edges (for a total of 15), 3 new edges (total 7), 2 new faces (total 4), and 1 new vertex (total 5). Next, I reassigned all elements to their appropriate half-edge and updated their isNew field when necessary. I defined the vertex as the midpoint between the appropriate vertices. Fortunately, programming the flip operation prepared me well for this part and I did not run into any bugs.

Below are outputs from performing edge splits on the teapot:

before	after edge splits	after edge splits + flips

Part 6: Loop Subdivision for Mesh Upsampling

Finally, I implemented loop subdivision for upsampling. This algorithm is used to convert a coarse polygon mesh into a higher-resolution one. In a loop, I performed the following steps:

1. 4-1 subdivision: subdivides the triangle in the mesh into 4 by connecting midpoints. To do this, I first performed splits on existing edges, then flipped any new edge connecting an old vertex to a new vertex.

2. Vertex position updates as a weighted average of neighboring vertex positions, using the following logic for newly added vertices versus existing vertices:

Position of new vertex created when splitting edge AB: 3/8 * (A + B) + 1/8 * (C + D)

Updated position of old vertex: (1 - n * u) * original_position + u * original_neighbor_position_sum where original_position is the original position of the old vertes and original_neighbor_sum is the sum of all original positions of neighboring vertices.

I implemented this algorithm using the following steps: 1. Computed vertex positions using the original mesh, 2. 4-1 subdivision, 3. Updated vertex positions using already computed values.

The only issue I ran into was determining which edges to flip, until I realized I could use xor to make sure only one of 2 vertices was new.

Below is an animation of the teapot after 3 iterations of loop subdivision. This yielded a smoother, rounder mesh with a significantly higher resolution.

Upsampling smoothed out corners and edges and caused asymmetry. This effect is even more noticeable when looking at the following cube:

Turns out, we can reduce the effects of smoothening and asymmetry by splitting interior edges. To keep the cube more symmetrical, I split the interior edges of each face. Having more than 1 edge per face helps better preserve symmetry. The following is a pre-split cube, upsampled 3 times.

CONCLUSION

This project offered me incredible insight into the world of computer graphics and geometric modeling. And yet again, I got to see the power of triangles. This was overall a very enjoyable project and I learned a lot in the process!