rita - Randomized Incremental Triangulation Algorithms

An implementation of (randomized) incremental weighted Delaunay triangulations in safe rust.

You can create a two- or three-dimensional Delaunay triangulation, including weighted points, as follows.

2D

let vertices = vec![
    [0.0, 0.0],
    [-0.5, 1.0],
    [0.0, 2.5],
    [2.0, 3.0],
    [4.0, 2.5],
    [5.0, 1.5],
    [4.5, 0.5],
    [2.5, -0.5],
    [1.5, 1.5],
    [3.0, 1.0],
];
let weights = vec![0.2, 0.3, 0.55, 0.5, 0.6, 0.4, 0.65, 0.7, 0.85, 0.35]; // or None

let mut triangulation = Triangulation::new(None); // specify epsilon here
let result = triangulation.insert_vertices(&vertices, Some(weights), true);  // last parameter toggles spatial sorting

3D

let vertices = vec![
    [0.0, 0.0, 0.0],
    [-0.5, 1.0, 0.5],
    [0.0, 2.5, 2.5],
    [2.0, 3.0, 5.0],
    [4.0, 2.5, 6.5],
    [5.0, 1.5, 6.5],
    [4.5, 0.5, 5.0],
    [2.5, -0.5, 2.0],
    [1.5, 1.5, 3.0],
    [3.0, 1.0, 4.0],
];
let weights = vec![0.2, 0.3, 0.55, 0.5, 0.6, 0.4, 0.65, 0.7, 0.85, 0.35]; // or None

let mut tetrahedralization = Tetrahedralization::new(None); // specify epsilon here
let result = tetrahedralization.insert_vertices(&vertices, Some(weights), true);  // last parameter toggles spatial sorting

The eps parameter is used to perform an approximation technique, which leaves out certain vertices based on epsilon in the incremental insertion process.

:warning: This is a work in progress. :warning: The algorithms work, as test coverage indicates. However, the code is not yet fully optimized and the API is not yet simplified. There might be duplicate and unnecessarily complex code.

Robustness

Robustness is achieved through geogram_predicates, which itself uses cxx to make the geometric predicates from geogram available in rust.

Wasm

In order to have an easy wasm compilable target it is necessary to have a rust only version of this crate. The usage of geogram_predicates makes this difficult as its an ffi to the geogram c++ library. The workaround is to have an abstraction layer over the geometric predicates. For normal usage the geogram_predicates will be used. When activating wasm the fallback rust-only predicates will be used. The downside of these is that they do not support lifted orientation test, i.e. we can not compute weighted Delaunay triangulations. For the majority of the use cases however this is fine, and maybe robust can be extended in the future to support the weighted predicates as well.

Building and publishing the WASM package

The name rita is already taken on npm, so pass the scope at build time so the generated package.json gets a scoped name (e.g. @lempf/rita). If you build without --scope, the package name stays rita and publish will try to use the existing npm package.

Build with your npm scope (use -- so --no-default-features and --features go to cargo, not wasm-pack):

wasm-pack build rita --scope lempf --target web -- --no-default-features --features "std,wasm"

Then publish (scoped packages require --access public):

cd rita/pkg && npm publish --access=public

Install as npm install @lempf/rita.

Usage in web

The WASM build exposes two functions: triangulate (2D) and triangulate3d (3D). Both accept a flat array of coordinates and an optional epsilon (pass null to omit).

2D — triangles

import * as rita from '@lempf/rita';

// Flat array: [x1, y1, x2, y2, ...]
const vertices = [0, 0, 1, 0, 0.5, 1, 0.2, 0.3];
const result = rita.triangulate(vertices, null);

// result.triangles: Array<{ id: string, a: { x, y }, b: { x, y }, c: { x, y } }>
// result.vertices:  Array<{ x, y }>
console.log(result.triangles.length, result.vertices.length);

3D — tetrahedra

import * as rita from '@lempf/rita';

// Flat array: [x1, y1, z1, x2, y2, z2, ...]
const vertices = [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0.5, 0.5, 0.5];
const result = rita.triangulate3d(vertices, null);

// result.tetrahedra: Array<{ id: string, a: { x, y, z }, b, c, d }>
// result.vertices:   Array<{ x, y, z }>
console.log(result.tetrahedra.length, result.vertices.length);

Data structures

| API | Input (flat) | Output | |----------------|----------------|------------------------------------------------------------------------| | triangulate | [x, y, ...] | { triangles: [{ id, a, b, c }], vertices: [{ x, y }] } | | triangulate3d| [x, y, z, ...] | { tetrahedra: [{ id, a, b, c, d }], vertices: [{ x, y, z }] } |

Corner fields a, b, c (and d for 3D) are vertex objects with x, y and optionally z. At least 3 points are required for 2D and 4 for 3D. Note: epsilon and weighted triangulations are not yet supported in wasm

Testing

To make sure both predicate libraries produce the same results tests can be run for both features.

Testing with geogram_predicates

cargo test -p rita --features logging

Testing with robust

cargo test -p rita --no-default-features --features "std,wasm"

Base implementation

There is decent preliminary work done in the rust eco-system by Bastien Durix in the crate simple_delaunay_lib.

We forked this and re-fined by adding

• weighted triangulations for 2D and 3D
• adding geograms robust predicates
• adding novel method: eps-Circles

Theoretical Concepts

• extended for 2D weighted delaunay triangulations, which includes
  • the flippability check (check for an edge to be flippable and only then and if it is not regular flip it)
  • the 3->1 flip (with weights come possible redundant points, i.e. points not present in the final triangulation, which are achieved by 3->1 flips)
  • the in_power_circler predicate via geogram_predicates (this is the "in_circle test" for weighted points)
• extend for 3D weighted Delaunay triangulations, which includes
  • adding weights to the general data structure
  • use regular "in-circle" predicates in the appropriate places
  • do not insert redundant vertices

Code structure

• reused Node struct, for 3D (instead of duplicating)
• split each struct into own files for better readabilit and maintainability
• implement fmt::Display for structs that had print() or println()
• improved overall readabilit, e.g. by refactoring larger functions, documenting or adding comments
• ...

Conventions

• improved overall naming conventions
• applied clippy style guide, e.g. exchanging a lot of if else with match
• align naming in code with literature, i.e. flip namings, data structure namings etc.

Algorithmic Improvements

• remove unneccary push of 2 extra edges after 2->2 flip
• remove unused match case in should_flip_hedge()
• early out for match case in should_flip_hedge that always returns false i.e. Flip::None
• exchange geo::robust for geogram_predicates which has the same features plus:
  • perurbation of simplicity
  • arithmetic schemes
• add a naive version of last inserted triangle, which speeds up location (especially when using spatial sorting)

WIP

• add 3D Flipping Algo (there are just a few edge cases to fix. main work is done)
• extend 3D flipping algo for weighted cases

Acknowledgements

Thanks to Bastien Durix for his prior work on incremental Delaunay triangulations in rust.