---
title: "The fmesher C++ library"
author: "Finn Lindgren"
bibliography: references.bib
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{The fmesher C++ library}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)
```

```{r setup, echo = FALSE}
suppressPackageStartupMessages(library(fmesher))
```

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_daehlen_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:

* `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 `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

* `Dart` location objects; originator vertex, edge direction, and triangle
* Each `alpha` operator alters only one simplex quantity:
  * `alpha0`: swap the originating vertex for the edge, keep the triangle
  * `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
* Each `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 the triangle

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