
IV. HalfEdge Data Structure (Eastman, 1982)"DoublyConnected Edge List"
 Orientable Surfaces Only (no Mobius Strips!)
 Consider only 2 of the 4 ways to look at an edge
 Pick the two on the "outside" of the mesh
 Consistency is the key!
 Local consistency everywhere implies global consistency
 Every edge is represented by two HalfEdge structures
 Each HalfEdge is a "directed edge"
 Each HalfEdge is associated with exactly one vertex, edge, and face
 Vertex and end of directed edge
 Edge is obvious
 Face to left of edge
 Orientation is essential, but can be done consistently!
 Three Pointers: Vertex, Sym, and Next
 Vertex points to Vertex at end of HalfEdge
 Sym points to symmetric HalfEdge
 Same Edge
 Opposite Vertex
 Opposite Face
HE>Sym>Sym = HE
 Next points to HalfEdge CounterClockwise around Face on left
 Same Face
 CCW Vertex around Face on left
 CCW Edge around Face on left
HE>Next>Face = HE>Face
HE>Next>Sym>Vertex = HE>Vertex
 Data
 Geometric Information in Vertices only!
 Attribute Information in Vertices, HalfEdges, and/or Faces
 Topological Information in HalfEdges only!
 What can we do with this?
 Loop around a Face:
HalfEdgeMesh::FaceLoop(HalfEdge *HE) { HalfEdge *loop = HE; do { loop = loop>Next; } while (loop != HE); } Loop around a Vertex:
HalfEdgeMesh::VertexLoop(HalfEdge *HE) { HalfEdge *loop = HE; do { loop = loop>Next>Sym; } while (loop != HE); } Time Complexity
 Time is linear in the amount of information gathered
 Independent of global complexity!
 We will revisit queries later
