Loading AI tools
Data structure for representing polygon meshes in computer memory From Wikipedia, the free encyclopedia
In computer graphics, the winged edge data structure is a way to represent polygon meshes in computer memory. It is a type of boundary representation and describes both the geometry and topology of a model. Three types of records are used: vertex records, edge records, and face records. Given a reference to an edge record, one can answer several types of adjacency queries (queries about neighboring edges, vertices and faces) in constant time. This kind of adjacency information is useful for algorithms such as subdivision surface.[1]
This article includes a list of general references, but it lacks sufficient corresponding inline citations. (July 2018) |
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 unstructured grid is in contrast to simpler specifications of polygon meshes such as a node and element list, or the implied connectivity of a regular grid. An alternative to the winged edge data structure is the Half-edge data structure.
The face and vertex records are relatively simple, while the edge record is more complex.
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; }
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.