Project 2: MeshEdit

CS 184: Computer Graphics and Imaging, Spring 2019

Andrew Campbell, `cs184-adu`

Overview

In this project, I implemented a variety of widely-used techniques for geometric modeling. I began with de Casteljau’s algorithm to draw Bezier curves and surfaces. Then I added support for various half-edge mesh manipulations, and finally loop subdivision. The end result is a tool capable of loading and editing a basic COLLADA mesh file, which is an interchange file format for interactive 3D applications.

This project gave me insight into how we can explicitly model smooth curves, represent 3D objects with polygon meshes, and perform basic operations on meshes. In particular, I learned the power and usefulness of the half-edge data structure for fast mesh operations.

Section I: Bezier Curves and Surfaces

Bézier curves are commonly-used parametric representations of smooth curves in computer graphics. They can be linked together to model smooth and indefinitely scalable surfaces. A Bezier curve of degree $n$ is defined by $n+1$ control points, and is parametrized by $t$ for $0 \leq t \leq 1$ .

Part 1: Bezier curves with 1D de Casteljau subdivision

Beginning with the 1D case, I implemented BezierCurve::evaluateStep to perform one step of de Casteljau’s algorithm, a recursive method to evaluate Bézier curves. The basic idea is as follows: given $n$ points $p_0, \dots, p_n$ , compute a new set of $n-1$ points $p'_0, \dots, p'_{n-1}$ through linear interpolation:

$p'_i = lerp(p_i, p_{i+1}, t)$

where

$lerp(p_i, p_{i+1}, t) = (1-t)p_i + tp_{i+1}.$

We repeat until there is only one point left; the path traced out by this point as $t$ varies defines the Bézier curve.

We illustrate the process below. Beginning with six control points, we recursively apply de Casteljau’s algorithm on each new set of points.

The final point, shown in red, represents the value of the Bezier curve at a particular value of $t$ . The entire completed curve is shown below.

Below we illustrate the behavior of the curve (and intermediate levels of the algorithm) as we move the control points and vary the value of $t$ .

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

We can easily extend the concept of Bézier curves to Bézier surfaces. In this section, we work with chains of cubic Bezier surfaces defined by an array of 4x4 control points. The Bezier surfaces is now a parametric equation of $u$ and $v$ , instead of just $t$ . I implemented the simple method of separable 1D de Casteljau - first perform 1D de Casteljau in $uv$ , then in $v$ . The algorithm is given below.

for each row i:
  q(i, u) := apply de Casteljau's algorithm with parameter u to the i-th row of control points

p(u, v) := apply de Casteljau's algorithm with parameter v to all q(i, u) 
return p(u, v)

Below is a rendering of bez/teapot.bez using this technique.

Section II: Loop Subdivision of General Triangle Meshes

Triangle meshes are a widely-used data format for geometric modeling. The half-edge data structure is a powerful and popular representation of triangle meshes to store mesh entities and their connectivity information.

The halfedge data representation uses the usual concept of vertices, edges, and faces that make up a polygon mesh, as well as a structure called a halfedge that connects the different elements. Traversal of half-edges allows traversal of the mesh network.

Part 3: Average normals for half-edge meshes

In this part, I implemented the Vertex::normal function, which returns the area-weighted average normal vector at a vertex. This allows for more realistic local shading than the default flat shading, since the normal vector can be smoothly interpolated across the face of the triangle.

This task involved looping over the relevant pointers in the halfedges in order to traverse all the faces sharing a central vertex. Below is an illustration I made to aid in the implementation.

For a given face, we calculate two vectors (labeled edge1 and edge2 in the figure above). We then take their cross-product to obtain the normal vector of that face. By averaging and normalizing all neighboring normal vectors, we obtain a better estimate of the normal of the vertex.

The shading before and after area-averaged normal vectors is shown below.

Part 4: Half-edge flip

To allow for basic mesh editing, I implemented a local remeshing operation that “flips” an edge, implemented inside HalfedgeMesh::flipEdge.

The edge flip operation is illustrated below:

It is fairly simple operation, but requires a lot of pointer modifications. To make the process easier, I drew and named all elements needed from the original mesh, then all the elements after the flip operation.

By following this diagram exactly, implementation was straightforward, if not a bit tedious.

Below we see the before/after of applying some edge flips to a mesh.

Part 5: Half-edge split

Next, I implemented a more involved local remeshing operation that “splits” an edge. The operation is illustrated below:

The implementation of this task was similar to that of the edge flip, but involved the allocation of new elements and considerably more pointers to track. Again, I made drawings of the original and modified elements to aid in my implementation.

By following this diagram carefully, I ran into no issues.

Below we see the before/after of applying some edge splits to a mesh.

Below we see the before/after of applying some edge splits and flips to a mesh.

Part 6: Loop subdivision for mesh upsampling

In this task, I utilized the two basic mesh operations previously implemented in order to add support for loop subdivision in MeshResampler::upsample. The idea is analagous to upsampling using interpolation in image processing - we upsample a mesh by splitting each triangle into four and then interpolating the vertex positions as a weighted average of neighboring positions.

The weighting scheme for the new averaged vertex positions is shown below.

That is, the position of old vertices is given by (1 - num_neighbors * u) * original_position + u * neighbor_position_sum where u is as described in the diagram. The position for a newly created vertex v that splits an edge AB connecting vertices A and B and is flanked by opposite vertices C and D across the two faces connected to AB in the original mesh is given by 3/8 * (A + B) + 1/8 * (C + D).

The implementation overview is as follows: compute all new vertex positions as described above and temporarily store them; split every edge in the mesh; flip any edge that connects an old and new vertex; and finally update the new vertex positions.

I had some trouble during implementation related to the isNew member; I realized it was important to mark all current edges/vertices as old prior to performing upsampling, and mark any newly created edge/vertex as new. Doing this improperly led to incorrect vertex position calculations. The process was otherwise fairly smooth.

Below we illustrate successive applications of upsample to a torus mesh.

As we can see, the effect of upsampling is to alleviate blocky silhouettes and chunky features. Sharp edges and corners get smoothed out. Below we show several iterations of upsampling on dae/cube.dae.

The cube becomes asymmetric after repeated subdivision steps because the original mesh had asymmetric edges. Not all corners have the same number of incident edges. By pre-processing the cube to split all diagonal edges across all faces of the cube, we can achieve symmetry, as shown below.

By pre-splitting select edges on the cube before upsampling, we can get interesting effects. The mesh below was created by repeatedly splitting edges incident on the top right vertex. The higher concentration of faces on one corner led to stronger boundaries.