all_is_cubes_base/math/
octant.rs

1use core::{fmt, ops};
2
3use euclid::{Vector3D, vec3};
4
5use crate::math::{Cube, Face6, FreeVector, GridCoordinate, GridPoint};
6
7// -------------------------------------------------------------------------------------------------
8
9/// Identifies one of eight octants, or elements of a 2×2×2 cube.
10///
11/// Used with [`OctantMask`] and [`OctantMap`].
12///
13/// This enum's discriminants are not currently to be considered stable; they may be reordered.
14//---
15// TODO: Replace this with an enum.
16#[expect(clippy::exhaustive_enums)]
17#[derive(Clone, Copy, Eq, Hash, PartialEq, exhaust::Exhaust)]
18#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
19#[repr(u8)]
20pub enum Octant {
21    /// The -X, -Y, -Z octant.
22    Nnn = 0,
23    /// The -X, -Y, +Z octant.
24    Nnp = 1,
25    /// The -X, +Y, -Z octant.
26    Npn = 2,
27    /// The -X, +Y, +Z octant.
28    Npp = 3,
29    /// The +X, -Y, -Z octant.
30    Pnn = 4,
31    /// The +X, -Y, +Z octant.
32    Pnp = 5,
33    /// The +X, +Y, -Z octant.
34    Ppn = 6,
35    /// The +X, +Y, +Z octant.
36    Ppp = 7,
37}
38
39impl Octant {
40    /// All values of the enum.
41    //---
42    // Note: `OctantMap::iter()` depends on the ordering of this.
43    pub const ALL: [Self; 8] = [
44        Self::Nnn,
45        Self::Nnp,
46        Self::Npn,
47        Self::Npp,
48        Self::Pnn,
49        Self::Pnp,
50        Self::Ppn,
51        Self::Ppp,
52    ];
53
54    #[inline]
55    fn from_zmaj_index(index: u8) -> Self {
56        match index {
57            0 => Self::Nnn,
58            1 => Self::Nnp,
59            2 => Self::Npn,
60            3 => Self::Npp,
61            4 => Self::Pnn,
62            5 => Self::Pnp,
63            6 => Self::Ppn,
64            7 => Self::Ppp,
65            _ => panic!("Octant::from_zmaj_index({index}) is out of bounds"),
66        }
67    }
68
69    /// Given a cube in the volume (0..2)³, return which octant of that volume it is.
70    #[inline]
71    pub fn try_from_positive_cube(cube: Cube) -> Option<Self> {
72        match <[i32; 3]>::from(cube) {
73            [0, 0, 0] => Some(Self::Nnn),
74            [0, 0, 1] => Some(Self::Nnp),
75            [0, 1, 0] => Some(Self::Npn),
76            [0, 1, 1] => Some(Self::Npp),
77            [1, 0, 0] => Some(Self::Pnn),
78            [1, 0, 1] => Some(Self::Pnp),
79            [1, 1, 0] => Some(Self::Ppn),
80            [1, 1, 1] => Some(Self::Ppp),
81            _ => None,
82        }
83    }
84
85    /// Given the low corner of an octant in the volume (0..2)³,
86    /// return which octant it is.
87    ///
88    /// That is, each coordinate of the returned [`Vector3D`] is either 0 or 1.
89    /// This is equivalent to [`Self::try_from_positive_cube()`] but with more flexible input.
90    ///
91    /// TODO: better trait bounds would be `Zero + One`
92    #[inline]
93    pub fn try_from_01<T: Copy + num_traits::NumCast, U>(
94        corner_or_translation: Vector3D<T, U>,
95    ) -> Option<Self> {
96        let low_corner: GridPoint =
97            corner_or_translation.try_cast::<GridCoordinate>()?.cast_unit().to_point();
98        Self::try_from_positive_cube(Cube::from(low_corner))
99    }
100
101    const fn to_zmaj_index(self) -> u8 {
102        self as u8
103    }
104
105    /// Returns the octant the given vector points toward, when interpreted as pointing away
106    /// from the center point where all octants meet.
107    ///
108    /// Ties due to zero components are broken in the positive direction.
109    #[inline]
110    pub fn from_vector(vector: FreeVector) -> Self {
111        let index = (u8::from(vector.x >= 0.) << 2)
112            | (u8::from(vector.y >= 0.) << 1)
113            | u8::from(vector.z >= 0.);
114        Self::from_zmaj_index(index)
115    }
116
117    // TODO: decide whether to make these public
118    #[inline(always)]
119    pub(crate) fn negative_on_x(self) -> bool {
120        self.to_zmaj_index() & 0b100 == 0
121    }
122    #[inline(always)]
123    pub(crate) fn negative_on_y(self) -> bool {
124        self.to_zmaj_index() & 0b010 == 0
125    }
126    #[inline(always)]
127    pub(crate) fn negative_on_z(self) -> bool {
128        self.to_zmaj_index() & 0b001 == 0
129    }
130
131    /// Returns this octant of the volume (0..2)³.
132    ///
133    /// That is, each coordinate of the returned [`Cube`] is either 0 or 1.
134    #[inline]
135    #[must_use]
136    pub fn to_positive_cube(self) -> Cube {
137        Cube::from(self.to_01::<Cube>().map(GridCoordinate::from).to_point())
138    }
139
140    /// Returns this octant of the volume (0..2)³ expressed as a translation vector
141    /// from the origin.
142    ///
143    /// That is, each coordinate of the returned [`Vector3D`] is either 0 or 1.
144    #[inline]
145    #[must_use]
146    pub fn to_01<U>(self) -> Vector3D<u8, U> {
147        let i = self.to_zmaj_index();
148        vec3((i >> 2) & 1, (i >> 1) & 1, i & 1)
149    }
150
151    /// For each component of `vector`, negate it if `self` is on the negative side of that axis.
152    ///
153    /// This may be used to transform between positive-octant-only data and data mirrored into
154    /// arbitrary octants.
155    #[inline]
156    pub fn reflect<T, U>(self, mut vector: Vector3D<T, U>) -> Vector3D<T, U>
157    where
158        T: ops::Neg<Output = T>,
159    {
160        if self.negative_on_x() {
161            vector.x = -vector.x;
162        }
163        if self.negative_on_y() {
164            vector.y = -vector.y;
165        }
166        if self.negative_on_z() {
167            vector.z = -vector.z;
168        }
169        vector
170    }
171}
172
173impl fmt::Debug for Octant {
174    #[inline(never)]
175    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
176        f.write_str(match self {
177            Self::Nnn => "−X−Y−Z",
178            Self::Nnp => "−X−Y+Z",
179            Self::Npn => "−X+Y−Z",
180            Self::Npp => "−X+Y+Z",
181            Self::Pnn => "+X−Y−Z",
182            Self::Pnp => "+X−Y+Z",
183            Self::Ppn => "+X+Y−Z",
184            Self::Ppp => "+X+Y+Z",
185        })
186    }
187}
188
189// -------------------------------------------------------------------------------------------------
190
191/// A set of [`Octant`]s (or equivalently, one [`bool`] for each cube of a 2×2×2 volume).
192///
193/// Internally represented as a `u8` bit-set.
194///
195/// This type may be used for culling or other calculations relating to the axis-aligned volumes
196/// surrounding a point. If more data than `bool` is needed, use [`OctantMap`].
197#[derive(Clone, Copy, Eq, Hash, PartialEq, exhaust::Exhaust)]
198#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
199pub struct OctantMask {
200    /// A bit-mask of octants, where the bit positions are, LSB first, [-X-Y-Z, -X-Y+Z, ..., +X+Y+Z]
201    ///
202    /// TODO: It would probably make more sense in many cases to use the opposite bit ordering.
203    flags: u8,
204}
205
206impl OctantMask {
207    /// The mask including all octants (all bits set).
208    pub const ALL: Self = Self { flags: 0xFF };
209    /// The mask including no octants (no bits set).
210    pub const NONE: Self = Self { flags: 0x00 };
211
212    #[inline]
213    #[doc(hidden)]
214    pub const fn from_zmaj_bits(flags: u8) -> Self {
215        Self { flags }
216    }
217
218    /// Get the flag for the given octant.
219    #[inline]
220    pub fn get(self, octant: Octant) -> bool {
221        self.flags & (1 << octant.to_zmaj_index()) != 0
222    }
223
224    /// Set the flag for the given octant.
225    #[inline]
226    pub fn set(&mut self, octant: Octant) {
227        self.flags |= 1 << octant.to_zmaj_index();
228    }
229
230    /// Clear the flat for the given octant.
231    #[inline]
232    pub fn clear(&mut self, octant: Octant) {
233        self.flags &= !(1 << octant.to_zmaj_index());
234    }
235
236    /// Shift the data in the specified direction, discarding overflows and filling with
237    /// [`false`]/clear.
238    #[inline]
239    #[must_use]
240    pub fn shift(self, direction: Face6) -> Self {
241        let flags = self.flags;
242        Self {
243            flags: match direction {
244                Face6::NX => flags >> 4,
245                Face6::PX => flags << 4,
246                Face6::NY => (flags & 0b11001100) >> 2,
247                Face6::PY => (flags & 0b00110011) << 2,
248                Face6::NZ => (flags & 0b10101010) >> 1,
249                Face6::PZ => (flags & 0b01010101) << 1,
250            },
251        }
252    }
253
254    /// Returns the first octant included in the mask.
255    ///
256    /// “First” is in an arbitrary ordering which corresponds to the binary-counting ordering
257    /// which has X as most significant bit and Z as least significant bit:
258    ///
259    /// ```text
260    /// -X -Y -Z
261    /// -X -Y +Z
262    /// -X +Y -Z
263    /// -X +Y +Z
264    /// +X -Y -Z
265    /// +X -Y +Z
266    /// +X +Y -Z
267    /// +X +Y +Z
268    /// ```
269    #[inline(always)]
270    #[doc(hidden)] // TODO: Decide what bit ordering we really want before locking it in
271    pub fn first(self) -> Option<Octant> {
272        let tz = self.flags.trailing_zeros();
273        if tz >= u8::BITS {
274            None
275        } else {
276            Some(Octant::from_zmaj_index(tz as u8))
277        }
278    }
279
280    /// As [`Self::first()`], but the opposite ordering.
281    #[inline(always)]
282    #[doc(hidden)] // TODO: Decide what bit ordering we really want before locking it in
283    pub fn last(self) -> Option<Octant> {
284        let lz = self.flags.leading_zeros();
285        if lz >= u8::BITS {
286            None
287        } else {
288            Some(Octant::from_zmaj_index((7 - lz) as u8))
289        }
290    }
291
292    /// Along each of the specified axes, move set bits on the negative side to the positive side,
293    /// combining with logical or.
294    ///
295    /// TODO: `collapse_to_positive()` would make more sense as an operation matching
296    /// `Octant::reflect()`; this is just what we happened to have before `OctantMask`
297    /// was a thing in itself.
298    #[doc(hidden)]
299    #[inline]
300    #[must_use]
301    pub fn collapse_to_negative(mut self, x: bool, y: bool, z: bool) -> Self {
302        if x {
303            self.flags = (self.flags & 0b00001111) | ((self.flags & 0b11110000) >> 4);
304        }
305        if y {
306            self.flags = (self.flags & 0b00110011) | ((self.flags & 0b11001100) >> 2);
307        }
308        if z {
309            self.flags = (self.flags & 0b01010101) | ((self.flags & 0b10101010) >> 1);
310        }
311        self
312    }
313}
314
315impl fmt::Debug for OctantMask {
316    #[inline(never)]
317    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
318        // Not using f.debug_set() because we want never-multiline output.
319        write!(f, "{{")?;
320        let mut first = true;
321        for octant in Octant::ALL {
322            if self.get(octant) {
323                if !first {
324                    write!(f, ", ")?;
325                }
326                first = false;
327                write!(f, "{octant:?}")?;
328            }
329        }
330        write!(f, "}}")?;
331        Ok(())
332    }
333}
334
335impl ops::BitOr for OctantMask {
336    type Output = Self;
337    #[inline]
338    fn bitor(self, rhs: Self) -> Self::Output {
339        Self {
340            flags: self.flags | rhs.flags,
341        }
342    }
343}
344impl ops::BitAnd for OctantMask {
345    type Output = Self;
346    #[inline]
347    fn bitand(self, rhs: Self) -> Self::Output {
348        Self {
349            flags: self.flags & rhs.flags,
350        }
351    }
352}
353impl ops::Not for OctantMask {
354    type Output = Self;
355    #[inline]
356    fn not(self) -> Self::Output {
357        Self { flags: !self.flags }
358    }
359}
360
361impl ops::BitOrAssign for OctantMask {
362    #[inline]
363    fn bitor_assign(&mut self, rhs: Self) {
364        *self = *self | rhs
365    }
366}
367impl ops::BitAndAssign for OctantMask {
368    #[inline]
369    fn bitand_assign(&mut self, rhs: Self) {
370        *self = *self & rhs
371    }
372}
373
374impl FromIterator<Octant> for OctantMask {
375    #[inline]
376    fn from_iter<T: IntoIterator<Item = Octant>>(iter: T) -> Self {
377        let mut new_self = OctantMask::NONE;
378        iter.into_iter().for_each(|octant| {
379            new_self.set(octant);
380        });
381        new_self
382    }
383}
384
385impl From<Octant> for OctantMask {
386    #[inline]
387    fn from(octant: Octant) -> Self {
388        let mut new_self = OctantMask::NONE;
389        new_self.set(octant);
390        new_self
391    }
392}
393
394// -------------------------------------------------------------------------------------------------
395
396/// Collection of 8 values keyed by [`Octant`]s.
397///
398/// If the values are [`bool`], use [`OctantMask`] instead for a more efficient representation.
399#[derive(Clone, Copy, Default, Hash, PartialEq, Eq, exhaust::Exhaust)]
400#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
401pub struct OctantMap<T>([T; 8]);
402
403impl<T> OctantMap<T> {
404    /// Constructs an [`OctantMap`] by using the provided function to compute
405    /// a value for each octant.
406    #[inline]
407    #[must_use]
408    pub fn from_fn(mut function: impl FnMut(Octant) -> T) -> Self {
409        Self(core::array::from_fn(|i| {
410            function(Octant::from_zmaj_index(i as u8))
411        }))
412    }
413
414    /// Constructs an [`OctantMap`] by cloning the provided value.
415    #[inline]
416    #[must_use]
417    pub fn repeat(value: T) -> Self
418    where
419        T: Clone,
420    {
421        Self([
422            value.clone(),
423            value.clone(),
424            value.clone(),
425            value.clone(),
426            value.clone(),
427            value.clone(),
428            value.clone(),
429            value,
430        ])
431    }
432    /// Returns an [`OctantMask`] constructed by applying the given `predicate` to each octant
433    /// of the data in `self`.
434    #[inline]
435    #[must_use]
436    pub fn to_mask(&self, mut predicate: impl FnMut(&T) -> bool) -> OctantMask {
437        let mut output = 0;
438        for (i, value) in self.0.iter().enumerate() {
439            output |= u8::from(predicate(value)) << i;
440        }
441        OctantMask::from_zmaj_bits(output)
442    }
443
444    // /// Moves the data into a [`Vol`] that covers the same volume as
445    // /// [`Octant::to_positive_cube()`].
446    // #[inline]
447    // #[must_use]
448    // pub fn into_positive_vol(self) -> Vol<Box<[T]>> {
449    //     Vol::from_elements(GridAab::for_block(Resolution::R2), self.0).unwrap()
450    // }
451
452    #[doc(hidden)]
453    #[inline]
454    #[must_use]
455    pub fn into_zmaj_array(self) -> [T; 8] {
456        self.0
457    }
458
459    /// Returns an iterator over all elements by reference, and their octants.
460    ///
461    /// The order of iteration is not currently guarateed.
462    #[inline]
463    pub fn iter(&self) -> impl Iterator<Item = (Octant, &T)> + '_ {
464        Octant::ALL.into_iter().zip(self.0.iter())
465    }
466
467    /// Returns an iterator over all elements by reference.
468    ///
469    /// The order of iteration is not currently guarateed.
470    #[inline]
471    pub fn values(&self) -> impl Iterator<Item = &T> + '_ {
472        self.0.iter()
473    }
474
475    /// Returns an iterator over all elements by mutable reference.
476    ///
477    /// The order of iteration is not currently guarateed.
478    #[inline]
479    pub fn iter_mut(&mut self) -> impl Iterator<Item = (Octant, &mut T)> + '_ {
480        Octant::ALL.into_iter().zip(self.0.iter_mut())
481    }
482}
483
484impl<T: fmt::Debug> fmt::Debug for OctantMap<T> {
485    #[inline(never)]
486    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
487        let mut s = f.debug_struct("OctantMap");
488        for octant in Octant::ALL {
489            s.field(&format!("{octant:?}"), &self[octant]);
490        }
491        s.finish()
492    }
493}
494
495impl<T> ops::Index<Octant> for OctantMap<T> {
496    type Output = T;
497    #[inline]
498    fn index(&self, octant: Octant) -> &Self::Output {
499        &self.0[octant.to_zmaj_index() as usize]
500    }
501}
502impl<T> ops::IndexMut<Octant> for OctantMap<T> {
503    #[inline]
504    fn index_mut(&mut self, octant: Octant) -> &mut Self::Output {
505        &mut self.0[octant.to_zmaj_index() as usize]
506    }
507}
508
509// -------------------------------------------------------------------------------------------------
510
511#[cfg(test)]
512mod tests {
513    use super::*;
514    use Face6::*;
515    use euclid::vec3;
516
517    #[test]
518    fn reflect() {
519        let vec3 = vec3::<i32, ()>; // avoid ambiguous type
520
521        assert_eq!(Octant::Ppp.reflect(vec3(1, 2, 3)), vec3(1, 2, 3));
522        assert_eq!(Octant::Ppn.reflect(vec3(1, 2, 3)), vec3(1, 2, -3));
523        assert_eq!(Octant::Pnp.reflect(vec3(1, 2, 3)), vec3(1, -2, 3));
524        assert_eq!(Octant::Npp.reflect(vec3(1, 2, 3)), vec3(-1, 2, 3));
525        assert_eq!(Octant::Nnn.reflect(vec3(1, 2, 3)), vec3(-1, -2, -3));
526    }
527
528    #[test]
529    fn mask_debug() {
530        let none = OctantMask::NONE;
531
532        assert_eq!(format!("{none:?}"), "{}");
533        assert_eq!(format!("{none:#?}"), "{}");
534
535        let mut some = OctantMask::NONE;
536        some.set(Octant::Pnn);
537        some.set(Octant::Ppn);
538
539        assert_eq!(format!("{some:?}"), "{+X−Y−Z, +X+Y−Z}");
540        assert_eq!(format!("{some:#?}"), "{+X−Y−Z, +X+Y−Z}");
541    }
542
543    #[test]
544    fn shifts() {
545        let all = OctantMask::ALL;
546        assert_eq!(all.shift(NX), OctantMask::from_zmaj_bits(0b00001111));
547        assert_eq!(all.shift(PX), OctantMask::from_zmaj_bits(0b11110000));
548        assert_eq!(all.shift(NY), OctantMask::from_zmaj_bits(0b00110011));
549        assert_eq!(all.shift(PY), OctantMask::from_zmaj_bits(0b11001100));
550        assert_eq!(all.shift(NZ), OctantMask::from_zmaj_bits(0b01010101));
551        assert_eq!(all.shift(PZ), OctantMask::from_zmaj_bits(0b10101010));
552    }
553
554    #[test]
555    fn collapse_to_negative() {
556        // TODO: more test coverage
557        assert_eq!(
558            OctantMask::ALL.collapse_to_negative(true, true, false),
559            OctantMask::from_iter([Octant::Nnn, Octant::Nnp])
560        );
561        for octant in Octant::ALL {
562            let mask = OctantMask::from_iter([octant]);
563            assert_eq!(
564                mask.collapse_to_negative(true, true, true),
565                OctantMask::from_iter([Octant::Nnn])
566            );
567        }
568    }
569
570    #[test]
571    fn octant_mask_smoke_test() {
572        let mut mask = OctantMask::NONE;
573        assert_eq!(mask, OctantMask::NONE);
574        mask.set(Octant::from_vector(vec3(1., 1., 1.)));
575        assert_eq!(mask, OctantMask { flags: 0b1000_0000 });
576        mask.set(Octant::from_vector(vec3(-1., -1., -1.)));
577        assert_eq!(mask, OctantMask { flags: 0b1000_0001 });
578        assert_eq!(mask.first(), Some(Octant::from_zmaj_index(0)));
579        assert_eq!(mask.last(), Some(Octant::from_zmaj_index(7)));
580    }
581}
all_is_cubes_base/math/octant.rs

all_is_cubes_base/math/
octant.rs
