halfedges

Halfedges are a fundamental component of the half-edge data structure used to represent polygonal meshes. An undirected edge is split into two directed halfedges that share the same endpoints but point in opposite directions. Each halfedge typically stores references to its origin vertex, its opposite (twin) halfedge, the next halfedge along the boundary of the face to its left, and the face that lies to that left side. Some variants also include a previous halfedge pointer or an explicit reference to the underlying edge object. The exact set of pointers depends on the particular implementation.

The half-edge structure organizes mesh topology by linking vertices, edges, and faces through these halfedges. To traverse a face, one follows the next pointers around the boundary. To move around a vertex, one uses the pair relationships and the next pointers around incident faces; boundary conditions may use a special boundary halfedge or a null reference to indicate the outer face. In a well-formed mesh, every undirected edge corresponds to two halfedges, except at boundary edges where only one halfedge exists on the inner side.

Uses and benefits include efficient topological queries and local mesh edits. The half-edge data structure supports operations such as edge splits, edge collapses, vertex insertions, and face subdivisions without reconstructing global adjacency information, making it popular in computer graphics, CAD, and finite element analysis. It also preserves embedding information, which is useful for algorithms that rely on the geometric ordering of incident elements.

Limitations include increased implementation complexity and memory overhead compared with simpler representations. Maintaining consistency of multiple pointers during edits requires careful, sometimes intricate, updates to preserve the integrity of the mesh topology.