oktree/
bounding.rs

1//! Bounding primitives.
2//!
3//! [`TUVec3`], [`BVec3`], [`Aabb`]
4
5use crate::{Position, TreeError};
6use core::fmt::{self, Debug, Display};
7use core::ops::{Add, AddAssign, BitAnd, Div, DivAssign, Mul, MulAssign, Shr, Sub, SubAssign};
8use num::{cast, Integer, NumCast, Saturating, Unsigned as NumUnsigned};
9
10pub trait Unsigned:
11    Integer
12    + NumUnsigned
13    + NumCast
14    + Saturating
15    + Add
16    + AddAssign
17    + Sub
18    + SubAssign
19    + Div
20    + DivAssign
21    + Mul
22    + MulAssign
23    + Shr<Self, Output = Self>
24    + BitAnd<Self, Output = Self>
25    + Copy
26    + Display
27    + Debug
28    + Default
29{
30}
31impl Unsigned for u8 {}
32impl Unsigned for u16 {}
33impl Unsigned for u32 {}
34impl Unsigned for u64 {}
35impl Unsigned for u128 {}
36impl Unsigned for usize {}
37
38/// Tree Unsigned Vec3
39///
40/// Inner typy shuld be any [`Unsigned`](num::Unsigned):
41/// `u8`, `u16`, `u32`, `u64`, `u128`, `usize`.
42#[derive(Default, Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
43pub struct TUVec3<U: Unsigned> {
44    pub x: U,
45    pub y: U,
46    pub z: U,
47}
48
49impl<U: Unsigned> Add for TUVec3<U> {
50    type Output = Self;
51
52    fn add(self, other: Self) -> Self {
53        TUVec3 {
54            x: self.x + other.x,
55            y: self.y + other.y,
56            z: self.z + other.z,
57        }
58    }
59}
60
61impl<U: Unsigned> Sub for TUVec3<U> {
62    type Output = Self;
63
64    fn sub(self, other: Self) -> Self {
65        TUVec3 {
66            x: self.x.saturating_sub(other.x),
67            y: self.y.saturating_sub(other.y),
68            z: self.z.saturating_sub(other.z),
69        }
70    }
71}
72
73impl<U: Unsigned> AddAssign for TUVec3<U> {
74    fn add_assign(&mut self, other: Self) {
75        self.x += other.x;
76        self.y += other.y;
77        self.z += other.z;
78    }
79}
80
81impl<U: Unsigned> SubAssign for TUVec3<U> {
82    fn sub_assign(&mut self, other: Self) {
83        self.x = self.x.saturating_sub(other.x);
84        self.y = self.y.saturating_sub(other.y);
85        self.z = self.z.saturating_sub(other.z);
86    }
87}
88
89impl<U: Unsigned> Mul<U> for TUVec3<U> {
90    type Output = Self;
91
92    fn mul(self, other: U) -> Self {
93        TUVec3 {
94            x: self.x * other,
95            y: self.y * other,
96            z: self.z * other,
97        }
98    }
99}
100
101impl<U: Unsigned> MulAssign<U> for TUVec3<U> {
102    fn mul_assign(&mut self, other: U) {
103        self.x *= other;
104        self.y *= other;
105        self.z *= other;
106    }
107}
108
109impl<U: Unsigned> Div<U> for TUVec3<U> {
110    type Output = Self;
111
112    fn div(self, other: U) -> Self {
113        TUVec3 {
114            x: self.x / other,
115            y: self.y / other,
116            z: self.z / other,
117        }
118    }
119}
120
121impl<U: Unsigned> DivAssign<U> for TUVec3<U> {
122    fn div_assign(&mut self, other: U) {
123        self.x /= other;
124        self.y /= other;
125        self.z /= other;
126    }
127}
128
129impl<U: Unsigned> Display for TUVec3<U> {
130    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
131        write!(f, "Uvec3: x: {}, y: {}, z: {}", self.x, self.y, self.z)
132    }
133}
134
135impl<U: Unsigned> TUVec3<U> {
136    pub fn new(x: U, y: U, z: U) -> Self {
137        TUVec3 { x, y, z }
138    }
139
140    pub fn splat(size: U) -> Self {
141        TUVec3 {
142            x: size,
143            y: size,
144            z: size,
145        }
146    }
147
148    pub fn zero() -> Self {
149        TUVec3 {
150            x: cast(0).unwrap(),
151            y: cast(0).unwrap(),
152            z: cast(0).unwrap(),
153        }
154    }
155
156    pub fn lt(&self, other: &Self) -> BVec3 {
157        BVec3::new(self.x < other.x, self.y < other.y, self.z < other.z)
158    }
159
160    pub fn gt(&self, other: &Self) -> BVec3 {
161        BVec3::new(self.x > other.x, self.y > other.y, self.z > other.z)
162    }
163
164    pub fn le(&self, other: &Self) -> BVec3 {
165        BVec3::new(self.x <= other.x, self.y <= other.y, self.z <= other.z)
166    }
167
168    pub fn ge(&self, other: &Self) -> BVec3 {
169        BVec3::new(self.x >= other.x, self.y >= other.y, self.z >= other.z)
170    }
171
172    #[inline]
173    /// Checks if [`Aabb`] creted from this [`TUVec3`] and `half_size` will have all dimensions positive.
174    pub fn is_positive_aabb(&self, half_size: U) -> bool {
175        self.x >= half_size && self.y >= half_size && self.z >= half_size
176    }
177
178    /// Creates [`Aabb`] with size of 1 from current [`TUVec3`].
179    pub fn unit_aabb(&self) -> Aabb<U> {
180        let max = TUVec3::new(
181            self.x + cast(1).unwrap(),
182            self.y + cast(1).unwrap(),
183            self.z + cast(1).unwrap(),
184        );
185        Aabb { min: *self, max }
186    }
187}
188
189/// Boolean Vec3 mask.
190#[derive(Default, Clone, Copy, PartialEq, Debug)]
191pub struct BVec3 {
192    x: bool,
193    y: bool,
194    z: bool,
195}
196
197impl BVec3 {
198    fn new(x: bool, y: bool, z: bool) -> Self {
199        BVec3 { x, y, z }
200    }
201
202    pub fn all(&self) -> bool {
203        self.x && self.y && self.z
204    }
205
206    pub fn any(&self) -> bool {
207        self.x || self.y || self.z
208    }
209
210    pub fn none(&self) -> bool {
211        !self.x && !self.y && !self.z
212    }
213}
214
215/// Axis Aligned Bounding Box
216///
217/// Resulting Aabb should be positive and it's dimensions should be the power of 2.
218/// Inner type shuld be any [`Unsigned`](num::Unsigned):
219/// `u8`, `u16`, `u32`, `u64`, `u128`, `usize`.
220#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
221pub struct Aabb<U: Unsigned> {
222    pub min: TUVec3<U>,
223    pub max: TUVec3<U>,
224}
225
226impl<U: Unsigned> Default for Aabb<U> {
227    fn default() -> Self {
228        Self {
229            min: TUVec3::new(cast(0).unwrap(), cast(0).unwrap(), cast(0).unwrap()),
230            max: TUVec3::new(cast(1).unwrap(), cast(1).unwrap(), cast(1).unwrap()),
231        }
232    }
233}
234
235impl<U: Unsigned> Display for Aabb<U> {
236    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
237        write!(f, "Aabb(min: {}, max: {})", self.min, self.max)
238    }
239}
240
241impl<U: Unsigned> Aabb<U> {
242    /// Creates a new [Aabb] object without any checks
243    pub fn new_unchecked(center: TUVec3<U>, half_size: U) -> Self {
244        Aabb {
245            min: TUVec3::new(
246                center.x.saturating_sub(half_size),
247                center.y.saturating_sub(half_size),
248                center.z.saturating_sub(half_size),
249            ),
250            max: TUVec3::new(
251                center.x + half_size,
252                center.y + half_size,
253                center.z + half_size,
254            ),
255        }
256    }
257
258    /// Creates a new [`Aabb`] object
259    ///
260    /// Checks that it's dimensions are positive
261    /// and are powers of 2.
262    pub fn new(center: TUVec3<U>, half_size: U) -> Result<Self, TreeError> {
263        if !center.is_positive_aabb(half_size) {
264            Err(TreeError::NotPositive(
265                "Center: {center}, half size: {half_size}".into(),
266            ))
267        } else if !is_power2(half_size) {
268            Err(TreeError::NotPower2("half size: {half_size}".into()))
269        } else {
270            Ok(Self::new_unchecked(center, half_size))
271        }
272    }
273
274    /// Creates a new [`Aabb`] object from a min and max
275    pub fn from_min_max(min: TUVec3<U>, max: TUVec3<U>) -> Self {
276        Self { min, max }
277    }
278
279    pub fn center(&self) -> TUVec3<U> {
280        TUVec3::new(
281            (self.min.x + self.max.x) >> cast(1).unwrap(),
282            (self.min.y + self.max.y) >> cast(1).unwrap(),
283            (self.min.z + self.max.z) >> cast(1).unwrap(),
284        )
285    }
286
287    #[inline]
288    pub fn split(&self) -> [Aabb<U>; 8] {
289        let center = self.center();
290        [
291            Aabb::from_min_max(
292                TUVec3::new(self.min.x, self.min.y, self.min.z),
293                TUVec3::new(center.x, center.y, center.z),
294            ),
295            Aabb::from_min_max(
296                TUVec3::new(center.x, self.min.y, self.min.z),
297                TUVec3::new(self.max.x, center.y, center.z),
298            ),
299            Aabb::from_min_max(
300                TUVec3::new(self.min.x, center.y, self.min.z),
301                TUVec3::new(center.x, self.max.y, center.z),
302            ),
303            Aabb::from_min_max(
304                TUVec3::new(center.x, center.y, self.min.z),
305                TUVec3::new(self.max.x, self.max.y, center.z),
306            ),
307            Aabb::from_min_max(
308                TUVec3::new(self.min.x, self.min.y, center.z),
309                TUVec3::new(center.x, center.y, self.max.z),
310            ),
311            Aabb::from_min_max(
312                TUVec3::new(center.x, self.min.y, center.z),
313                TUVec3::new(self.max.x, center.y, self.max.z),
314            ),
315            Aabb::from_min_max(
316                TUVec3::new(self.min.x, center.y, center.z),
317                TUVec3::new(center.x, self.max.y, self.max.z),
318            ),
319            Aabb::from_min_max(
320                TUVec3::new(center.x, center.y, center.z),
321                TUVec3::new(self.max.x, self.max.y, self.max.z),
322            ),
323        ]
324    }
325
326    fn _split(&self, i: usize, center: TUVec3<U>) -> Aabb<U> {
327        let x_mask = (i & 0b1) != 0;
328        let y_mask = (i & 0b10) != 0;
329        let z_mask = (i & 0b100) != 0;
330
331        Aabb {
332            min: TUVec3::new(
333                if x_mask { center.x } else { self.min.x },
334                if y_mask { center.y } else { self.min.y },
335                if z_mask { center.z } else { self.min.z },
336            ),
337            max: TUVec3::new(
338                if x_mask { self.max.x } else { center.x },
339                if y_mask { self.max.y } else { center.y },
340                if z_mask { self.max.z } else { center.z },
341            ),
342        }
343    }
344
345    /// Checks if the aabb contains a [`position`](TUVec3).
346    pub fn contains(&self, position: &TUVec3<U>) -> bool {
347        let lemin = self.min.le(position);
348        let gtmax = self.max.gt(position);
349
350        lemin.all() && gtmax.all()
351    }
352
353    /// Checks if this volume overlaps with another [`Aabb`].
354    pub fn overlaps(&self, other: &Aabb<U>) -> bool {
355        self.max.x.min(other.max.x) > self.min.x.max(other.min.x)
356            && self.max.y.min(other.max.y) > self.min.y.max(other.min.y)
357            && self.max.z.min(other.max.z) > self.min.z.max(other.min.z)
358    }
359
360    pub fn unit(&self) -> bool {
361        self.max.x - self.min.x == cast(1).unwrap()
362    }
363
364    pub fn size(&self) -> U {
365        self.max.x - self.min.x
366    }
367}
368
369/// Check if `half_size` is the power of 2.
370///
371/// Used in [`aabb creation`](Aabb::new) checks.
372pub fn is_power2<U: Unsigned>(mut half_size: U) -> bool {
373    if half_size < cast(2).unwrap() {
374        return false;
375    }
376
377    while half_size > cast(1).unwrap() {
378        if half_size & cast(0b1).unwrap() != cast(0).unwrap() {
379            return false;
380        }
381
382        half_size = half_size >> cast(1).unwrap();
383    }
384
385    true
386}
387
388#[cfg(test)]
389mod tests {
390    use super::{is_power2, Aabb, TUVec3};
391
392    #[test]
393    fn test_aabb_contains() {
394        let aabb = Aabb::new_unchecked(TUVec3::new(8, 8, 8), 8u16);
395        assert!(aabb.contains(&TUVec3::zero()));
396
397        assert!(aabb.contains(&TUVec3::new(8, 8, 8)));
398
399        assert!(!aabb.contains(&TUVec3::new(16, 16, 16)));
400
401        assert!(!aabb.contains(&TUVec3::new(0, 16, 8)));
402    }
403
404    #[test]
405    fn test_ispower2() {
406        assert!(!is_power2(0u32));
407        assert!(!is_power2(1u32));
408        assert!(is_power2(2u8));
409        assert!(!is_power2(3u32));
410        assert!(is_power2(4u16));
411        assert!(!is_power2(5u16));
412        assert!(is_power2(8u8));
413        assert!(!is_power2(1023usize));
414        assert!(is_power2(1024usize));
415        assert!(!is_power2(1025usize));
416    }
417
418    #[test]
419    fn test_aabb_constructor() {
420        // Ok
421        assert!(Aabb::new(TUVec3::splat(2u8), 2).is_ok());
422
423        // Negative dimensions
424        assert!(Aabb::new(TUVec3::splat(16u16), 64).is_err());
425
426        // 7 is not the power of 2
427        assert!(Aabb::new(TUVec3::splat(16u16), 7).is_err());
428    }
429}
430
431#[derive(Default, Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
432pub struct TUVec3u8(pub TUVec3<u8>);
433impl TUVec3u8 {
434    pub fn new(x: u8, y: u8, z: u8) -> Self {
435        TUVec3u8(TUVec3::new(x, y, z))
436    }
437}
438impl Position for TUVec3u8 {
439    type U = u8;
440    fn position(&self) -> TUVec3<u8> {
441        self.0
442    }
443}
444
445#[derive(Default, Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
446pub struct TUVec3u16(pub TUVec3<u16>);
447impl TUVec3u16 {
448    pub fn new(x: u16, y: u16, z: u16) -> Self {
449        TUVec3u16(TUVec3::new(x, y, z))
450    }
451}
452impl Position for TUVec3u16 {
453    type U = u16;
454    fn position(&self) -> TUVec3<u16> {
455        self.0
456    }
457}
458
459#[derive(Default, Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
460pub struct TUVec3u32(pub TUVec3<u32>);
461impl TUVec3u32 {
462    pub fn new(x: u32, y: u32, z: u32) -> Self {
463        TUVec3u32(TUVec3::new(x, y, z))
464    }
465}
466impl Position for TUVec3u32 {
467    type U = u32;
468    fn position(&self) -> TUVec3<u32> {
469        self.0
470    }
471}
472
473#[derive(Default, Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
474pub struct TUVec3u64(pub TUVec3<u64>);
475impl TUVec3u64 {
476    pub fn new(x: u64, y: u64, z: u64) -> Self {
477        TUVec3u64(TUVec3::new(x, y, z))
478    }
479}
480impl Position for TUVec3u64 {
481    type U = u64;
482    fn position(&self) -> TUVec3<u64> {
483        self.0
484    }
485}
486
487#[derive(Default, Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
488pub struct TUVec3u128(pub TUVec3<u128>);
489impl TUVec3u128 {
490    pub fn new(x: u128, y: u128, z: u128) -> Self {
491        TUVec3u128(TUVec3::new(x, y, z))
492    }
493}
494impl Position for TUVec3u128 {
495    type U = u128;
496    fn position(&self) -> TUVec3<u128> {
497        self.0
498    }
499}
oktree/bounding.rs

oktree/
bounding.rs
