Half-Edge Data Structures

We can represent discrete surfaces as polygon meshes. Polygon meshes can be thought of as graphs (which have vertices and edges between vertices) plus a list of faces, where a face is a cycle of edges.

Below, we specify a mesh as a list of vertices and a list of faces, where each face is specified as a cycle of vertices. The edges of the mesh are implied—edges connect adjacent vertices of a face.

The face-list representation is popular for on-disk storage due to its lack of redundancy, however it is difficult to write algorithms that operate directly on such a representation. For example, to determine whether or not $v_6$ and $v_3$ are connected, we must iterate through the face list until we find (or fail to find) the edge we are looking for.

A popular data structure which can answer such queries in constant time is the half-edge data structure. In a half-edge data structure, we explicitly store the edges of the mesh by representing each edge with a pair of directed half-edge twins, with each of the two half-edges twins pointing in opposite directions. A half-edge stores a reference to its twin, as well as references to the previous and next half-edges along the same face or hole. A vertex stores its position and a reference to an arbitrary half-edge that originates from that vertex, and a face stores an arbitrary half-edge belonging to that face. A half-edge data structure stores arrays of vertex, face, and half-edge records.

For representing boundary edges (edges adjacent to a hole), we have two options. We can either represent boundary edges with a single half-edge whose twin pointer is null, or we can represent boundary edges as a pair of half-edges, with the half-edge adjacent to the hole having a null face pointer. It turns out the latter design choice results in much simpler code, since we will soon see that getting a half-edge’s twin is a far more common operation than getting a half-edge’s face, and being able to simply assume that we have a non-null twin results in far fewer special cases.

Below, we show the half-edge diagram and records table for a more complex mesh. The mesh vertices and connectivity can be edited in the editor.

Iterating around a face

Sometimes we need to traverse a face to get all of its vertices or half-edges. For example, if we wish to compute the centroid of a face, we must find the positions of the vertices of that face.

In code, given the face f, this will look something like this:

start_he = f.halfedge
he = start_he
do {
    # do something useful

    he = he.next
} while he != start_he

Note that we use a do-while loop instead of a while loop, since we want to check the condition at the end of the loop iteration. At the start of the first iteration, he == start_he, so if we checked the condition at the start of the loop, our loop wouldn’t run for any iterations.

To traverse the face in the opposite direction, one can simply replace he.next with he.prev.

Iterating around a vertex

In the last section, we described how to construct a face iterator. Another useful iterator is the vertex ring iterator. Often, we want to iterate around the vertex ring (also known as a vertex umbrella) around a vertex. More specifically, we want to iterate through all the half-edges with a given vertex as its origin.

In the next two sections we will assume a counter-clockwise winding order for the faces (which is the default in OpenGL).

Counter-clockwise traversal

In code, given the vertex v, iterating through all the half-edges going out of v in counter-clockwise order looks like this:

start_he = v.halfedge
he = start_he
do {
    # do something useful

    he = he.prev.twin
} while he != start_he

Note that our code still works even if there are boundary half-edges or non-triangular faces.

Clockwise traversal

Traversing the vertex ring in clockwise order to very similar to traversing the ring in counter-clockwise order, except that we replace he = he.prev.twin with he = he.twin.next.

Modifying a half-edge data structure

In the previous section, we discussed how to iterate over a face and over a vertex ring. Modifying a half-edge data structure is more tricky, because it can be easy for references to become inconsistent if the records are not modified properly.

As an exercise, we will walk through how to implement the EdgeFlip algorithm, which, given a half-edge in the middle of two triangle faces, flips the orientation of the half-edge and its twin.

We will show the records table at each step of the algorithm.

We begin with our input half-edge highlighted (either e₃ or e₂ in the below mesh, but let’s say e₃).

We first get references to all affected half-edges, since traversing the mesh whilst it is in an inconsistent state will be difficult.

def FlipEdge(HalfEdge e):
    e5 = e.prev
    e4 = e.next
    twin = e.twin
    e1 = twin.prev
    e0 = twin.next

Next, we make sure there’s no face or vertex references to e or twin (e₃ and e₂ in the diagram), which will we recycle in the process of performing the edge flip.

    for he in {e0, e1, e4, e5}:
        he.origin.halfedge = &he
    e1.face.halfedge = &e1
    e5.face.halfedge = &e5

These operations are safe to do since the choice of representative half-edge is arbitrary; the mesh is still in a consistent state. The affected cells are coloured light blue, although not all cells change to values different from their old values.

Next we recycle e and twin. We will (arbitrarily) have e be the top diagonal half-edge in the diagram, and twin be its twin. We can fill in the members of e and twin according to the below diagram. After this, our data structure will become inconsistent. We outline inconsistent cells in red.

    e.next = &e5
    e.prev = &e0
    e.origin = e1.origin
    e.face = e5.face
    twin.next = &e1
    twin.prev = &e4
    twin.origin = e5.origin
    twin.face = e1.face

We update affected next and prev references. Again, we can reference the diagram to fill in these values.

    e0.next = &e
    e1.next = &e4
    e4.next = &twin
    e5.next = &e0
    e0.prev = &e5
    e1.prev = &twin
    e4.prev = &e1
    e5.prev = &e