From CGAFaq

Contents 1 What is the half-edge structure? 1.1 Introduction 1.2 Data structures 1.3 Example usage 1.3.1 Traversing the edges around a vertex 1.3.2 Traversing the edges around a polygon 1.4 Variants 1.5 Invariants 1.6 An example use of invariants

What is the half-edge structure?

Introduction

The half-edge structure, also known as a doubly connected edge list, is a description of the connections between vertices, half-edges, edges and polygons (collectively, elements).

In computer graphics, its most common use is for describing geometric polygon meshes. However, the data structure in itself is just a connectedness description. Many geometric interpretations can be given to it by attaching geometric information to the elements. The most common interpretation is to map vertices to points, half-edges to directed line segments, edges to line segments and polygons to planar polygons. Another interpretation could map the data structure to a sphere: vertices to points, edges to arcs and polygons to spherical polygons.

What makes the half-edge structure interesting is its ability to efficiently answer questions (called 'adjacency queries') such as :

• What edges are connected to this vertex?
• What polygons are connected to this vertex?
• What vertices are connected to this polygon?

In addition, the data structure is compact in storage in that it requires only constant amount of data for each element.

The half-edge structure is able to describe many of the polygon meshes and all of the graphs (this includes multigraphs with loops). It can even describe many mixes of a polygon mesh and a wireframe mesh. A wireframe mesh occurs naturally as an intermediate polygon mesh building phase: first you create a polyline which you then convert to a solid polygon.

There are two important restrictions on the relationships that can be described. While these could be stated without reference to geometry, it is more intuitive to consider them through the first interpretation above in 3d. The restrictions then are:

• No non-orientable surfaces (e.g. Moebius strip).
• No non-manifold surfaces (e.g. two cubes sharing a corner vertex). A closed polygon mesh can't share a vertex with another closed polygon mesh.

The second restriction implies an analogous statement for edges and polygons.

Removing these restrictions requires changes to the data structures. The quad-edge structure is a minimal upgrade to the half-edge structure that enables representation of non-orientable surfaces. The partial entity structure extends the idea of halving edges to halving all elements and handles also non-manifold surfaces.

Data structures

Each element type carries some connectedness information. For vertices, edges and polygons it suffices just to give one (arbitrary) half-edge in which they are connected to. The half-edges are the real source of connectedness information. Other elements can be thought to be merely attached to the half-edges.

For describing the half-edges, consider the first geometric interpretation above in 2d. A half-edge is a directed line segment. It has an origin, which is given by a vertex. It always has a predecessor and a successor, which are again half-edges. The end-point of the line segment is given by the origin of the successor. The successors form a chain which actually is a loop. This is of course a natural consequence of the facts that every half-edge must have a successor and that there are finitely many half-edges. But more importantly these loops correspond to the boundaries of polygons. The predecessors can be used to traverse these loops in the reverse direction.

A half-edge is connected to another half-edge which has the same end-vertices but reversed direction. This another half-edge is called its pair. A half-edge is also connected to a polygon on its left side (when looking along the half-edge from the origin), if there is one. Finally, a half-edge is always connected to exactly one edge.

To say the same in a more compact fashion, here are the element types sketched in C++:

struct VertexData;
struct EdgeData;
struct PolygonData;

struct HalfData
{
    HalfData* next;
    HalfData* previous;
    HalfData* pair;

    VertexData* origin;
    PolygonData* left;
    EdgeData* edge;
};

struct VertexData
{
    HalfData* half;
};

struct EdgeData
{
    HalfData* half;
};

struct PolygonData
{
    HalfData* half;
};

Example usage

The commonly needed operations with a half-edge structure include traversing the edges around a vertex or traversing the edges around a polygon. You can examine how the traversal is done by comparing the code and the image above.

Traversing the edges around a vertex

if (vertex.half != 0)
{
    HalfData* begin = vertex.half;
    HalfData* half = begin;
    do
    {
        // Do something.
        half = half->pair->next;
    }
    while(half != begin);
}

For abstraction, it might be useful to form the following functions:

vertexNext(half) := half->pair->next
vertexPrev(half) := half->previous->pair

Traversing the edges around a polygon

if (polygon.half != 0)
{
    HalfData* begin = polygon.half;
    HalfData* half = begin;
    do
    {
        // Do something.
        half = half->next;
    }
    while(half != begin);
}

The algorithms for adding and removing vertices, edges and polygons are described in the implementation article.

Variants

The half-edge structure has many variants depending on the amount of information used and how it is organized.

Efficiency vs memory

The 'previous' and 'next' fields form a looped doubly-linked list around a polygon. Because the list is looped, it is enough to give only one of these two forming a looped singly-linked list. But now the deduction of the left out field takes linear time (w.r.t the number of polygon vertices).

Generality vs memory

Edges might not be needed leaving the 'edge' field out (there will still be the directed half-edges). Polygons are not needed if the data structure represents a graph. Even vertices can be left out leaving only a set of half-edges with relations between them.

Different data organization

You could use the destination vertex rather than the origin vertex as well as use the right polygon rather than the left polygon. You could store 'vertexNext' and 'vertexPrev' fields instead of the 'next' and 'previous' fields. These two representations are equivalent, as given the first pair, one can easily deduce the second pair and vice versa. Actually, given any two fields of these four, the left out fields can be deduced in constant time. If only one of the fields is given, then one of the left out fields can be deduced in constant time and the other two in linear time. However you choose to organize the data, they will all be equivalent in the expressive power and efficiency. This choice (naturally) does have effect on the form of the algorithms.

Given the equivalence, for the purposes of this FAQ we define half-edges with the origin vertex and its left polygon and choose to store the polygon successor and polygon predecessor.

Invariants

The following function notation will be used to retrieve the fields of the half-edges:

• 
• 
• 
• 
• 
• 

The following work as useful shortcuts:

• 
• 
• 

Let denote a half-edge.

• 1)
• 2)
• 3)
• 4)
• 5)
• 6)
• 7)
• 8)
• 9)
• 10)
• 11)
• 12)
• 13)
• 14)
• 15)

An example use of invariants

Consider removing the 'previous' field from HalfData, how do we deduce it then?

By invariant 6:

Let be such a number that the equation holds. Substitute :

Unwrap one application of out:

Plug the definition of the in:

By invariant 1:

By invariant 12:

By invariant 1:

And there we go. This result is easily turned into code:

HalfData* previous(HalfData* half)
{
    HalfData* current = half;
    HalfData* currentPair = 0;

    do
    {
        currentPair = current.pair;
        current = currentPair.next
    }
    while(current != half);

    return currentPair;
}