phys_geom/

aabb3.rs

// Copyright (C) 2020-2025 phys-geom authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! Axis-Aligned Bounding Box (AABB) operations in 3D space.
//!
//! This module provides comprehensive functionality for working with axis-aligned bounding boxes,
//! which are fundamental components in physics engines, collision detection, and spatial
//! partitioning systems.
//!
//! # Overview
//!
//! An AABB is a rectangular box whose faces are aligned with the coordinate axes. It's defined
//! by two points: a minimum corner (min) and a maximum corner (max). The AABB is the smallest
//! box that contains all specified points and is axis-aligned.
//!
//! # Key Features
//!
//! - **Construction**: Multiple ways to create AABBs from points, shapes, or raw data
//! - **Ray Casting**: Efficient ray-AABB intersection testing for collision detection
//! - **Transformations**: Support for transforming AABBs with isometries
//! - **Operations**: Union, intersection, expansion, and other set operations
//! - **Validation**: Runtime assertions for valid AABB constraints
//! - **Serialization**: Optional serde support for persistence
//!
//! # Common Operations
//!
//! ```rust
//! use phys_geom::{Aabb3, math::Point3, math::Vec3, math::Isometry3};
//!
//! // Create an AABB from two points
//! let aabb = Aabb3::new(Point3::new(-1.0, -1.0, -1.0), Point3::new(1.0, 1.0, 1.0));
//!
//! // Get properties
//! let center = aabb.center();
//! let extents = aabb.get_extents();
//!
//! // Transform the AABB
//! let isometry = Isometry3::default();
//! let transformed_aabb = aabb.transform(isometry);
//!
//! // Expand the AABB
//! let expanded_aabb = aabb.with_margin(Vec3::new(0.1, 0.1, 0.1));
//! ```
//!
//! # Ray Casting
//!
//! The module provides efficient ray-AABB intersection testing:
//!
//! ```rust
//! use phys_geom::{Aabb3, Ray, math::Point3, math::Vec3};
//!
//! let aabb = Aabb3::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0));
//! let direction = Vec3::x_axis();
//! let ray = Ray::new(Point3::new(-1.0, 0.5, 0.5), direction);
//!
//! // Check if ray intersects AABB
//! let intersects = aabb.raycast(ray, 10.0);
//! ```
//!
//! # Performance Considerations
//!
//! - AABB operations are generally O(1) time complexity
//! - Ray casting uses efficient slab-based algorithms
//! - Transform operations require computing all 8 corners (can be optimized)
//! - Memory usage is minimal (just two 3D points)
//!
//! # Special Values
//!
//! - [`Aabb3::ANTI_INFINITE`]: An empty AABB used as initial value for union operations
//! - [`Aabb3::ZERO`]: A zero-sized AABB at the origin

use std::ops::{Add, AddAssign, Sub, SubAssign};

use na::point;

use super::Interval;
use crate::aabb2::Aabb2;
use crate::math::{Isometry3, Point3, Real, Vec3};
use crate::shape::*;
use crate::Ray;

/// An axis-aligned bounding box in 3D space.
///
/// An AABB is the smallest rectangular box that contains a set of points, with its faces
/// aligned to the coordinate axes. It's defined by two 3D points:
/// - `min`: The corner with minimum coordinate values
/// - `max`: The corner with maximum coordinate values
///
/// AABBs are fundamental in physics engines for:
/// - Broad-phase collision detection
/// - Spatial partitioning and culling
/// - Bounding volume hierarchies
/// - Ray casting and intersection testing
///
/// # Examples
///
/// ```rust
/// use phys_geom::{Aabb3, math::Point3};
///
/// // Create an AABB from two points
/// let aabb = Aabb3::new(
///     Point3::new(-1.0, -1.0, -1.0),
///     Point3::new(1.0, 1.0, 1.0)
/// );
///
/// // Use special constants
/// let empty_aabb = Aabb3::ANTI_INFINITE;
/// let zero_aabb = Aabb3::ZERO;
/// ```
///
/// # Invariants
///
/// For a valid AABB, the following must hold: `min.x <= max.x`, `min.y <= max.y`, `min.z <= max.z`
///
/// # Memory Layout
///
/// The struct uses `#[repr(C)]` for FFI compatibility and contains exactly two Point3 values.
#[derive(Copy, Clone, Default, Debug, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[repr(C)]
pub struct Aabb3 {
    /// The corner with minimum coordinate values
    min: Point3,
    /// The corner with maximum coordinate values
    max: Point3,
}

impl Aabb3 {
    /// An empty/invalid AABB used as initial value for union operations.
    ///
    /// This special AABB has `min = [MAX, MAX, MAX]` and `max = [MIN, MIN, MIN]`,
    /// making it the identity element for union operations. Any AABB unioned with
    /// ANTI_INFINITE will result in the original AABB.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use phys_geom::{Aabb3, math::Point3};
    ///
    /// let mut aabb = Aabb3::ANTI_INFINITE;
    /// aabb.grow(Point3::new(1.0, 2.0, 3.0));
    /// aabb.grow(Point3::new(-1.0, -2.0, -3.0));
    ///
    /// assert_eq!(aabb.min(), Point3::new(-1.0, -2.0, -3.0));
    /// assert_eq!(aabb.max(), Point3::new(1.0, 2.0, 3.0));
    /// ```
    pub const ANTI_INFINITE: Self = Self {
        min: point![Real::MAX, Real::MAX, Real::MAX],
        max: point![Real::MIN, Real::MIN, Real::MIN],
    };
    /// A zero-sized AABB located at the origin.
    ///
    /// Both min and max points are at the origin (0, 0, 0), resulting in an AABB
    /// with zero volume. This is useful as a starting point for incremental
    /// bounding box computation.
    pub const ZERO: Aabb3 = Self {
        min: point![0.0, 0.0, 0.0],
        max: point![0.0, 0.0, 0.0],
    };

    #[inline]
    #[must_use]
    pub fn new(p1: impl Into<[Real; 3]>, p2: impl Into<[Real; 3]>) -> Aabb3 {
        let p1: Point3 = p1.into().into();
        let p2: Point3 = p2.into().into();
        Aabb3 {
            min: Point3::new(
                Real::min(p1.x, p2.x),
                Real::min(p1.y, p2.y),
                Real::min(p1.z, p2.z),
            ),
            max: Point3::new(
                Real::max(p1.x, p2.x),
                Real::max(p1.y, p2.y),
                Real::max(p1.z, p2.z),
            ),
        }
    }

    /// Create AABB bound with min and max point.
    /// Different from `new` method, the `new_unchecked` won't compare min and max point, and will
    /// assign them to AABB directly. It means user should be ensure that min point is
    /// `actually` smaller than max point.
    #[inline]
    #[must_use]
    pub fn new_unchecked(min: impl Into<Point3>, max: impl Into<Point3>) -> Self {
        let min = min.into();
        let max = max.into();
        #[cfg(debug_assertions)]
        if min != Self::ANTI_INFINITE.min || max != Self::ANTI_INFINITE.max {
            // If not in anti-infinite state, we should check min and max.
            let error_msg = format!("min > max, min = {min}, max = {max}");
            debug_assert!(min.x <= max.x, "{}", error_msg);
            debug_assert!(min.y <= max.y, "{}", error_msg);
            debug_assert!(min.z <= max.z, "{}", error_msg);
        }
        Self { min, max }
    }

    //first 3 element is min, later 3 elements is max
    #[inline]
    #[must_use]
    pub fn from_array_unchecked(values: [Real; 6]) -> Self {
        Aabb3 {
            min: Point3::new(values[0], values[1], values[2]),
            max: Point3::new(values[3], values[4], values[5]),
        }
    }

    /// Create AABB from center and extents.
    #[inline]
    #[must_use]
    pub fn from_center_extents(center: impl Into<Point3>, extents: impl Into<Vec3>) -> Self {
        let center = center.into();
        let extents = extents.into();
        Aabb3::new_unchecked(center - extents, center + extents)
    }

    /// Returns the minimum point of the AABB.
    #[inline]
    #[must_use]
    pub fn min(&self) -> Point3 {
        self.min
    }

    /// Returns the maximum point of the AABB.
    #[inline]
    #[must_use]
    pub fn max(&self) -> Point3 {
        self.max
    }

    /// Get the interval of the AABB along the given axis.
    ///
    /// # Panics
    ///
    /// Panics if `axis` is greater than 2.
    #[inline]
    #[must_use]
    pub fn get_interval(&self, axis: usize) -> Interval {
        debug_assert!(axis < 3);
        Interval::new(self.min[axis], self.max[axis])
    }

    /// Set the minimum value of the AABB at the given axis.
    ///
    /// # Panics
    ///
    /// Panics if the set value is large than `max[axis]`
    #[inline]
    pub fn set_min_at(&mut self, axis: usize, value: Real) {
        debug_assert!(axis < 3);
        assert!(value <= self.max[axis]);
        self.min[axis] = value;
    }

    /// Set the maximum value of the AABB at the given axis.
    ///
    /// # Panics
    ///
    /// Panics if the set value is smaller than `min[axis]`
    #[inline]
    pub fn set_max_at(&mut self, axis: usize, value: Real) {
        debug_assert!(axis < 3);
        assert!(self.min[axis] <= value);
        self.max[axis] = value;
    }

    /// Grow the aabb to include the given point.
    #[inline]
    pub fn grow(&mut self, p: impl Into<Point3>) {
        let p = p.into();
        self.min = self.min.inf(&p);
        self.max = self.max.sup(&p);
    }

    #[inline]
    pub fn merge(&mut self, other: &Self) {
        self.min = self.min.inf(&other.min);
        self.max = self.max.sup(&other.max);
    }

    #[inline]
    pub fn expand(&mut self, margin: Real) {
        self.min -= Vec3::new(margin, margin, margin);
        self.max += Vec3::new(margin, margin, margin);
    }

    /// Offset the AABB by the given vector.
    #[inline]
    pub fn offset(&mut self, offset: impl Into<[Real; 3]>) {
        let offset = Vec3::from(offset.into());
        self.min += offset;
        self.max += offset;
    }

    /// Offset the AABB by the given vector, returning the modified AABB.
    #[inline]
    pub fn with_offset(mut self, offset: impl Into<[Real; 3]>) -> Self {
        self.offset(offset);
        self
    }

    #[inline]
    #[must_use]
    pub fn corners(&self) -> [Point3; 8] {
        let min = self.min;
        let max = self.max;

        // Use consistent coordinate combinations for all 8 corners
        [
            min,                              // (min.x, min.y, min.z)
            Point3::new(min.x, min.y, max.z), // (min.x, min.y, max.z)
            Point3::new(min.x, max.y, min.z), // (min.x, max.y, min.z)
            Point3::new(min.x, max.y, max.z), // (min.x, max.y, max.z)
            Point3::new(max.x, min.y, min.z), // (max.x, min.y, min.z)
            Point3::new(max.x, min.y, max.z), // (max.x, min.y, max.z)
            Point3::new(max.x, max.y, min.z), // (max.x, max.y, min.z)
            max,                              // (max.x, max.y, max.z)
        ]
    }

    /// Extend AABB with margin.
    #[inline]
    #[must_use]
    pub fn with_margin(&self, margin: impl Into<[Real; 3]>) -> Self {
        let margin = Vec3::from(margin.into());
        let min = self.min - margin;
        let max = self.max + margin;
        Self::new_unchecked(min, max)
    }

    ///TODO: maybe we have more more efficient method (issue #1243)
    #[inline]
    #[must_use]
    pub fn transform(&self, transform: impl Into<Isometry3>) -> Self {
        let transform = transform.into();
        let corners = self.corners();
        let c0 = transform * corners[0];
        let c1 = transform * corners[1];
        let mut aabb = Aabb3::new(c0, c1);
        for corner in corners.iter().skip(2) {
            aabb.grow(transform * *corner);
        }
        aabb
    }

    /// Get the center point of the AABB
    #[inline]
    #[must_use]
    pub fn center(&self) -> Point3 {
        const HALF: Real = 0.5;
        Point3::from((self.min.coords + self.max.coords) * HALF)
    }

    /// Get the size of the AABB (Excludes cases where the end points are equal)
    #[inline]
    #[must_use]
    pub fn size(&self) -> Vec3 {
        self.max - self.min
    }

    #[inline]
    #[must_use]
    pub fn get_extents(&self) -> Vec3 {
        const HALF: Real = 0.5;
        self.size() * HALF
    }

    /// Overlap test two AABB.
    #[inline]
    #[must_use]
    pub fn overlap_test(&self, rhs: &Aabb3) -> bool {
        Self::overlap_test_1d(self.min[0], self.max[0], rhs.min[0], rhs.max[0])
            && Self::overlap_test_1d(self.min[1], self.max[1], rhs.min[1], rhs.max[1])
            && Self::overlap_test_1d(self.min[2], self.max[2], rhs.min[2], rhs.max[2])
    }

    #[inline]
    fn overlap_test_1d(min0: Real, max0: Real, min1: Real, max1: Real) -> bool {
        max0 > min1 && min0 < max1
    }

    #[inline]
    #[must_use]
    pub fn raycast(&self, ray: Ray, max_distance: Real) -> bool {
        self.raycast_by_one_over_direction(ray.origin, ray.one_over_direction(), max_distance)
    }

    /// # Examples
    /// ```
    /// use phys_geom::{Aabb3, Ray};
    /// use phys_geom::{math::Point3, math::Vec3};
    /// let ray = Ray::new_with_vec3(Point3::origin(), Vec3::new(0.0, 0.0, 1.0));
    /// let aabb = Aabb3::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0));
    /// aabb.raycast_by_one_over_direction(ray.origin, ray.one_over_direction(), 1.0);
    /// ```
    #[inline]
    #[must_use]
    pub fn raycast_by_one_over_direction(
        &self,
        origin: impl Into<[Real; 3]>,
        one_over_direction: impl Into<[Real; 3]>,
        max_distance: Real,
    ) -> bool {
        self.raycast_by_one_over_direction_impl(origin, one_over_direction, max_distance)
            .is_some()
    }

    /// Raycast the AABB with one over direction.
    /// Return:
    ///  * distance vector to each entry side of the AABB,
    ///  * entry distance
    #[inline]
    pub fn raycast_by_one_over_direction_impl(
        &self,
        origin: impl Into<[Real; 3]>,
        one_over_direction: impl Into<[Real; 3]>,
        max_distance: Real,
    ) -> Option<(Vec3, Real)> {
        let origin = Point3::from(origin.into());
        let one_over_direction = Vec3::from(one_over_direction.into());
        let t0 = (self.min - origin).component_mul(&one_over_direction);
        let t1 = (self.max - origin).component_mul(&one_over_direction);
        let term_exit = t0.sup(&t1);
        let term_entry = t0.inf(&t1);
        let exit = Real::min(max_distance, term_exit.min());
        let max_entry = term_entry.max();
        let term = Real::max(0.0, max_entry);
        if term <= exit {
            Some((term_entry, max_entry))
        } else {
            None
        }
    }

    #[inline]
    #[must_use]
    pub fn xz(&self) -> Aabb2 {
        Aabb2::new(self.min.xz(), self.max.xz())
    }

    #[inline]
    #[must_use]
    pub fn xy(&self) -> Aabb2 {
        Aabb2::new(self.min.xy(), self.max.xy())
    }

    #[inline]
    #[must_use]
    pub fn yz(&self) -> Aabb2 {
        Aabb2::new(self.min.yz(), self.max.yz())
    }
}

impl Add<Vec3> for Aabb3 {
    type Output = Aabb3;

    #[inline]
    fn add(self, rhs: Vec3) -> Self::Output {
        let mut aabb = self;
        aabb.offset(rhs);
        aabb
    }
}

impl Sub<Vec3> for Aabb3 {
    type Output = Aabb3;

    #[inline]
    fn sub(self, rhs: Vec3) -> Self::Output {
        let min = self.min - rhs;
        let max = self.max - rhs;
        Aabb3::new_unchecked(min, max)
    }
}

impl AddAssign<Vec3> for Aabb3 {
    #[inline]
    fn add_assign(&mut self, rhs: Vec3) {
        self.min += rhs;
        self.max += rhs;
    }
}

impl SubAssign<Vec3> for Aabb3 {
    #[inline]
    fn sub_assign(&mut self, rhs: Vec3) {
        self.min -= rhs;
        self.max -= rhs;
    }
}

pub trait ComputeAabb3 {
    /// Compute the AABB in local space.
    fn compute_aabb(&self) -> Aabb3;
}

impl ComputeAabb3 for Sphere {
    #[inline]
    fn compute_aabb(&self) -> Aabb3 {
        let r = self.radius();
        Aabb3::new_unchecked(Point3::new(-r, -r, -r), Point3::new(r, r, r))
    }
}

impl ComputeAabb3 for Cuboid {
    #[inline]
    fn compute_aabb(&self) -> Aabb3 {
        let [hx, hy, hz] = self.half_length();
        Aabb3 {
            min: Point3::new(-hx, -hy, -hz),
            max: Point3::new(hx, hy, hz),
        }
    }
}

impl ComputeAabb3 for Capsule {
    #[inline]
    fn compute_aabb(&self) -> Aabb3 {
        let r = self.radius();
        let hh = self.half_height();
        Aabb3::new_unchecked(Point3::new(-r, -hh - r, -r), Point3::new(r, hh + r, r))
    }
}

impl ComputeAabb3 for Cylinder {
    #[inline]
    fn compute_aabb(&self) -> Aabb3 {
        let radius = self.radius();
        let half_height = self.half_height();
        Aabb3::new_unchecked(
            Point3::new(-radius, -half_height, -radius),
            Point3::new(radius, half_height, radius),
        )
    }
}

// infinite plane's aabb usually covers the entire world,
// since the plane is always axis-aligned in its space, we can compute a smaller aabb
impl ComputeAabb3 for InfinitePlane {
    fn compute_aabb(&self) -> Aabb3 {
        // limit the aabb to a reasonable large enough size
        let max_aabb = Real::MAX * 0.25;
        let min_aabb = Real::MIN * 0.25;
        Aabb3::new_unchecked(
            Point3::new(min_aabb, min_aabb, min_aabb),
            Point3::new(max_aabb, 0.0, max_aabb),
        )
    }
}

#[cfg(test)]
mod tests {
    use approx::assert_relative_eq;

    use super::*;
    use crate::math::UnitVec3;
    use crate::Ray;

    #[test]
    fn test_aabb_grow() {
        let mut aabb = Aabb3::new(Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0));
        aabb.grow(Point3::new(-1.0, 2.0, 3.0));
        assert_relative_eq!(aabb.min(), Point3::new(-1.0, 0.0, 0.0));
        assert_relative_eq!(aabb.max(), Point3::new(1.0, 2.0, 3.0));
    }

    #[test]
    fn test_aabb_corners() {
        let aabb = Aabb3::new(Point3::new(-1.0, -2.0, -3.0), Point3::new(1.0, 2.0, 3.0));
        let corners = aabb.corners();
        assert_relative_eq!(corners[0], Point3::new(-1.0, -2.0, -3.0));
        assert_relative_eq!(corners[1], Point3::new(-1.0, -2.0, 3.0));
        assert_relative_eq!(corners[2], Point3::new(-1.0, 2.0, -3.0));
        assert_relative_eq!(corners[3], Point3::new(-1.0, 2.0, 3.0));

        assert_relative_eq!(corners[4], Point3::new(1.0, -2.0, -3.0));
        assert_relative_eq!(corners[5], Point3::new(1.0, -2.0, 3.0));
        assert_relative_eq!(corners[6], Point3::new(1.0, 2.0, -3.0));
        assert_relative_eq!(corners[7], Point3::new(1.0, 2.0, 3.0));
    }

    #[test]
    fn test_raycast() {
        let aabb = Aabb3::new(Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0));

        let ray_origin_0 = Point3::new(0.5, 0.5, -0.5);
        let ray_direction_0 = UnitVec3::new_normalize(Vec3::new(0.0, 0.0, 1.0));
        let max_distance_0 = 1.0;
        assert!(aabb.raycast_by_one_over_direction(
            ray_origin_0,
            Ray::compute_one_over_direction(ray_direction_0),
            max_distance_0
        ));

        {
            let ray_origin_1 = Point3::new(0.5, 1.1, -0.5);
            assert!(!aabb.raycast_by_one_over_direction(
                ray_origin_1,
                Ray::compute_one_over_direction(ray_direction_0),
                max_distance_0
            ));
        }

        {
            let ray_direction_2 = UnitVec3::new_normalize(Vec3::new(0.0, 0.0, -1.0));
            assert!(!aabb.raycast_by_one_over_direction(
                ray_origin_0,
                Ray::compute_one_over_direction(ray_direction_2),
                max_distance_0
            ));
        }

        {
            let max_distance_3 = 0.3;
            assert!(!aabb.raycast_by_one_over_direction(
                ray_origin_0,
                Ray::compute_one_over_direction(ray_direction_0),
                max_distance_3
            ));
        }

        {
            let ray_direction_4 = UnitVec3::new_normalize(Vec3::new(0.0, 0.4, 0.5));
            assert!(aabb.raycast_by_one_over_direction(
                ray_origin_0,
                Ray::compute_one_over_direction(ray_direction_4),
                max_distance_0
            ));
        }

        // The origin is inside the AABB.
        {
            let ray_origin_5 = Point3::new(0.5, 0.5, 0.5);
            assert!(aabb.raycast_by_one_over_direction(
                ray_origin_5,
                Ray::compute_one_over_direction(ray_direction_0),
                max_distance_0
            ));
        }
    }
}