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 best-known 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
Simple data structures
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).
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
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 winged-edge 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 half-edge data structure is a little more mature than the winged-edge 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 two-dimensional manifolds ; H. each edge is surrounded by exactly two facets (for each half-edge there is an opposite half-edge), i.e. H. T-connections, inner polygons and breaks are not allowed.
With the half-edge structure, not edges, but half-edges are stored. Half-edges are directed and two matching half-edges (pair) form an edge and point in the opposite direction.
Another data structure is the doubly-connected edge list (DCEL).
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|
- : 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|
As you can see, the winged-edge and half-edge 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.
- Jens Neumann: Procedure for adhoc modeling and simulation of spatial spring-mass systems for use in virtual reality-based handling simulations. Technical University of Berlin, Fraunhofer IRB Verlag, 2009, ISBN 978-3-8167-7954-4 .
- 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.