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 best-known structures are the node list, edge list, winged edge and the doubly connected halfedge list .

Different wireframe models , the easiest way to represent a mesh.

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

The picture shows typical mesh properties of different polygon meshes: a) shows a polygon mesh without special properties, b) a structured polygon mesh, c) shows a polygon mesh that is structured and regular, and d) is structured, regular and orthogonal.

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	Separation of geometry and topology minimal redundancies (points are only stored once)	Edges are passed through and output several times Efficient search for facets belonging to edges is not possible (only possible with an exhaustive search) For all edges in F1 (every node pair) we search in all other facets to see whether they are contained, if not, then edge edge Searching for facets that contain an edge or corner is inefficient
Edge list	Separation of geometry and topology Fast determination of edge edges (edges with only one reference to the facet)	Searching for facets that contain an edge or corner is inefficient

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).

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	${\ displaystyle {\ mathcal {O}} (1)}$	${\ displaystyle {\ mathcal {O}} (1)}$	${\ displaystyle {\ mathcal {O}} (1)}$
Edge → facets	N / A	${\ displaystyle {\ mathcal {O}} (1)}$	${\ displaystyle {\ mathcal {O}} (1)}$	${\ displaystyle {\ mathcal {O}} (1)}$
Edge → adjacent edges	N / A	${\ displaystyle {\ mathcal {O}} (k)}$	${\ displaystyle {\ mathcal {O}} (k)}$	${\ displaystyle {\ mathcal {O}} (k_ {v})}$
Vertex → edges	${\ displaystyle {\ mathcal {O}} (f * k_ {f})}$	${\ displaystyle {\ mathcal {O}} (k)}$	${\ displaystyle {\ mathcal {O}} (k)}$	${\ displaystyle {\ mathcal {O}} (k_ {v})}$
Vertex → facets	${\ displaystyle {\ mathcal {O}} (f * k_ {f})}$	${\ displaystyle {\ mathcal {O}} (k)}$	${\ displaystyle {\ mathcal {O}} (k)}$	${\ displaystyle {\ mathcal {O}} (k_ {v})}$
Facet → edges	${\ displaystyle {\ mathcal {O}} (k_ {f})}$	${\ displaystyle {\ mathcal {O}} (k_ {f})}$	${\ displaystyle {\ mathcal {O}} (k_ {f})}$	${\ displaystyle {\ mathcal {O}} (k_ {f})}$
Facet → corner points	${\ displaystyle {\ mathcal {O}} (k_ {f})}$	${\ displaystyle {\ mathcal {O}} (k_ {f})}$	${\ displaystyle {\ mathcal {O}} (k_ {f})}$	${\ displaystyle {\ mathcal {O}} (k_ {f})}$
Facet → neighboring facet	${\ displaystyle {\ mathcal {O}} (f * k_ {f} ^ {2})}$	${\ displaystyle {\ mathcal {O}} (k_ {f})}$	${\ displaystyle {\ mathcal {O}} (k_ {f})}$	${\ displaystyle {\ mathcal {O}} (k_ {f})}$

Here:

${\ displaystyle k}$ : Number of all edges
${\ displaystyle k_ {f}}$ : Number of edges of a facet
${\ displaystyle k_ {v}}$ : Number of edges that belong to a point
${\ displaystyle f}$ : 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 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.

Individual evidence

↑ ^a ^b 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. @1@ 2

[neumann-1] 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 .