Crates.io | meshless_voronoi |
lib.rs | meshless_voronoi |
version | 0.6.0 |
source | src |
created_at | 2023-02-03 13:23:42.482326 |
updated_at | 2024-04-10 09:36:38.996281 |
description | An implementation of the Meshless Voronoi algorithm. |
homepage | |
repository | https://github.com/yuyttenhove/meshless_voro |
max_upload_size | |
id | 775554 |
size | 173,457 |
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
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).
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.
Note: the features for choosing a backend are all mutually exclusive.
rayon
-- Enable parallel construction of the Voronoi grid.ibig
-- 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.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 toLicensed under:
ibig
, dashu
or num_bigint
arbitrary precision arithmetic backends.malachite
backendrug
backend.