Module halfedge 

Halfedge surface mesh: O(1) adjacency and in-place connectivity edits.

Why this exists

EdgeAdjacency answers “which triangles meet along this edge” over a TriMesh that stays the owner of the data, and every consumer that reads it writes a new mesh. Remeshing, hole filling, subdivision, geodesics and parameterisation instead rewrite connectivity in place, many times, and walk the one-ring of a vertex in its cyclic order. That needs a persistent structure whose links survive each edit: this is it.

Layout

The layout follows CGAL’s Surface_mesh: index-based arrays rather than pointers. Each edge e owns the two halfedges 2e and 2e + 1, so HalfedgeMesh::opposite is h ^ 1 and stores nothing. Each halfedge stores its next, prev, target vertex and incident face; a vertex stores one outgoing halfedge and a face one halfedge of its loop. Every navigation query is one array read.

A halfedge with no face is a boundary halfedge. Boundary halfedges are linked by next/prev into loops, one per hole, so a hole is walked the same way as a face. An isolated vertex has no halfedge.

Invariants

HalfedgeMesh::validate checks every one of these; every constructor and edit keeps them.

• next and prev are inverse permutations of the live halfedges, and face(next(h)) == face(h).
• source(h) == target(opposite(h)) and an edge never joins a vertex to itself.
• Every face loop has at least three halfedges and no repeated vertex.
• No edge has a boundary on both sides.
• The mesh is simple: two vertices are joined by at most one edge.
• Every vertex is manifold: rotating around it reaches every outgoing halfedge, at most one of them is a boundary halfedge, and when one is, it is the vertex’s stored halfedge. So HalfedgeMesh::is_boundary_vertex is O(1) and a vertex circulation starts at the boundary.

Non-manifold input is refused by name (HalfedgeBuildError) rather than represented: an edge shared by three faces, a vertex pinched between two fans, and two faces disagreeing on winding each have their own variant.

Identity

A mesh built from a TriMesh or face list keeps the input’s numbering: vertex i is position i and face j is input face j. Edits that remove elements mark them removed instead of renumbering, so ids held by a caller stay valid across edits; HalfedgeMesh::compact renumbers densely and returns the mapping.

Structs

EdgeId

An undirected edge of a HalfedgeMesh; it owns halfedges 2e and 2e + 1.

FaceId

A face of a HalfedgeMesh.

HalfedgeId

A directed halfedge of a HalfedgeMesh.

HalfedgeInvariantError

The first structural invariant a HalfedgeMesh was found to break.

HalfedgeMesh

Halfedge (doubly-connected edge list) surface mesh of a 2-manifold, with or without boundary, with polygonal faces.

HalfedgeRemap

Old-to-new id mapping returned by HalfedgeMesh::compact.

VertexId

A vertex of a HalfedgeMesh.

Enums

HalfedgeBuildError

Why a face list cannot become a HalfedgeMesh.

HalfedgeEditError

Why a local edit or a conversion was refused.