Mesh Data Structures (Half-Edge)

A character's face in a modern film is a polygon mesh of tens of thousands of vertices, and every frame the rig has to ask questions about neighbours: which faces touch this vertex? (for skinning weights), which edges border this face? (for subdivision), which vertices surround this one? (for smoothing). Those are the queries that subdivision, skinning and mesh editing fire millions of times. Ask them of the wrong data structure and your tool crawls; ask them of a half-edge mesh and each one is a handful of pointer hops.

This page is about how a mesh is stored. We start with the obvious way — a list of vertices and a list of faces — see exactly why it makes adjacency queries slow, then build the half-edge (doubly-connected edge list) structure that makes local traversal O(1).

The naive way: vertices + faces ("polygon soup")

The simplest storage is two arrays. A vertex list holds the positions, (x, y, z) per vertex; a face index list holds, per face, the indices of its corner vertices. This is exactly what an OBJ file or a raw triangle buffer is:

const vertices: [number, number, number][] = [ [0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], ]; // each face lists the vertex indices around it const faces: number[][] = [ [0, 1, 2], // triangle A [0, 2, 3], // triangle B ];

It is compact and perfect for drawing — the GPU wants precisely this. But it stores geometry, not connectivity. Ask "which faces touch vertex 0?" and there is no pointer to follow: you must scan every face and test whether it mentions index 0. That is an O(F) sweep of the whole mesh for one local question — and the one-ring of a vertex is a query deformation code needs constantly. This unindexed pile is affectionately called polygon soup: all the triangles are there, but nothing knows who its neighbours are.

The half-edge idea: split every edge in two

The fix is to store the connectivity explicitly, and the elegant way to do it is the half-edge structure (also called the doubly-connected edge list, or DCEL). The key move: take every edge shared by two faces and split it into two directed half-edges, one for each side, pointing in opposite directions. Each half-edge belongs to exactly one face and runs along one boundary of it.

Each half-edge stores four references: A vertex stores one outgoing half-edge; a face stores one of its half-edges. That is the whole structure. interface HalfEdge { vertex: Vertex; // the vertex this half-edge points to twin: HalfEdge; // opposite half-edge (other side of the edge) next: HalfEdge; // next half-edge around this face face: Face; // the face this half-edge borders } interface Vertex { position: [number, number, number]; halfEdge: HalfEdge; } interface Face { halfEdge: HalfEdge; }

Notice there is no explicit "list of neighbours" anywhere — the neighbours are reachable by following pointers, and because every pointer is O(1), so is every local walk. Some variants also store a prev pointer (handy but derivable by following next around the face).

A picture: the twin pair

Below are two triangles sharing one edge. That shared edge is stored as two half-edges drawn as arrows pointing opposite ways: the upper arrow belongs to face A and runs one direction; its twin belongs to face B and runs the other. Follow either arrow's next and you walk around its own face; jump across via twin and you step onto the neighbour. The arrows are offset slightly off the true edge so you can see both.

This is the whole trick made visible: an undirected edge becomes an oriented boundary segment of each face, and the two segments know about each other through twin. Orientation is consistent — every face is wound the same way (say counter-clockwise seen from outside), so a twin pair always disagrees on direction. That consistency is what makes the traversals below work.

Worked example: the two traversals that matter

1. Walk every edge of a face. Start at any half-edge of the face and keep following next. Because next stays on the same face and cycles, you return to the start after visiting each border exactly once:

function faceHalfEdges(start: HalfEdge): HalfEdge[] { const result: HalfEdge[] = []; let h = start; do { result.push(h); h = h.next; // step to the next edge around this face } while (h !== start); return result; // e.g. 3 half-edges for a triangle }

2. Visit every face around a vertex (its one-ring). This is the query the naive structure could not answer cheaply. Around a vertex you alternate twin then next (or next.twin, depending on your origin convention) to pivot from one incident face to the next, sweeping around the vertex like the spokes of a fan:

// visit each face touching the origin vertex of `start` function facesAroundVertex(start: HalfEdge): Face[] { const faces: Face[] = []; let h = start; do { faces.push(h.face); h = h.twin.next; // twin crosses the edge; next pivots to the neighbouring face } while (h !== start); return faces; }

Each iteration is two pointer hops, and the loop runs once per incident face — so the cost is proportional to the local valence of the vertex (typically 4–6), not to the size of the whole mesh. That O(\text{valence}) one-ring walk is exactly what a subdivision mask, a Laplacian smoothing step, or a skinning-weight computation needs at every vertex.

You could — it is called an adjacency list, and it answers "who are my neighbours?" in O(1) too. But it throws away order and faces. A subdivision or smoothing mask needs the one-ring in rotational order (neighbour after neighbour as you sweep around), and needs to know the faces between them, not just the vertices. The half-edge keeps geometry, topology and orientation in one connected fabric, so it answers face-queries, edge-queries and ordered-vertex-queries all from the same pointers. That is why mesh-editing kernels (OpenMesh, CGAL, Blender's BMesh) are built on half-edge or its cousins rather than a bare adjacency list.

The whole structure rests on an assumption: the mesh is an orientable 2-manifold. That means every edge is shared by at most two faces, and all faces are wound consistently so twin pairs point opposite ways. Break that and the pointers break:

Boundaries are fine — an edge on the mesh border simply has a twin whose face is a special "hole"/null face (or the twin is marked as boundary), so the walk still works. But genuine non-manifold geometry and bad winding must be cleaned first: merge or split the offending edges, and unify the orientation, before you build the half-edge structure.

Cousins: winged-edge and quad-edge

Half-edge is the most common choice, but it has relatives that make the same "store the connectivity" bargain differently:

For animation — deformation, subdivision, editing — half-edge's directed, orientation-carrying edges make the one-ring and face walks branch-free, which is why it dominates in practice.