knitr::opts_chunk$set( collapse = TRUE, comment = "#>" )
suppressPackageStartupMessages(library(fmesher))
The plan is to briefly describe the backend fmesher C++ library.
The 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_daehlen_2006, extended
to RCDTs on spheres.
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 coordinates, S
,
and three triangle graph topology 3-column integer matrices:
TV
: 3 vertex indices, in CCW orderTT
: 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 orbit0
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 VT
single-index vector with a vector of sets, and replacing some key algorithms that
currently rely on orbit0
operations.
Dart
location objects; originator vertex, edge direction, and trianglealpha
operator alters only one simplex quantity:alpha0
: swap the originating vertex for the edge, keep the trianglealpha1
: swap to the edge pointing to the remaining 3rd vertex, keep the originator vertex and trianglealpha2
: swap to the adjacent triangle, stay along the same edge and keep the originator vertexorbit
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 boundaryorbit1 = alpha2,alpha0
: move to the adjacent triangle and swap edge
direction, except on boundaryorbit2 = alpha0,alpha1
: move to the next CCW vertex in the triangleThese operators, and their inverses, allow arbitrary graph traversal of 2-manifold meshes with triangles connected via edges.
Any scripts or data that you put into this service are public.
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.