Winged edge
Encyclopedia
The winged edge data structure
is a data representation
used to describe polygon model
s in computer graphics
. It 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.
The winged edge data structure allows for quick traversal between faces, edges, and vertices due to the explicitly linked structure of the network. This rich form of specifying an unstructured grid
is in contrast to simpler specifications of polygon mesh
es such as a node and element list, or the implied connectivity of a regular grid
.
class WE_Edge {
WE_Vertex vert1, vert2;
WE_Face aFace, bFace;
WE_Edge aPrev, aNext, bPrev, bNext; // clockwise ordering
WE_EdgeDataObject data;
}
class WE_Vertex {
List edges;
WE_VertexDataObject data;
}
class WE_Face {
List edges;
WE_FaceDataObject data;
}
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
is a data representation
Boundary representation
In solid modeling and computer-aided design, boundary representation—often abbreviated as B-rep or BREP—is a method for representing shapes using the limits...
used to describe polygon model
Polygon mesh
A polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling...
s in computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
. It explicitly describes the geometry and topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
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. This rich form of specifying an unstructured grid
Unstructured grid
An unstructured 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...
is in contrast to simpler specifications of polygon mesh
Polygon mesh
A polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling...
es such as a node and element list, or the implied connectivity of a regular grid
Regular grid
A regular grid is a tessellation of n-dimensional Euclidean space by congruent parallelotopes . Grids of this type appear on graph paper and may be used in finite element analysis as well as finite volume methods and finite difference methods...
.
Pseudocode
Here is a data structure suitable for representing a winged edge. The abbreviation "WE" stands for "Winged Edge".class WE_Edge {
WE_Vertex vert1, vert2;
WE_Face aFace, bFace;
WE_Edge aPrev, aNext, bPrev, bNext; // clockwise ordering
WE_EdgeDataObject data;
}
class WE_Vertex {
List
WE_VertexDataObject data;
}
class WE_Face {
List
WE_FaceDataObject data;
}
See also
- Quad-edge data structureQuad-edge data structureA quad-edge data structure is a computer representation of the topology of a two-dimensional or three-dimensional map, that is, a graph drawn on a surface.-Overview:The quad-edge data structure:...
- Combinatorial maps
- Doubly connected edge list
- Doubly linked face listDoubly Linked Face ListIn applied mathematics, a doubly linked face list is an efficient data structure for storing 2-manifold mesh data. The structure stores linked lists for a 3D mesh's faces, edges, vertices, and corners. The structure guarantees the preservation of the manifold property.This data structure is used...
External links
- Winged Edge Polyhedron Representation for Computer Vision, Bruce G. Baumgart
- The Winged-Edge Data Structure, on Michigan Technological University
- Winged Edge, on university of Pisa