Winged Edge on:
[Wikipedia]
[Google]
[Amazon]
In
In computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
, the winged edge data structure is a way to represent polygon mesh
In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedral object. The faces usually consist of triangles ( triangle mesh), quadrilaterals (quads), or other simple convex p ...
es in computer memory
In computing, memory is a device or system that is used to store information for immediate use in a computer or related computer hardware and digital electronic devices. The term ''memory'' is often synonymous with the term '' primary storag ...
. It is a type of boundary representation
In solid modeling and computer-aided design, boundary representation (often abbreviated B-rep or BREP) is a method for representing a 3D shape by defining the limits of its volume. A solid is represented as a collection of connected surface ...
and describes both the geometry and topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
. This kind of adjacency information is useful for algorithms such as subdivision surface.
Features
The winged edge data structure explicitly describes the geometry andtopology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
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.
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
An unstructured grid or irregular grid is a tessellation of a part of the Euclidean plane or Euclidean space by simple shapes, such as triangles or tetrahedra, in an irregular pattern. Grids of this type may be used in finite element analysis w ...
is in contrast to simpler specifications of polygon mesh
In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedral object. The faces usually consist of triangles ( triangle mesh), quadrilaterals (quads), or other simple convex p ...
es such as a node and element list, or the implied connectivity of a regular grid
A regular grid is a tessellation of ''n''-dimensional Euclidean space by congruent parallelotopes (e.g. bricks).
Its opposite is irregular grid.
Grids of this type appear on graph paper and may be used in finite element analysis, finite vol ...
. An alternative to the winged edge data structure is the Half-edge data structure.
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 class Vertex class FaceSee also
* Quad-edge data structure * Combinatorial maps * Doubly connected edge list * Doubly linked face list * Half-edge data structureExternal links
* * * * {{refend Computer-aided design Computer graphics data structures Articles with example pseudocode