collide-mesh 0.2.0

#![deny(missing_docs)]

//! Triangle mesh collision for character controllers.
//!
//! This crate is deliberately 3D-only and uses [`ga3::Vector<f32>`] directly:
//! triangle meshes have no meaningful N-dimensional generalization, and the
//! ground semantics (walkable slopes, ground height) are inherently
//! three-dimensional gameplay concepts. The up direction is a caller-supplied
//! unit vector, not fixed to an axis: [`CollisionWorld::collide_capsule`]'s
//! ground classification, height bookkeeping and capsule alignment all follow
//! it, so a world that isn't Y-up needs no conversion at this boundary.

mod bvh;
mod mesh;
mod triangle;

pub use mesh::{TriangleHit, TriangleMesh};

use collide_capsule::Capsule;
use collide_ray::Ray;
use ga3::Vector;
use inner_space::DotProduct;

use bvh::Bvh;

/// An axis-aligned bounding box in 3D space.
#[derive(Clone, Copy)]
pub struct Aabb {
    /// The corner with the smallest coordinates on all axes.
    pub min: [f32; 3],
    /// The corner with the largest coordinates on all axes.
    pub max: [f32; 3],
}

impl Aabb {
    /// The empty box: including the first point turns it into that point.
    pub const EMPTY: Self = Self {
        min: [f32::INFINITY; 3],
        max: [f32::NEG_INFINITY; 3],
    };

    /// Checks if two boxes overlap, boundaries included.
    #[must_use]
    pub fn overlaps(&self, other: &Self) -> bool {
        (0..3).all(|axis| self.max[axis] >= other.min[axis] && self.min[axis] <= other.max[axis])
    }

    /// Grows the box to contain the given point.
    pub fn include(&mut self, point: [f32; 3]) {
        for ((minimum, maximum), value) in self.min.iter_mut().zip(&mut self.max).zip(point) {
            *minimum = minimum.min(value);
            *maximum = maximum.max(value);
        }
    }

    /// Returns the smallest box containing both boxes.
    #[must_use]
    pub fn merged(&self, other: &Self) -> Self {
        let mut result = *self;
        result.include(other.min);
        result.include(other.max);
        result
    }
}

/// Walkable ground supporting a capsule.
#[derive(Clone, Copy)]
pub struct Ground {
    /// Signed distance along `up` from the capsule's feet to the ground:
    /// positive means the feet are below it (move the capsule along `up` by
    /// this much to rest on it), negative means they hover above it.
    pub distance: f32,
    /// The face normal of the ground.
    pub normal: Vector<f32>,
}

/// Whether a capsule is moving along `up` or against it.
#[derive(Clone, Copy, PartialEq, Eq)]
pub enum Motion {
    /// Moving against `up` or resting: ground below can support the capsule.
    Falling,
    /// Moving along `up`: ground is passed rather than landed on.
    Rising,
}

impl Motion {
    /// Classifies a velocity against the up direction.
    #[must_use]
    pub fn from_velocity(velocity: Vector<f32>, up: Vector<f32>) -> Self {
        if velocity.dot(&up) <= 0.0 {
            Self::Falling
        } else {
            Self::Rising
        }
    }
}

/// The combined result of resolving a capsule against a [`CollisionWorld`].
pub struct CollisionResult {
    /// The walkable ground supporting the capsule, if any.
    pub ground: Option<Ground>,
    /// The accumulated displacement pushing the capsule out of steep geometry.
    pub push: Vector<f32>,
}

/// A set of triangle meshes behind a bounding volume hierarchy.
pub struct CollisionWorld {
    meshes: Vec<TriangleMesh>,
    bvh: Bvh,
}

impl CollisionWorld {
    /// Creates a world from a set of meshes.
    #[must_use]
    pub fn new(meshes: Vec<TriangleMesh>) -> Self {
        let bounds: Vec<Aabb> = meshes.iter().map(|mesh| *mesh.bounds()).collect();
        Self {
            bvh: Bvh::build(&bounds),
            meshes,
        }
    }

    /// Resolves a capsule aligned with `up` against all meshes.
    ///
    /// `up` is the unit vector walkable ground is measured against; `velocity`
    /// distinguishes landing on ground (falling or resting) from passing it
    /// while moving up.
    #[must_use]
    pub fn collide_capsule(
        &self,
        capsule: &Capsule<Vector<f32>>,
        up: Vector<f32>,
        velocity: Vector<f32>,
    ) -> CollisionResult {
        let radius = capsule.rad;
        let motion = Motion::from_velocity(velocity, up);

        let mut result = CollisionResult {
            ground: None,
            push: Vector::new(0.0, 0.0, 0.0),
        };

        let pad = Vector::new(radius, radius, radius);
        let mut capsule_bounds = Aabb::EMPTY;
        capsule_bounds.include((capsule.start - pad).into());
        capsule_bounds.include((capsule.start + pad).into());
        capsule_bounds.include((capsule.end - pad).into());
        capsule_bounds.include((capsule.end + pad).into());

        for mesh_index in self.bvh.overlapping(&capsule_bounds) {
            let Some(mesh) = self.meshes.get(mesh_index) else {
                continue;
            };
            let Some(hit) = mesh.collide_capsule(capsule.start, capsule.end, radius, up, motion)
            else {
                continue;
            };

            if let Some(ground) = hit.ground
                && result
                    .ground
                    .is_none_or(|best| ground.distance > best.distance)
            {
                result.ground = Some(ground);
            }
            result.push += hit.push;
        }

        result
    }

    /// Returns the distance to the closest mesh hit by the ray, if any.
    ///
    /// The ray direction is expected to be normalized; the result is limited
    /// to `max_distance`.
    pub fn raycast(&self, ray: &Ray<Vector<f32>>, max_distance: f32) -> Option<f32> {
        let origin: [f32; 3] = ray.origin.into();
        let inverse_direction = <[f32; 3]>::from(ray.direction).map(f32::recip);

        let mut closest: Option<f32> = None;
        for mesh_index in self
            .bvh
            .ray_overlapping(origin, inverse_direction, max_distance)
        {
            let Some(mesh) = self.meshes.get(mesh_index) else {
                continue;
            };
            if let Some(distance) = mesh.raycast(ray.origin, ray.direction, max_distance)
                && closest.is_none_or(|best| distance < best)
            {
                closest = Some(distance);
            }
        }
        closest
    }
}