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    /// Test whether a ray (origin + positive-t direction) intersects this box.
221    ///
222    /// Uses the slab method. Returns `true` if the ray hits the box at any
223    /// `t >= 0`.
224    #[must_use]
225    pub fn ray_intersects(self, origin: Point3, inv_dir: Vec3) -> bool {
226        let t1x = (self.min.x() - origin.x()) * inv_dir.x();
227        let t2x = (self.max.x() - origin.x()) * inv_dir.x();
228        let t1y = (self.min.y() - origin.y()) * inv_dir.y();
229        let t2y = (self.max.y() - origin.y()) * inv_dir.y();
230        let t1z = (self.min.z() - origin.z()) * inv_dir.z();
231        let t2z = (self.max.z() - origin.z()) * inv_dir.z();
232
233        let tmin = t1x.min(t2x).max(t1y.min(t2y)).max(t1z.min(t2z));
234        let tmax = t1x.max(t2x).min(t1y.max(t2y)).min(t1z.max(t2z));
235
236        tmax >= tmin.max(0.0)
237    }
238
239    /// Squared distance from a point to the closest point on the box.
240    #[must_use]
241    pub fn distance_squared_to_point(self, p: Point3) -> f64 {
242        let dx = (self.min.x() - p.x()).max(0.0).max(p.x() - self.max.x());
243        let dy = (self.min.y() - p.y()).max(0.0).max(p.y() - self.max.y());
244        let dz = (self.min.z() - p.z()).max(0.0).max(p.z() - self.max.z());
245        dx.mul_add(dx, dy.mul_add(dy, dz * dz))
246    }
247}
248
249#[cfg(test)]
250mod tests {
251    use super::*;
252
253    #[test]
254    fn aabb3_from_points() {
255        let bb = Aabb3::from_points([
256            Point3::new(1.0, 2.0, 3.0),
257            Point3::new(-1.0, 5.0, 0.0),
258            Point3::new(3.0, 0.0, 1.0),
259        ]);
260        assert_eq!(bb.min, Point3::new(-1.0, 0.0, 0.0));
261        assert_eq!(bb.max, Point3::new(3.0, 5.0, 3.0));
262    }
263
264    #[test]
265    fn aabb3_empty_returns_none() {
266        let bb = Aabb3::try_from_points(std::iter::empty());
267        assert!(bb.is_none());
268    }
269
270    #[test]
271    fn aabb3_intersects() {
272        let a = Aabb3::from_points([Point3::new(0.0, 0.0, 0.0), Point3::new(2.0, 2.0, 2.0)]);
273        let b = Aabb3::from_points([Point3::new(1.0, 1.0, 1.0), Point3::new(3.0, 3.0, 3.0)]);
274        let c = Aabb3::from_points([Point3::new(5.0, 5.0, 5.0), Point3::new(6.0, 6.0, 6.0)]);
275        assert!(a.intersects(b));
276        assert!(!a.intersects(c));
277    }
278
279    #[test]
280    fn aabb3_contains_point() {
281        let bb = Aabb3::from_points([Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0)]);
282        assert!(bb.contains_point(Point3::new(0.5, 0.5, 0.5)));
283        assert!(!bb.contains_point(Point3::new(2.0, 0.5, 0.5)));
284    }
285
286    #[test]
287    fn aabb3_union() {
288        let a = Aabb3::from_points([Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0)]);
289        let b = Aabb3::from_points([Point3::new(2.0, 2.0, 2.0), Point3::new(3.0, 3.0, 3.0)]);
290        let u = a.union(b);
291        assert_eq!(u.min, Point3::new(0.0, 0.0, 0.0));
292        assert_eq!(u.max, Point3::new(3.0, 3.0, 3.0));
293    }
294
295    #[test]
296    fn aabb3_expanded() {
297        let bb = Aabb3::from_points([Point3::new(1.0, 1.0, 1.0), Point3::new(2.0, 2.0, 2.0)]);
298        let ex = bb.expanded(0.5);
299        assert!((ex.min.x() - 0.5).abs() < 1e-14);
300        assert!((ex.max.x() - 2.5).abs() < 1e-14);
301    }
302
303    #[test]
304    fn aabb3_surface_area() {
305        let bb = Aabb3::from_points([Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 2.0, 3.0)]);
306        // SA = 2*(1*2 + 2*3 + 3*1) = 2*11 = 22
307        assert!((bb.surface_area() - 22.0).abs() < 1e-14);
308    }
309
310    #[test]
311    fn aabb3_distance_to_point() {
312        let bb = Aabb3::from_points([Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0)]);
313        // Point inside: distance is 0
314        assert!(bb.distance_squared_to_point(Point3::new(0.5, 0.5, 0.5)) < 1e-14);
315        // Point outside along x axis: distance = 1.0
316        assert!((bb.distance_squared_to_point(Point3::new(2.0, 0.5, 0.5)) - 1.0).abs() < 1e-14);
317    }
318
319    #[test]
320    fn aabb2_basic() {
321        let bb = Aabb2::from_points([Point2::new(0.0, 0.0), Point2::new(1.0, 1.0)]);
322        assert!(bb.contains_point(Point2::new(0.5, 0.5)));
323        assert!(!bb.contains_point(Point2::new(2.0, 0.5)));
324    }
325}
brepkit_math/aabb.rs

brepkit_math/
aabb.rs
