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
nD 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 != nullthis.next != thisthis.next.next != thisthis.next.next.next == this;this.next.next.next.next == this;.nexts to this
gets you back to this.this.twin == null || this.twin.twin == thisthis.twin == null || this.v == this.twin.next.vthis.twin == null || this.twin.v == this.next.vthis.twin != nullTo visit all the half-edges around a face:
use(this)
let he = this.next
while(he != this) {
use(he)
he = he.next
}To visit all the half-edges exiting a non-boundary vertex:
use(this)
let he = this.twin.next
while(he != this) {
useExiting(he)
he = he.twin.next
}To find one half-edge from a list half_edges
representing each edge,
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
}To find one half-edge from a list half_edges
representing each face,
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;
}To flip an edge, merging the two triangles adjacent to the edge into a quad and then re-split them along the other diagonal. This results in no next change in the number of triangles, vertices, or edges.
next field change and the flipped edge also changed their
v fields, but no twin fields changed.
To split an edge, add a new vertex in the center of the edge and six new half-edges to break the original triangles adjacent to the edge into smaller triangles.
vs, 2 have new
twins, and 4 have new nexts.
To refine an edge, add a new vertex in the center of the edge and two new half-edges to break the original edge into two edges. This results in increasing the number of sides on each adjacent face by one: triangles become quads, quads become pentagons, and so on.
There are multiple ways to decide where the old half-edges go and
where the new ones go. The number of changes needed is minimized by
keeping the old half-edges with the same vs and making the
new half-edges their twins.
twin
and next, no other pre-existing edge changes. Note that
this increases the number of vertices per face.
To clip a corner of a non-triangular face, add two new half-edges connecting the vertices on either side of the triangle. This results in a reduction in the number of sides of the face by 1 and the creation of a new triangle.
There are multiple ways to define a corner of a face using
half-edges. This integrates most easily with triangle subdivision if the new
triangle’s edges are this, this.next, and a
new half-edge.
next which bypasses its old next and
next.next. The previous half-edge is not usually stored as
part of a half-edge data structure, but can be found by looping
nexts around the face. Note that this decreases the number
of vertices per face and won’t work if the original face was a triangle.
Triangle subdivision is one of three common subdivision patterns, and can be implemented using the above operations in two different ways.
The first option is to split every edge then flip any new edge that connects a new vertex to an old vertex.
Split an edge
Split another edge
Split all the remaining edges
Identify new edges connecting old and new vertices
Flip new edges connecting old and new vertices
This technique is nice in that it only involves triangles at all steps, meaning it can also be ported to triangle-only data structures in addition to half-edges. It does involve a bit more bookkeeping than the other technique because it requires tracking which edges connect new and old vertices.
The second option is to refine every edge and then clip the corner of every new half-edge, or equivalently the corner of every old vertex.
Refine every edge; now all faces are hexagons, not triangles
Clip the corner of every new half-edge; or equivalently, clip the corner of every old vertex
This technique is nice in that it does not require much bookkeeping. However, its intermediate step is non-triangles so while it works well for half-edge data structures it does not work as well for some other triangle-only data structures.