From CGAFaq

Contents 1 What kind of polygon meshes can the half-edge structure represent? 1.1 Representable polygon meshes 1.2 Non-representable polygon meshes 1.3 Non-manifold conditions

What kind of polygon meshes can the half-edge structure represent?

Representable polygon meshes

Half-edge structure can represent the following combinations of adjacencies:

• 1) Edge loops. That is, edges with the same starting and ending vertex (but not always, see discussion).
• 2) Multi-edges. That is, there are many edges with the same starting and ending vertices (but not always, see discussion).
• 3) Isolated polygons.
• 4) Isolated edges.
• 5) Isolated vertices.
• 6) Mixed wireframe and polygon meshes (but not always, see discussion).
• 7) Polygons with an arbitrary number of vertices and edges.
• 8) Polygons meeting only at one vertex.

Here's an image showing these configurations in action.

Note the edges drawn with dashes. The dashing is to highlight the fact that they have nothing to do with the polygons they are lying on. They are just wireframe edges connected to the same vertices as the polygon.

Recall that the half-edge structure itself represents only topological relationships, not geometric. What you see in the image is an embedding of the structure in a geometric space. The embedding has been deliberately chosen such that you can see the individual multi-edges and edge loops by curving some of the edges.

Non-representable polygon meshes

The feature list above is to be taken with caution. There are restrictions on the kind of relationships the half-edge structure can represent. To make this precise, lets define:

• The following indices are mod n. In particular, .
• A half-edge path is an -length sequence of half-edges such that .
• An -length half-edge path is called a loop if .
• An -length half-edge loop is called properly oriented if .
• A half-edge is called reserved if it is adjacent to a polygon (). Otherwise the half-edge is called free.
• A vertex is called reserved if all of its adjacent outgoing half-edges are reserved. Otherwise the vertex is called free.

Now the two important restrictions over the half-edge structure can be stated as:

• An edge can be added between two vertices A and B if and only if both A and B are free.
• A polygon described by a half-edge loop can be added if and only if every half-edge in the half-edge loop is free and the half-edge loop can be made properly oriented by reordering half-edge links around the vertices of the half-edge loop.

The second statement (among other things) excludes the representation of non-orientable surfaces, such as the Moebius strip. Both statements together exclude many of the non-manifold meshes (but see the discussion below). The reordering mentioned in the second statement is important in that it enables the representation of polygons that are connected only by one vertex, for example a propel. This is important, because this situation arises frequently when building the polygon model. The reordering algorithm is described in the implementation article.

Interpret this image in 3D, with the dashed line representing the occluded edge. This image shows a non-manifold edge at the join of more than two polygons.

Interpret this image in 2D, with the dashed line representing a wireframe edge. This image shows a non-manifold vertex at the lower vertex of the wireframe edge.

Interpret this image in 3D, with the dashed lines representing occluded edges. This shows a non-manifold vertex at the join of the closed meshes.

Non-manifold conditions

Could we represent non-manifold edges with half-edge structure? This sounds rational if we relax the requirement . Then we would link the half-edge pairs in a singly-linked list around the shared edge. The good and the bad news are the same: it works in half of the cases. However, these cases are interleaved, and as such is not at all practical.

Here is a simple mesh containing a non-manifold edge, which cannot be represented in the half-edge structure. Interpret this image in 3D, with the dashed line representing the occluded edge.

Four polygons joining an edge is representable, while five polygons are not. In general an even number of polygons sharing an edge is representable, and an odd number of polygons sharing an edge is not. The important thing to notice is that to get to the four polygon case, you need to go through the three polygon case, which is not representable.

If such non-manifold conditions need to be represented, one should consider more advanced data structures such as the 'partial entity structure'.