Polygon mesh

Interconnected with edge points form a mesh that defines the shape of a polyhedron in computer graphics. Triangular meshes and quadrilateral nets are most commonly here. For storing meshes and polygons there are a number of known data structures. The most common structures are the node list, edge list, Winged Edge and the doubly-linked edge list ( doubly connected edge list helped ).

Each node must have the rest of the network to be a member of at least one network connection. It follows that each node is reachable from each other in the network. In graph theory meshes are represented as undirected graphs without multiple edges.

• 3.2.1 Winged Edge by Baumgart
• 3.2.2 Double- connected edge list ( HalfEdge )

• 3.3.1 Explanation of the request classes
• 3.3.2 Summary

Properties of meshes

The following properties of a network can have, but none of them are required for a mesh:

• Structuredness of: a mesh structure is referred to as if any internal point has the same number of abutting edges, and faces.
• Regularity: A polygon mesh is regular if the edge lengths are constant in each direction. This property is based on the structured nature.
• Orthogonality: A mesh is called orthogonal if the network edges form right angles. The orthogonality builds on the structured nature and the regularity property.

Mesh as a triangle mesh

The mesh as a triangle mesh is a widespread form of the mesh. It is particularly important for triangulations and the meshing of importance.

( TIN)

Data Structures

Simple data structures

Node list

In the node list, the points are stored in a separate list item. A surface is then defined as a list of pointers to the items in the list. This separation between the geometry ( the coordinates of the nodes ) and the topology ( which nodes which connect edges which delimit areas that edge ) realized.

Edge list

The disadvantages of the node list are bypassed at the edge list in that all edges are stored in a separate list. Facets are defined here as a pointer to the edge list. In addition to the start and end point and the maximum of two respective facets for each edge are stored. The order of specifying the parameters for edge defines an orientation and determined at facets, where inside and outside where.

Advantages and disadvantages

• Separation of geometry and topology
• Minimal redundancies ( points are only stored once )

• Edges are run through several times and spent
• Search for edges belonging facets not efficiently possible (only with exhaustive search possible) for all edges in F1 ( each pair of nodes ), we are looking in all other facets, whether it is contained, if not then edge
• Search for facets which comprise an edge or corner, is inefficient

• Separation of geometry and topology
• Rapid determination of boundary edges ( edges with only one reference to facet)

• Search for facets which comprise an edge or corner, is inefficient

Generally speaking, for node and edge lists that the search for child objects such as edges and nodes is starting from a very efficient facet feasible. In the reverse direction is true but the opposite. Thus, for example, finding all facets that contain a certain corner, still only by an exhaustive search possible.

More complex data structures

Winged Edge by Baumgart

A data structure with the help of very many queries can be processed efficiently is the Winged - Edge representation by Baumgart. In addition to the information of the edge list here pointers are still stored on the edges radiating from start and end point of the current edge. Due to the orientation of each edge is traversed ( counterclockwise) once positive (clockwise ) and one negative.

The winged -edge data structure, it is possible to retrieve in a constant time, or facets which nodes belong to a given edge. K has a facet edges, these edges can be scanned sequentially (only polygonal networks without changing the flow direction of a polygon ) in linear time. Other requests, especially those starting from a corner, look for the edges or facets in which this vertex belongs, are considerably slower.

Doubly linked list of edges ( HalfEdge )

The Half- Edge data structure is a little more mature than the Winged - Edge list. It allows to carry out most of the operations listed in the following table in a constant time, that is, constant time per information collected. If, for example, all wants to find to a vertex adjacent edges, the operation of the number of adjacent edges is linear but constant in time with respect to each edge. HalfEdge works only with 2-dimensional manifold, ie each edge is of exactly two facets ( for each half edge there is an opposite half edge ) surrounded, ie T-joints, inner polygons and fractures are not allowed.

The Half- Edge structure not edge, but half edges are stored. Half edges are directed and two belong together half edges (pair) form an edge and pointing in the opposite direction.

Another data structure is the doubly -connected edge list ( DCEL ).

Running time comparison

The following table shows a comparison of the asymptotic running time as a function of the existing elements nodes, edges and surfaces. There are nine possible queries on the structure, namely, " which corner, edge or surface of one of which corner edge or surface ". All queries except for the one on the adjacent corners of a given area are listed in the table. The comparison shows how different well edit the data structures of the request classes.

Herein:

• : The number of edges
• : Number of edges of a facet
• : The number of edges that are part of a point
• : Number of all facets

Explanation of the request classes

Summary

As you can see, the Winged - Edge and the Half- Edge structure of the information herein are nearly identical. They therefore also have almost the same lifetimes for searching. Half Edge is slightly better in the more complex inquiries. Here will just need this to be handled due to the pointer of a point on an associated starting edge finding all edges of a point. The node list differs from the outset and the edge list is from searching ago as good as the Winged - Edge list, but needs a little more space because when Winged Edge only a starting edge must be passed to a facet.