IV. HalfEdge Data Structure (Eastman, 1982)

"Doubly-Connected 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
1. Vertex and end of directed edge
2. Edge is obvious
3. Face to left of edge
4. 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
1. Same Edge
2. Opposite Vertex
3. Opposite Face
4. HE->Sym->Sym = HE
• Next points to HalfEdge Counter-Clockwise around Face on left
1. Same Face
2. CCW Vertex around Face on left
3. CCW Edge around Face on left
4. HE->Next->Face = HE->Face
5. 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 re-visit queries later