1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//! Adaptively sampled distance fields in ℝᴺ, with Lipschitz-certified pruning.
//!
//! An [`ADF`](adf::ADF) stores a signed distance field as a `2^N`-tree whose
//! leaves each hold a handful of [`Primitive`](adf::Primitive)s — a field
//! closure paired with an honest upper bound on its gradient. The tree
//! represents their pointwise `min`, so a field composed of millions of
//! primitives is sampled in logarithmic time by descending to the leaf covering
//! the query point, instead of evaluating every primitive.
//!
//! What makes that sound rather than merely fast is the Lipschitz bound. Every
//! decision the structure makes — whether a new primitive can be skipped,
//! whether a stored one has become redundant, which subtrees an insertion can
//! possibly change — is settled by branch-and-bound over
//! `f - g ≥ (f - g)(c) - (L_f + L_g)·h`, which either *proves* a region clean or
//! descends to a witness. A primitive is never dropped on a heuristic, only on a
//! proof, so the stored field never deviates from the `min` over everything
//! inserted.
//!
//! ```no_run
//! use adaptive_distance_field::{
//! adf::{ADF, Primitive},
//! geometry::{Point, VectorExt},
//! line_search::LineSearch,
//! sdf::{self, SDF},
//! };
//!
//! // seed a 3D field with the walls of the unit cube, positive inside
//! let mut field = ADF::<f64, 3>::new(6, vec![Primitive::new(sdf::boundary_rect)]);
//!
//! // climb to a local maximum of the free space — the deepest point around
//! let start = Point::from([0.3, 0.6, 0.5]);
//! let peak = LineSearch::default().optimize(|p| field.sdf(p), start);
//! let clearance = field.sdf(peak);
//!
//! // drop a ball there, and let the tree work out which cells that can affect
//! let ball = move |p: Point<f64, 3>| (p - peak).length() - clearance / 2.0;
//! field.insert_at_maximum(
//! adaptive_distance_field::geometry::DistPoint { point: peak, distance: clearance },
//! Primitive::new(ball),
//! );
//! ```
//!
//! # Layout
//!
//! - [`geometry`] — the vocabulary: [`Point`](geometry::Point) and
//! [`Vector`](geometry::Vector) (both [`nalgebra`]'s, re-exported so
//! downstream code can name the same versions), the axis-aligned
//! [`Aabb`](geometry::Aabb), [`BoundingBox`](geometry::BoundingBox), and the
//! [`Combinator`](geometry::Combinator) trait — every way to transform or
//! combine one field into another. Each combinator preserves or `max`-combines
//! its operands' constants, so a composed chain still reports an honest bound.
//! - [`sdf`] — the [`SDF`](sdf::SDF) and [`Lipschitz`](sdf::Lipschitz) traits
//! everything is written against, the field types the combinators return, and
//! [`sdf_geq_everywhere`](adf::sdf_geq_everywhere): the branch-and-bound
//! proof that underpins all of it. [`boundary_rect`](sdf::boundary_rect) seeds
//! a field with the walls of the unit cube.
//! - [`adf`] — the structure itself, over the [`quadtree`](adf::quadtree) arena.
//! - [`line_search`] — adaptive gradient ascent, for locating the maxima that
//! [`insert_at_maximum`](adf::ADF::insert_at_maximum) consumes.
//!
//! Dimension count is a compile-time constant throughout, so `ADF<f64, 2>` and
//! `ADF<f64, 3>` monomorphize separately and the 2D case costs exactly what a
//! quadtree-only implementation would.
//!
//! # Beyond this crate
//!
//! The [`space-filling`](https://docs.rs/space-filling/) crate builds on this
//! one: a catalogue of shape primitives in 2, 3, 4 and N dimensions, a discrete
//! bitmap solver for exact global maxima, batched parallel maxima search, and
//! 2D rasterization.
/// Re-exported: the geometry vocabulary is nalgebra's, so downstream code can
/// name the exact same versions.
pub use nalgebra;