brepkit_math/
aabb.rs

1//! Axis-aligned bounding boxes for spatial queries.
2
3use crate::vec::{Point2, Point3, Vec2, Vec3};
4
5/// A 2D axis-aligned bounding box.
6#[derive(Debug, Clone, Copy, PartialEq)]
7#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
8pub struct Aabb2 {
9    /// Minimum corner.
10    pub min: Point2,
11    /// Maximum corner.
12    pub max: Point2,
13}
14
15impl Aabb2 {
16    /// Create an AABB from an iterator of points.
17    ///
18    /// # Panics
19    ///
20    /// Panics if the iterator is empty. Use [`Aabb2::try_from_points`] for
21    /// a fallible version.
22    #[must_use]
23    #[allow(clippy::expect_used)]
24    pub fn from_points(points: impl IntoIterator<Item = Point2>) -> Self {
25        Self::try_from_points(points).expect("at least one point required")
26    }
27
28    /// Create an AABB from an iterator of points, returning `None` if empty.
29    #[must_use]
30    pub fn try_from_points(points: impl IntoIterator<Item = Point2>) -> Option<Self> {
31        let mut iter = points.into_iter();
32        let first = iter.next()?;
33        let mut min = first;
34        let mut max = first;
35        for p in iter {
36            if p.x() < min.x() {
37                min.0[0] = p.x();
38            }
39            if p.y() < min.y() {
40                min.0[1] = p.y();
41            }
42            if p.x() > max.x() {
43                max.0[0] = p.x();
44            }
45            if p.y() > max.y() {
46                max.0[1] = p.y();
47            }
48        }
49        Some(Self { min, max })
50    }
51
52    /// Whether this box intersects another.
53    #[inline]
54    #[must_use]
55    pub fn intersects(self, other: Self) -> bool {
56        self.min.x() <= other.max.x()
57            && self.max.x() >= other.min.x()
58            && self.min.y() <= other.max.y()
59            && self.max.y() >= other.min.y()
60    }
61
62    /// Whether this box contains a point.
63    #[must_use]
64    pub fn contains_point(self, p: Point2) -> bool {
65        p.x() >= self.min.x()
66            && p.x() <= self.max.x()
67            && p.y() >= self.min.y()
68            && p.y() <= self.max.y()
69    }
70
71    /// Compute the union of two bounding boxes.
72    #[inline]
73    #[must_use]
74    pub const fn union(self, other: Self) -> Self {
75        Self {
76            min: Point2::new(
77                self.min.x().min(other.min.x()),
78                self.min.y().min(other.min.y()),
79            ),
80            max: Point2::new(
81                self.max.x().max(other.max.x()),
82                self.max.y().max(other.max.y()),
83            ),
84        }
85    }
86
87    /// Return a new box expanded by `margin` on each side.
88    #[inline]
89    #[must_use]
90    pub fn expanded(self, margin: f64) -> Self {
91        Self {
92            min: self.min + Vec2::new(-margin, -margin),
93            max: self.max + Vec2::new(margin, margin),
94        }
95    }
96}
97
98/// A 3D axis-aligned bounding box.
99#[derive(Debug, Clone, Copy, PartialEq)]
100#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
101pub struct Aabb3 {
102    /// Minimum corner.
103    pub min: Point3,
104    /// Maximum corner.
105    pub max: Point3,
106}
107
108impl Aabb3 {
109    /// Create an AABB from an iterator of points.
110    ///
111    /// # Panics
112    ///
113    /// Panics if the iterator is empty. Use [`Aabb3::try_from_points`] for
114    /// a fallible version.
115    #[must_use]
116    #[allow(clippy::expect_used)]
117    pub fn from_points(points: impl IntoIterator<Item = Point3>) -> Self {
118        Self::try_from_points(points).expect("at least one point required")
119    }
120
121    /// Create an AABB from an iterator of points, returning `None` if empty.
122    #[must_use]
123    pub fn try_from_points(points: impl IntoIterator<Item = Point3>) -> Option<Self> {
124        let mut iter = points.into_iter();
125        let first = iter.next()?;
126        let mut min = first;
127        let mut max = first;
128        for p in iter {
129            if p.x() < min.x() {
130                min.0[0] = p.x();
131            }
132            if p.y() < min.y() {
133                min.0[1] = p.y();
134            }
135            if p.z() < min.z() {
136                min.0[2] = p.z();
137            }
138            if p.x() > max.x() {
139                max.0[0] = p.x();
140            }
141            if p.y() > max.y() {
142                max.0[1] = p.y();
143            }
144            if p.z() > max.z() {
145                max.0[2] = p.z();
146            }
147        }
148        Some(Self { min, max })
149    }
150
151    /// Whether this box intersects another.
152    #[inline]
153    #[must_use]
154    pub fn intersects(self, other: Self) -> bool {
155        self.min.x() <= other.max.x()
156            && self.max.x() >= other.min.x()
157            && self.min.y() <= other.max.y()
158            && self.max.y() >= other.min.y()
159            && self.min.z() <= other.max.z()
160            && self.max.z() >= other.min.z()
161    }
162
163    /// Whether this box contains a point.
164    #[inline]
165    #[must_use]
166    pub fn contains_point(self, p: Point3) -> bool {
167        p.x() >= self.min.x()
168            && p.x() <= self.max.x()
169            && p.y() >= self.min.y()
170            && p.y() <= self.max.y()
171            && p.z() >= self.min.z()
172            && p.z() <= self.max.z()
173    }
174
175    /// Compute the union of two bounding boxes.
176    #[inline]
177    #[must_use]
178    pub const fn union(self, other: Self) -> Self {
179        Self {
180            min: Point3::new(
181                self.min.x().min(other.min.x()),
182                self.min.y().min(other.min.y()),
183                self.min.z().min(other.min.z()),
184            ),
185            max: Point3::new(
186                self.max.x().max(other.max.x()),
187                self.max.y().max(other.max.y()),
188                self.max.z().max(other.max.z()),
189            ),
190        }
191    }
192
193    /// Return a new box expanded by `margin` on each side.
194    #[inline]
195    #[must_use]
196    pub fn expanded(self, margin: f64) -> Self {
197        Self {
198            min: self.min + Vec3::new(-margin, -margin, -margin),
199            max: self.max + Vec3::new(margin, margin, margin),
200        }
201    }
202
203    /// Surface area of the box (used for SAH cost in BVH).
204    #[must_use]
205    pub fn surface_area(self) -> f64 {
206        let d = self.max - self.min;
207        2.0 * d.x().mul_add(d.y(), d.y().mul_add(d.z(), d.z() * d.x()))
208    }
209
210    /// Center point of the bounding box.
211    #[must_use]
212    pub fn center(self) -> Point3 {
213        Point3::new(
214            self.min.x().mul_add(0.5, self.max.x() * 0.5),
215            self.min.y().mul_add(0.5, self.max.y() * 0.5),
216            self.min.z().mul_add(0.5, self.max.z() * 0.5),
217        )
218    }
219
220    /// Whether the whole line through `origin` along `dir`, both ways,
221    /// meets this box (touching counts).
222    ///
223    /// A zero direction component is tested by the origin's coordinate
224    /// alone, so an origin lying on a face of the box with the line in that
225    /// face still meets it.
226    #[must_use]
227    pub fn line_intersects(self, origin: Point3, dir: Vec3) -> bool {
228        let mut lo = f64::NEG_INFINITY;
229        let mut hi = f64::INFINITY;
230        for (o, d, min, max) in [
231            (origin.x(), dir.x(), self.min.x(), self.max.x()),
232            (origin.y(), dir.y(), self.min.y(), self.max.y()),
233            (origin.z(), dir.z(), self.min.z(), self.max.z()),
234        ] {
235            if d == 0.0 {
236                if o < min || o > max {
237                    return false;
238                }
239                continue;
240            }
241            let (t1, t2) = ((min - o) / d, (max - o) / d);
242            lo = lo.max(t1.min(t2));
243            hi = hi.min(t1.max(t2));
244            if lo > hi {
245                return false;
246            }
247        }
248        true
249    }
250
251    /// Test whether a ray (origin + positive-t direction) intersects this box.
252    ///
253    /// Uses the slab method. Returns `true` if the ray hits the box at any
254    /// `t >= 0`.
255    #[must_use]
256    pub fn ray_intersects(self, origin: Point3, inv_dir: Vec3) -> bool {
257        let t1x = (self.min.x() - origin.x()) * inv_dir.x();
258        let t2x = (self.max.x() - origin.x()) * inv_dir.x();
259        let t1y = (self.min.y() - origin.y()) * inv_dir.y();
260        let t2y = (self.max.y() - origin.y()) * inv_dir.y();
261        let t1z = (self.min.z() - origin.z()) * inv_dir.z();
262        let t2z = (self.max.z() - origin.z()) * inv_dir.z();
263
264        let tmin = t1x.min(t2x).max(t1y.min(t2y)).max(t1z.min(t2z));
265        let tmax = t1x.max(t2x).min(t1y.max(t2y)).min(t1z.max(t2z));
266
267        tmax >= tmin.max(0.0)
268    }
269
270    /// Squared distance from a point to the closest point on the box.
271    #[must_use]
272    pub fn distance_squared_to_point(self, p: Point3) -> f64 {
273        let dx = (self.min.x() - p.x()).max(0.0).max(p.x() - self.max.x());
274        let dy = (self.min.y() - p.y()).max(0.0).max(p.y() - self.max.y());
275        let dz = (self.min.z() - p.z()).max(0.0).max(p.z() - self.max.z());
276        dx.mul_add(dx, dy.mul_add(dy, dz * dz))
277    }
278}
279
280#[cfg(test)]
281mod tests {
282    use super::*;
283
284    #[test]
285    fn aabb3_from_points() {
286        let bb = Aabb3::from_points([
287            Point3::new(1.0, 2.0, 3.0),
288            Point3::new(-1.0, 5.0, 0.0),
289            Point3::new(3.0, 0.0, 1.0),
290        ]);
291        assert_eq!(bb.min, Point3::new(-1.0, 0.0, 0.0));
292        assert_eq!(bb.max, Point3::new(3.0, 5.0, 3.0));
293    }
294
295    #[test]
296    fn aabb3_empty_returns_none() {
297        let bb = Aabb3::try_from_points(std::iter::empty());
298        assert!(bb.is_none());
299    }
300
301    #[test]
302    fn aabb3_intersects() {
303        let a = Aabb3::from_points([Point3::new(0.0, 0.0, 0.0), Point3::new(2.0, 2.0, 2.0)]);
304        let b = Aabb3::from_points([Point3::new(1.0, 1.0, 1.0), Point3::new(3.0, 3.0, 3.0)]);
305        let c = Aabb3::from_points([Point3::new(5.0, 5.0, 5.0), Point3::new(6.0, 6.0, 6.0)]);
306        assert!(a.intersects(b));
307        assert!(!a.intersects(c));
308    }
309
310    #[test]
311    fn aabb3_contains_point() {
312        let bb = Aabb3::from_points([Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0)]);
313        assert!(bb.contains_point(Point3::new(0.5, 0.5, 0.5)));
314        assert!(!bb.contains_point(Point3::new(2.0, 0.5, 0.5)));
315    }
316
317    #[test]
318    fn aabb3_union() {
319        let a = Aabb3::from_points([Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0)]);
320        let b = Aabb3::from_points([Point3::new(2.0, 2.0, 2.0), Point3::new(3.0, 3.0, 3.0)]);
321        let u = a.union(b);
322        assert_eq!(u.min, Point3::new(0.0, 0.0, 0.0));
323        assert_eq!(u.max, Point3::new(3.0, 3.0, 3.0));
324    }
325
326    #[test]
327    fn aabb3_expanded() {
328        let bb = Aabb3::from_points([Point3::new(1.0, 1.0, 1.0), Point3::new(2.0, 2.0, 2.0)]);
329        let ex = bb.expanded(0.5);
330        assert!((ex.min.x() - 0.5).abs() < 1e-14);
331        assert!((ex.max.x() - 2.5).abs() < 1e-14);
332    }
333
334    #[test]
335    fn aabb3_surface_area() {
336        let bb = Aabb3::from_points([Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 2.0, 3.0)]);
337        // SA = 2*(1*2 + 2*3 + 3*1) = 2*11 = 22
338        assert!((bb.surface_area() - 22.0).abs() < 1e-14);
339    }
340
341    #[test]
342    fn aabb3_distance_to_point() {
343        let bb = Aabb3::from_points([Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0)]);
344        // Point inside: distance is 0
345        assert!(bb.distance_squared_to_point(Point3::new(0.5, 0.5, 0.5)) < 1e-14);
346        // Point outside along x axis: distance = 1.0
347        assert!((bb.distance_squared_to_point(Point3::new(2.0, 0.5, 0.5)) - 1.0).abs() < 1e-14);
348    }
349
350    #[test]
351    fn aabb2_basic() {
352        let bb = Aabb2::from_points([Point2::new(0.0, 0.0), Point2::new(1.0, 1.0)]);
353        assert!(bb.contains_point(Point2::new(0.5, 0.5)));
354        assert!(!bb.contains_point(Point2::new(2.0, 0.5)));
355    }
356}
brepkit_math/aabb.rs

brepkit_math/
aabb.rs
