The Half-edge Data Structure

For simple mesh operations (e.g., loading a mesh from disk and drawing it on screen), one can use a very simple mesh data structure like polygon soup, i.e., just a list of vertices together with a list of polygons connecting them. For many geometry processing tasks, however, this simple representation is no longer sufficient (or leads to unnecessarily bad asymptotic performance). In this assignment, we use the halfedge data structure, which provides a good tradeoff between simplicity and sophistication.

The basic idea behind the halfedge data structure is that, in addition to the usual vertices, edges, and faces that make up a polygon mesh, we also have an entity called a halfedge that acts like a "glue" connecting the different elements. It is this glue that allows us to easily navigate the mesh.

In particular, there are two halfedges associated with each edge (see picture above). For an edge connecting two vertices i and j, one of its halfedges points from i to j; the other points from j to i. In other words, we say that the two halfedges are oppositely oriented. One of the halfedges is associated with the face to the "left" of the edge; the other is associated with the face to the "right." Each halfedge knows about the opposite halfedge, which we call its twin. It also knows about the next halfedge around its face, as well as its associated edge, face, and vertex.

In contrast, the primitive mesh elements (vertices, edges, and faces) know about only one of their halfedges. In particular: a vertex knows about one of its "outgoing" halfedges; an edge knows about one of its two halfedges; and a face knows about one of the halfedges circulating around its interior.

In summary, we have the following relationships:

Mesh element Pointers
Vertex one halfedge
Edge one halfedge
Face one halfedge
Halfedge twin, next, vertex, edge, face

This list emphasizes that it is really the halfedges that connect everything up. An easy example is if we want to visit all the vertices of a given face. We can start at the face's halfedge, and follow the "next" pointer until we're back at the beginning. A more interesting example is visiting all the vertices adjacent to a given vertex v. We can start by getting its outgoing halfedge, then its twin, then its next halfedge; this final halfedge will also point out of vertex v, but it will point toward a different vertex than the first halfedge. By repeating this process, we can visit all the neighboring vertices:

(Can you easily do this traversal with a polygon soup? Why or why not?) In some sense, a halfedge mesh is kind of like a linked list on steroids. For instance, the halfedges around a given face (connected by next pointers) form a sort of "cyclic" linked list, where the tail points back to the head.

An interesting consequence of the halfedge representation is that any valid halfedge mesh must be manifold and orientable. In this assignment, we will therefore only provide manifold, oriented meshes as input (in fact, the parser will complain if the input does not satisfy these criteria).

The HalfedgeMesh Class

Although the halfedge data structure is designed to support general polygon meshes, you can assume that all meshes used in this assignment will be made of triangles only. You can also assume that the input mesh is manifold, possibly with boundary, i.e., that each edge is contained in at most two polygons (or one polygon if it is on the boundary), and each vertex is connected to a single "fan" of triangles. Note that the atomic remeshing operations (flip and split) must preserve the manifold property of the mesh. If you implement flip and split correctly and map all the pointers to the right places, you do not need to worry about this. However, if you don't, the mesh will no longer be valid and the traversal code that renders the onscreen view will segfault and crash when looping over the data structure's pointers, as you've probably experienced when working with linked lists or graph structures in your previous classes!

For this assignment, we've already provided a C++ implementation of the halfedge data structure. Although the detailed implementation might appear a bit intimidating at first (especially if you haven't had much experience with C++), the basic interface you'll need for this assignment is not much different from the abstract description given above. For instance, suppose we have a face f and want to print out the positions of all its vertices. We would write a routine like this:

void printVertexPositions(FaceCIter f) {
  HalfEdgeCIter h = f->halfedge(); // get the first halfedge of the face
  do {
    VertexCIter v = h->vertex();   // get the vertex of the current halfedge
    cout << v->position << endl;   // print the vertex position
    h = h->next();                 // move to the next halfedge around the face
  } while (h != f->halfedge());    // keep going until we're back at the beginning
}

(For an explanation of the low-level details (e.g., why do we call it a FaceCIter rather than just a Face?), see the inline documentation in the code, or the corresponding Doxygen documentation.) Similarly, to print out the positions of all the neighbors of a given vertex we could write a routine like this:

void printNeighborPositions(VertexCIter v) {
  HalfEdgeCIter h = v->halfedge();    // get one of the outgoing halfedges of the vertex
  do {
    HalfEdgeCIter h_twin = h->twin(); // get the vertex of the current halfedge
    VertexCIter v = h_twin->vertex(); // vertex is 'source' of the half edge.
                                      // so h->vertex() is v,
                                      // whereas h_twin->vertex() is the neighbor vertex.
    cout << v->position << endl;      // print the vertex position
    h = h_twin->next();               // move to the next outgoing halfedge of the vertex.
  } while(h != v->halfedge());        // keep going until we're back at the beginning
}

To iterate over all the vertices in a halfedge mesh, we could write a loop like this:

for(VertexCIter v = mesh.verticesBegin(); v != mesh.verticesEnd(); v++) {
  printNeighborPositions(v); // do something interesting here
}

Internally, the lists of vertices, edges, faces, and halfedges are stored as linked lists, which allows us to easily add or delete elements to our mesh. For instance, to add a new vertex we can write

VertexIter v = mesh.newVertex();

Likewise, to delete a vertex we can write

mesh.deleteVertex(v);

Note, however, that one should be very, very careful when adding or deleting mesh elements. New mesh elements must be properly linked to the mesh -- for instance, this new vertex must be pointed to one of its associated halfedges by writing something like

v->halfedge() = h;

Likewise, if we delete a mesh element, we must be certain that no existing elements still point to it; the halfedge data structure does not take care of these relationships for you automatically. In fact, that is exactly the point of this assignment: to get some practice directly manipulating the halfedge data structure. Being able to perform these low-level manipulations will enable you to write useful and interesting mesh code far beyond the basic operations in this assignment.

Finally, the boundary of the surface (e.g., the ankles and waist of a pair of pants) requires special care in our halfedge implementation. At first glance, it would seem that the routine printNeighborPositions() above might break if the vertex v is on the boundary, because at some point we worry that we have no twin() element to visit. Fortunately, our implementation has been designed to avoid this kind of catastrophe. In particular, rather than having an actual hole in the mesh, we create a "virtual" boundary face whose edges are all the edges of the boundary loop. This way, we can iterate over boundary elements just like any other mesh element. If we ever need to check whether an element is on the boundary, we have the methods.

Vertex::isBoundary()
Edge::isBoundary()
Face::isBoundary()
Halfedge::isBoundary()

These methods return true if and only if the element is contained in the domain boundary. Additionally, we store an explicit list of boundary faces, which we can iterate over like any other type of mesh element:

for(FaceCIter b = mesh.boundariesBegin(); b != mesh.boundariesEnd(); b++) {
  // do something interesting with this boundary loop
}

These virtual faces are not stored in the usual face list, i.e., they will not show up when iterating over faces.

Please refer to the inline comments for further details.

Iterating over mesh elements

When dealing with a dynamic data structure like a halfedge mesh, one must think very carefully about the order in which mesh elements are processed -- it is quite easy to delete an element at one point in the code, and try to access it later (usually resulting in a crash!). For instance, suppose we write a loop like this:

// iterate over all edges in the mesh
for (EdgeIter e = mesh.edgesBegin(); e != mesh.edgesEnd(); e++) {
  if (some condition is met) {
    mesh.splitEdge(e);
  }
}

Sounds pretty simple, but this routine could very easily crash! Do you see why? The reason is fairly subtle: we are iterating over edges in the mesh by incrementing the iterator e (e++). But since the routine HalfedgeMesh::splitEdge() is allowed to create and delete mesh elements, it might deallocate this edge before we get to increment this iterator to the next edge! To be safe, we could instead write our loop like this:

// iterate over all edges in the mesh
EdgeIter e = mesh.edgesBegin();
while (e != mesh.edgesEnd()) {

  // get the next edge NOW!
  EdgeIter nextEdge = e;
  nextEdge++;

  // now, even if splitting the edge deletes it...
  if (some condition is met) {
    mesh.splitEdge(e);
  }

  // ...we still have a valid reference to the next edge.
  e = nextEdge;
}

Note that this loop is just one example -- in general, you should think about which elements might be affected by a local mesh operation when writing your loops. Likewise, you can make life easier on yourself by making sure that your atomic edge operations provide certain guarantees. For instance, if your implementation of HalfedgeMesh::flipEdge() guarantees that no edges will be created or destroyed (as it should), then you can safely do edge flips inside a loop without worrying about these kinds of side effects.

Debugging aid

We've left four debug functions near the bottom of halfEdgeMesh.h as members of the HalfEdgeMesh class: they are all called check_for. Given an iterator to one of the four types of mesh object, the function looks through every object in the mesh and finds the ones that point to the provided object. Whenever it finds a match, it prints a message with the address of the pointing object. This could be useful when you want to confirm that an object is pointed to by the right number of other objects, or that those pointing objects have the expected addresses. (This will make more sense after you start Parts 3 and 4.)

Resources and Notes

In addition to the writeup, these supplemental notes may be useful in guiding your implementation. (Note that you do not have to handle surfaces with boundary, unless you are shooting for extra credit!)

Another tutorial on the halfedge data structure.

A different implementation than the one used in our assignment, but discusses some of the software design challenges associated with building a halfedge data structure.