OpenMesh is a generic and efficient data structure for representing
and manipulating polygonal meshes. OpenMesh is developed at the
Computer Graphics Group, RWTH Aachen ,
as part of the
OpenSGPlus
project, is funded by the German Ministry for Research and Education (
BMBF),
and will serve as geometry kernel upon which the so-called
high level primitives (e.g. subdivision surfaces or
progressive meshes) of OpenSGPlus are built.
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.
Features
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)
Choose the type of containers the mesh items are stored in.
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.
OpenSG integration.
OpenInventor 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:
one vertex
one face
the next halfedge
the opposite halfedge
optional: the previous halfedge
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
Repeat steps (2) to (4) until all neighboring vertices are found. In
analogy one can also determine the neighbouring faces or
halfedges. Note, however, that the programmer himself does not have to
cope with internal data structure, but is provided with
iterators/circulators that fulfill this task.
Implementation
The 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.
