# Half-Edge Data Structures

Jerry Yin and Jeffrey Goh
Dec. 10, 2019

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.

\begin{aligned} v_1 &= (1,4) \qquad v_2 = (3,4) \qquad v_3 = (0,2) \qquad v_4 = (2, 2) \\ v_5 &= (4, 2) \qquad v_6 = (1, 0) \qquad v_7 = (3, 0) \end{aligned} $V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}$ $F = \{(v_1, v_3, v_4), (v_1, v_4, v_2), (v_2, v_4, v_5), (v_3, v_6, v_4), (v_4, v_6, v_7), (v_4, v_7, v_5)\}$

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.

Visualization of a half-edge h, along with its twin, next, and previous half-edges. h also stores references to its origin vertex and incident face.

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.

#### Records

VertexCoordinateIncident edge
v1(1, 4, 0)e0
v2(3, 4, 0)e5
v3(0, 2, 0)e1
v4(2, 2, 0)e2
v5(4, 2, 0)e8
v6(1, 0, 0)e10
v7(3, 0, 0)e14
FaceHalf-edge
f0e0
f1e3
f2e6
f3e9
f4e12
f5e15
Half-edgeOriginTwinIncident faceNextPrev
e0v1e18f0e1e2
e1v3e11f0e2e0
e2v4e3f0e0e1
e3v1e2f1e4e5
e4v4e6f1e5e3
e5v2e19f1e3e4
e6v2e4f2e7e8
e7v4e17f2e8e6
e8v5e20f2e6e7
e9v3e21f3e10e11
e10v6e12f3e11e9
e11v4e1f3e9e10
e12v4e10f4e13e14
e13v6e22f4e14e12
e14v7e15f4e12e13
e15v4e14f5e16e17
e16v7e23f5e17e15
e17v5e7f5e15e16
e18v3e0e19e21
e19v1e5e20e18
e20v2e8e23e19
e21v6e9e18e22
e22v7e13e21e23
e23v5e16e22e20

## 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.

Illustration of the EdgeFlip algorithm.

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 e3 or e2 in the below mesh, but let’s say e3).

#### Records

VertexCoordinateIncident edge
v1(0, 1, 0)e0
v2(1, 1, 0)e5
v3(0, 0, 0)e1
v4(1, 0, 0)e2
FaceHalf-edge
f0e0
f1e3
Half-edgeOriginTwinIncident faceNextPrev
e0v1e6f0e1e2
e1v3e7f0e2e0
e2v4e3f0e0e1
e3v1e2f1e4e5
e4v4e8f1e5e3
e5v2e9f1e3e4
e6v3e0e9e7
e7v4e1e6e8
e8v2e4e7e9
e9v1e5e8e6

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 (e3 and e2 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.

#### Records

VertexCoordinateIncident edge
v1(0, 1, 0)e0
v2(1, 1, 0)e5
v3(0, 0, 0)e1
v4(1, 0, 0)e4
FaceHalf-edge
f0e1
f1e5
Half-edgeOriginTwinIncident faceNextPrev
e0v1e6f0e1e2
e1v3e7f0e2e0
e2v4e3f0e0e1
e3v1e2f1e4e5
e4v4e8f1e5e3
e5v2e9f1e3e4
e6v3e0e9e7
e7v4e1e6e8
e8v2e4e7e9
e9v1e5e8e6

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

#### Records

VertexCoordinateIncident edge
v1(0, 1, 0)e0
v2(1, 1, 0)e5
v3(0, 0, 0)e1
v4(1, 0, 0)e4
FaceHalf-edge
f0e1
f1e5
Half-edgeOriginTwinIncident faceNextPrev
e0v1e6f0e1e2
e1v3e7f0e2e0
e2v2e3f0e1e4
e3v3e2f1e5e0
e4v4e8f1e5e3
e5v2e9f1e3e4
e6v3e0e9e7
e7v4e1e6e8
e8v2e4e7e9
e9v1e5e8e6

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

#### Records

VertexCoordinateIncident edge
v1(0, 1, 0)e0
v2(1, 1, 0)e5
v3(0, 0, 0)e1
v4(1, 0, 0)e4
FaceHalf-edge
f0e1
f1e5
Half-edgeOriginTwinIncident faceNextPrev
e0v1e6f0e3e5
e1v3e7f0e4e2
e2v2e3f0e1e4
e3v3e2f1e5e0
e4v4e8f1e2e1
e5v2e9f1e0e3
e6v3e0e9e7
e7v4e1e6e8
e8v2e4e7e9
e9v1e5e8e6