Half-Edge Adjacency and Constant-Time Mesh Traversal

Operations on a mesh are almost never about one triangle. Smoothing needs the one-ring of a vertex, decimation needs the faces around an edge, boundary detection needs to know whether an edge has a second face, and normal averaging needs every face touching a position. A structure that stores triangles as independent triples answers all of these by searching, which is $O(f)$ per query. A structure that stores adjacency explicitly answers them in time independent of mesh size.

The failure of face-indexed storage

Start with the format most files use: an array of vertex positions and an array of index triples. Asked for the neighbours of vertex $v$, the only available procedure scans every triangle and collects those containing $v$. For a mesh with $10^6$ triangles and a vertex with six neighbours, that is $10^6$ index comparisons to answer a question about six. The information needed to avoid the scan is entirely derivable from the mesh, but it is not stored.

The naive fix is to precompute a vertex-to-faces table. Each entry points at the face list for one vertex, and a query becomes a table lookup followed by a walk of the incident faces. This works, and many production structures are exactly this. It costs a variable-length adjacency list per vertex and, critically, it does not link faces to each other: finding the face across a given edge still requires scanning the incident faces of one endpoint to find the one that contains both endpoints.

Two directed halves per edge

The half-edge structure, also called the directed-edge structure, makes adjacency part of the element identity. Each undirected edge is split into two directed halves. A half-edge stores the face on its left, the next half-edge around that face, the opposite half-edge (the twin), and one endpoint, either its origin or its destination. Storing four fields is the minimum; the previous half-edge is either stored as a fifth field or derived by rotating twice when the face is a triangle, since prev(h) is next(next(h)) there. The two endpoint conventions are equally workable as long as every routine agrees, and mixing them silently is a common source of inverted traversals.

Walking the boundary of a face is following next once per corner, three times for a triangle. Walking the faces around a vertex needs an outgoing half-edge $h$, meaning one whose origin is the vertex in question. The twin of $h$ runs back along the same edge, and the next of that twin is again outgoing from the same vertex, in the next face around. Each step is a pointer dereference, and the number of steps equals the degree of the vertex.

struct HalfEdge {
    twin: u32,
    next: u32,
    vertex: u32,   // destination vertex of this half
    face: u32,
}

// Faces around the origin vertex of `start`, which must be an outgoing half-edge.
// With destination storage the origin is recoverable as edges[twin].vertex, so an
// outgoing half-edge from v is any h whose twin's destination is v.
fn faces_around(edges: &[HalfEdge], start: u32) -> Vec<u32> {
    let mut out = Vec::new();
    let mut h = start;
    loop {
        out.push(edges[h as usize].face);
        // twin(h) points back into the origin vertex; its next leaves that vertex again
        h = edges[edges[h as usize].twin as usize].next;
        if h == start { break; }
    }
    out
}

The loop terminates when it returns to the start, which requires the vertex to be interior. At a boundary vertex the rotation does not close; it hits a half-edge whose twin is a sentinel and stops. That asymmetry is the structure’s main implementation annoyance, and the two common responses are to store an invalid index (typically all-ones for an unsigned field) and test for it, or to add explicit boundary half-edges that link around the hole with an invalid face.

Bytes per element and what the pointers buy

For a closed triangle mesh with $v$ vertices, $f = 2v$ faces, and $e = 3v$ edges, there are $2e = 6v$ half-edges. With four 32-bit fields each, that is 24 bytes per half-edge and 144 bytes per vertex, plus 32 bytes per vertex position and 24 bytes of per-face record for the $2v$ faces, one 12-byte triangle record each. Total is about 200 bytes per vertex, against roughly 56 bytes per vertex for the indexed format described in indexed meshes and the vertex cache. The structure costs between three and four times the memory of the rendering format, and in exchange every adjacency query becomes constant time.

That ratio is the entire trade. The indexed format is a transport and rendering format; the half-edge structure is an editing and analysis format. Renderers consume the former, and modelling tools and geometry processing passes use the latter, often converting at the boundary and discarding the adjacency once a pass completes.

The pointer fields also make the structure hostile to bulk operations. Iterating a half-edge mesh in array order jumps around memory, because consecutive half-edges are usually not adjacent in the mesh. Collecting all faces of a vertex touches scattered cache lines, one per face. Compared with a structure that groups a vertex’s incident faces into one contiguous block, the traversal-heavy layout loses on cache behaviour even though it uses fewer bytes per query. Layout choices of this kind also decide what an edge collapse under the quadric error metric has to rewrite when it merges two vertices.

Invariants that must hold, and the checks that catch violations

The structure is only valid if a set of identities hold for every half-edge: twin(twin(h)) == h, next(prev(h)) == h, and around each face the next cycle closes in exactly the face’s vertex count. A fourth identity ties the two directions together: for a half-edge $h$ with destination $v$, twin(h) must have destination equal to the origin of $h$. These four are cheap to verify in linear time and they catch nearly every construction bug, including off-by-one errors in the twin table and faces whose vertex list was truncated.

Construction from an indexed mesh is the delicate step. The usual approach builds a map from ordered vertex pair to half-edge index. For each face, emit three half-edges in order, set next within the face, and look up the reverse pair; if it exists, link the twins, otherwise insert the pair. When an edge is encountered a third time, the map already holds a half-edge whose twin is taken, and the insertion fails. That failure is the correct signal: the input has a non-manifold edge.

Manifoldness is the precondition, not a detail. A half-edge mesh cannot represent an edge shared by three faces, because a half-edge has exactly one twin. Nor can it represent two faces that share only a vertex, because the vertex rotation cannot have two disjoint cycles. Practitioners handle this by splitting vertices: the two fans get separate vertex records with the same position. The split is invisible geometrically and essential structurally, and it is a clean example of the general rule that a data structure encodes its assumptions in its invariants. The same class of problem appears when welding vertices by attribute tuple changes which seams exist.

Alternatives and when they win

Face-vertex adjacency with per-vertex face lists beats the half-edge structure on one axis: it tolerates non-manifold input and needs no twin bookkeeping, so it is the safer choice for importing arbitrary files. It loses the ability to answer “which face is across this edge” without a search, which is exactly what flood-fill-based algorithms need.

The winged-edge structure is the older relative, storing per-edge the four incident edges and two endpoints of each adjoining face. It uses fewer records than half-edge because edges are not duplicated, at the cost of queries that must branch on which endpoint of the edge is under consideration. Half-edge won on simplicity of traversal, which is why it dominates in practice.

Corner tables, or indexed face sets, store per-corner records: one entry per face-corner, each pointing to its vertex and to the adjacent corners. This is the layout of the widely used OpenMesh-style and polygon-mesh libraries’ corner tables, and it handles boundaries and non-manifold configurations more gracefully than a strict twin-based scheme. It is closer in spirit to the indexed format, since a face-corner table is essentially three parallel arrays, and it converts to a rendering buffer without a rebuild.

The choice among them is decided by which query dominates. If the workload is rendering, none of this matters. If the workload is a sequence of passes that each need adjacency once, building and tearing down a half-edge structure per pass is usually worse than keeping a corner table around for the whole pipeline.

Operations that mutate connectivity and what they invalidate

The structure earns its keep during edits, but every edit invalidates part of it. An edge flip replaces the two triangles adjacent to an interior edge with the other two triangles spanning the same four vertices. In half-edge terms it rewires six next pointers and four twin links, and nothing else changes; the vertex records stay, the half-edge count stays, and only the face assignments and the two twins of the flipped edge swap. It is the cheapest topological edit, and it requires that the quadrilateral formed by the four vertices be strictly convex, or the flipped triangles have zero or negative area.

A split inserts elements. Splitting an edge adds one vertex and splits two faces into four, so a closed mesh gains 2 faces, 3 edges, and 1 vertex, which preserves the Euler characteristic: $\Delta v - \Delta e + \Delta f = 1 - 3 + 2 = 0$. Splitting a face by inserting a vertex and joining it to all corners adds 1 vertex, 3 edges, and 2 faces for a triangle, again zero. These are worth checking in an implementation because an off-by-one in the twin relinking typically shows up as an Euler characteristic that drifts by one per operation, which is a far clearer symptom than a corrupted traversal.

Collapse does the reverse and is the operation that most often produces an invalid structure. The link condition is easier to state in half-edge terms than in index terms: an edge may be collapsed only if the two vertices’ rotations share exactly the two opposite vertices of the incident faces. Checking it means walking both rotations, which is constant time in the vertex degree, and it rejects precisely the collapses that would create an edge with three faces or a vertex whose fan splits into two cycles.

The invariant checks listed earlier are worth running after any bulk edit rather than during it, because a single inconsistent twin link makes every traversal from that point onward undefined rather than wrong. A checker that walks all half-edges and verifies the four identities costs one pass and catches the error at the operation that caused it, which is the difference between a debuggable tool and a mysterious mesh corruption three passes later.