The fundamental idea behind the quad-edge structure is the recognition that a single edge, in a closed polygonal mesh topology, sits between exactly two faces and exactly two vertices.
The Quad-Edge Data Structure
The quad-edge data structure represents an edge, along with the edges it is connected to around the adjacent vertices and faces to encode the topology of the graph. An example implementation of the quad-edge data-type is as follows
Each quad-edge contains four references to adjacent quad-edges. Each of the four references points to the next edge counter-clockwise around either a vertex or a face. Each of these references represent either the origin vertex of the edge, the right face, the destination vertex, or the left face. Each quad-edge reference points to a quad-edge and the rotation (from 0 to 3) of the 'arm' it points at.
Due to this representation, the quad-edge:
represents a graph, its dual, and its mirror image.
the dual of the graph can be obtained simply by reversing the convention on what is a vertex and what is a face; and
can represent the most general form of a map, admitting vertices and faces of degree 1 and 2.
Detailsedit
The quad-edge structure gets its name from the general mechanism by which they are stored. A single Edge structure conceptually stores references to up to two faces, two vertices, and 4 edges. The four edges stored are the edges starting with the two vertices that are attached to the two stored faces.
Usesedit
Much like Winged Edge, quad-edge structures are used in programs to store the topology of a 2D or 3Dpolygonal mesh. The mesh itself does not need to be closed in order to form a valid quad-edge structure.
Using a quad-edge structure, iterating through the topology is quite easy. Often, the interface to quad-edge topologies is through directed edges. This allows the two vertices to have explicit names (start and end), and this gives faces explicit names as well (left and right, relative to a person standing on start and looking in the direction of end). The four edges are also given names, based on the vertices and faces: start-left, start-right, end-left, and end-right. A directed edge can be reversed to generate the edge in the opposite direction.
Iterating around a particular face only requires having a single directed edge to which that face is on the left (by convention) and then walking through all of the start-left edges until the original edge is reached.
^Stolfi, Jorge; Guibas, Leonidas J. (April 1985). "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams". ACM Transactions on Graphics. 4 (2): 74‒169. doi:10.1145/282918.282923. S2CID 52852815.
quad, edge, this, article, includes, list, references, related, reading, external, links, sources, remain, unclear, because, lacks, inline, citations, please, help, improve, this, article, introducing, more, precise, citations, january, 2021, learn, when, remo. This article includes a list of references related reading or external links but its sources remain unclear because it lacks inline citations Please help improve this article by introducing more precise citations January 2021 Learn how and when to remove this message A 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 closed surface It was first described by Jorge Stolfi and Leonidas J Guibas 1 It is a variant of the earlier winged edge data structure Contents 1 Overview 2 Details 3 Uses 4 See also 5 References 6 External linksOverview editThe fundamental idea behind the quad edge structure is the recognition that a single edge in a closed polygonal mesh topology sits between exactly two faces and exactly two vertices nbsp The Quad Edge Data Structure The quad edge data structure represents an edge along with the edges it is connected to around the adjacent vertices and faces to encode the topology of the graph An example implementation of the quad edge data type is as follows typedef struct quadedge ref e 4 quadedge typedef struct quadedge next unsigned int rot quadedge ref Each quad edge contains four references to adjacent quad edges Each of the four references points to the next edge counter clockwise around either a vertex or a face Each of these references represent either the origin vertex of the edge the right face the destination vertex or the left face Each quad edge reference points to a quad edge and the rotation from 0 to 3 of the arm it points at Due to this representation the quad edge represents a graph its dual and its mirror image the dual of the graph can be obtained simply by reversing the convention on what is a vertex and what is a face and can represent the most general form of a map admitting vertices and faces of degree 1 and 2 Details editThe quad edge structure gets its name from the general mechanism by which they are stored A single Edge structure conceptually stores references to up to two faces two vertices and 4 edges The four edges stored are the edges starting with the two vertices that are attached to the two stored faces Uses editMuch like Winged Edge quad edge structures are used in programs to store the topology of a 2D or 3D polygonal mesh The mesh itself does not need to be closed in order to form a valid quad edge structure Using a quad edge structure iterating through the topology is quite easy Often the interface to quad edge topologies is through directed edges This allows the two vertices to have explicit names start and end and this gives faces explicit names as well left and right relative to a person standing on start and looking in the direction of end The four edges are also given names based on the vertices and faces start left start right end left and end right A directed edge can be reversed to generate the edge in the opposite direction Iterating around a particular face only requires having a single directed edge to which that face is on the left by convention and then walking through all of the start left edges until the original edge is reached See also editWinged edge Combinatorial maps Doubly connected edge listReferences edit Stolfi Jorge Guibas Leonidas J April 1985 Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams ACM Transactions on Graphics 4 2 74 169 doi 10 1145 282918 282923 S2CID 52852815 External links edithttps www cs cmu edu afs andrew scs cs 15 463 2001 pub src a2 quadedge html A quad edge implementation in C http www ic unicamp br stolfi EXPORT software c 2000 05 04 libquad A quad edge implementation in C Retrieved from https en wikipedia org w index php title Quad edge amp oldid 1169996068, wikipedia, wiki, book, books, library,
