Skip to main content

kernel_api/
aabb.rs

1//! An axis-aligned box in single precision: what a mesh spans, moved by a
2//! placement or a matrix as a box around its moved corners, so every
3//! caller that moves a box gets the same answer.
4
5/// An axis-aligned box from `min` to `max`, both corners included.
6#[derive(Clone, Copy, Debug, PartialEq)]
7pub struct Aabb {
8    pub min: [f32; 3],
9    pub max: [f32; 3],
10}
11
12impl Aabb {
13    pub const fn new(min: [f32; 3], max: [f32; 3]) -> Self {
14        Self { min, max }
15    }
16
17    /// The box around `points`; `None` when there are none.
18    pub fn around(points: impl IntoIterator<Item = [f32; 3]>) -> Option<Self> {
19        let mut points = points.into_iter();
20        let first = points.next()?;
21        Some(points.fold(Self::new(first, first), |b, p| b.with(p)))
22    }
23
24    /// The box grown to hold `p`.
25    pub fn with(self, p: [f32; 3]) -> Self {
26        Self {
27            min: std::array::from_fn(|k| self.min[k].min(p[k])),
28            max: std::array::from_fn(|k| self.max[k].max(p[k])),
29        }
30    }
31
32    /// The eight corners, corner `i` taking `max` along axis `k` where
33    /// bit `k` of `i` is set.
34    pub fn corners(&self) -> [[f32; 3]; 8] {
35        std::array::from_fn(|i| {
36            std::array::from_fn(|k| {
37                if i >> k & 1 == 0 {
38                    self.min[k]
39                } else {
40                    self.max[k]
41                }
42            })
43        })
44    }
45
46    /// The box around the corners once each is moved by `f`, which for a
47    /// rigid motion or any affine map holds everything the box held.
48    pub fn moved(&self, f: impl Fn([f32; 3]) -> [f32; 3]) -> Self {
49        let [first, rest @ ..] = self.corners().map(f);
50        rest.into_iter().fold(Self::new(first, first), Self::with)
51    }
52
53    /// The box moved by the affine column-major matrix `m` (`m[3]` the
54    /// translation; its last row is not read).
55    pub fn transformed(&self, m: &[[f32; 4]; 4]) -> Self {
56        self.moved(|p| {
57            std::array::from_fn(|r| m[0][r] * p[0] + m[1][r] * p[1] + m[2][r] * p[2] + m[3][r])
58        })
59    }
60
61    /// The smallest box holding both.
62    pub fn union(&self, other: &Self) -> Self {
63        self.with(other.min).with(other.max)
64    }
65
66    /// Whether `p` lies in the box, its faces included.
67    pub fn contains(&self, p: [f32; 3]) -> bool {
68        (0..3).all(|k| self.min[k] <= p[k] && p[k] <= self.max[k])
69    }
70}
71
72impl From<([f32; 3], [f32; 3])> for Aabb {
73    fn from((min, max): ([f32; 3], [f32; 3])) -> Self {
74        Self::new(min, max)
75    }
76}
77
78impl From<Aabb> for ([f32; 3], [f32; 3]) {
79    fn from(b: Aabb) -> Self {
80        (b.min, b.max)
81    }
82}
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87
88    fn close(a: [f32; 3], b: [f32; 3]) -> bool {
89        (0..3).all(|k| (a[k] - b[k]).abs() < 1e-5)
90    }
91
92    /// A box turned a quarter about Z and moved spans what its turned
93    /// corners do, by matrix or by function alike.
94    #[test]
95    fn a_turned_box_spans_its_turned_corners() {
96        let b = Aabb::new([1.0, 2.0, 3.0], [4.0, 6.0, 5.0]);
97        let (s, c) = (0.3f32.sin(), 0.3f32.cos());
98        // Column-major: a turn of 0.3 rad about Z, then (10, -1, 2).
99        let m = [
100            [c, s, 0.0, 0.0],
101            [-s, c, 0.0, 0.0],
102            [0.0, 0.0, 1.0, 0.0],
103            [10.0, -1.0, 2.0, 1.0],
104        ];
105        let turn = |p: [f32; 3]| {
106            [
107                c * p[0] - s * p[1] + 10.0,
108                s * p[0] + c * p[1] - 1.0,
109                p[2] + 2.0,
110            ]
111        };
112        let mut lo = [f32::INFINITY; 3];
113        let mut hi = [f32::NEG_INFINITY; 3];
114        for x in [1.0, 4.0] {
115            for y in [2.0, 6.0] {
116                for z in [3.0, 5.0] {
117                    let p = turn([x, y, z]);
118                    lo = std::array::from_fn(|k| lo[k].min(p[k]));
119                    hi = std::array::from_fn(|k| hi[k].max(p[k]));
120                }
121            }
122        }
123        for moved in [b.transformed(&m), b.moved(turn)] {
124            assert!(close(moved.min, lo) && close(moved.max, hi), "{moved:?}");
125        }
126    }
127
128    #[test]
129    fn union_contains_and_empty() {
130        assert_eq!(Aabb::around([]), None);
131        let a = Aabb::around([[0.0, 0.0, 0.0], [1.0, 2.0, -1.0]]).unwrap();
132        assert_eq!(a, Aabb::new([0.0, 0.0, -1.0], [1.0, 2.0, 0.0]));
133        let u = a.union(&Aabb::new([-3.0, 1.0, 0.5], [0.5, 1.5, 4.0]));
134        assert_eq!(u, Aabb::new([-3.0, 0.0, -1.0], [1.0, 2.0, 4.0]));
135        assert!(u.contains([1.0, 2.0, 4.0]) && u.contains([0.0, 1.0, 0.0]));
136        assert!(!u.contains([1.01, 1.0, 0.0]));
137    }
138}