axiolid_tetrahedralize/
lib.rs

1// SPDX-License-Identifier: MPL-2.0
2#![forbid(unsafe_code)]
3#![warn(missing_docs)]
4
5//! Exact 3D Delaunay tetrahedralization.
6//!
7//! [`Delaunay3`] is an incremental Bowyer-Watson triangulation of a point
8//! set in space. Its guarantees are stated and tested, not hoped for:
9//!
10//! - every tetrahedron is positively oriented, decided by the exact
11//!   `orient3d`;
12//! - no point lies strictly inside any tetrahedron's circumsphere, decided
13//!   by the exact `insphere`;
14//! - the boundary faces are exactly the convex hull, kept with an infinite
15//!   vertex rather than a bounding box, so nothing outside the input is
16//!   inserted;
17//! - degenerate input -- cospherical points such as a cubic grid, points in
18//!   the plane of a hull face, exact duplicates -- is handled by a symbolic
19//!   perturbation (simulation of simplicity) that depends only on the
20//!   coordinates, so the triangulation is the same for every insertion
21//!   order.
22//!
23//! # What is refused
24//!
25//! - Points spanning fewer than three dimensions have no tetrahedra:
26//!   [`Delaunay3::from_points`] reports [`Delaunay3Error::NotFullDimensional`]
27//!   (a coplanar set belongs to `axiolid-triangulate`).
28//! - Non-finite coordinates, and non-zero coordinates whose magnitude lies
29//!   outside `[2^-100, 2^100]`, where the degree-5 and degree-6 exact
30//!   predicates would leave binary64's normal range.
31//! - Weighted (regular) triangulation, and constraints: neither input
32//!   segments nor input faces are recovered (#126).
33//!
34//! # Example
35//!
36//! ```
37//! use axiolid_core::Point3;
38//! use axiolid_tetrahedralize::Delaunay3;
39//!
40//! // The eight corners of a cube are cospherical: several Delaunay
41//! // tetrahedralizations exist, and the perturbation picks one of them.
42//! let corners: Vec<Point3> = (0..8)
43//!     .map(|i| Point3::new(f64::from(i & 1), f64::from((i >> 1) & 1), f64::from(i >> 2)))
44//!     .collect();
45//! let delaunay = Delaunay3::from_points(&corners)?;
46//! let mesh = delaunay.tetrahedra();
47//! assert!(mesh.tetrahedra.len() == 5 || mesh.tetrahedra.len() == 6);
48//! assert_eq!(delaunay.hull_triangles().len(), 12);
49//! # Ok::<(), axiolid_tetrahedralize::Delaunay3Error>(())
50//! ```
51
52mod delaunay;
53mod hilbert;
54mod sos;
55
56pub use delaunay::{
57    Delaunay3, Delaunay3Error, Insertion, Tetrahedra, MAX_COORDINATE, MIN_COORDINATE,
58};