parry2d/bounding_volume/aabb.rs
1//! Axis Aligned Bounding Box.
2
3use crate::bounding_volume::{BoundingSphere, BoundingVolume};
4use crate::math::{Pose, Real, Vector, DIM, TWO_DIM};
5use crate::shape::{Cuboid, SupportMap};
6use crate::utils::PoseOps;
7use arrayvec::ArrayVec;
8use num::Bounded;
9
10use crate::query::{Ray, RayCast};
11
12/// An Axis-Aligned Bounding Box (AABB).
13///
14/// An AABB is the simplest bounding volume, defined by its minimum and maximum corners.
15/// It's called "axis-aligned" because its edges are always parallel to the coordinate axes
16/// (X, Y, and Z in 3D), making it very fast to test and compute.
17///
18/// # Structure
19///
20/// - **mins**: The point with the smallest coordinates on each axis (bottom-left-back corner)
21/// - **maxs**: The point with the largest coordinates on each axis (top-right-front corner)
22/// - **Invariant**: `mins.x ≤ maxs.x`, `mins.y ≤ maxs.y` (and `mins.z ≤ maxs.z` in 3D)
23///
24/// # Properties
25///
26/// - **Axis-aligned**: Edges always parallel to coordinate axes
27/// - **Conservative**: May be larger than the actual shape for rotated objects
28/// - **Fast**: Intersection tests are very cheap (just coordinate comparisons)
29/// - **Hierarchical**: Perfect for spatial data structures (BVH, quadtree, octree)
30///
31/// # Use Cases
32///
33/// AABBs are fundamental to collision detection and are used for:
34///
35/// - **Broad-phase collision detection**: Quickly eliminate distant object pairs
36/// - **Spatial partitioning**: Building BVHs, quadtrees, and octrees
37/// - **View frustum culling**: Determining what's visible
38/// - **Ray tracing acceleration**: Quickly rejecting non-intersecting rays
39/// - **Bounding volume for any shape**: Every shape can compute its AABB
40///
41/// # Performance
42///
43/// AABBs are the fastest bounding volume for:
44/// - Intersection tests: O(1) with just 6 comparisons (3D)
45/// - Merging: O(1) with component-wise min/max
46/// - Contains test: O(1) with coordinate comparisons
47///
48/// # Limitations
49///
50/// - **Rotation invariance**: Must be recomputed when objects rotate
51/// - **Tightness**: May waste space for rotated or complex shapes
52/// - **No orientation**: Cannot represent oriented bounding boxes (OBB)
53///
54/// # Example
55///
56/// ```rust
57/// # #[cfg(all(feature = "dim3", feature = "f32"))] {
58/// use parry3d::bounding_volume::Aabb;
59/// use parry3d::math::Vector;
60///
61/// // Create an AABB for a unit cube centered at origin
62/// let mins = Vector::new(-0.5, -0.5, -0.5);
63/// let maxs = Vector::new(0.5, 0.5, 0.5);
64/// let aabb = Aabb::new(mins, maxs);
65///
66/// // Check if a point is inside
67/// let point = Vector::ZERO;
68/// assert!(aabb.contains_local_point(point));
69///
70/// // Get center and extents
71/// assert_eq!(aabb.center(), Vector::ZERO);
72/// assert_eq!(aabb.extents().x, 1.0); // Full width
73/// assert_eq!(aabb.half_extents().x, 0.5); // Half width
74/// # }
75/// ```
76///
77/// ```rust
78/// # #[cfg(all(feature = "dim3", feature = "f32"))] {
79/// use parry3d::bounding_volume::Aabb;
80/// use parry3d::math::Vector;
81///
82/// // Create from a set of points
83/// let points = vec![
84/// Vector::new(1.0, 2.0, 3.0),
85/// Vector::new(-1.0, 4.0, 2.0),
86/// Vector::new(0.0, 0.0, 5.0),
87/// ];
88/// let aabb = Aabb::from_points(points);
89///
90/// // The AABB encloses all points
91/// assert_eq!(aabb.mins, Vector::new(-1.0, 0.0, 2.0));
92/// assert_eq!(aabb.maxs, Vector::new(1.0, 4.0, 5.0));
93/// # }
94/// ```
95#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
96#[cfg_attr(feature = "bytemuck", derive(bytemuck::Pod, bytemuck::Zeroable))]
97#[cfg_attr(
98 feature = "rkyv",
99 derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize)
100)]
101#[derive(Debug, PartialEq, Copy, Clone)]
102#[repr(C)]
103pub struct Aabb {
104 /// The point with minimum coordinates (bottom-left-back corner).
105 ///
106 /// Each component (`x`, `y`, `z`) should be less than or equal to the
107 /// corresponding component in `maxs`.
108 pub mins: Vector,
109
110 /// The point with maximum coordinates (top-right-front corner).
111 ///
112 /// Each component (`x`, `y`, `z`) should be greater than or equal to the
113 /// corresponding component in `mins`.
114 pub maxs: Vector,
115}
116
117impl Aabb {
118 /// The vertex indices of each edge of this `Aabb`.
119 ///
120 /// This gives, for each edge of this `Aabb`, the indices of its
121 /// vertices when taken from the `self.vertices()` array.
122 /// Here is how the faces are numbered, assuming
123 /// a right-handed coordinate system:
124 ///
125 /// ```text
126 /// y 3 - 2
127 /// | 7 − 6 |
128 /// ___ x | | 1 (the zero is below 3 and on the left of 1,
129 /// / 4 - 5 hidden by the 4-5-6-7 face.)
130 /// z
131 /// ```
132 #[cfg(feature = "dim3")]
133 pub const EDGES_VERTEX_IDS: [(usize, usize); 12] = [
134 (0, 1),
135 (1, 2),
136 (3, 2),
137 (0, 3),
138 (4, 5),
139 (5, 6),
140 (7, 6),
141 (4, 7),
142 (0, 4),
143 (1, 5),
144 (2, 6),
145 (3, 7),
146 ];
147
148 /// The vertex indices of each face of this `Aabb`.
149 ///
150 /// This gives, for each face of this `Aabb`, the indices of its
151 /// vertices when taken from the `self.vertices()` array.
152 /// Here is how the faces are numbered, assuming
153 /// a right-handed coordinate system:
154 ///
155 /// ```text
156 /// y 3 - 2
157 /// | 7 − 6 |
158 /// ___ x | | 1 (the zero is below 3 and on the left of 1,
159 /// / 4 - 5 hidden by the 4-5-6-7 face.)
160 /// z
161 /// ```
162 #[cfg(feature = "dim3")]
163 pub const FACES_VERTEX_IDS: [(usize, usize, usize, usize); 6] = [
164 // Face with normal +X
165 (1, 2, 6, 5),
166 // Face with normal -X
167 (0, 3, 7, 4),
168 // Face with normal +Y
169 (2, 3, 7, 6),
170 // Face with normal -Y
171 (1, 0, 4, 5),
172 // Face with normal +Z
173 (4, 5, 6, 7),
174 // Face with normal -Z
175 (0, 1, 2, 3),
176 ];
177
178 /// The vertex indices of each face of this `Aabb`.
179 ///
180 /// This gives, for each face of this `Aabb`, the indices of its
181 /// vertices when taken from the `self.vertices()` array.
182 /// Here is how the faces are numbered, assuming
183 /// a right-handed coordinate system:
184 ///
185 /// ```text
186 /// y 3 - 2
187 /// | | |
188 /// ___ x 0 - 1
189 /// ```
190 #[cfg(feature = "dim2")]
191 pub const FACES_VERTEX_IDS: [(usize, usize); 4] = [
192 // Face with normal +X
193 (1, 2),
194 // Face with normal -X
195 (3, 0),
196 // Face with normal +Y
197 (2, 3),
198 // Face with normal -Y
199 (0, 1),
200 ];
201
202 /// Creates a new AABB from its minimum and maximum corners.
203 ///
204 /// # Arguments
205 ///
206 /// * `mins` - The point with the smallest coordinates on each axis
207 /// * `maxs` - The point with the largest coordinates on each axis
208 ///
209 /// # Invariant
210 ///
211 /// Each component of `mins` should be ≤ the corresponding component of `maxs`.
212 ///
213 /// # Example
214 ///
215 /// ```
216 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
217 /// use parry3d::bounding_volume::Aabb;
218 /// use parry3d::math::Vector;
219 ///
220 /// // Create a 2x2x2 cube centered at origin
221 /// let aabb = Aabb::new(
222 /// Vector::new(-1.0, -1.0, -1.0),
223 /// Vector::new(1.0, 1.0, 1.0)
224 /// );
225 ///
226 /// assert_eq!(aabb.center(), Vector::ZERO);
227 /// assert_eq!(aabb.extents(), Vector::new(2.0, 2.0, 2.0));
228 /// # }
229 /// ```
230 #[inline]
231 pub fn new(mins: Vector, maxs: Vector) -> Aabb {
232 Aabb { mins, maxs }
233 }
234
235 /// Creates an invalid AABB with inverted bounds.
236 ///
237 /// The resulting AABB has `mins` set to maximum values and `maxs` set to
238 /// minimum values. This is useful as an initial value for AABB merging
239 /// algorithms (similar to starting a min operation with infinity).
240 ///
241 /// # Example
242 ///
243 /// ```
244 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
245 /// use parry3d::bounding_volume::{Aabb, BoundingVolume};
246 /// use parry3d::math::Vector;
247 ///
248 /// let mut aabb = Aabb::new_invalid();
249 ///
250 /// // Merge with actual points to build proper AABB
251 /// aabb.merge(&Aabb::new(Vector::new(1.0, 2.0, 3.0), Vector::new(1.0, 2.0, 3.0)));
252 /// aabb.merge(&Aabb::new(Vector::new(-1.0, 0.0, 2.0), Vector::new(-1.0, 0.0, 2.0)));
253 ///
254 /// // Now contains the merged bounds
255 /// assert_eq!(aabb.mins, Vector::new(-1.0, 0.0, 2.0));
256 /// assert_eq!(aabb.maxs, Vector::new(1.0, 2.0, 3.0));
257 /// # }
258 /// ```
259 #[inline]
260 pub fn new_invalid() -> Self {
261 Self::new(
262 Vector::splat(Real::max_value()),
263 Vector::splat(-Real::max_value()),
264 )
265 }
266
267 /// Creates a new AABB from its center and half-extents.
268 ///
269 /// This is often more intuitive than specifying min and max corners.
270 ///
271 /// # Arguments
272 ///
273 /// * `center` - The center point of the AABB
274 /// * `half_extents` - Half the dimensions along each axis
275 ///
276 /// # Example
277 ///
278 /// ```
279 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
280 /// use parry3d::bounding_volume::Aabb;
281 /// use parry3d::math::Vector;
282 ///
283 /// // Create a 10x6x8 box centered at (5, 0, 0)
284 /// let aabb = Aabb::from_half_extents(
285 /// Vector::new(5.0, 0.0, 0.0),
286 /// Vector::new(5.0, 3.0, 4.0)
287 /// );
288 ///
289 /// assert_eq!(aabb.mins, Vector::new(0.0, -3.0, -4.0));
290 /// assert_eq!(aabb.maxs, Vector::new(10.0, 3.0, 4.0));
291 /// assert_eq!(aabb.center(), Vector::new(5.0, 0.0, 0.0));
292 /// # }
293 /// ```
294 #[inline]
295 pub fn from_half_extents(center: Vector, half_extents: Vector) -> Self {
296 Self::new(center - half_extents, center + half_extents)
297 }
298
299 /// Creates a new AABB that tightly encloses a set of points (references).
300 ///
301 /// Computes the minimum and maximum coordinates across all points.
302 ///
303 /// # Arguments
304 ///
305 /// * `pts` - An iterator over point references
306 ///
307 /// # Example
308 ///
309 /// ```
310 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
311 /// use parry3d::bounding_volume::Aabb;
312 /// use parry3d::math::Vector;
313 ///
314 /// let points = vec![
315 /// Vector::new(1.0, 2.0, 3.0),
316 /// Vector::new(-1.0, 4.0, 2.0),
317 /// Vector::new(0.0, 0.0, 5.0),
318 /// ];
319 ///
320 /// let aabb = Aabb::from_points_ref(&points);
321 /// assert_eq!(aabb.mins, Vector::new(-1.0, 0.0, 2.0));
322 /// assert_eq!(aabb.maxs, Vector::new(1.0, 4.0, 5.0));
323 /// # }
324 /// ```
325 pub fn from_points_ref<'a, I>(pts: I) -> Self
326 where
327 I: IntoIterator<Item = &'a Vector>,
328 {
329 super::aabb_utils::local_point_cloud_aabb(pts.into_iter().copied())
330 }
331
332 /// Creates a new AABB that tightly encloses a set of points (values).
333 ///
334 /// Computes the minimum and maximum coordinates across all points.
335 ///
336 /// # Arguments
337 ///
338 /// * `pts` - An iterator over point values
339 ///
340 /// # Example
341 ///
342 /// ```
343 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
344 /// use parry3d::bounding_volume::Aabb;
345 /// use parry3d::math::Vector;
346 ///
347 /// let aabb = Aabb::from_points(vec![
348 /// Vector::new(1.0, 2.0, 3.0),
349 /// Vector::new(-1.0, 4.0, 2.0),
350 /// Vector::new(0.0, 0.0, 5.0),
351 /// ]);
352 ///
353 /// assert_eq!(aabb.mins, Vector::new(-1.0, 0.0, 2.0));
354 /// assert_eq!(aabb.maxs, Vector::new(1.0, 4.0, 5.0));
355 /// # }
356 /// ```
357 pub fn from_points<I>(pts: I) -> Self
358 where
359 I: IntoIterator<Item = Vector>,
360 {
361 super::aabb_utils::local_point_cloud_aabb(pts)
362 }
363
364 /// Returns the center point of this AABB.
365 ///
366 /// The center is the midpoint between `mins` and `maxs`.
367 ///
368 /// # Example
369 ///
370 /// ```
371 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
372 /// use parry3d::bounding_volume::Aabb;
373 /// use parry3d::math::Vector;
374 ///
375 /// let aabb = Aabb::new(
376 /// Vector::new(-2.0, -3.0, -4.0),
377 /// Vector::new(2.0, 3.0, 4.0)
378 /// );
379 ///
380 /// assert_eq!(aabb.center(), Vector::ZERO);
381 /// # }
382 /// ```
383 #[inline]
384 pub fn center(&self) -> Vector {
385 self.mins.midpoint(self.maxs)
386 }
387
388 /// Returns the half-extents of this AABB.
389 ///
390 /// Half-extents are half the dimensions along each axis.
391 ///
392 /// # Example
393 ///
394 /// ```
395 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
396 /// use parry3d::bounding_volume::Aabb;
397 /// use parry3d::math::Vector;
398 ///
399 /// let aabb = Aabb::new(
400 /// Vector::new(-5.0, -3.0, -2.0),
401 /// Vector::new(5.0, 3.0, 2.0)
402 /// );
403 ///
404 /// let half = aabb.half_extents();
405 /// assert_eq!(half, Vector::new(5.0, 3.0, 2.0));
406 ///
407 /// // Full dimensions are 2 * half_extents
408 /// let full = aabb.extents();
409 /// assert_eq!(full, Vector::new(10.0, 6.0, 4.0));
410 /// # }
411 /// ```
412 #[inline]
413 pub fn half_extents(&self) -> Vector {
414 let half: Real = 0.5;
415 (self.maxs - self.mins) * half
416 }
417
418 /// Returns the volume of this AABB.
419 ///
420 /// - **2D**: Returns the area (width × height)
421 /// - **3D**: Returns the volume (width × height × depth)
422 ///
423 /// # Example
424 ///
425 /// ```
426 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
427 /// use parry3d::bounding_volume::Aabb;
428 /// use parry3d::math::Vector;
429 ///
430 /// // A 2x3x4 box
431 /// let aabb = Aabb::new(
432 /// Vector::ZERO,
433 /// Vector::new(2.0, 3.0, 4.0)
434 /// );
435 ///
436 /// assert_eq!(aabb.volume(), 24.0); // 2 * 3 * 4
437 /// # }
438 /// ```
439 #[inline]
440 pub fn volume(&self) -> Real {
441 let extents = self.extents();
442 #[cfg(feature = "dim2")]
443 return extents.x * extents.y;
444 #[cfg(feature = "dim3")]
445 return extents.x * extents.y * extents.z;
446 }
447
448 /// In 3D, returns the half-area. In 2D returns the half-perimeter of the AABB.
449 pub fn half_area_or_perimeter(&self) -> Real {
450 #[cfg(feature = "dim2")]
451 return self.half_perimeter();
452 #[cfg(feature = "dim3")]
453 return self.half_area();
454 }
455
456 /// The half perimeter of this `Aabb`.
457 #[cfg(feature = "dim2")]
458 pub fn half_perimeter(&self) -> Real {
459 let extents = self.extents();
460 extents.x + extents.y
461 }
462
463 /// The half area of this `Aabb`.
464 #[cfg(feature = "dim3")]
465 pub fn half_area(&self) -> Real {
466 let extents = self.extents();
467 extents.x * (extents.y + extents.z) + extents.y * extents.z
468 }
469
470 /// The extents of this `Aabb`.
471 #[inline]
472 pub fn extents(&self) -> Vector {
473 self.maxs - self.mins
474 }
475
476 /// Enlarges this `Aabb` so it also contains the point `pt`.
477 pub fn take_point(&mut self, pt: Vector) {
478 self.mins = self.mins.min(pt);
479 self.maxs = self.maxs.max(pt);
480 }
481
482 /// Computes the `Aabb` bounding `self` transformed by `m`.
483 #[inline]
484 pub fn transform_by(&self, m: &Pose) -> Self {
485 let ls_center = self.center();
486 let center = m * ls_center;
487 let ws_half_extents = m.absolute_transform_vector(self.half_extents());
488
489 Aabb::new(center + (-ws_half_extents), center + ws_half_extents)
490 }
491
492 /// Computes the Aabb bounding `self` translated by `translation`.
493 #[inline]
494 pub fn translated(mut self, translation: Vector) -> Self {
495 self.mins += translation;
496 self.maxs += translation;
497 self
498 }
499
500 #[inline]
501 pub fn scaled(self, scale: Vector) -> Self {
502 let a = self.mins * scale;
503 let b = self.maxs * scale;
504 Self {
505 mins: a.min(b),
506 maxs: a.max(b),
507 }
508 }
509
510 /// Returns an AABB with the same center as `self` but with extents scaled by `scale`.
511 ///
512 /// # Parameters
513 /// - `scale`: the scaling factor. It can be non-uniform and/or negative. The AABB being
514 /// symmetric wrt. its center, a negative scale value has the same effect as scaling
515 /// by its absolute value.
516 #[inline]
517 #[must_use]
518 pub fn scaled_wrt_center(self, scale: Vector) -> Self {
519 let center = self.center();
520 // Multiply the extents by the scale. Negative scaling might modify the half-extent
521 // sign, so we take the absolute value. The AABB being symmetric that absolute value
522 // is valid.
523 let half_extents = self.half_extents() * scale.abs();
524 Self::from_half_extents(center, half_extents)
525 }
526
527 /// The smallest bounding sphere containing this `Aabb`.
528 #[inline]
529 pub fn bounding_sphere(&self) -> BoundingSphere {
530 let center = self.center();
531 let radius = self.mins.distance(self.maxs) * 0.5;
532 BoundingSphere::new(center, radius)
533 }
534
535 /// Does this AABB contains a point expressed in the same coordinate frame as `self`?
536 #[inline]
537 pub fn contains_local_point(&self, point: Vector) -> bool {
538 for i in 0..DIM {
539 if point[i] < self.mins[i] || point[i] > self.maxs[i] {
540 return false;
541 }
542 }
543
544 true
545 }
546
547 /// Computes the distance between the origin and this AABB.
548 pub fn distance_to_origin(&self) -> Real {
549 self.mins.max(-self.maxs).max(Vector::ZERO).length()
550 }
551
552 /// Does this AABB intersects an AABB `aabb2` moving at velocity `vel12` relative to `self`?
553 #[inline]
554 pub fn intersects_moving_aabb(&self, aabb2: &Self, vel12: Vector) -> bool {
555 // Minkowski sum.
556 let msum = Aabb {
557 mins: self.mins - aabb2.maxs,
558 maxs: self.maxs - aabb2.mins,
559 };
560 let ray = Ray::new(Vector::ZERO, vel12);
561
562 msum.intersects_local_ray(&ray, 1.0)
563 }
564
565 /// Computes the intersection of this `Aabb` and another one.
566 pub fn intersection(&self, other: &Aabb) -> Option<Aabb> {
567 let result = Aabb {
568 mins: self.mins.max(other.mins),
569 maxs: self.maxs.min(other.maxs),
570 };
571
572 for i in 0..DIM {
573 if result.mins[i] > result.maxs[i] {
574 return None;
575 }
576 }
577
578 Some(result)
579 }
580
581 /// Computes two AABBs for the intersection between two translated and rotated AABBs.
582 ///
583 /// This method returns two AABBs: the first is expressed in the local-space of `self`,
584 /// and the second is expressed in the local-space of `aabb2`.
585 pub fn aligned_intersections(&self, pos12: &Pose, aabb2: &Self) -> Option<(Aabb, Aabb)> {
586 let pos21 = pos12.inverse();
587
588 let aabb2_1 = aabb2.transform_by(pos12);
589 let inter1_1 = self.intersection(&aabb2_1)?;
590 let inter1_2 = inter1_1.transform_by(&pos21);
591
592 let aabb1_2 = self.transform_by(&pos21);
593 let inter2_2 = aabb2.intersection(&aabb1_2)?;
594 let inter2_1 = inter2_2.transform_by(pos12);
595
596 Some((
597 inter1_1.intersection(&inter2_1)?,
598 inter1_2.intersection(&inter2_2)?,
599 ))
600 }
601
602 /// Returns the difference between this `Aabb` and `rhs`.
603 ///
604 /// Removing another `Aabb` from `self` will result in zero, one, or up to 4 (in 2D) or 8 (in 3D)
605 /// new smaller Aabbs.
606 pub fn difference(&self, rhs: &Aabb) -> ArrayVec<Self, TWO_DIM> {
607 self.difference_with_cut_sequence(rhs).0
608 }
609
610 /// Returns the difference between this `Aabb` and `rhs`.
611 ///
612 /// Removing another `Aabb` from `self` will result in zero, one, or up to 4 (in 2D) or 8 (in 3D)
613 /// new smaller Aabbs.
614 ///
615 /// # Return
616 /// This returns a pair where the first item are the new Aabbs and the second item is
617 /// the sequence of cuts applied to `self` to obtain the new Aabbs. Each cut is performed
618 /// along one axis identified by `-1, -2, -3` for `-X, -Y, -Z` and `1, 2, 3` for `+X, +Y, +Z`, and
619 /// the plane’s bias.
620 ///
621 /// The cuts are applied sequentially. For example, if `result.1[0]` contains `1`, then it means
622 /// that `result.0[0]` is equal to the piece of `self` lying in the negative half-space delimited
623 /// by the plane with outward normal `+X`. Then, the other piece of `self` generated by this cut
624 /// (i.e. the piece of `self` lying in the positive half-space delimited by the plane with outward
625 /// normal `+X`) is the one that will be affected by the next cut.
626 ///
627 /// The returned cut sequence will be empty if the aabbs are disjoint.
628 pub fn difference_with_cut_sequence(
629 &self,
630 rhs: &Aabb,
631 ) -> (ArrayVec<Self, TWO_DIM>, ArrayVec<(i8, Real), TWO_DIM>) {
632 let mut result = ArrayVec::new();
633 let mut cut_sequence = ArrayVec::new();
634
635 // NOTE: special case when the boxes are disjoint.
636 // This isn’t exactly the same as `!self.intersects(rhs)`
637 // because of the equality.
638 for i in 0..DIM {
639 if self.mins[i] >= rhs.maxs[i] || self.maxs[i] <= rhs.mins[i] {
640 result.push(*self);
641 return (result, cut_sequence);
642 }
643 }
644
645 let mut rest = *self;
646
647 for i in 0..DIM {
648 if rhs.mins[i] > rest.mins[i] {
649 let mut fragment = rest;
650 fragment.maxs[i] = rhs.mins[i];
651 rest.mins[i] = rhs.mins[i];
652 result.push(fragment);
653 cut_sequence.push((i as i8 + 1, rhs.mins[i]));
654 }
655
656 if rhs.maxs[i] < rest.maxs[i] {
657 let mut fragment = rest;
658 fragment.mins[i] = rhs.maxs[i];
659 rest.maxs[i] = rhs.maxs[i];
660 result.push(fragment);
661 cut_sequence.push((-(i as i8 + 1), -rhs.maxs[i]));
662 }
663 }
664
665 (result, cut_sequence)
666 }
667
668 /// Computes the vertices of this `Aabb`.
669 ///
670 /// The vertices are given in the following order in a right-handed coordinate system:
671 /// ```text
672 /// y 3 - 2
673 /// | | |
674 /// ___ x 0 - 1
675 /// ```
676 #[inline]
677 #[cfg(feature = "dim2")]
678 pub fn vertices(&self) -> [Vector; 4] {
679 [
680 Vector::new(self.mins.x, self.mins.y),
681 Vector::new(self.maxs.x, self.mins.y),
682 Vector::new(self.maxs.x, self.maxs.y),
683 Vector::new(self.mins.x, self.maxs.y),
684 ]
685 }
686
687 /// Computes the vertices of this `Aabb`.
688 ///
689 /// The vertices are given in the following order, in a right-handed coordinate system:
690 /// ```text
691 /// y 3 - 2
692 /// | 7 − 6 |
693 /// ___ x | | 1 (the zero is below 3 and on the left of 1,
694 /// / 4 - 5 hidden by the 4-5-6-7 face.)
695 /// z
696 /// ```
697 #[inline]
698 #[cfg(feature = "dim3")]
699 pub fn vertices(&self) -> [Vector; 8] {
700 [
701 Vector::new(self.mins.x, self.mins.y, self.mins.z),
702 Vector::new(self.maxs.x, self.mins.y, self.mins.z),
703 Vector::new(self.maxs.x, self.maxs.y, self.mins.z),
704 Vector::new(self.mins.x, self.maxs.y, self.mins.z),
705 Vector::new(self.mins.x, self.mins.y, self.maxs.z),
706 Vector::new(self.maxs.x, self.mins.y, self.maxs.z),
707 Vector::new(self.maxs.x, self.maxs.y, self.maxs.z),
708 Vector::new(self.mins.x, self.maxs.y, self.maxs.z),
709 ]
710 }
711
712 /// Splits this `Aabb` at its center, into four parts (as in a quad-tree).
713 #[inline]
714 #[cfg(feature = "dim2")]
715 pub fn split_at_center(&self) -> [Aabb; 4] {
716 let center = self.center();
717
718 [
719 Aabb::new(self.mins, center),
720 Aabb::new(
721 Vector::new(center.x, self.mins.y),
722 Vector::new(self.maxs.x, center.y),
723 ),
724 Aabb::new(center, self.maxs),
725 Aabb::new(
726 Vector::new(self.mins.x, center.y),
727 Vector::new(center.x, self.maxs.y),
728 ),
729 ]
730 }
731
732 /// Splits this `Aabb` at its center, into eight parts (as in an octree).
733 #[inline]
734 #[cfg(feature = "dim3")]
735 pub fn split_at_center(&self) -> [Aabb; 8] {
736 let center = self.center();
737
738 [
739 Aabb::new(
740 Vector::new(self.mins.x, self.mins.y, self.mins.z),
741 Vector::new(center.x, center.y, center.z),
742 ),
743 Aabb::new(
744 Vector::new(center.x, self.mins.y, self.mins.z),
745 Vector::new(self.maxs.x, center.y, center.z),
746 ),
747 Aabb::new(
748 Vector::new(center.x, center.y, self.mins.z),
749 Vector::new(self.maxs.x, self.maxs.y, center.z),
750 ),
751 Aabb::new(
752 Vector::new(self.mins.x, center.y, self.mins.z),
753 Vector::new(center.x, self.maxs.y, center.z),
754 ),
755 Aabb::new(
756 Vector::new(self.mins.x, self.mins.y, center.z),
757 Vector::new(center.x, center.y, self.maxs.z),
758 ),
759 Aabb::new(
760 Vector::new(center.x, self.mins.y, center.z),
761 Vector::new(self.maxs.x, center.y, self.maxs.z),
762 ),
763 Aabb::new(
764 Vector::new(center.x, center.y, center.z),
765 Vector::new(self.maxs.x, self.maxs.y, self.maxs.z),
766 ),
767 Aabb::new(
768 Vector::new(self.mins.x, center.y, center.z),
769 Vector::new(center.x, self.maxs.y, self.maxs.z),
770 ),
771 ]
772 }
773
774 /// Enlarges this AABB on each side by the given `half_extents`.
775 #[must_use]
776 pub fn add_half_extents(&self, half_extents: Vector) -> Self {
777 Self {
778 mins: self.mins - half_extents,
779 maxs: self.maxs + half_extents,
780 }
781 }
782
783 /// Projects every point of `Aabb` on an arbitrary axis.
784 pub fn project_on_axis(&self, axis: Vector) -> (Real, Real) {
785 let cuboid = Cuboid::new(self.half_extents());
786 let shift = cuboid.local_support_point_toward(axis).dot(axis).abs();
787 let center = self.center().dot(axis);
788 (center - shift, center + shift)
789 }
790
791 #[cfg(feature = "dim3")]
792 #[cfg(feature = "alloc")]
793 pub fn intersects_spiral(
794 &self,
795 point: Vector,
796 spiral_center: Vector,
797 axis: Vector,
798 linvel: Vector,
799 angvel: Real,
800 ) -> bool {
801 use crate::math::{Matrix2, Vector2};
802 use crate::utils::WBasis;
803 use crate::utils::{Interval, IntervalFunction};
804 use alloc::vec;
805
806 struct SpiralPlaneDistance {
807 spiral_center: Vector,
808 tangents: [Vector; 2],
809 linvel: Vector,
810 angvel: Real,
811 point: Vector2,
812 plane: Vector,
813 bias: Real,
814 }
815
816 impl SpiralPlaneDistance {
817 fn spiral_pt_at(&self, t: Real) -> Vector {
818 let angle = t * self.angvel;
819
820 // NOTE: we construct the rotation matrix explicitly here instead
821 // of using `Rotation2::new()` because we will use similar
822 // formulas on the interval methods.
823 let (sin, cos) = <Real as simba::scalar::ComplexField>::sin_cos(angle);
824 // Mat2 in column-major: first column is [cos, sin], second is [-sin, cos]
825 let rotmat = Matrix2::from_cols(Vector2::new(cos, sin), Vector2::new(-sin, cos));
826
827 let rotated_pt = rotmat * self.point;
828 let shift = self.tangents[0] * rotated_pt.x + self.tangents[1] * rotated_pt.y;
829 self.spiral_center + self.linvel * t + shift
830 }
831 }
832
833 impl IntervalFunction<Real> for SpiralPlaneDistance {
834 fn eval(&self, t: Real) -> Real {
835 let point_pos = self.spiral_pt_at(t);
836 point_pos.dot(self.plane) - self.bias
837 }
838
839 fn eval_interval(&self, t: Interval<Real>) -> Interval<Real> {
840 // This is the same as `self.eval` except that `t` is an interval.
841 let angle = t * self.angvel;
842 let (sin, cos) = angle.sin_cos();
843
844 // Compute rotated point manually with interval arithmetic
845 let rotated_pt_x =
846 cos * Interval::splat(self.point.x) - sin * Interval::splat(self.point.y);
847 let rotated_pt_y =
848 sin * Interval::splat(self.point.x) + cos * Interval::splat(self.point.y);
849
850 let shift_x = Interval::splat(self.tangents[0].x) * rotated_pt_x
851 + Interval::splat(self.tangents[1].x) * rotated_pt_y;
852 let shift_y = Interval::splat(self.tangents[0].y) * rotated_pt_x
853 + Interval::splat(self.tangents[1].y) * rotated_pt_y;
854 let shift_z = Interval::splat(self.tangents[0].z) * rotated_pt_x
855 + Interval::splat(self.tangents[1].z) * rotated_pt_y;
856
857 let point_pos_x = Interval::splat(self.spiral_center.x)
858 + Interval::splat(self.linvel.x) * t
859 + shift_x;
860 let point_pos_y = Interval::splat(self.spiral_center.y)
861 + Interval::splat(self.linvel.y) * t
862 + shift_y;
863 let point_pos_z = Interval::splat(self.spiral_center.z)
864 + Interval::splat(self.linvel.z) * t
865 + shift_z;
866
867 point_pos_x * Interval::splat(self.plane.x)
868 + point_pos_y * Interval::splat(self.plane.y)
869 + point_pos_z * Interval::splat(self.plane.z)
870 - Interval::splat(self.bias)
871 }
872
873 fn eval_interval_gradient(&self, t: Interval<Real>) -> Interval<Real> {
874 let angle = t * self.angvel;
875 let (sin, cos) = angle.sin_cos();
876 let angvel_interval = Interval::splat(self.angvel);
877
878 // Derivative of rotation matrix applied to point
879 let rotated_pt_x = (-sin * angvel_interval) * Interval::splat(self.point.x)
880 - (cos * angvel_interval) * Interval::splat(self.point.y);
881 let rotated_pt_y = (cos * angvel_interval) * Interval::splat(self.point.x)
882 + (-sin * angvel_interval) * Interval::splat(self.point.y);
883
884 let shift_x = Interval::splat(self.tangents[0].x) * rotated_pt_x
885 + Interval::splat(self.tangents[1].x) * rotated_pt_y;
886 let shift_y = Interval::splat(self.tangents[0].y) * rotated_pt_x
887 + Interval::splat(self.tangents[1].y) * rotated_pt_y;
888 let shift_z = Interval::splat(self.tangents[0].z) * rotated_pt_x
889 + Interval::splat(self.tangents[1].z) * rotated_pt_y;
890
891 let point_vel_x = shift_x + Interval::splat(self.linvel.x);
892 let point_vel_y = shift_y + Interval::splat(self.linvel.y);
893 let point_vel_z = shift_z + Interval::splat(self.linvel.z);
894
895 point_vel_x * Interval::splat(self.plane.x)
896 + point_vel_y * Interval::splat(self.plane.y)
897 + point_vel_z * Interval::splat(self.plane.z)
898 }
899 }
900
901 let tangents = axis.orthonormal_basis();
902 let dpos = point - spiral_center;
903 #[cfg(feature = "f32")]
904 let spiral_point = glamx::Vec2::new(dpos.dot(tangents[0]), dpos.dot(tangents[1]));
905 #[cfg(feature = "f64")]
906 let spiral_point = glamx::DVec2::new(dpos.dot(tangents[0]), dpos.dot(tangents[1]));
907 let mut distance_fn = SpiralPlaneDistance {
908 spiral_center,
909 tangents,
910 linvel,
911 angvel,
912 point: spiral_point,
913 plane: Vector::X,
914 bias: 0.0,
915 };
916
917 // Check the 8 planar faces of the Aabb.
918 let mut roots = vec![];
919 let mut candidates = vec![];
920
921 let planes = [
922 (-self.mins[0], -Vector::X, 0),
923 (self.maxs[0], Vector::X, 0),
924 (-self.mins[1], -Vector::Y, 1),
925 (self.maxs[1], Vector::Y, 1),
926 (-self.mins[2], -Vector::Z, 2),
927 (self.maxs[2], Vector::Z, 2),
928 ];
929
930 let range = self.project_on_axis(axis);
931 let range_bias = spiral_center.dot(axis);
932 let interval = Interval::sort(range.0, range.1) - range_bias;
933
934 for (bias, axis, i) in &planes {
935 distance_fn.plane = *axis;
936 distance_fn.bias = *bias;
937
938 crate::utils::find_root_intervals_to(
939 &distance_fn,
940 interval,
941 1.0e-5,
942 1.0e-5,
943 100,
944 &mut roots,
945 &mut candidates,
946 );
947
948 for root in roots.drain(..) {
949 let point = distance_fn.spiral_pt_at(root.midpoint());
950 let (j, k) = ((i + 1) % 3, (i + 2) % 3);
951 if point[j] >= self.mins[j]
952 && point[j] <= self.maxs[j]
953 && point[k] >= self.mins[k]
954 && point[k] <= self.maxs[k]
955 {
956 return true;
957 }
958 }
959 }
960
961 false
962 }
963}
964
965impl BoundingVolume for Aabb {
966 #[inline]
967 fn center(&self) -> Vector {
968 self.center()
969 }
970
971 #[inline]
972 fn intersects(&self, other: &Aabb) -> bool {
973 (self.mins.cmple(other.maxs) & self.maxs.cmpge(other.mins)).all()
974 }
975
976 #[inline]
977 fn contains(&self, other: &Aabb) -> bool {
978 (self.mins.cmple(other.mins) & self.maxs.cmpge(other.maxs)).all()
979 }
980
981 #[inline]
982 fn merge(&mut self, other: &Aabb) {
983 self.mins = self.mins.min(other.mins);
984 self.maxs = self.maxs.max(other.maxs);
985 }
986
987 #[inline]
988 fn merged(&self, other: &Aabb) -> Aabb {
989 Aabb {
990 mins: self.mins.min(other.mins),
991 maxs: self.maxs.max(other.maxs),
992 }
993 }
994
995 #[inline]
996 fn loosen(&mut self, amount: Real) {
997 assert!(amount >= 0.0, "The loosening margin must be positive.");
998 self.mins += Vector::splat(-amount);
999 self.maxs += Vector::splat(amount);
1000 }
1001
1002 #[inline]
1003 fn loosened(&self, amount: Real) -> Aabb {
1004 assert!(amount >= 0.0, "The loosening margin must be positive.");
1005 Aabb {
1006 mins: self.mins + Vector::splat(-amount),
1007 maxs: self.maxs + Vector::splat(amount),
1008 }
1009 }
1010
1011 #[inline]
1012 fn tighten(&mut self, amount: Real) {
1013 assert!(amount >= 0.0, "The tightening margin must be positive.");
1014 self.mins += Vector::splat(amount);
1015 self.maxs += Vector::splat(-amount);
1016 assert!(
1017 self.mins.cmple(self.maxs).all(),
1018 "The tightening margin is to large."
1019 );
1020 }
1021
1022 #[inline]
1023 fn tightened(&self, amount: Real) -> Aabb {
1024 assert!(amount >= 0.0, "The tightening margin must be positive.");
1025
1026 Aabb::new(
1027 self.mins + Vector::splat(amount),
1028 self.maxs + Vector::splat(-amount),
1029 )
1030 }
1031}