molgfx_math/bounds/
aabb.rs

1//! Axis-aligned bounds and bounding spheres.
2//!
3//! Building a bound over `n` points is `O(n)`; every query on a built bound
4//! is `O(1)`.
5
6use crate::{Mat4, Vec3};
7
8#[cfg(test)]
9#[path = "aabb_tests.rs"]
10mod tests;
11
12/// An axis-aligned bounding box in whichever space its points came from.
13///
14/// The empty box has `min > max` on every axis, so extending it with the
15/// first point produces a degenerate box at that point, and a union with any
16/// box returns the other operand.
17#[derive(Clone, Copy, PartialEq, Debug)]
18pub struct Aabb {
19    /// Componentwise minimum corner.
20    pub min: Vec3,
21    /// Componentwise maximum corner.
22    pub max: Vec3,
23}
24
25impl Default for Aabb {
26    #[inline]
27    fn default() -> Self {
28        Self::EMPTY
29    }
30}
31
32impl Aabb {
33    /// The identity of `union`: contains nothing, extends from any point.
34    pub const EMPTY: Self = Self {
35        min: Vec3::splat(f32::INFINITY),
36        max: Vec3::splat(f32::NEG_INFINITY),
37    };
38
39    /// Builds a box from explicit corners; callers guarantee `min <= max`.
40    #[must_use]
41    #[inline]
42    pub const fn new(min: Vec3, max: Vec3) -> Self {
43        Self { min, max }
44    }
45
46    /// Builds the tightest box over a set of points, `O(n)`.
47    /// Non-finite coordinates are skipped so one bad atom cannot poison the
48    /// bound of a whole structure.
49    #[must_use]
50    pub fn from_points(points: impl IntoIterator<Item = Vec3>) -> Self {
51        let mut aabb = Self::EMPTY;
52        for p in points {
53            aabb.extend(p);
54        }
55        aabb
56    }
57
58    /// True when no point has been added.
59    #[must_use]
60    #[inline]
61    pub fn is_empty(&self) -> bool {
62        self.min.x > self.max.x
63    }
64
65    /// Grows the box to contain `point`; non-finite points are ignored.
66    #[inline]
67    pub fn extend(&mut self, point: Vec3) {
68        if point.is_finite() {
69            self.min = self.min.min(point);
70            self.max = self.max.max(point);
71        }
72    }
73
74    /// Grows the box to contain a sphere of `radius` around `center`.
75    #[inline]
76    pub fn extend_sphere(&mut self, center: Vec3, radius: f32) {
77        if center.is_finite() && radius.is_finite() {
78            let r = Vec3::splat(radius.abs());
79            self.min = self.min.min(center - r);
80            self.max = self.max.max(center + r);
81        }
82    }
83
84    /// The smallest box containing both operands.
85    #[must_use]
86    #[inline]
87    pub fn union(&self, other: &Self) -> Self {
88        Self {
89            min: self.min.min(other.min),
90            max: self.max.max(other.max),
91        }
92    }
93
94    /// True when two non-empty boxes share any volume or boundary.
95    #[must_use]
96    #[inline]
97    pub fn overlaps(&self, other: &Self) -> bool {
98        !self.is_empty()
99            && !other.is_empty()
100            && self.min.x <= other.max.x
101            && self.min.y <= other.max.y
102            && self.min.z <= other.max.z
103            && other.min.x <= self.max.x
104            && other.min.y <= self.max.y
105            && other.min.z <= self.max.z
106    }
107
108    /// Center point; meaningless on an empty box.
109    #[must_use]
110    #[inline]
111    pub fn center(&self) -> Vec3 {
112        (self.min + self.max) * 0.5
113    }
114
115    /// Half the diagonal extent on each axis.
116    #[must_use]
117    #[inline]
118    pub fn half_extents(&self) -> Vec3 {
119        (self.max - self.min) * 0.5
120    }
121
122    /// The eight corner points, fixed order (x fastest, then y, then z).
123    #[must_use]
124    #[inline]
125    pub fn corners(&self) -> [Vec3; 8] {
126        let (lo, hi) = (self.min, self.max);
127        [
128            Vec3::new(lo.x, lo.y, lo.z),
129            Vec3::new(hi.x, lo.y, lo.z),
130            Vec3::new(lo.x, hi.y, lo.z),
131            Vec3::new(hi.x, hi.y, lo.z),
132            Vec3::new(lo.x, lo.y, hi.z),
133            Vec3::new(hi.x, lo.y, hi.z),
134            Vec3::new(lo.x, hi.y, hi.z),
135            Vec3::new(hi.x, hi.y, hi.z),
136        ]
137    }
138
139    /// The tightest axis-aligned box containing this box after an affine
140    /// transform: the transformed corners' bound.
141    #[must_use]
142    #[inline]
143    pub fn transform(&self, matrix: &Mat4) -> Self {
144        if self.is_empty() {
145            return Self::EMPTY;
146        }
147        let mut out = Self::EMPTY;
148        for corner in self.corners() {
149            out.extend(matrix.transform_point3(corner));
150        }
151        out
152    }
153
154    /// Slab test: the parametric interval where a ray overlaps the box, or
155    /// `None` when it misses. `inv_dir` is the componentwise reciprocal of
156    /// the ray direction (infinities from zero components behave correctly).
157    #[must_use]
158    #[inline]
159    pub fn ray_intersect(&self, origin: Vec3, inv_dir: Vec3) -> Option<(f32, f32)> {
160        let t0 = (self.min - origin) * inv_dir;
161        let t1 = (self.max - origin) * inv_dir;
162        let t_near = t0.min(t1).max_element();
163        let t_far = t0.max(t1).min_element();
164        if t_near <= t_far && t_far >= 0.0 {
165            Some((t_near.max(0.0), t_far))
166        } else {
167            None
168        }
169    }
170
171    /// The bounding sphere of the box: centered, radius to a corner.
172    #[must_use]
173    #[inline]
174    pub fn bounding_sphere(&self) -> BoundingSphere {
175        if self.is_empty() {
176            return BoundingSphere {
177                center: Vec3::ZERO,
178                radius: 0.0,
179            };
180        }
181        BoundingSphere {
182            center: self.center(),
183            radius: self.half_extents().length(),
184        }
185    }
186}
187
188/// A sphere enclosing a set of geometry; the shape cameras frame against.
189#[derive(Clone, Copy, PartialEq, Debug)]
190pub struct BoundingSphere {
191    /// Sphere center.
192    pub center: Vec3,
193    /// Sphere radius; never negative.
194    pub radius: f32,
195}
196
197impl BoundingSphere {
198    /// Encloses a set of points in two `O(n)` passes: centroid, then the
199    /// farthest distance from it. Not minimal, but tight enough for camera
200    /// framing and never smaller than the points it covers. The centroid
201    /// accumulates in f64 so summing a million single-precision coordinates
202    /// does not drift; only the result returns to f32.
203    #[must_use]
204    pub fn from_points(points: &[Vec3]) -> Self {
205        let mut sum = glam::DVec3::ZERO;
206        let mut count = 0u32;
207        for p in points {
208            if p.is_finite() {
209                sum += glam::Vec3::from(*p).as_dvec3();
210                count += 1;
211            }
212        }
213        if count == 0 {
214            return Self {
215                center: Vec3::ZERO,
216                radius: 0.0,
217            };
218        }
219        let center = Vec3::from((sum / f64::from(count)).as_vec3());
220        let mut radius_sq = 0.0f32;
221        for p in points {
222            if p.is_finite() {
223                radius_sq = radius_sq.max(center.distance_squared(*p));
224            }
225        }
226        Self {
227            center,
228            radius: radius_sq.sqrt(),
229        }
230    }
231}
molgfx_math/bounds/aabb.rs

molgfx_math/bounds/
aabb.rs
