all_is_cubes_base/math/
aab.rs

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

all_is_cubes_base/math/
aab.rs
