IV. QuadEdge Data Structure (Guibas and Stolfi, 1985)

Consider the Mesh and its Dual Simultaneously


• Vertices and Faces switch roles, we just re-label them
• Edges remain Edges

Now there are eight ways to look at each edge

• Four ways to look at primal edge
• Four ways to look at dual edge
• Bug Demo (reprise)

Relations Between Edges: Edge Algebra

• Elements in Edge Algebra:
1. Each of 8 ways to look at each edge


• Operators in Edge Algebra:
1. Rot: Bug rotates 90 degrees to its right
2. Sym: Bug turns around 180 degrees
3. Flip: Bug flips up-side down
4. Onext: Bug rotates CCW about its origin (either Vertex or Face)


• Some Properties of Flip, Rot, and Onext:
1. e Rot4 = e
2. e Rot2 != e
3. e Flip2 = e
4. e Flip Rot Flip Rot = e
5. e Rot Flip Rot Flip = e
6. e Rot Onext Rot Onext = e
7. e Flip Onext Flip Onext = e


• Properties of Edge Algebra deduced from those above:
1. e Flip-1 = e Flip
2. e Sym = e Rot2
3. e Rot-1 = e Rot3
4. e Rot-1 = e Flip Rot Flip
5. e Onext-1 = e Rot Onext Rot
6. e Onext-1 = e Flip Onext Flip


• Other Useful Definitions:
1. e Lnext = e Rot-1 Onext Rot
2. e Rnext = e Rot Onext Rot-1
3. e Dnext = e Sym Onext Sym-1


• Even More Useful Definitions:
1. e Oprev = e Onext-1 = e Rot Onext Rot
2. e Lprev = e Lnext-1 = e Onext Sym
3. e Rprev = e Rnext-1 = e Sym Onext
4. e Dprev = e Dnext-1 = e Rot-1 Onext Rot-1

NOTE: Every function defined so far can be expressed as a constant number of Rot, Flip, and Onext operations! This is independent of the local topology and the global size and complexity of the mesh.

One QuadEdge Structure per Edge, with 4 Parts

• Pick 4 of the 8 Edge elements on a single side
• Can represent flipped versions with an extra bit
• Each part has 2 pointers, "Data" and "Onext"
• Demo

"Data" Pointer

• Geometric and Attribute Information
• Application Specific
• No Effect on Adjacency Operations

"Onext" Pointer

• Pointer to Onext Edge element
• CCW element around Origin of edge (either a Vertex or a Face)

Four Parts to an Edge -> Four Loops

• Each element is a node in 1 of 4 linked lists
• Loop around Face on both sides of Edge
• Loop around Vertex on both ends of Edge

Duality

• The QuadEdge structure represents both the mesh and its dual simultaneously
• Therefore, computing the dual is easy:

    QuadEdgeMesh::ComputeDual()
    {
    }