1 Data Structure

The half-edge data structure, also sometimes called the doubly-linked edge list data structure, is a special type of linked graph data structure for storing polygonal meshes. It is the simplest of a set of related data structures including the winged edge and the BMesh.

The half-edge data structure only works correctly when storing orientable manifolds, which is sometimes seen as a benefit rather than a limitation in graphics: the most common surface meshes in graphics are representing the boundary between two volumes (such as person and air) and all such boundary surface are orientable manifolds, so this data structure limitation can help prevent or detect some kinds of meshing errors.

The core component of a half-edge data structure is a half-edge, which entirely consists of three pointers: two (twin and next) to other half-edges and one (v) to a vertex. Vertices may be stored in any way you wish: a 3D point, and $n$D point concatenating position with other vertex attributes, an index into attribute arrays, etc.

A half-edge’s next is never null, and walking nexts always results in traveling around a loop consisting of the edges of a single polygonal face in the mesh. Hence, each half-edge belongs to exactly one face, and each $n$-sided face consists of $n$ half-edges. To represent this, half-edges are often draw as if they were slightly inset into their face.

Each edge connects to vertices; its own v and the v of its next half-edge. To represent this, half-edges are often drawn pointing from their v to their next.v.

Each geometric edge in a mesh is either the boundary between two faces or the edge of the mesh itself. Edge-of-mesh half-edges have a null twin; other half-edges have their twin being the half-edge along the same edge belonging to the neighboring face. A half-edge and its twin always point in opposite directions; that is, this.twin.v == this.next.v and this.twin.next.v == this.v. You can make a half-edge-like structure where the opposite-direction criteria doesn’t hold, but doing so prevents many half-edge algorithms from working properly.

Some half-edge data structure sanity checks:

• this.next != null
• this.next != this
• this.next.next != this
• for triangles, this.next.next.next == this;
  for quads this.next.next.next.next == this;
  for $n$-sided faces, adding $n$ .nexts to this gets you back to this.
• this.twin == null || this.twin.twin == this
• this.twin == null || this.v == this.twin.next.v
• this.twin == null || this.twin.v == this.next.v
• for closed meshes (no holes), this.twin != null

2 Query operations

use(this)
let he = this.next
while(he != this) {
    use(he)
    he = he.next
}

use(this)
let he = this.twin.next
while(he != this) {
    useExiting(he)
    he = he.twin.next
}

for(let he of half_edges) he.used = false;
let one_per_edge = []
for(let he of half_edges) {
    if (he.used) continue
    one_per_edge.push(he)
    he.used = true
    he.twin.used = true
}

for(let he of half_edges) he.used = false;
let one_per_face = []
for(let he of half_edges) {
    if (he.used) continue
    one_per_face.push(he)
    he.used = true
    for(let ptr = he.next; ptr != he; ptr+=1) ptr.used = true;
}

3 Modification operations