As we have learned from Lecture 8, there are many ways to represent polygon meshes. If we only need to perform some basic operations, e.g., loading and rendering a mesh on screen, we can use very basic mesh data structures such as a polygon soup. A polygon soup is just a list of vertices together with a list of polygons referencing the vertices, as shown in this lecture slide.
However, this simple representation does not facilitate meaningful traversal of polygon meshes; and is therefore often not sufficient for many geometry processing tasks. In Assignment 2, we will use the half-edge data structure to represent polygon meshes instead. As you will learn to appreciate, the half-edge data structure provides a good balance between simplicity and geometry processing capability.
The simple idea behind the half-edge data structure is that, in addition to the usual mesh elements vertices, edges, and faces that make up the polygon mesh, we also have an element called a half-edge that acts like a "glue" connecting the different mesh elements. It is this glue that allows us to easily navigate the mesh.
In particular, there are two half-edges associated with each edge, shown in the figure above. For an edge connecting two vertices and , one of its half-edges points from to , while the other points from to . In other words, the two half-edges are always oppositely oriented.
Each half-edge is associated with the face where the half-edge points along the counterclockwise (CCW) direction on the face. For example, the half-edge labeled "halfedge" in the figure points along the CCW direction in the left triangle. Therefore, "halfedge" is associated with the left triangle. As a result, each half-edge of an edge is associated with only one of the two faces connected to the edge.
The half-edge data structure is designed such that each half-edge has pointers to (1) the opposite half-edge, called its twin, (2) the next half-edge CCW around the face associated with the half-edge, and (3) the vertex that is the "source" of the half-edge, (4) its associated edge, and (5) its associated face as explained above.
In contrast, each primitive mesh element (a vertex, edge, and face) only has a pointer to one of their half-edges. In more detail, (1) a vertex only has a pointer to one of the half-edges that points away from the vertex, (2) an edge only has a pointer to one of its two half-edges, and (3) a face only has a pointer to one of the half-edges circulating around its interior.
The lecture slide summarizes the relationships between mesh elements; and it underscores that it is really the half-edges that connect mesh elements together.
An interesting consequence of the half-edge data structure is that any valid half-edge mesh must be manifold and orientable. In Assignment 2, we will therefore only provide manifold, oriented meshes as input. In fact, the mesh parser will complain if the input does not satisfy these criteria.