ogeom_math/
bounds.rs

1//! Axis-aligned bounding boxes.
2//!
3//! Every use of a bounding box in a kernel is a *rejection* test: cull this
4//! pair, skip this subtree, prune this branch. So the one property that matters
5//! is that a box genuinely contains what it claims to. A box that is too large
6//! costs time; a box that is too small silently drops a real intersection, and
7//! nothing downstream can tell.
8//!
9//! Everything that produces an [`Aabb`] here therefore errs outward, and says
10//! how. Sampling a curve at a few parameters and taking the extremes would
11//! *not* qualify: the curve bulges between the samples.
12
13use core::fmt;
14
15use ogeom_core::Tolerances;
16
17use crate::{Point, Vector};
18
19/// An axis-aligned box, or the empty box.
20///
21/// The empty box is a distinct state rather than a degenerate one with reversed
22/// bounds: "no points at all" and "a box of zero size at the origin" answer
23/// containment questions differently, and conflating them makes an empty shape
24/// appear to be at the origin.
25#[derive(Debug, Clone, Copy, PartialEq)]
26pub struct Aabb {
27    /// `None` when empty.
28    extent: Option<(Point, Point)>,
29}
30
31impl Default for Aabb {
32    fn default() -> Self {
33        Self::EMPTY
34    }
35}
36
37impl Aabb {
38    /// A box containing nothing.
39    pub const EMPTY: Self = Self { extent: None };
40
41    /// A box containing exactly one point.
42    #[must_use]
43    pub const fn of_point(p: Point) -> Self {
44        Self {
45            extent: Some((p, p)),
46        }
47    }
48
49    /// A box spanning two corners, in either order.
50    #[must_use]
51    pub fn of_corners(a: Point, b: Point) -> Self {
52        Self {
53            extent: Some((a.min(b), a.max(b))),
54        }
55    }
56
57    /// A box containing every point given.
58    #[must_use]
59    pub fn of_points(points: &[Point]) -> Self {
60        points.iter().fold(Self::EMPTY, |acc, p| acc.with_point(*p))
61    }
62
63    /// Whether this box contains nothing.
64    #[must_use]
65    pub const fn is_empty(&self) -> bool {
66        self.extent.is_none()
67    }
68
69    /// The lower corner, or `None` if empty.
70    #[must_use]
71    pub fn low(&self) -> Option<Point> {
72        self.extent.map(|(low, _)| low)
73    }
74
75    /// The upper corner, or `None` if empty.
76    #[must_use]
77    pub fn high(&self) -> Option<Point> {
78        self.extent.map(|(_, high)| high)
79    }
80
81    /// The centre, or `None` if empty.
82    #[must_use]
83    pub fn centre(&self) -> Option<Point> {
84        self.extent.map(|(low, high)| low.midpoint(high))
85    }
86
87    /// The size along each axis, or zero if empty.
88    #[must_use]
89    pub fn size(&self) -> Vector {
90        self.extent.map_or(Vector::ZERO, |(low, high)| high - low)
91    }
92
93    /// The length of the longest axis, or zero if empty.
94    #[must_use]
95    pub fn extent_max(&self) -> f64 {
96        let s = self.size();
97        s.x.max(s.y).max(s.z)
98    }
99
100    /// The length of the diagonal, or zero if empty.
101    #[must_use]
102    pub fn diagonal(&self) -> f64 {
103        self.size().magnitude()
104    }
105
106    /// The enclosed volume, or zero if empty or flat.
107    #[must_use]
108    pub fn volume(&self) -> f64 {
109        let s = self.size();
110        s.x * s.y * s.z
111    }
112
113    /// This box grown to include `p`.
114    #[must_use]
115    pub fn with_point(&self, p: Point) -> Self {
116        match self.extent {
117            None => Self::of_point(p),
118            Some((low, high)) => Self {
119                extent: Some((low.min(p), high.max(p))),
120            },
121        }
122    }
123
124    /// This box grown to include `other`.
125    #[must_use]
126    pub fn union(&self, other: &Self) -> Self {
127        match (self.extent, other.extent) {
128            (None, _) => *other,
129            (_, None) => *self,
130            (Some((al, ah)), Some((bl, bh))) => Self {
131                extent: Some((al.min(bl), ah.max(bh))),
132            },
133        }
134    }
135
136    /// This box grown by `margin` in every direction.
137    ///
138    /// The usual way to account for a tolerance before a rejection test: two
139    /// shapes whose boxes miss by less than their tolerances may still touch.
140    #[must_use]
141    pub fn expanded(&self, margin: f64) -> Self {
142        match self.extent {
143            None => Self::EMPTY,
144            Some((low, high)) => {
145                let m = Vector::splat(margin.max(0.0));
146                Self {
147                    extent: Some((low - m, high + m)),
148                }
149            }
150        }
151    }
152
153    /// This box grown by the confusion tolerance.
154    #[must_use]
155    pub fn with_tolerance(&self, tol: Tolerances) -> Self {
156        self.expanded(tol.confusion())
157    }
158
159    /// Whether `p` lies inside, boundary included.
160    #[must_use]
161    pub fn contains(&self, p: Point) -> bool {
162        self.extent.is_some_and(|(low, high)| {
163            p.x >= low.x
164                && p.x <= high.x
165                && p.y >= low.y
166                && p.y <= high.y
167                && p.z >= low.z
168                && p.z <= high.z
169        })
170    }
171
172    /// Whether `other` lies entirely inside this box.
173    #[must_use]
174    pub fn contains_box(&self, other: &Self) -> bool {
175        match other.extent {
176            // Nothing is contained by anything, vacuously, including by the
177            // empty box.
178            None => true,
179            Some((low, high)) => self.contains(low) && self.contains(high),
180        }
181    }
182
183    /// Whether the two boxes share any point.
184    ///
185    /// The rejection test everything else is built on. An empty box intersects
186    /// nothing.
187    #[must_use]
188    pub fn intersects(&self, other: &Self) -> bool {
189        let (Some((al, ah)), Some((bl, bh))) = (self.extent, other.extent) else {
190            return false;
191        };
192        al.x <= bh.x && ah.x >= bl.x && al.y <= bh.y && ah.y >= bl.y && al.z <= bh.z && ah.z >= bl.z
193    }
194
195    /// The overlap of two boxes, or empty if they do not meet.
196    #[must_use]
197    pub fn intersection(&self, other: &Self) -> Self {
198        if !self.intersects(other) {
199            return Self::EMPTY;
200        }
201        let (Some((al, ah)), Some((bl, bh))) = (self.extent, other.extent) else {
202            return Self::EMPTY;
203        };
204        Self {
205            extent: Some((al.max(bl), ah.min(bh))),
206        }
207    }
208
209    /// The shortest distance from `p` to this box, zero if inside.
210    #[must_use]
211    pub fn distance_to(&self, p: Point) -> f64 {
212        let Some((low, high)) = self.extent else {
213            return f64::INFINITY;
214        };
215        // Per axis, how far outside the slab the point lies. Zero inside.
216        let outside = Vector::new(
217            (low.x - p.x).max(p.x - high.x).max(0.0),
218            (low.y - p.y).max(p.y - high.y).max(0.0),
219            (low.z - p.z).max(p.z - high.z).max(0.0),
220        );
221        outside.magnitude()
222    }
223
224    /// A lower bound on the distance between two boxes, zero if they meet.
225    ///
226    /// A *bound*, not the distance between the shapes inside them, which is why
227    /// it is only ever useful for rejection: if this exceeds a threshold the
228    /// shapes certainly do too.
229    #[must_use]
230    pub fn distance_to_box(&self, other: &Self) -> f64 {
231        let (Some((al, ah)), Some((bl, bh))) = (self.extent, other.extent) else {
232            return f64::INFINITY;
233        };
234        let gap = Vector::new(
235            (bl.x - ah.x).max(al.x - bh.x).max(0.0),
236            (bl.y - ah.y).max(al.y - bh.y).max(0.0),
237            (bl.z - ah.z).max(al.z - bh.z).max(0.0),
238        );
239        gap.magnitude()
240    }
241
242    /// The eight corners, or an empty list if the box is empty.
243    #[must_use]
244    pub fn corners(&self) -> Vec<Point> {
245        let Some((low, high)) = self.extent else {
246            return Vec::new();
247        };
248        let mut out = Vec::with_capacity(8);
249        for i in 0..8 {
250            out.push(Point::new(
251                if i & 1 == 0 { low.x } else { high.x },
252                if i & 2 == 0 { low.y } else { high.y },
253                if i & 4 == 0 { low.z } else { high.z },
254            ));
255        }
256        out
257    }
258
259    /// This box transformed, as the box of the transformed corners.
260    ///
261    /// The result contains the transformed box but is generally larger than the
262    /// tightest one: a rotated box is not axis-aligned, and its bounding box
263    /// must cover the rotation. Erring outward is the safe direction, and
264    /// repeatedly transforming a box therefore inflates it; transform the
265    /// geometry and re-bound instead of chaining this.
266    #[must_use]
267    pub fn transformed(&self, t: &crate::Transform) -> Self {
268        Self::of_points(
269            &self
270                .corners()
271                .iter()
272                .map(|p| t.apply(*p))
273                .collect::<Vec<_>>(),
274        )
275    }
276}
277
278impl fmt::Display for Aabb {
279    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
280        match self.extent {
281            None => f.write_str("empty"),
282            Some((low, high)) => write!(
283                f,
284                "[{:.6}, {:.6}, {:.6}] .. [{:.6}, {:.6}, {:.6}]",
285                low.x, low.y, low.z, high.x, high.y, high.z
286            ),
287        }
288    }
289}
290
291impl FromIterator<Point> for Aabb {
292    fn from_iter<I: IntoIterator<Item = Point>>(iter: I) -> Self {
293        iter.into_iter()
294            .fold(Self::EMPTY, |acc, p| acc.with_point(p))
295    }
296}
297
298#[cfg(test)]
299#[allow(clippy::unwrap_used)]
300mod tests {
301    use super::*;
302    use crate::{Axis, Transform};
303    use approx::assert_relative_eq;
304
305    const T: Tolerances = Tolerances::millimetres();
306
307    fn unit() -> Aabb {
308        Aabb::of_corners(Point::ORIGIN, Point::new(1.0, 1.0, 1.0))
309    }
310
311    #[test]
312    fn the_empty_box_is_distinct_from_a_zero_sized_one() {
313        // Conflating them makes an empty shape appear to be at the origin, and
314        // every containment question about it answers wrongly.
315        let empty = Aabb::EMPTY;
316        let degenerate = Aabb::of_point(Point::ORIGIN);
317
318        assert!(empty.is_empty());
319        assert!(!degenerate.is_empty());
320        assert!(!empty.contains(Point::ORIGIN));
321        assert!(degenerate.contains(Point::ORIGIN));
322        assert_eq!(empty.centre(), None);
323        assert_eq!(degenerate.centre(), Some(Point::ORIGIN));
324        assert!(!empty.intersects(&degenerate));
325        assert_eq!(empty.distance_to(Point::ORIGIN), f64::INFINITY);
326    }
327
328    #[test]
329    fn corners_are_taken_in_either_order() {
330        let a = Aabb::of_corners(Point::new(1.0, 2.0, 3.0), Point::ORIGIN);
331        let b = Aabb::of_corners(Point::ORIGIN, Point::new(1.0, 2.0, 3.0));
332        assert_eq!(a, b);
333        assert_eq!(a.low(), Some(Point::ORIGIN));
334        assert_eq!(a.high(), Some(Point::new(1.0, 2.0, 3.0)));
335    }
336
337    #[test]
338    fn union_grows_and_the_empty_box_is_its_identity() {
339        let a = Aabb::of_point(Point::ORIGIN);
340        let b = Aabb::of_point(Point::new(1.0, 2.0, 3.0));
341        let joined = a.union(&b);
342        assert_eq!(joined.low(), Some(Point::ORIGIN));
343        assert_eq!(joined.high(), Some(Point::new(1.0, 2.0, 3.0)));
344
345        assert_eq!(a.union(&Aabb::EMPTY), a);
346        assert_eq!(Aabb::EMPTY.union(&a), a);
347        assert_eq!(Aabb::EMPTY.union(&Aabb::EMPTY), Aabb::EMPTY);
348    }
349
350    #[test]
351    fn measurements_of_a_unit_box() {
352        let b = unit();
353        assert_eq!(b.size(), Vector::new(1.0, 1.0, 1.0));
354        assert_relative_eq!(b.volume(), 1.0);
355        assert_relative_eq!(b.extent_max(), 1.0);
356        assert_relative_eq!(b.diagonal(), 3.0_f64.sqrt());
357        assert_eq!(b.centre(), Some(Point::new(0.5, 0.5, 0.5)));
358        assert_eq!(b.corners().len(), 8);
359        assert!(Aabb::EMPTY.corners().is_empty());
360        assert_relative_eq!(Aabb::EMPTY.volume(), 0.0);
361    }
362
363    #[test]
364    fn containment_includes_the_boundary() {
365        // A rejection test that excluded the boundary would drop shapes that
366        // touch exactly, which is the case that matters most.
367        let b = unit();
368        assert!(b.contains(Point::ORIGIN));
369        assert!(b.contains(Point::new(1.0, 1.0, 1.0)));
370        assert!(b.contains(Point::new(0.5, 0.0, 1.0)));
371        assert!(!b.contains(Point::new(1.000_001, 0.5, 0.5)));
372    }
373
374    #[test]
375    fn boxes_that_touch_are_reported_as_intersecting() {
376        // Two shapes whose boxes meet exactly may well touch, and rejecting
377        // them would drop a real contact.
378        let a = unit();
379        let touching = Aabb::of_corners(Point::new(1.0, 0.0, 0.0), Point::new(2.0, 1.0, 1.0));
380        let apart = Aabb::of_corners(Point::new(1.001, 0.0, 0.0), Point::new(2.0, 1.0, 1.0));
381
382        assert!(a.intersects(&touching));
383        assert!(!a.intersects(&apart));
384        assert_relative_eq!(a.distance_to_box(&touching), 0.0);
385        assert_relative_eq!(a.distance_to_box(&apart), 0.001, epsilon = 1e-12);
386    }
387
388    #[test]
389    fn intersection_is_the_overlap_and_empty_when_there_is_none() {
390        let a = unit();
391        let b = Aabb::of_corners(Point::new(0.5, 0.5, 0.5), Point::new(2.0, 2.0, 2.0));
392        let overlap = a.intersection(&b);
393        assert_eq!(overlap.low(), Some(Point::new(0.5, 0.5, 0.5)));
394        assert_eq!(overlap.high(), Some(Point::new(1.0, 1.0, 1.0)));
395
396        let apart = Aabb::of_corners(Point::new(5.0, 5.0, 5.0), Point::new(6.0, 6.0, 6.0));
397        assert!(a.intersection(&apart).is_empty());
398        assert!(a.intersection(&Aabb::EMPTY).is_empty());
399    }
400
401    #[test]
402    fn distance_is_zero_inside_and_measured_from_the_nearest_face() {
403        let b = unit();
404        assert_relative_eq!(b.distance_to(Point::new(0.5, 0.5, 0.5)), 0.0);
405        assert_relative_eq!(
406            b.distance_to(Point::new(0.5, 0.5, 1.0)),
407            0.0,
408            epsilon = 1e-15
409        );
410        assert_relative_eq!(b.distance_to(Point::new(0.5, 0.5, 3.0)), 2.0);
411        // Diagonally outside: the distance combines every axis it is outside on.
412        assert_relative_eq!(
413            b.distance_to(Point::new(-3.0, -4.0, 0.5)),
414            5.0,
415            epsilon = 1e-15
416        );
417    }
418
419    #[test]
420    fn expansion_errs_outward_and_never_shrinks() {
421        let b = unit();
422        let grown = b.expanded(0.5);
423        assert_eq!(grown.low(), Some(Point::new(-0.5, -0.5, -0.5)));
424        assert!(grown.contains_box(&b));
425
426        // A negative margin would shrink the box, which for a rejection test
427        // means dropping shapes that are really there.
428        assert_eq!(b.expanded(-1.0), b);
429        assert!(Aabb::EMPTY.expanded(1.0).is_empty());
430        assert!(b.with_tolerance(T).contains_box(&b));
431    }
432
433    #[test]
434    fn transforming_a_box_errs_outward() {
435        // A rotated box is not axis-aligned, so its bound must cover the
436        // rotation. That means the result is larger than the tightest box round
437        // the rotated shape, which is the safe direction, and the reason to
438        // re-bound the geometry rather than chain this.
439        let b = unit();
440        let rotated = b.transformed(&Transform::rotation(Axis::Z, core::f64::consts::FRAC_PI_4));
441
442        for corner in b.corners() {
443            let moved = Transform::rotation(Axis::Z, core::f64::consts::FRAC_PI_4).apply(corner);
444            assert!(
445                rotated.contains(moved),
446                "corner {moved:?} escaped the bound"
447            );
448        }
449        assert!(
450            rotated.volume() > b.volume(),
451            "a rotation cannot tighten a bound"
452        );
453
454        // A translation, by contrast, is exact.
455        let moved = b.transformed(&Transform::translation(Vector::new(10.0, 0.0, 0.0)));
456        assert_relative_eq!(moved.volume(), b.volume(), epsilon = 1e-12);
457    }
458
459    #[test]
460    fn the_empty_box_is_contained_by_everything() {
461        assert!(unit().contains_box(&Aabb::EMPTY));
462        assert!(Aabb::EMPTY.contains_box(&Aabb::EMPTY));
463        assert!(!Aabb::EMPTY.contains_box(&unit()));
464    }
465
466    #[test]
467    fn collecting_points_builds_their_bound() {
468        let points = [
469            Point::new(1.0, 0.0, 0.0),
470            Point::new(-2.0, 5.0, 1.0),
471            Point::new(0.0, -1.0, 3.0),
472        ];
473        let from_iter: Aabb = points.iter().copied().collect();
474        assert_eq!(from_iter, Aabb::of_points(&points));
475        assert_eq!(from_iter.low(), Some(Point::new(-2.0, -1.0, 0.0)));
476        assert_eq!(from_iter.high(), Some(Point::new(1.0, 5.0, 3.0)));
477        for p in points {
478            assert!(from_iter.contains(p));
479        }
480        assert!(Aabb::of_points(&[]).is_empty());
481    }
482
483    #[test]
484    fn display_distinguishes_empty_from_degenerate() {
485        assert_eq!(Aabb::EMPTY.to_string(), "empty");
486        assert!(
487            Aabb::of_point(Point::ORIGIN)
488                .to_string()
489                .contains("0.000000")
490        );
491    }
492}
ogeom_math/bounds.rs

ogeom_math/
bounds.rs
