Half-Edge Data Structure

2 min read•1 page

The Half-Edge Data Structure (Doubly Connected Edge List / DCEL) splits each manifold edge into two oppositely directed half-edges. This enables constant-time $O(1)$ adjacency navigation across faces, edges, and vertex star rings.

HalfEdge Structure:

1. origin: The vertex this directed arrow originates from. 2. pair: The opposite half-edge on the neighboring face. 3. next / prev: Cycle counter-clockwise around the bounded polygon face. 4. face: The polygon face to the left of the half-edge.

python

1class HalfEdge:
2    def __init__(self, origin_vertex):
3        self.origin = origin_vertex # Vertex where the directed half-edge begins
4        self.pair = None            # Oppositely directed half-edge on adjacent face
5        self.next = None            # Next half-edge around current face (counter-clockwise)
6        self.prev = None            # Previous half-edge around current face
7        self.face = None            # Face bounded by this half-edge
8
9class HalfEdgeMesh:
10    def __init__(self):
11        self.vertices = []
12        self.half_edges = []
13        self.faces = []
14
15    def edge_loop(self, start_he):
16        """Traverse all half-edges bounding a face in O(deg(face)) time."""
17        curr = start_he
18        loop = []
19        while True:
20            loop.append(curr)
21            curr = curr.next
22            if curr == start_he:
23                break
24        return loop

Cycle Face Edge

0.00

2 min read•1 page

A Vertex Circulator queries the 1-ring neighborhood of a vertex without searching the entire mesh. By repeatedly stepping h ← h.prev.pair, it orbits around the center hub in O(k) time proportional to vertex valence.

One-Ring Circulator:

1. Valence Calculation: Number of neighboring vertices incident to a vertex hub. 2. Star Orbit: Moving from edge to edge around a shared vertex. 3. Local Laplacian: The 1-ring vertices define the neighborhood for smoothing and curvature estimation.

python

1def one_ring_neighbors(vertex):
2    """Yield all adjacent vertices around a 1-ring star in counter-clockwise order."""
3    curr_he = vertex.half_edge
4    while True:
5        yield curr_he.pair.origin # Opposite vertex of the outgoing edge
6        # Advance circulator: swing to next incident edge via twin and next
7        curr_he = curr_he.prev.pair
8        if curr_he == vertex.half_edge:
9            break
10
11def vertex_valence(vertex):
12    """Compute number of edges connected to vertex."""
13    return sum(1 for _ in one_ring_neighbors(vertex))

Orbit Step (1-Ring)

0.00