Half-Edge Data Structure
Halfedge data structure is an edge centered data structure to store polygon mesh.
The key idea is to split every edge into two half edges. Halfedge act as “glue” between mesh elements, and each vertex and edge face points to just one of its halfedges.
Halfedge makes mesh traversal easy since we can use “twin” and “next” pointers to move around edges, and use “vertex,” “edge,” and “face” pointers to grab elements.
For example, to visit all vertices of a triangle, we can do the following:
To visit all neighbors of a vertex, we can do the following:
Halfedge Connectivity is Always Manifold
To make a halfedge data structure valid, it must satisfy some “common-sense” conditions:
this->twin->twin == this
this->twin != this
- Every halfedge is someone’s “next”
Those three conditions also guarantee that a polygon mesh is manifold. Since
- keep following “next,” and we get faces
- following “twin” and we get edges
- keep following “next→twin” and we get vertices
Alternatives to Halfedge
- Many very similar data structures
- Each stores local neighborhood information
- Similar tradeoffs relative to simple polygon list
- Cons: additional storage, incoherent memory access
- Pros: better access time for individual elements, intuitive traversal of local neighborhoods