Crate meshless_voronoi

An implementation of the Meshless Voronoi algorithm in Rust.

The algorithm is primarily aimed at generating 3D Voronoi diagrams, but can also be used to compute 1D and 2D Voronoi diagrams.

Like Voro++, this algorithm is meshless implying that no global geometry is constructed. Instead a cell-based approach is used and we only compute integrals (cell/face volumes and centroids) and connectivity information (it is possible to determine a cell’s neighbours).

The algorithm can generate Voronoi tessellations with a rectangular boundary or periodic boundary conditions and also supports computing a subset of the Voronoi tessellation.

If necessary, arbitrary precision arithmetic is used to treat degeneracies and to ensure globally consistent local geometry. See the appendix of this reference for more info:

Nicolas Ray, Dmitry Sokolov, Sylvain Lefebvre, Bruno Lévy. Meshless Voronoi on the GPU. ACM Transactions on Graphics, 2018, 37 (6), pp.1-12. 10.1145/3272127.3275092. hal-01927559

Features

• Construction of 1D, 2D and 3D Voronoi grids.

• Partial construction of grids.

• Parallel construction of the Voronoi grid.

• Saving Voronoi grids to HDF5 format.

• Evaluation of custom integrals for cells (e.g. weighted centroid) and faces (e.g. solid angles).

Integer Arithmetic Backend

You can select from five backends for arbitrary precision integer arithmetic. These all provide identical functionality and vary only in performance and licensing.

For most practical applications, the choice of backend does not significantly alter performance (see results for a perturbed grid below). However, for highly degenerate seed configurations – i.e. with many groups of more than four (almost) co-spherical seed points – many arbitrary precision arithmetic tests must be performed leading to some performance differences in such cases (see results for a perfect grid below).

Benchmarks for construction of a 3D Voronoi grid with 64³ seeds:

	Perfect grid	Perturbed grid
rug	2.062 s ± 0.005 s	1.308 s ± 0.008 s
malachite	2.846 s ± 0.016 s	1.293 s ± 0.005 s
ibig	3.105 s ± 0.048 s	1.320 s ± 0.022 s
dashu	3.249 s ± 0.091 s	1.313 s ± 0.009 s
num-bigint	4.852 s ± 0.078 s	1.301 s ± 0.004 s

See the next section for details.

Cargo Features

Note: the features for choosing a backend are all mutually exclusive.

• rayon (enabled by default) — Enable parallel construction of the Voronoi grid.
• ibig (enabled by default) — Use the ibig crate (MIT/Apache 2.0) as the arbitrary precision integer arithmetic backend. It generally has good performance, but can be up to 50% slower than the rug backend for highly degenerate seed configurations (e.g. a perfect grid).
• dashu — Use the dashu crate (MIT/Apache 2.0) as the arbitrary precision integer arithmetic backend. Similar performance to the ibig backend.
• malachite — Use the malachite crate as the arbitrary precision integer arithmetic backend. Warning: this changes the license to the more restrictive LGPL-3.0-only license. Slightly faster than the dashu backend (up to 40% slower than rug).
• num_bigint — Use the num_bigint crate (MIT/Apache 2.0) as the arbitrary precision integer arithmetic backend. Worst performance for degenerate seed configurations (measured up to 140% slower than rug).
• rug — Use the rug crate as arbitrary precision integer arithmetic backend. Warning: this changes the license to the more restrictive LGPL-3.0+ license. The fastest backend, but depends on GNU GMP via the gmp-mpfr-sys crate which requires a C compiler to build and hence has the slowest build time.
• hdf5 — Allow saving Voronoi grids to HDF5 format.

Modules

geometry

A few general-purpose geometry functions and structs, which might also be useful for users of this library.

integrals

Contains traits used to define custom integrals over cells and faces.

Structs

ConvexCell

Meshless representation of a Voronoi cell as an intersection of HalfSpaces.

HalfSpace

Oriented half-space. Voronoi cells are constructed as the intersection of HalfSpaces

Vertex

A vertex of a ConvexCell.

Voronoi

The main Voronoi struct.

VoronoiCell

A Voronoi cell.

VoronoiFace

A Voronoi face between two neighbouring generators.

VoronoiIntegrator

An meshless representation of the Voronoi mesh as a collection of independent ConvexCells.

Enums

Dimensionality

The dimensionality of the Voronoi tessellation.