all_is_cubes_base/math/
aab.rs

1use core::cmp::Ordering;
2use core::fmt;
3use core::iter::FusedIterator;
4
5use euclid::{Point3D, Size3D, Vector3D};
6
7/// Acts as polyfill for float methods
8#[cfg(not(feature = "std"))]
9#[allow(unused_imports)]
10use num_traits::float::FloatCore as _;
11
12use crate::math::{
13    Axis, Cube, Face6, FreeCoordinate, FreePoint, FreeVector, GridAab, GridCoordinate, LineVertex,
14    Wireframe,
15};
16
17/// Axis-Aligned Box data type.
18///
19/// Note that this has continuous coordinates, and a discrete analogue exists as
20/// [`GridAab`].
21///
22#[doc = include_str!("../serde-warning.md")]
23// TODO(euclid migration): Replace this with `euclid` box type? Probably not.
24#[derive(Copy, Clone, PartialEq)]
25pub struct Aab {
26    // TODO: Should we be using NotNan coordinates?
27    // The upper > lower checks will reject NaNs anyway.
28    //
29    // TODO: Consider what to do about equality-but-not-equivalence of negative zero.
30    lower_bounds: FreePoint,
31    upper_bounds: FreePoint,
32}
33
34impl Aab {
35    /// The [`Aab`] of zero size at the origin.
36    pub const ZERO: Aab = Aab {
37        lower_bounds: Point3D::new(0., 0., 0.),
38        upper_bounds: Point3D::new(0., 0., 0.),
39    };
40
41    /// Constructs an [`Aab`] from individual coordinates.
42    #[inline]
43    #[track_caller]
44    pub fn new(
45        lx: FreeCoordinate,
46        hx: FreeCoordinate,
47        ly: FreeCoordinate,
48        hy: FreeCoordinate,
49        lz: FreeCoordinate,
50        hz: FreeCoordinate,
51    ) -> Self {
52        Self::from_lower_upper(Point3D::new(lx, ly, lz), Point3D::new(hx, hy, hz))
53    }
54
55    /// Constructs an [`Aab`] from most-negative and most-positive corner points.
56    ///
57    /// Panics if the points are not in the proper order or if they are NaN.
58    #[inline]
59    #[track_caller]
60    pub fn from_lower_upper(
61        lower_bounds: impl Into<FreePoint>,
62        upper_bounds: impl Into<FreePoint>,
63    ) -> Self {
64        let lower_bounds = lower_bounds.into();
65        let upper_bounds = upper_bounds.into();
66        match Self::checked_from_lower_upper(lower_bounds, upper_bounds) {
67            Some(aab) => aab,
68            None => panic!(
69                "invalid AAB points that are misordered or NaN: \
70                lower {lower_bounds:?} upper {upper_bounds:?}"
71            ),
72        }
73    }
74
75    /// Constructs an [`Aab`] from most-negative and most-positive corner points.
76    ///
77    /// Returns [`None`] if the points are not in the proper order or if they are NaN.
78    // TODO: Make this public but give it an error type?
79    pub(crate) fn checked_from_lower_upper(
80        lower_bounds: FreePoint,
81        upper_bounds: FreePoint,
82    ) -> Option<Self> {
83        if lower_bounds.x <= upper_bounds.x
84            && lower_bounds.y <= upper_bounds.y
85            && lower_bounds.z <= upper_bounds.z
86        {
87            Some(Self {
88                lower_bounds,
89                upper_bounds,
90            })
91        } else {
92            None
93        }
94    }
95
96    /// The most negative corner of the box, as a [`Point3D`].
97    #[inline]
98    pub const fn lower_bounds_p(&self) -> FreePoint {
99        self.lower_bounds
100    }
101
102    /// The most positive corner of the box, as a [`Point3D`].
103    #[inline]
104    pub const fn upper_bounds_p(&self) -> FreePoint {
105        self.upper_bounds
106    }
107
108    /// The most negative corner of the box, as a [`Vector3D`].
109    #[inline]
110    pub fn lower_bounds_v(&self) -> FreeVector {
111        self.lower_bounds.to_vector()
112    }
113
114    /// The most positive corner of the box, as a [`Vector3D`].
115    #[inline]
116    pub fn upper_bounds_v(&self) -> FreeVector {
117        self.upper_bounds.to_vector()
118    }
119
120    /// Returns the position of the identified face of the box on the axis it is
121    /// perpendicular to.
122    ///
123    /// Note that negative faces' coordinates _are_ inverted; that is, all results
124    /// will be positive if the box contains its origin.
125    #[inline]
126    pub fn face_coordinate(&self, face: Face6) -> FreeCoordinate {
127        match face {
128            Face6::NX => -self.lower_bounds.x,
129            Face6::NY => -self.lower_bounds.y,
130            Face6::NZ => -self.lower_bounds.z,
131            Face6::PX => self.upper_bounds.x,
132            Face6::PY => self.upper_bounds.y,
133            Face6::PZ => self.upper_bounds.z,
134        }
135    }
136
137    /// Size of the box in each axis; equivalent to
138    /// `self.upper_bounds() - self.lower_bounds()`.
139    ///
140    /// Note that due to floating-point rounding, translating one corner point by the size
141    /// does not necessarily exactly reach the opposite corner.
142    /// (See the [Sterbenz lemma](https://en.wikipedia.org/wiki/Sterbenz_lemma) for when
143    /// it does.)
144    /// Therefore, in cases where exact comparisons matter, take care to prefer the corner
145    /// points over calculating with the size.
146    #[inline]
147    pub fn size(&self) -> Size3D<FreeCoordinate, Cube> {
148        Size3D::from(self.upper_bounds - self.lower_bounds)
149    }
150
151    /// The center of the enclosed volume.
152    ///
153    /// ```
154    /// # extern crate all_is_cubes_base as all_is_cubes;
155    /// use all_is_cubes::math::{Aab, FreePoint};
156    ///
157    /// let aab = Aab::new(1.0, 2.0, 3.0, 4.0, 5.0, 6.0);
158    /// assert_eq!(aab.center(), FreePoint::new(1.5, 3.5, 5.5));
159    /// ```
160    #[inline]
161    pub fn center(&self) -> FreePoint {
162        (self.lower_bounds + self.upper_bounds.to_vector()) * 0.5
163    }
164
165    /// Iterates over the eight corner points of the box.
166    /// The ordering is deterministic but not currently declared stable.
167    #[doc(hidden)]
168    #[inline]
169    pub fn corner_points(
170        self,
171    ) -> impl DoubleEndedIterator<Item = FreePoint> + ExactSizeIterator + FusedIterator {
172        let l = self.lower_bounds;
173        let u = self.upper_bounds;
174        (0..8).map(move |i| {
175            Point3D::new(
176                if i & 1 == 0 { l.x } else { u.x },
177                if i & 2 == 0 { l.y } else { u.y },
178                if i & 4 == 0 { l.z } else { u.z },
179            )
180        })
181    }
182
183    /// Returns whether this AAB, including the boundary, contains the point.
184    ///
185    /// TODO: example + tests
186    #[inline]
187    pub fn contains(&self, point: FreePoint) -> bool {
188        // I tried changing this to an Iterator::all() and the asm was longer.
189        // I tried changing this to be completely unrolled and it was more or less the same.
190        for axis in Axis::ALL {
191            if !(self.lower_bounds[axis] <= point[axis] && point[axis] <= self.upper_bounds[axis]) {
192                return false;
193            }
194        }
195        true
196    }
197
198    /// Returns whether this AAB, including the boundary, intersects the other AAB.
199    ///
200    /// TODO: example + tests
201    #[inline]
202    pub fn intersects(&self, other: Aab) -> bool {
203        for axis in Axis::ALL {
204            let intersection_min = self.lower_bounds[axis].max(other.lower_bounds[axis]);
205            let intersection_max = self.upper_bounds[axis].min(other.upper_bounds[axis]);
206            match intersection_min.partial_cmp(&intersection_max) {
207                Some(Ordering::Less | Ordering::Equal) => {}
208                _ => return false,
209            }
210        }
211        true
212    }
213
214    /// Returns the smallest [`Aab`] which contains every point the two inputs contain,
215    /// including boundary points.
216    #[inline]
217    #[must_use]
218    pub fn union(self, other: Self) -> Self {
219        Self {
220            // No NaN cases here!
221            lower_bounds: self.lower_bounds.min(other.lower_bounds),
222            upper_bounds: self.upper_bounds.max(other.upper_bounds),
223        }
224    }
225
226    /// Extend the bounds of `self` so that `point` is on the interior or edge of this.
227    ///
228    /// If any coordinate is NaN, the box is unchanged on that axis.
229    ///
230    /// # Example
231    ///
232    /// ```
233    /// # extern crate all_is_cubes_base as all_is_cubes;
234    /// use all_is_cubes::math::{Aab, FreePoint};
235    ///
236    /// assert_eq!(
237    ///     Aab::ZERO.union_point(FreePoint::new(2., 5., 10.)),
238    ///     Aab::from_lower_upper([0., 0., 0.], [2., 5., 10.]),
239    /// );
240    /// ```
241    #[inline]
242    #[must_use]
243    pub fn union_point(self, point: FreePoint) -> Self {
244        Self {
245            // Note that Point3D::min returns components from the second argument on NaN
246            lower_bounds: point.min(self.lower_bounds),
247            upper_bounds: point.max(self.upper_bounds),
248        }
249    }
250
251    /// Returns a random point within this box, using inclusive ranges
252    /// (`lower_bounds[axis] ≤ random_point()[axis] ≤ upper_bounds[axis]`).
253    #[allow(clippy::missing_inline_in_public_items)]
254    pub fn random_point(self, rng: &mut impl rand::Rng) -> FreePoint {
255        FreePoint::new(
256            rng.gen_range(self.lower_bounds.x..=self.upper_bounds.x),
257            rng.gen_range(self.lower_bounds.y..=self.upper_bounds.y),
258            rng.gen_range(self.lower_bounds.z..=self.upper_bounds.z),
259        )
260    }
261
262    /// Translate this box by the specified offset.
263    ///
264    /// Note that due to rounding error, the result may not have the same size.
265    #[inline]
266    #[must_use]
267    #[track_caller] // in case of NaN
268    pub fn translate(self, offset: FreeVector) -> Self {
269        Self::from_lower_upper(self.lower_bounds + offset, self.upper_bounds + offset)
270    }
271
272    /// Scale this AAB by the given amount (about the zero point, not its center).
273    #[must_use]
274    #[inline]
275    pub fn scale(self, scalar: FreeCoordinate) -> Self {
276        Self::from_lower_upper(self.lower_bounds * scalar, self.upper_bounds * scalar)
277    }
278
279    /// Enlarges the AAB by moving each face outward by the specified distance (or inward
280    /// if negative).
281    ///
282    /// If this would result in a negative or NaN size, produces a zero size AAB located
283    /// at the center point of `self`.
284    ///
285    /// ```
286    /// # extern crate all_is_cubes_base as all_is_cubes;
287    /// use all_is_cubes::math::Aab;
288    ///
289    /// assert_eq!(
290    ///     Aab::new(1.0, 2.0, 3.0, 4.0, 5.0, 6.0).expand(0.25),
291    ///     Aab::new(0.75, 2.25, 2.75, 4.25, 4.75, 6.25)
292    /// );
293    /// ````
294    #[must_use]
295    #[inline]
296    pub fn expand(self, distance: FreeCoordinate) -> Self {
297        // We could imagine a non-uniform version of this, but the fully general one
298        // looks a lot like generally constructing a new Aab.
299        let distance_vec = Vector3D::splat(distance);
300        match Self::checked_from_lower_upper(
301            self.lower_bounds - distance_vec,
302            self.upper_bounds + distance_vec,
303        ) {
304            Some(aab) => aab,
305            None => {
306                let center = self.center();
307                Aab::from_lower_upper(center, center)
308            }
309        }
310    }
311
312    #[inline]
313    #[doc(hidden)] // Not public because this is an odd interface that primarily helps with collision.
314    pub fn leading_corner(&self, direction: FreeVector) -> FreeVector {
315        let mut leading_corner = Vector3D::zero();
316        for axis in Axis::ALL {
317            if direction[axis] >= 0.0 {
318                leading_corner[axis] = self.upper_bounds[axis];
319            } else {
320                leading_corner[axis] = self.lower_bounds[axis];
321            }
322        }
323        leading_corner
324    }
325
326    /// Construct the [`GridAab`] containing all cubes this [`Aab`] intersects.
327    ///
328    /// Grid cubes are considered to be half-open ranges, so, for example, an [`Aab`] with
329    /// exact integer bounds on some axis will convert exactly as one might intuitively
330    /// expect, while non-integer bounds will be rounded outward:
331    ///
332    /// ```
333    /// # extern crate all_is_cubes_base as all_is_cubes;
334    /// use all_is_cubes::math::{Aab, GridAab};
335    ///
336    /// let grid_aab = Aab::from_lower_upper([3.0, 0.5, 0.0], [5.0, 1.5, 1.0])
337    ///     .round_up_to_grid();
338    /// assert_eq!(grid_aab, GridAab::from_lower_upper([3, 0, 0], [5, 2, 1]));
339    ///
340    /// assert!(grid_aab.contains_cube([4, 1, 0].into()));
341    /// assert!(!grid_aab.contains_cube([5, 1, 0].into()));
342    /// ```
343    ///
344    /// If the floating-point coordinates are out of [`GridCoordinate`]'s numeric range,
345    /// then they will be clamped.
346    ///
347    /// ```
348    /// # extern crate all_is_cubes_base as all_is_cubes;
349    /// # use all_is_cubes::math::{Aab, GridAab};
350    /// use all_is_cubes::math::{FreeCoordinate, GridCoordinate};
351    ///
352    /// assert_eq!(
353    ///     Aab::from_lower_upper(
354    ///         [3.0, 0.0, 0.0],
355    ///         [(GridCoordinate::MAX as FreeCoordinate) * 10.0, 1.0, 1.0],
356    ///     ).round_up_to_grid(),
357    ///     GridAab::from_lower_upper([3, 0, 0], [GridCoordinate::MAX, 1, 1]),
358    /// );
359    /// assert_eq!(
360    ///     Aab::from_lower_upper(
361    ///         [3.0, 0.0, 0.0],
362    ///         [FreeCoordinate::INFINITY, 1.0, 1.0],
363    ///     ).round_up_to_grid(),
364    ///     GridAab::from_lower_upper([3, 0, 0], [GridCoordinate::MAX, 1, 1]),
365    /// );
366    /// ```
367    ///
368    /// (There is no handling of NaN, because [`Aab`] does not allow NaN values.)
369    #[inline]
370    pub fn round_up_to_grid(self) -> GridAab {
371        GridAab::from_lower_upper(
372            self.lower_bounds.map(|c| c.floor() as GridCoordinate),
373            self.upper_bounds.map(|c| c.ceil() as GridCoordinate),
374        )
375    }
376}
377
378impl fmt::Debug for Aab {
379    #[allow(clippy::missing_inline_in_public_items)]
380    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
381        let Aab {
382            lower_bounds: l,
383            upper_bounds: u,
384        } = *self;
385        f.debug_tuple("Aab")
386            .field(&(l.x..=u.x))
387            .field(&(l.y..=u.y))
388            .field(&(l.z..=u.z))
389            .finish()
390    }
391}
392
393/// [`Aab`] rejects NaN values, so it can implement [`Eq`]
394/// even though it contains floats.
395impl Eq for Aab {}
396
397impl Wireframe for Aab {
398    #[inline(never)]
399    fn wireframe_points<E>(&self, output: &mut E)
400    where
401        E: Extend<LineVertex>,
402    {
403        let mut vertices = [LineVertex::from(FreePoint::origin()); 24];
404        let l = self.lower_bounds_p();
405        let u = self.upper_bounds_p();
406        for axis_0 in Axis::ALL {
407            let vbase = usize::from(axis_0) * 8;
408            let axis_1 = axis_0.increment();
409            let axis_2 = axis_0.decrement();
410            let mut p = l;
411            // Walk from lower to upper in a helix.
412            vertices[vbase].position = p;
413            p[axis_0] = u[axis_0];
414            vertices[vbase + 1].position = p;
415            vertices[vbase + 2].position = p;
416            p[axis_1] = u[axis_1];
417            vertices[vbase + 3].position = p;
418            vertices[vbase + 4].position = p;
419            p[axis_2] = u[axis_2];
420            vertices[vbase + 5].position = p;
421            // Go back and fill in the remaining bar.
422            p[axis_2] = l[axis_2];
423            vertices[vbase + 6].position = p;
424            p[axis_0] = l[axis_0];
425            vertices[vbase + 7].position = p;
426        }
427        output.extend(vertices);
428    }
429}
430
431#[cfg(test)]
432mod tests {
433    use super::*;
434    use alloc::vec::Vec;
435    use euclid::point3;
436
437    #[test]
438    fn new_wrong_order() {
439        assert_eq!(
440            Aab::checked_from_lower_upper(point3(2., 1., 1.), point3(1., 2., 2.)),
441            None
442        );
443        assert_eq!(
444            Aab::checked_from_lower_upper(point3(1., 2., 1.), point3(2., 1., 2.)),
445            None
446        );
447        assert_eq!(
448            Aab::checked_from_lower_upper(point3(1., 1., 2.), point3(2., 2., 1.)),
449            None
450        );
451    }
452
453    #[test]
454    fn new_nan() {
455        assert_eq!(
456            Aab::checked_from_lower_upper(point3(0., 0., 0.), point3(1., 1., f64::NAN)),
457            None
458        );
459    }
460
461    #[test]
462    #[should_panic = "invalid AAB points that are misordered or NaN: lower (0.0, 0.0, 0.0) upper (1.0, 1.0, NaN)"]
463    fn new_panic_message() {
464        Aab::from_lower_upper([0., 0., 0.], [1., 1., f64::NAN]);
465    }
466
467    #[test]
468    /// Test `Debug` formatting. Note this should be similar to the [`GridAab`]
469    /// formatting.
470    fn debug() {
471        let aab = Aab::new(1.0000001, 2.0, 3.0, 4.0, 5.0, 6.0);
472        assert_eq!(
473            format!("{aab:?}"),
474            "Aab(1.0000001..=2.0, 3.0..=4.0, 5.0..=6.0)"
475        );
476        assert_eq!(
477            format!("{aab:#?}\n"),
478            indoc::indoc! {"
479                Aab(
480                    1.0000001..=2.0,
481                    3.0..=4.0,
482                    5.0..=6.0,
483                )
484            "}
485        );
486    }
487
488    #[test]
489    fn union_point_nan() {
490        assert_eq!(
491            Aab::ZERO.union_point(FreePoint::new(2., f64::NAN, 10.)),
492            Aab::from_lower_upper([0., 0., 0.], [2., 0., 10.]),
493        );
494    }
495
496    #[test]
497    fn expand_nan() {
498        let aab = Aab::new(1.0, 2.0, 3.0, 4.0, 5.0, 6.0);
499        assert_eq!(
500            aab.expand(FreeCoordinate::NAN),
501            Aab::from_lower_upper(aab.center(), aab.center()),
502        );
503    }
504
505    #[test]
506    fn expand_negative_failure() {
507        let aab = Aab::new(1.0, 2.0, 3.0, 4.0, 5.0, 6.0);
508        assert_eq!(
509            aab.expand(-10.0),
510            Aab::from_lower_upper(aab.center(), aab.center()),
511        );
512    }
513
514    #[test]
515    fn expand_negative_success() {
516        let aab = Aab::new(1.0, 2.0, 3.0, 4.0, 5.0, 6.0);
517        assert_eq!(
518            aab.expand(-0.25),
519            Aab::new(1.25, 1.75, 3.25, 3.75, 5.25, 5.75),
520        );
521    }
522
523    #[test]
524    fn expand_inf() {
525        const INF: FreeCoordinate = FreeCoordinate::INFINITY;
526        assert_eq!(
527            Aab::new(1.0, 2.0, 3.0, 4.0, 5.0, 6.0).expand(INF),
528            Aab::new(-INF, INF, -INF, INF, -INF, INF),
529        );
530    }
531
532    #[test]
533    fn wireframe_smoke_test() {
534        let aab: Aab = Cube::new(1, 2, 3).aab();
535        let mut wireframe: Vec<LineVertex> = Vec::new();
536        aab.wireframe_points(&mut wireframe);
537        for LineVertex { position, color } in wireframe {
538            assert!(color.is_none());
539            assert!(position.x == 1.0 || position.x == 2.0);
540            assert!(position.y == 2.0 || position.y == 3.0);
541            assert!(position.z == 3.0 || position.z == 4.0);
542        }
543    }
544
545    #[test]
546    fn leading_corner_consistency() {
547        let aab = Aab::new(-1.1, 2.2, -3.3, 4.4, -5.5, 6.6);
548        for direction in (-1..=1)
549            .zip(-1..=1)
550            .zip(-1..=1)
551            .map(|((x, y), z)| Vector3D::new(x, y, z).map(FreeCoordinate::from))
552        {
553            let leading_corner = aab.leading_corner(direction);
554
555            for axis in Axis::ALL {
556                // Note that this condition is not true in general, but only if the AAB
557                // contains the origin.
558                assert_eq!(leading_corner[axis].signum(), direction[axis].signum());
559            }
560        }
561    }
562
563    /// This would be a doc test except `corner_points` is not public for now
564    /// (since it's oddball and not fully nailed down).
565    #[test]
566    fn corner_points() {
567        assert_eq!(
568            Cube::new(10, 20, 30)
569                .aab()
570                .corner_points()
571                .collect::<Vec<_>>(),
572            vec![
573                point3(10., 20., 30.),
574                point3(11., 20., 30.),
575                point3(10., 21., 30.),
576                point3(11., 21., 30.),
577                point3(10., 20., 31.),
578                point3(11., 20., 31.),
579                point3(10., 21., 31.),
580                point3(11., 21., 31.),
581            ],
582        );
583    }
584}
all_is_cubes_base/math/aab.rs

all_is_cubes_base/math/
aab.rs
