halfedge

The half-edge data structure, also known as the half-edge mesh, is a boundary representation for polygonal meshes used in computer graphics and computational geometry. In this structure, every edge of the mesh is split into two directed half-edges that run in opposite directions. A half-edge contains a reference to its origin vertex, its twin half-edge (the other direction along the same edge), the next half-edge around the face, and the face that the half-edge bounds. Edges are implicitly represented by their two oppositely directed half-edges. Each vertex stores a reference to one of its outgoing half-edges, and each face stores a reference to one of its bounding half-edges.

The arrangement enables efficient traversal and adjacency queries. By following the next pointers, one can walk around a face; following twin pointers connects neighboring faces via their shared edge; the origin of a half-edge identifies its vertex. This organization supports local topology operations and queries such as listing all vertices around a vertex, all edges around a face, or locating an incident element in constant time.

Half-edge meshes are widely used for dynamic editing of polygonal meshes, including operations such as edge splits, edge collapses, and edge flips, with updates constrained to local regions. They are compact and flexible compared to other boundary representations and are particularly well suited for representing non-manifold edges and complex topology. They underpin many mesh processing algorithms, rendering pipelines, and finite element methods.

While related to other representations, the half-edge model remains a standard tool in computer graphics for robust, efficient mesh connectivity management.