Mesh Editing with Halfedges

1 Base Project

For my base project I implemented Loop subdivision. We can perform operations (load, subdivide, display) on the mesh using a command-line interface. The tool can use cglv to display the current state of the mesh.

1.1 OBJ File Parsing

The models come in as .obj files. I implemented a parser for a subset of the OBJ file format.

Below is an (incomplete) input to the parser. The three kinds of items we care about are vertex locations (the vs), normals (ns), and face descriptors (the fs), which indicate the indices of the vertices in the face (and their normals).

v -0.5 -0.5 -0.5

vn 0.0 0.0 1.0

f 1//2 7//2 5//2

1.2 Tesselator

Since Loop subdivision works only on triangles and some of the models I wanted to render use non-triangular faces, I implemented a simple tesselator that splits every (polygonal) face into a bunch of triangles.

Below is an example of a dodecahedron, where the top face (a pentagon) was divided into three triangles.

1.3 Mesh Representation

The base project uses a mesh representation that stores the list of faces and vertices, plus a bunch of adjacency information based on edges.

The Scala code below shows the main fields:

// What are the neighbours of a given vertex?

val vertLinks: Array[mutable.ArrayBuffer[Index]]

// What are the faces incident to the given vertex

val facesIncident: Array[mutable.ArrayBuffer[Index]]

// What are the polygons that neighbour a given polygon?

val polyLinks = mutable.Map[Edge, Seq[Index]]()

1.4 Loop Subdivision

f and v indicate the number of faces (triangles) and vertices, respectively

The "naive" version of Loop subdivision uses the adjacency information above to directly implement the different subdivision masks (obtained from these course notes).

We can see how an icosahedron quickly converges to a sphere (the first mesh looks opaque because the original model did not specify normals):

We can see that both the number of faces and vertices is roughly quadrupled after each iteration.

Unlike the icosahedron, the subdivision of the cube produces a non-symmetric surface:

I also found and subdivided a few more-complicated models, like the Stanford bunny

and a teapot

It was interesting to see that even "complicated" meshes converge pretty quickly, and it’s hard to tell if there’s any improvement from subdivision level 2 onwards.

1.4.1 Normals

I calculated surface normals at each triangle (taking the cross product of the sides in the appropriate order), and then calculated the vertex normals as the area-weighted average of the normal for each face incident to the vertex.

2 Extras

For the extras, I implemented a data structure called the half-edge, which (like the list of faces used in the base project) can represent meshes.

On top of the half-edge mesh, I implemented three local operations on edges: flip, split, and collapse.

I then combined the local operations to implement three global operations: Loop subdivision (as in the base project), downsampling, and re-sampling.

I closely followed the approach in this assignment.

2.1 Halfedge Mesh

The halfedge mesh consists of four lists of components: faces, edges, vertices, and halfedges. The first three are self-explanatory. The last one, the halfedge, is the one that glues all the other components together. In this way, we can store the adjacency information mostly in the halfedge, and don’t need to maintain external maps or arrays like in the adjacency list representation.

Image source: http://462cmu.github.io/asst2_meshedit/

halfedges can only represent orientable manifold meshes. These are meshes where every edge is shared by at most two faces, and the faces surrounding a vertex form a fan (see here).

Creating the halfedge out of a "simpler mesh" (one just containing faces and vertices) is a pain. We have to set up all the pointers carefully, and some meshes just can’t be represented with halfedges.

2.2 Local Operations

Once the halfedge mesh is set up, we gain a lot of flexibility as to how we can traverse the mesh. This is because the halfedge stores a lot of adjacency information that can be combined in different ways.

For example, to visit the edges in a face, we can traverse the next pointer of the face’s halfedge until we’ve circled back. Another more useful operation is to do something to every vertex (or face) adjacent to a specific vertex. This can be achieved by starting at the halfedge for the vertex, and then alternating between the twin and next pointers until we "circle back" to the original halfedge.

Using these primitives I implemented the local (in the sense that they typically affect a constant number of mesh elements) operations below.

2.2.1 Flip

Notice thow the diagonal edge on the front face has been rotated counter-clockwise. Flip doesn’t add or remove mesh elements.

2.2.2 Split

The diagonal edge on the front face has been split in two at its midpoint. Split only adds mesh elements.

2.2.3 Collapse

The diagonal edge has been collapse to its midpoint in the picture above. Collapse only removes mesh elements.

2.3 Upsampling (Loop Subdivision)

Using halfedges, flips, and splits, we can implement Loop subdivision (again). Additionally, I added support for surfaces with boundary edges (edges with only incident face).

For example, see the open cube below:

2.4 Downsampling (Quadric Error Approximation)

Just like collapse is the "dual" of split, we can come up with a global operation that is the counterpart to subdivision. Such downsampling operation collapses edges according to a certain error metric until a target number of faces has been reached.

Together, these two properties allow us to assign an error cost to each mesh edge. We can then put the edges in a priority queue (ordered by cost), and collapse the top N edges, for some choice of N. Once an edge is collapse, the quadric at its endpoints are added to obtain the quadric of the resulting vertex.

The results (when my program doesn’t crash!) look pretty good.

Again the Stanford bunny

BigGuy

and a cow

2.5 Resampling (Isotropic Remeshing)

The idea with remeshing is to improve the "quality" of your mesh for the benefit of subsequent operations. For this extra, I followed section 4 in this paper.

This one I only implemented partially: the code is pretty unstable and often crashes. The results are not very good (but I suspect that it’s probably because of bugs in my code, and not a problem with the original technique):

The first image is a teapot that’s been downsampled, so that we end up with irregular triangles. After resampling, we do get more equilateral triangles, but the shape is not preserved.

3 What I Learned

• Different mesh representations: e.g. list of faces, halfedges.

• How subdivision works and how to implement the Loop scheme.

• How to compose CAGD primitives to create more complex operations: e.g. iterated flip + split = Loop, collapse + priority queue = downsampling.

• Downsampling and error metrics.

• CAGD algorithms are harder to implement than I thought: often the explanation is conceptually simple (e.g. a halfedge can be described in one image) but the implementation is full of little details you have to get right (my implementation of halfedges is 700+ lines of Scala code); any small mistake can mess up the results significantly.

• I’m glad I’m in programming languages and not graphics...

4 References

• Wavefront .obj file. (2018, April 10). Retrieved from https://en.wikipedia.org/wiki/Wavefront_.obj_file

• Schröder, P. (1998). Subdivision for modeling and animation. In ACM SIGGRAPH 1998.

• Assignment 2: MeshEdit. (n.d.). Retrieved from http://462cmu.github.io/asst2_meshedit/

• Garland, M., & Heckbert, P. S. (1998, October). Simplifying surfaces with color and texture using quadric error metrics. In Visualization’98. Proceedings (pp. 263-269). IEEE.

• Garland, M., & Heckbert, P. S. (1997, August). Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques (pp. 209-216). ACM Press/Addison-Wesley Publishing Co..

• Botsch, M., & Kobbelt, L. (2004, July). A remeshing approach to multiresolution modeling. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing (pp. 185-192). ACM.

• For the models

  • The Stanford 3D Scanning Repository. (n.d.). Retrieved from http://graphics.stanford.edu/data/3Dscanrep/

  • Assignment 2: MeshEdit. (n.d.). Retrieved from http://462cmu.github.io/asst2_meshedit/

  • Burkardt, J. (n.d.). OBJ Files A 3D Object Format. Retrieved from http://people.sc.fsu.edu/~jburkardt/data/obj/obj.html