Mesh Topology & Decimation

2 min read•1 page

To edit mesh topology efficiently, we need a structure that allows local traversals. The Half-Edge structure splits every edge into two directed halves pointing in opposite directions, linking vertices, faces, and edges together.

Connectivity Links:

1. Twin Reference: Links opposite half-edges, allowing traversal between adjacent faces. 2. Next Reference: Links to the next half-edge in the clockwise/counter-clockwise face loop. 3. Origin Reference: Identifies the starting vertex of the half-edge.

python

1class HalfEdge:
2    def __init__(self):
3        self.origin = None    # Vertex at start of half-edge
4        self.twin = None      # Opposite half-edge sharing same edge
5        self.next = None      # Next half-edge in face boundary loop
6        self.face = None      # Face this half-edge bounds
7
8class Vertex:
9    def __init__(self, pos):
10        self.position = pos   # (x, y, z) coordinate
11        self.half_edge = None # Outgoing half-edge reference

Highlight (0=Base Mesh, 1=Twin Half-Edges, 2=Next/Prev Loop)

0.00

2 min read•1 page

Mesh simplification algorithms reduce polygon counts by applying local topological operations. The most fundamental of these is the Edge Collapse, which merges two vertices into one.

Local Operations:

1. Edge Collapse: Merges two vertices, deleting one edge and its two adjacent faces. 2. Edge Split: Inserts a vertex in the middle of an edge, splitting adjacent triangles into four. 3. Edge Flip: Re-routes a shared edge between two triangles to the opposite vertices.

python

1def collapse_edge(mesh, half_edge):
2    v0 = half_edge.origin
3    v1 = half_edge.twin.origin
4
5    # 1. Update outgoing/incoming pointers around v1 to v0
6    for edge in incoming_edges(v1):
7        edge.target = v0
8
9    # 2. Remove the collapsed edge and its twin
10    # 3. Remove the two adjacent faces that become degenerate
11    remove_vertex(mesh, v1)
12    remove_edge(mesh, half_edge)
13    remove_face(mesh, half_edge.face)
14    remove_face(mesh, half_edge.twin.face)

Mesh Operation