Winged edge

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (July 2018) (Learn how and when to remove this message)

In

The winged edge data structure explicitly describes the geometry and topology of faces, edges, and vertices when three or more surfaces come together and meet at a common edge. The ordering is such that the surfaces are ordered counter-clockwise with respect to the innate orientation of the intersection edge. Moreover the representation allows numerically unstable situations like that depicted below.^{[clarification needed]}

The winged edge data structure allows for quick traversal between faces, edges, and vertices due to the explicitly linked structure of the network. It serves adjacency queries in constant time with little storage overhead. This rich form of specifying an

Structure and pseudocode

The face and vertex records are relatively simple, while the edge record is more complex.

• For each vertex, its record stores only the vertex's position (e.g. coordinates) and a reference to one incident edge. The other edges can be found by following further references in the edge.
• Similarly each face record only stores a reference to one of the edges surrounding the face. There is no need to store the direction of the edge relative to the face (CCW or CW) as the face can be trivially compared to the edge's own left and right faces to obtain this information.
• Finally, the structure of the edge record is as follows. An edge is assumed to be directed. The edge record contains two references to the vertices that make up the endpoints of the edge, two references to the faces on either side of the edge, and four references to the previous and next edges surrounding the left and right face.

In short, the edge record has references to all its adjacent records, both when traversing around an adjacent vertex or around an adjacent face.

class Edge
{
    Vertex *vert_origin, *vert_destination;
    Face *face_left, *face_right;
    Edge *edge_left_cw,
         *edge_left_ccw,
         *edge_right_cw,
         *edge_right_ccw;
}

class Vertex
{
    float x, y, z;
    Edge *edge;
}

class Face
{
    Edge *edge;
}

See also

• Quad-edge data structure
• Combinatorial maps
• Doubly connected edge list
• Doubly linked face list
• Half-edge data structure

External links

The Wikibook Wings 3D/User Manual has a page on the topic of: The Nature of Subdivision Modeling/Winged Edge Topology

• Baumgart, Bruce G. (1972). Winged Edge Polyhedron Representation (PDF) (Technical report). Stanford University. CS-TR-72-320.
• Baumgart, Bruce G. (1975). "A polyhedron representation for computer vision" (PDF). AFIPS '75: Proceedings of the May 19-22, 1975, national computer conference and exposition. ACM Press. pp. 589–596.
  S2CID 9040571
  .
• Shene, C.-K. (2011). "The Winged-Edge Data Structure". CS3621 Introduction to Computing with Geometry Notes. Michigan Technological University.
• "Winged Edge". Polyhedral Data Structures: CS488/688: Introduction to Interactive Computer Graphics, University of Waterloo. University of Pisa.