The plan is to briefly describe the backend fmesher C++ library.
fmesher C++ library was initially written by Finn
Lindgren in April/May 2010, as an implementation of the data structures
and refined constrained Delaunay triangulation (RCDT) methods from Hjelle and Dæhlen (2006), extended to RCDTs on
The key to the algorithm speed is the use of traversal operators for the mesh graph, made efficient by support in the data structure for key operations.
The mesh storage is composed of a 3-column matrix of vertex
S, and three triangle graph topology 3-column
TV: 3 vertex indices, in CCW order
TT: For each of the 3 corners, the index of the
opposing edge neighbouring triangle, if any, otherwise -1.
TTi: For each of the 3 corners, the in-triangle index
of the opposing edge’s neighbouring triangle’s opposing in-triangle
index. This structure can be turned on/off to allow certain operations
to be more efficient.
This is similar to a winged-edge or half-edge structure, but treats triangles as primary objects, allowing compact storage as well as efficient graph traversal.
Note: A further structure,
VT, can be enabled, that for
each vertex gives the index of a single triangle that it is used by. A
limitation of this data structure is that there is no cheap way to
access all triangles that connect to a given vertex, unless the
mesh is a proper edge-connected manifold. For example, some operation
will not handle meshes where the forward and inverse
operations cannot reach all the connected triangles. To handle such
cases, the data structure may need to be extended with a triangle index
set for each vertex, in effect replacing the
single-index vector with a vector of sets, and replacing some key
algorithms that currently rely on
Dart location objects; originator vertex, edge
direction, and triangle
alpha operator alters only one simplex quantity:
alpha0: swap the originating vertex for the edge, keep
alpha1: swap to the edge pointing to the remaining 3rd
vertex, keep the originator vertex and triangle
alpha2: swap to the adjacent triangle, stay along the
same edge and keep the originator vertex
orbit keeps one simplex quantity fixed while
altering the other two, keeping orientation intact; If one starts with a
Dart pointing in CCW direction in a triangle, each
successful orbit operation will keep that property.
orbit0 = alpha1,alpha2: move to the next CCW adjacent
triangle, except on boundary
orbit1 = alpha2,alpha0: move to the adjacent triangle
and swap edge direction, except on boundary
orbit2 = alpha0,alpha1: move to the next CCW vertex in
These operators, and their inverses, allow arbitrary graph traversal of 2-manifold meshes with triangles connected via edges.