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 isThere 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.
Articles by others on the same topic
There are currently no matching articles.