The hardware and bandwidth for this mirror is donated by METANET, the Webhosting and Full Service-Cloud Provider.
If you wish to report a bug, or if you are interested in having us mirror your free-software or open-source project, please feel free to contact us at mirror[@]metanet.ch.

The fmesher C++ library

Finn Lindgren

The plan is to briefly describe the backend fmesher C++ library.

Introduction

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 and Dæhlen (2006), extended to RCDTs on spheres.

Data structures

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.

Triangle centric data model

The mesh storage is composed of a 3-column matrix of vertex coordinates, S, and three triangle graph topology 3-column integer matrices:

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.

Graph traversal algebra

These operators, and their inverses, allow arbitrary graph traversal of 2-manifold meshes with triangles connected via edges.

Matrices

Point locator trees

Operations

RCDT

Point locator

Rcpp interface

rcdt

bary

fem

split_lines

References

Hjelle, Øyvind, and Morten Dæhlen. 2006. Triangulations and Applications. Springer Berlin, Heidelberg. https://doi.org/10.1007/3-540-33261-8.

These binaries (installable software) and packages are in development.
They may not be fully stable and should be used with caution. We make no claims about them.