Mesh basics

_images/dragon_full.png

We define a polygonal mesh by specifying two sequences:

  • a sequence \(V = (v_i)_{i=0}^{n-1}\) of vertices such that \(v_i \in \mathbb{R}^3\) and

  • a sequence \(F = (f_j)_{j=0}^{m-1}\) of faces.

Faces \(f \in F\) are sequences themselves: a \(k\)-tuple \(f = (i_0, \dots, i_{k-1})\) of integers defines a face of valence \(k\) with vertices \(v_{i_0}, \dots, v_{i_{k-1}}\). In general, faces are neither planar nor convex. If \(k\) is equal to three for all faces, the pair \((V, F)\) defines a triangle mesh.

Note

We can identify the ordered sequence of vertices with a matrix \(V \in \mathbb{R}^{n \times 3}\). Replacing \(V\) with \(W \in \mathbb{R}^{n \times 3}\) yields a mesh with identical combinatorics \(F\) but different vertex positions.

Manifold meshes

A pair \((V,F)\) as just defined can describe arbitrary collections of polygonal faces. For simplicity we only consider triangular faces in the following definitions. A triangle mesh is 2-manifold if the faces incident to a vertex either form a closed or an open triangle fan.

_images/manifold_fan.png

The orientation of a face is defined by the cyclic ordering of its incident vertices as specified in the definition of \(f\). The orientation of two adjacent faces is compatible, if the two vertices of the common edge appear in opposite order. A manifold mesh is orientable if any two adjacent faces have compatible orientation.

Note

Both, manifoldness and orientability are determind by the mesh combinatorics \(F\) and do not depend on a concrete geometric realization (an embedding defined by specifying \(V\)).

Halfedge representation

Any orientable 2-manifold mesh can be represented using halfedges. Conceptually one splits each edge of a mesh into two so called halfedges. Each halfedge is oriented according to the orientation of its incident face. In this way adjacent faces give rise to oppositely oriented halfedges:

_images/halfedge_all.png

The Mesh class provides a generic halfedge data structure for orientable 2-manifold meshes. The combinatorics of a mesh is defined via its halfedges and their attributes. Each halfedge is aware of its incident face, its origin and target vertex, the neighboring halfedge pair, as well as its successor next and predecessor halfedge prev in a face defining loop of halfedges.

Note

The explicit representation of a face as a list of its vertices can be reconstructed from the set of halfedges – hence, the sequence \(F\) is not stored explicitly. It is sufficient to know one halfedge per face to compute the face defining loop of halfedges (or vertices).

References

  1. K. Crane: A Survey of Efficient Structures for Digital Geometry Processing, 2006.

  2. H. Brönnimann: Designing and Implementing a General Purpose Halfedge Data Structure, Proceedings of the 5th International Workshop on Algorithm Engineering, 2001.