Mesh
In computer graphics , points connected to one another by edges form a polygon network that defines the shape of a polyhedron . Triangle meshes and square meshes are the most common here. There are a number of known data structures for storing polygon meshes and polygons . The bestknown structures are the node list, edge list, winged edge and the doubly connected halfedge list .
Each node must have at least one connection to the rest of the network in order to be a member of the network. It follows that every node can be reached by every other node in the network. In graph theory , polygon networks can be represented as undirected graphs without multiple edges.
Properties of meshes
A mesh can have the following properties, but none of them are required for a mesh:
 Structuredness : A polygon mesh is said to be structured when every inner point has the same number of adjacent edges and faces.
 Regularity : A polygon mesh is regular if the edge lengths are constant in every direction. This property builds on the structure.
 Orthogonality : A polygon mesh is said to be orthogonal if the mesh edges form right angles . The orthogonality is based on the property of structuredness and regularity.
Polygon mesh as a triangular mesh
The polygon mesh as a triangular mesh is a widespread form of the polygon mesh. It is particularly important for triangulation and meshing .
(TIN)
Data structures
Simple data structures
Node list
With the node list, the points are stored in a separate point list. An area is then defined as a list of pointers to the points in that list. This creates a separation between the geometry (the coordinates of the nodes) and the topology (which nodes connect which edges, which edges limit which surfaces).
Edge list
The disadvantages of the node list are avoided in the edge list in that all edges are saved in a separate list. Facets are defined here as pointers to the edge list. In addition to the start and end point, the maximum of two associated facets are also stored for each edge. The order in which the corner points are specified for edges defines an orientation and, for facets, determines where inside and where outside is.
Advantages and disadvantages
Data structure  advantages  disadvantage 

Node list 


Edge list 


In general, for node and edge lists, the search for subordinate objects such as edges and nodes can be carried out very efficiently starting from a facet. In the opposite direction, however, it is the opposite. So is z. B. the search for all facets, which contain a certain corner, is still only possible through an exhaustive search.
More complex data structures
Winged Edge according to Baumgart
A data structure with the help of which a large number of queries can be processed efficiently is the wingededge representation according to Baumgart. In addition to the information in the edge list, pointers to the edges that start from the start and end point of the current edge are also stored here. Due to the orientation, each edge is traversed once positively (clockwise) and once negatively (counterclockwise).
With the winged edge data structure, it is possible to query in constant time which nodes or facets belong to a given edge. If a facet has k edges, these edges can be searched one after the other in linear time (only for polygonal networks without changing the direction of passage of a polygon). Other queries, especially those starting from a corner that are looking for the edges or facets that contain that corner, are significantly slower.
Doubly linked list of edges (Half Edge)
The halfedge data structure is a little more mature than the wingededge list. It allows most of the operations listed in the following table to be performed in constant time; H. constant time per information collected. If you z. B. wants to find out all edges adjacent to a corner point, the operation is linear with respect to the number of adjacent edges but constant in time per edge. Half Edge only works with twodimensional manifolds ; H. each edge is surrounded by exactly two facets (for each halfedge there is an opposite halfedge), i.e. H. Tconnections, inner polygons and breaks are not allowed.
With the halfedge structure, not edges, but halfedges are stored. Halfedges are directed and two matching halfedges (pair) form an edge and point in the opposite direction.
Another data structure is the doublyconnected edge list (DCEL).
Runtime comparison
The following table shows a comparison of the asymptotic runtime depending on the existing elements nodes, edges and surfaces. There are nine possible queries on the structure, namely "which corner, edge or surface belongs to which corner edge or surface". All queries except for the adjacent corners of a given corner are listed in the table. The comparison shows how differently well the data structures process the request classes.
Search query (given → searched)  Node list  Edge list  Winged Edge  Half Edge 

Edge → corner points  N / A  
Edge → facets  N / A  
Edge → adjacent edges  N / A  
Vertex → edges  
Vertex → facets  
Facet → edges  
Facet → corner points  
Facet → neighboring facet 
Here:
 : Number of all edges
 : Number of edges of a facet
 : Number of edges that belong to a point
 : Number of all facets
Explanation of the request classes
inquiry  Node list  Edge list  Winged Edge  Half Edge 

Edge → corner points  Not possible (there are no edges)  Can be read directly from the edges  read directly from the entry for edge  over half edge → vert and pair → vert. 
Edge → facets  Not possible (there are no edges)  Readable directly from the edges  visible directly from the edge  determine the adjacent surfaces via edge → face and edge → pair → face. 
Edge → adjacent edges  Not possible (there are no edges)  for both corner points: perform "corner point → edge"  see list of edges  see list of edges 
Vertex → edges  Since we are dealing with closed polygons, every facet (as many edges as points) has edges, these must be determined for every surface and checked to see whether the given corner is contained in it  just go through all edges  Determine the starting edge of the point, then search via "Predecessor right" until there is no edge left, then start again at the starting edge and walk in the other direction.  Get the first edge via vert → edge, then get the opposite edge and continue to the left. Do this until there is no successor edge on the left, then start again with vert → edge and this time walk to the right until there is no more adjacent edge. 
Vertex → facets  Simply go through the edges for all facets and see whether the corner point you are looking for is included.  Execute "Corner → Edge" and then read the associated facet directly from these edges.  simply determine the edges to the point and determine the associated surfaces in a constant time  see list of edges 
Facet → edges  Form all edges of a facet in pairs  can be read directly from facets  see Half Edge  Start at the start edge of the facet and walk to the left. If the following edge belongs to the same facet, then continue in the same direction. If no successor is found for the first time, the direction of travel is reversed. If the successor belongs to the same facet, then continue in this direction, otherwise cancel. The direction of travel can change several times. At some point you arrive at the starting edge. Then you can stop. 
Facet → corner points  Simply read out directly from facets  Execute "Facet → Edges" and read out the associated corner points in a constant time  see Half Edge  Execute "Facet → Edges" and read out the points from the edges, throw out double points. 
Facet → neighboring facet  Determine all edges of the facet to be checked and check for each edge whether the other facets also contain this edge.  Execute "Facet → Edges" and then read off the associated facets directly from the edges  Execute "Facet → Edges" and read out the adjacent surface for each edge  see Winged Edge 
Summary
As you can see, the wingededge and halfedge structures are almost identical in terms of the information they contain. They therefore also have almost the same search times. Half Edge is a bit better in the more complex requests. Here, due to the pointer of a point on an associated start edge when searching for all edges of a point, only these must be touched. The node list is eliminated from the start and the edge list is just as good in terms of searching as the winged edge list, but requires a little more storage space, since with winged edge only one start edge has to be stored for a facet.
See also
Individual evidence
 ↑ ^{a } ^{b} Jens Neumann: Procedure for adhoc modeling and simulation of spatial springmass systems for use in virtual realitybased handling simulations. Technical University of Berlin, Fraunhofer IRB Verlag, 2009, ISBN 9783816779544 .
 ↑ Oliver Burgert: Modeling II  Nodal Networks  Medical Planning and Simulation Systems. ( Memento of the original from August 10, 2007 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF) University of Leipzig, 2005.