collide_mesh/
lib.rs

1#![deny(missing_docs)]
2
3//! Triangle mesh collision for character controllers.
4//!
5//! This crate is deliberately 3D-only and uses [`ga3::Vector<f32>`] directly:
6//! triangle meshes have no meaningful N-dimensional generalization, and the
7//! ground semantics (walkable slopes, ground height along Y) are inherently
8//! three-dimensional gameplay concepts.
9
10mod bvh;
11mod mesh;
12mod triangle;
13
14pub use mesh::{TriangleHit, TriangleMesh};
15
16use collide_capsule::Capsule;
17use collide_ray::Ray;
18use ga3::Vector;
19
20use bvh::Bvh;
21
22/// An axis-aligned bounding box in 3D space.
23#[derive(Clone, Copy)]
24pub struct Aabb {
25    /// The corner with the smallest coordinates on all axes.
26    pub min: [f32; 3],
27    /// The corner with the largest coordinates on all axes.
28    pub max: [f32; 3],
29}
30
31impl Aabb {
32    /// The empty box: including the first point turns it into that point.
33    pub const EMPTY: Self = Self {
34        min: [f32::INFINITY; 3],
35        max: [f32::NEG_INFINITY; 3],
36    };
37
38    /// Checks if two boxes overlap, boundaries included.
39    pub fn overlaps(&self, other: &Self) -> bool {
40        (0..3).all(|axis| self.max[axis] >= other.min[axis] && self.min[axis] <= other.max[axis])
41    }
42
43    /// Grows the box to contain the given point.
44    pub fn include(&mut self, point: [f32; 3]) {
45        for ((minimum, maximum), value) in self.min.iter_mut().zip(&mut self.max).zip(point) {
46            *minimum = minimum.min(value);
47            *maximum = maximum.max(value);
48        }
49    }
50
51    /// Returns the smallest box containing both boxes.
52    pub fn merged(&self, other: &Self) -> Self {
53        let mut result = *self;
54        result.include(other.min);
55        result.include(other.max);
56        result
57    }
58}
59
60/// The combined result of resolving a capsule against a [`CollisionWorld`].
61pub struct CollisionResult {
62    /// Whether the capsule is supported by walkable ground.
63    pub grounded: bool,
64    /// The height of the supporting ground, or negative infinity when not grounded.
65    pub ground_y: f32,
66    /// The face normal of the supporting ground, or straight up when not grounded.
67    pub ground_normal: Vector<f32>,
68    /// The accumulated displacement pushing the capsule out of steep geometry.
69    pub push: Vector<f32>,
70}
71
72/// A set of triangle meshes behind a bounding volume hierarchy.
73pub struct CollisionWorld {
74    meshes: Vec<TriangleMesh>,
75    bvh: Bvh,
76}
77
78impl CollisionWorld {
79    /// Creates a world from a set of meshes.
80    pub fn new(meshes: Vec<TriangleMesh>) -> Self {
81        let bounds: Vec<Aabb> = meshes.iter().map(|mesh| *mesh.bounds()).collect();
82        Self {
83            bvh: Bvh::build(&bounds),
84            meshes,
85        }
86    }
87
88    /// Resolves a vertical capsule against all meshes.
89    ///
90    /// `velocity_y` distinguishes landing on ground (falling or resting)
91    /// from passing it while moving upward.
92    pub fn collide_capsule(
93        &self,
94        capsule: &Capsule<Vector<f32>>,
95        velocity_y: f32,
96    ) -> CollisionResult {
97        let radius = capsule.rad;
98        let position = capsule.start - Vector::y(radius);
99        let height = capsule.end.y - capsule.start.y + 2.0 * radius;
100
101        let mut result = CollisionResult {
102            grounded: false,
103            ground_y: f32::NEG_INFINITY,
104            ground_normal: Vector::y(1.0),
105            push: Vector::new(0.0, 0.0, 0.0),
106        };
107
108        let capsule_bounds = Aabb {
109            min: [position.x - radius, position.y, position.z - radius],
110            max: [
111                position.x + radius,
112                position.y + height,
113                position.z + radius,
114            ],
115        };
116
117        for mesh_index in self.bvh.overlapping(&capsule_bounds) {
118            let Some(mesh) = self.meshes.get(mesh_index) else {
119                continue;
120            };
121            let Some(hit) = mesh.collide_capsule(position, velocity_y, radius, height) else {
122                continue;
123            };
124
125            if hit.grounded && hit.ground_y > result.ground_y {
126                result.grounded = true;
127                result.ground_y = hit.ground_y;
128                result.ground_normal = hit.ground_normal;
129            }
130            result.push += hit.push;
131        }
132
133        result
134    }
135
136    /// Returns the distance to the closest mesh hit by the ray, if any.
137    ///
138    /// The ray direction is expected to be normalized; the result is limited
139    /// to `max_distance`.
140    pub fn raycast(&self, ray: &Ray<Vector<f32>>, max_distance: f32) -> Option<f32> {
141        let origin: [f32; 3] = ray.origin.into();
142        let inverse_direction = <[f32; 3]>::from(ray.direction).map(f32::recip);
143
144        let mut closest: Option<f32> = None;
145        for mesh_index in self
146            .bvh
147            .ray_overlapping(origin, inverse_direction, max_distance)
148        {
149            let Some(mesh) = self.meshes.get(mesh_index) else {
150                continue;
151            };
152            if let Some(distance) = mesh.raycast(ray.origin, ray.direction, max_distance)
153                && closest.is_none_or(|best| distance < best)
154            {
155                closest = Some(distance);
156            }
157        }
158        closest
159    }
160}
collide_mesh/lib.rs

collide_mesh/
lib.rs
