OpenMesh is a generic and efficient data structure for representing and manipulating polygonal meshes. OpenMesh is developed at the Computer Graphics Group, RWTH Aachen. It was funded by the German Ministry for Research and Education ( BMBF).
It was designed with the following goals in mind:
- Flexibility : provide a basis for many different algorithms without the need for adaptation.
- Efficiency : maximize time efficiency while keeping memory usage as low as possible.
- Ease of use : wrap complex internal structure in an easy-to-use interface.
OpenMesh provides the following features:
- Representation of arbitrary polygonal (the general case) and pure triangle meshes (providing more efficient, specialized algorithms)
- Explicit representation of vertices, halfedges, edges and faces.
- Fast neighborhood access, especially the one-ring neighborhood (see below).
- Highly customizable :
- Choose your coordinate type (dimension and scalar type)
- Attach user-defined elements/functions to the mesh elements.
- Attach and check for attributes.
- Attach data at runtime using dynamic properties.
In addition we provide some sample applications that demonstrate the usage of OpenMesh:
- Mesh Smoothing.
- Mesh Decimation.
- Qt integration.
The halfedge data structure
Polygonal meshes consist of geometry (vertices) and topology (edges, faces). Data structure for polygonal meshes mainly differ in the way they store the topology information. While face-based structures lack the explicit representation of edges, and edge-based structures loose efficiency because of their missing orientation of edges, halfedge-based structures overcome this disadvantages. The halfedges (that result in splitting the edges in two oriented parts) store the main connectivity information:
Intuitively, this provides a natural and simple way to represent vertices, edges and faces, as well as arbitrary polygons. In order to enable effiecient implementations of the algorithms in mind, one has to analyze the most frequent and time-critical accesses these algorithms will need. The most critical operation is the enumeration of the so-called one-ring neighborhood of a vertex. Exploiting the halfedge data structure this can be done very efficiently.
(1) start at a vertex
(2) find outgoing halfedge
(3) switch to opposite halfedge
(4) next halfedge points to neighbouring vertex
ImplementationThe following chart shows the interaction between the OpenMesh components:
The OpenMesh architecture allows for custom-tailored meshes: The user can specify arbitrary traits for vertices, edges and faces or choose from a set of predefined attributes which are then propagated to the mesh kernel. The kernel is responsible for the internal storage of the mesh elements and can be chosen to use either arrays or doubly-linked lists as container types. Since meshes with different attributes will results in different C++ types, OpenMesh makes uses the generic programming paradigm to implement algorithms operating on these meshes. This STL-like method leads to the following advantages:
- No virtual function tables and dynamic binding.
- No memory and run-time overhead.
- Input data are template parameters which are resolved at compile-time.