collide-mesh 0.1.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 along Y) are inherently
//! three-dimensional gameplay concepts.

mod bvh;
mod mesh;
mod triangle;

pub use mesh::{TriangleHit, TriangleMesh};

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

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.
    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.
    pub fn merged(&self, other: &Self) -> Self {
        let mut result = *self;
        result.include(other.min);
        result.include(other.max);
        result
    }
}

/// The combined result of resolving a capsule against a [`CollisionWorld`].
pub struct CollisionResult {
    /// Whether the capsule is supported by walkable ground.
    pub grounded: bool,
    /// The height of the supporting ground, or negative infinity when not grounded.
    pub ground_y: f32,
    /// The face normal of the supporting ground, or straight up when not grounded.
    pub ground_normal: Vector<f32>,
    /// 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.
    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 vertical capsule against all meshes.
    ///
    /// `velocity_y` distinguishes landing on ground (falling or resting)
    /// from passing it while moving upward.
    pub fn collide_capsule(
        &self,
        capsule: &Capsule<Vector<f32>>,
        velocity_y: f32,
    ) -> CollisionResult {
        let radius = capsule.rad;
        let position = capsule.start - Vector::y(radius);
        let height = capsule.end.y - capsule.start.y + 2.0 * radius;

        let mut result = CollisionResult {
            grounded: false,
            ground_y: f32::NEG_INFINITY,
            ground_normal: Vector::y(1.0),
            push: Vector::new(0.0, 0.0, 0.0),
        };

        let capsule_bounds = Aabb {
            min: [position.x - radius, position.y, position.z - radius],
            max: [
                position.x + radius,
                position.y + height,
                position.z + radius,
            ],
        };

        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(position, velocity_y, radius, height) else {
                continue;
            };

            if hit.grounded && hit.ground_y > result.ground_y {
                result.grounded = true;
                result.ground_y = hit.ground_y;
                result.ground_normal = hit.ground_normal;
            }
            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
    }
}