gifQuad Edge Data Structure

Overview

The quad-edge data structure, invented by Guibas and Stolfi, was designed to encapsulate the topology of arbitrary dual-manifolds and demonstrate new algorithms for Delauny triangulations. See “Primitives for the Manipulation of General Subdivisions and Computation of Voronoi Diagrams”, ACM Transactions on Graphics, 4(2), April 1985, pp. 74-123.

The quad-edge data structure is useful when constructing geodesic spaceframes because it elegantly encapsulates both Primal and Dual manifolds, and provides a means to navigate between them; however, the overhead of maintaining this data structure is quite high. For each edge in the original surface, there are 4 directed edges – two edges in the Primal manifold and two edges in the Dual manifold.

As an end user, you need not concern yourself with quad-edge internals, however, you will often see the words 'ORG' and 'DEST' printed in the Log, along with their respective ID’s. This page explains why they are there and outlines some quad-edge operations for navigating the manifolds. These operations are hidden from the user but are useful to know.

1. A directed edge, 'e'.

jpg

e.Org() is the vertex at ORG
e.Dest() is the vertex at DEST
e.Left() is the face on the Left of e.
e.Right() is the face on the Right of e.

2. The symmetric edge that points in the opposite direction of 'e' = e.Sym().

jpg

e.Sym().Dest() == e.Org()
e.Sym().Org() == e.Dest()
e.Sym().Right() == e.Left()
e.Sym().Left() == e.Right()

2. The dual edge that points to the face on the left of 'e' = e.Rot().

jpg

e.Rot().Dest() is the vertex at the center of the face e.Left()
e.Rot().Org() is the vertex at the center of the face e.Right()

2. The dual edge that points to the face on the right of 'e' = e.InvRot().

jpg

e.InvRot().Dest() is the Vertex at the center of the Face e.Right()
e.InvRot().Org() is the Vertex at the center of the Face e.Left()

The Quad Edge Record

The diagram below shows a single quad-edge record of four directed edges; note how the quad-edge operators Sym, Rot and InvRot relate to the record entries. Rot moves counter-clockwise and InvRot() moves clockwise.

jpg

The following diagram shows three edges a, b and c, which share vertex v. The second diagram shows the quad-edge representation; note that vertex v is just a ring of outgoing edges.

png

Edge Winding

Edges are ordered counter-clockwise around a given face. When you pick an edge with the mouse, the nearest counter-clockwise edge on the face is chosen. In the diagram below, the mouse is hovering over face a, and its position is marked by the yellow dot; this selects the nearest counter-clockwise edge marked by the yellow arrow.

png

In the following diagram, the mouse has moved over the edge into the adjacent face b, and its position is marked by the red dot; this selects the counter-clockwise symmetric edge marked by the red arrow. The two edges are topologically equivalent but have different IDs in the Log.

png

Dual Formation 2D

The following shows how the voronoi dual is formed from the centers of the delaunay triangulation.

png

e.Rot() will give the edge in the orbit of the green dual face: e.Rot().Left().

png

e.InvRot() will give the edge in the orbit of the green dual face: e.InvRot().Right().

png

Dual Formation 3D

In a convex polyhedron, the dual relationship is such that for each primal vertex there is a dual face, and for each dual vertex there is a primal face. The amount of edges remains the same. The dual vertices are the centers of the primal faces. For example, The Icosahedron and Dodecahedron are duals of each other:

animation

Icosahedron
V = 12, F = 20, E = 30

Dodecahedron
V = 20, F = 12, E = 30

Dual implementation in C++

The following outlines how dual generation was implemented at code level and is for the curious only. My quad-edge classes are based on an original implementation by Guibas and Stolfi, code in Graphics Gems, and GPL code written by Paul Heckbert. You can read about his Quad-Edge Data structure and library here.

The following assumes familiarity with the Quad-Edge data structure.

quad edge duality

The directed primal edges a, b, c, d, e, f share origin P at the center of the figure. The center of each primal triangle forms a new dual vertex so making the hexagonal dual face (shaded grey). The dual edge of e is returned by the quad edge operator e.Rot. The origin of e.Rot is then set to the dual vertex at center of primal face e.Right. Finally, e.Rot.Left is set to the new dual face.

Traversing the grid in terms of a single edge e

In order to grasp the relationship between Primal and Dual in terms of the Quad-Edge operators, consult the following diagram.

jpg 115.8 Kb

Note: there is more than one way to identify an edge. For example, the edge e.OrgNext.Rot is the same as e.Rot.LeftNext and e.InvRot.OrgPrev, etc.