= Solution
A <boundary representation> separates geometry, which supplies locations and supporting <planes>, from topology, which specifies incidence and orientation. A practical <winged-edge data structure> uses three related record types:
* A <vertex of a polyhedron> record holds its three <coordinates> and a reference to one incident edge, sufficient to begin traversing the local fan.
* A face record holds its supporting <plane>, an outward <normal vector> or equivalent orientation, and a reference to a boundary edge. Faces with holes need one entry per boundary loop.
* An edge record holds its two endpoint <vertices of a polyhedron>, its left and right incident faces, and predecessor and successor edges around each of those faces: four “wing” references. “Left” and “right” refer to a chosen orientation of the edge and compatible face traversal conventions.
This explicitly stores adjacency rather than recovering it by searching all faces. A <half-edge data structure> expresses much the same information with two oppositely directed records per undirected edge: each has an origin <vertex of a polyhedron>, an incident face, its next boundary record and its opposite record; a previous record is often stored as well. The destination can be obtained from the opposite record's origin. This mesh record is distinct from a dangling <half-edge of a graph>.
The compact implementation answer is
$$
\boxed{\text{vertex geometry + oriented face loops + explicit edge/face/vertex incidence}.}
$$
There is deliberate redundancy: the same adjacency can be reached from both an edge and a face, a stored previous edge is recoverable by walking the loop, and a face <normal vector> can be computed from its ordered noncollinear <vertices of a polyhedron>. These copies make neighbourhood queries and local edits cheap, and cached <plane> equations speed geometric tests. They impose consistency obligations: an edit must update reciprocal references, loops, orientations and affected geometric caches together. A <half-edge data structure> should share the undirected edge's geometry or keep its paired records synchronized.
Back to article page
