kvas_engine/
spatial.rs

1//! GPU-independent rays, axis-aligned bounds and conservative frustum queries.
2//!
3//! Constructors validate finite data. Queries use metres with a right-handed
4//! +Y-up world; frusta use the renderer's DirectX/wgpu depth range of 0..1.
5//!
6//! ```
7//! use kvas_engine::spatial::{Aabb, Ray};
8//! use glam::Vec3;
9//! let bounds = Aabb::new(-Vec3::ONE, Vec3::ONE).unwrap();
10//! let ray = Ray::new(Vec3::new(0.0, 0.0, 5.0), Vec3::NEG_Z).unwrap();
11//! assert_eq!(bounds.ray_distance(ray, 10.0), Some(4.0));
12//! assert!(bounds.contains(Vec3::ZERO));
13//! ```
14
15use glam::{Mat4, Vec3, Vec4};
16
17/// Finite world/local ray with a unit direction.
18#[derive(Clone, Copy, Debug, PartialEq)]
19pub struct Ray {
20    origin: Vec3,
21    direction: Vec3,
22}
23
24impl Ray {
25    /// Normalizes a nonzero direction; invalid data returns `None`.
26    pub fn new(origin: Vec3, direction: Vec3) -> Option<Self> {
27        if !origin.is_finite() || !direction.is_finite() {
28            return None;
29        }
30        // Rescale before length calculation to avoid overflow/underflow for
31        // finite directions far outside ordinary world-coordinate magnitudes.
32        let largest = direction.abs().max_element();
33        if largest == 0.0 { return None; }
34        Some(Self { origin, direction: (direction / largest).normalize() })
35    }
36    /// Ray start point.
37    pub fn origin(self) -> Vec3 {
38        self.origin
39    }
40    /// Unit direction along increasing distance.
41    pub fn direction(self) -> Vec3 {
42        self.direction
43    }
44    /// Point at a signed distance from the origin; negative distances go backward.
45    pub fn point_at(self, distance: f32) -> Vec3 {
46        self.origin + self.direction * distance
47    }
48    /// Transforms the origin and direction, then renormalizes the direction.
49    /// Only affine matrices are accepted; singular transforms may collapse the ray.
50    pub fn transformed(self, matrix: Mat4) -> Option<Self> {
51        if !is_affine(matrix) {
52            return None;
53        }
54        Self::new(matrix.transform_point3(self.origin), matrix.transform_vector3(self.direction))
55    }
56    /// Forward distance to a plane represented by a point and any nonzero normal.
57    /// Parallel, backward, non-finite or degenerate intersections return `None`.
58    pub fn plane_distance(self, point: Vec3, normal: Vec3) -> Option<f32> {
59        if !point.is_finite() || !normal.is_finite() {
60            return None;
61        }
62        let normal = normal.try_normalize()?;
63        let denominator = self.direction.dot(normal);
64        if denominator.abs() <= f32::EPSILON {
65            return None;
66        }
67        let distance = (point - self.origin).dot(normal) / denominator;
68        (distance.is_finite() && distance >= 0.0).then_some(distance)
69    }
70
71    /// First forward intersection with a finite positive-radius sphere.
72    /// Origins inside/on the sphere return zero, matching AABB query semantics.
73    /// Entirely backward intersections return `None` instead of a false zero hit.
74    pub fn sphere_distance(self, center: Vec3, radius: f32) -> Option<f32> {
75        if !center.is_finite() || !radius.is_finite() || radius <= 0.0 { return None; }
76        let offset = self.origin.as_dvec3() - center.as_dvec3();
77        let direction = self.direction.as_dvec3();
78        let a = direction.length_squared();
79        let b = offset.dot(direction);
80        let c = offset.length_squared() - (radius as f64).powi(2);
81        if c <= 0.0 { return Some(0.0); }
82        let discriminant = b * b - a * c;
83        if discriminant < 0.0 { return None; }
84        let distance = (-b - discriminant.sqrt()) / a;
85        (distance >= 0.0 && distance <= f32::MAX as f64).then_some(distance as f32)
86    }
87}
88
89/// Finite axis-aligned closed box. Degenerate extents (planes/points) are allowed.
90#[derive(Clone, Copy, Debug, PartialEq)]
91pub struct Aabb {
92    min: Vec3,
93    max: Vec3,
94}
95
96impl Aabb {
97    /// Creates ordered bounds; inverted or non-finite extents return `None`.
98    pub fn new(min: Vec3, max: Vec3) -> Option<Self> {
99        (min.is_finite() && max.is_finite() && min.cmple(max).all()).then_some(Self { min, max })
100    }
101    /// Builds bounds around at least one finite point; any invalid point rejects the set.
102    pub fn from_points(points: impl IntoIterator<Item = Vec3>) -> Option<Self> {
103        let mut points = points.into_iter();
104        let first = points.next()?;
105        let mut bounds = Self::new(first, first)?;
106        for point in points {
107            if !point.is_finite() {
108                return None;
109            }
110            bounds.min = bounds.min.min(point);
111            bounds.max = bounds.max.max(point);
112        }
113        Some(bounds)
114    }
115    /// Minimum corner.
116    pub fn min(self) -> Vec3 {
117        self.min
118    }
119    /// Maximum corner.
120    pub fn max(self) -> Vec3 {
121        self.max
122    }
123    /// Midpoint, computed without summing potentially large same-sign endpoints.
124    pub fn center(self) -> Vec3 {
125        self.min * 0.5 + self.max * 0.5
126    }
127    /// Full per-axis extents.
128    pub fn size(self) -> Vec3 {
129        self.max - self.min
130    }
131    /// Half of the per-axis extents.
132    pub fn half_extents(self) -> Vec3 {
133        self.max * 0.5 - self.min * 0.5
134    }
135    /// Whether a finite point lies inside or on the boundary.
136    pub fn contains(self, point: Vec3) -> bool {
137        point.is_finite() && point.cmpge(self.min).all() && point.cmple(self.max).all()
138    }
139    /// Whether two closed boxes overlap or touch.
140    pub fn intersects(self, other: Self) -> bool {
141        self.min.cmple(other.max).all() && self.max.cmpge(other.min).all()
142    }
143    /// Smallest axis-aligned box containing both inputs.
144    pub fn union(self, other: Self) -> Self {
145        Self { min: self.min.min(other.min), max: self.max.max(other.max) }
146    }
147    /// Closest point in/on the box; the caller must supply a finite point.
148    pub fn closest_point(self, point: Vec3) -> Vec3 {
149        point.clamp(self.min, self.max)
150    }
151    /// Expands every face by a non-negative finite margin; overflow returns `None`.
152    pub fn expanded(self, margin: f32) -> Option<Self> {
153        if !margin.is_finite() || margin < 0.0 {
154            return None;
155        }
156        Self::new(self.min - Vec3::splat(margin), self.max + Vec3::splat(margin))
157    }
158    /// Eight corners in bit order: bit 0 selects max X, bit 1 max Y, bit 2 max Z.
159    pub fn corners(self) -> [Vec3; 8] {
160        std::array::from_fn(|i| {
161            Vec3::new(
162                if i & 1 == 0 { self.min.x } else { self.max.x },
163                if i & 2 == 0 { self.min.y } else { self.max.y },
164                if i & 4 == 0 { self.min.z } else { self.max.z },
165            )
166        })
167    }
168    /// Axis-aligned envelope after a finite affine transformation, including mirrors/shear.
169    pub fn transformed(self, matrix: Mat4) -> Option<Self> {
170        if !is_affine(matrix) {
171            return None;
172        }
173        Self::from_points(self.corners().map(|point| matrix.transform_point3(point)))
174    }
175    /// First intersection distance within a finite non-negative range.
176    /// A ray beginning inside/on the box returns zero. Parallel axes are handled
177    /// without reciprocal infinities, including origins exactly on a slab face.
178    pub fn ray_distance(self, ray: Ray, max_distance: f32) -> Option<f32> {
179        if !max_distance.is_finite() || max_distance < 0.0 {
180            return None;
181        }
182        let (mut enter, mut exit) = (0.0f32, max_distance);
183        for axis in 0..3 {
184            let direction = ray.direction[axis];
185            let origin = ray.origin[axis];
186            if direction == 0.0 {
187                if origin < self.min[axis] || origin > self.max[axis] {
188                    return None;
189                }
190            } else {
191                let a = (self.min[axis] - origin) / direction;
192                let b = (self.max[axis] - origin) / direction;
193                enter = enter.max(a.min(b));
194                exit = exit.min(a.max(b));
195                if enter > exit {
196                    return None;
197                }
198            }
199        }
200        Some(enter)
201    }
202}
203
204/// Six inward-facing clip planes for a finite 0..1-depth view/projection matrix.
205#[derive(Clone, Copy, Debug)]
206pub struct Frustum {
207    planes: [Vec4; 6],
208}
209
210impl Frustum {
211    /// Extracts left/right/bottom/top/near/far planes from a wgpu view-projection matrix.
212    /// Invalid or degenerate planes return `None`; infinite-far projections are unsupported.
213    pub fn from_view_projection(matrix: Mat4) -> Option<Self> {
214        if !matrix.is_finite() {
215            return None;
216        }
217        let (x, y, z, w) = (matrix.row(0), matrix.row(1), matrix.row(2), matrix.row(3));
218        let mut planes = [w + x, w - x, w + y, w - y, z, w - z];
219        for plane in &mut planes {
220            let length = plane.truncate().length();
221            if !length.is_finite() || length <= f32::EPSILON {
222                return None;
223            }
224            *plane /= length;
225            if !plane.is_finite() {
226                return None;
227            }
228        }
229        Some(Self { planes })
230    }
231    /// Unit-normal planes in left/right/bottom/top/near/far order.
232    pub fn planes(&self) -> &[Vec4; 6] {
233        &self.planes
234    }
235    /// Whether a point lies on or inside every clip plane.
236    pub fn contains_point(&self, point: Vec3) -> bool {
237        point.is_finite() && self.planes.iter().all(|p| p.truncate().dot(point) + p.w >= 0.0)
238    }
239    /// Conservative world-box visibility test. May retain boxes outside a frustum corner.
240    pub fn intersects_aabb(&self, bounds: Aabb) -> bool {
241        self.planes.iter().all(|plane| {
242            let normal = plane.truncate();
243            let positive = Vec3::select(normal.cmpge(Vec3::ZERO), bounds.max, bounds.min);
244            normal.dot(positive) + plane.w >= 0.0
245        })
246    }
247    /// Conservative test of a transformed local box without heap allocation.
248    /// Non-finite corner positions conservatively return true to avoid hiding geometry.
249    pub fn intersects_transformed_aabb(&self, bounds: Aabb, model: Mat4) -> bool {
250        let corners = bounds.corners().map(|point| model.transform_point3(point));
251        if corners.iter().any(|p| !p.is_finite()) {
252            return true;
253        }
254        self.planes.iter().all(|plane| corners.iter().any(|point| plane.truncate().dot(*point) + plane.w >= 0.0))
255    }
256}
257
258fn is_affine(matrix: Mat4) -> bool {
259    matrix.is_finite() && matrix.row(3).abs_diff_eq(Vec4::W, 1e-6)
260}
261
262#[cfg(test)]
263mod tests {
264    use super::*;
265    #[test]
266    fn slab_queries_handle_parallel_inside_and_boundary_rays() {
267        let bounds = Aabb::new(-Vec3::ONE, Vec3::ONE).unwrap();
268        assert_eq!(bounds.ray_distance(Ray::new(Vec3::new(1.0, 0.0, 5.0), Vec3::NEG_Z).unwrap(), 10.0), Some(4.0));
269        assert_eq!(bounds.ray_distance(Ray::new(Vec3::new(2.0, 0.0, 5.0), Vec3::NEG_Z).unwrap(), 10.0), None);
270        assert_eq!(bounds.ray_distance(Ray::new(Vec3::ZERO, Vec3::X).unwrap(), 0.0), Some(0.0));
271        assert_eq!(bounds.ray_distance(Ray::new(Vec3::new(0.0, 0.0, 5.0), Vec3::NEG_Z).unwrap(), 3.0), None);
272        assert!(Ray::new(Vec3::ZERO, Vec3::ZERO).is_none());
273    }
274
275    #[test]
276    fn sphere_queries_reject_backward_hits_and_direction_normalization_is_stable() {
277        let ray = Ray::new(Vec3::ZERO, Vec3::new(0.0, 0.0, f32::MAX)).unwrap();
278        assert_eq!(ray.direction(), Vec3::Z);
279        assert_eq!(ray.sphere_distance(Vec3::Z * -5.0, 1.0), None);
280        assert_eq!(ray.sphere_distance(Vec3::Z * 5.0, 1.0), Some(4.0));
281        assert_eq!(ray.sphere_distance(Vec3::ZERO, 1.0), Some(0.0));
282        assert_eq!(Ray::new(Vec3::ZERO, Vec3::X * f32::MIN_POSITIVE).unwrap().direction(), Vec3::X);
283    }
284    #[test]
285    fn bounds_transform_and_frustum_use_wgpu_depth() {
286        let bounds = Aabb::new(Vec3::ZERO, Vec3::ONE).unwrap();
287        let moved =
288            bounds.transformed(Mat4::from_scale_rotation_translation(Vec3::new(-2.0, 3.0, 1.0), glam::Quat::IDENTITY, Vec3::X)).unwrap();
289        assert_eq!(moved.min(), Vec3::new(-1.0, 0.0, 0.0));
290        assert_eq!(moved.max(), Vec3::new(1.0, 3.0, 1.0));
291        let frustum = Frustum::from_view_projection(Mat4::IDENTITY).unwrap();
292        assert!(frustum.contains_point(Vec3::new(0.0, 0.0, 0.5)));
293        assert!(!frustum.contains_point(Vec3::new(0.0, 0.0, -0.1)));
294        assert!(frustum.intersects_aabb(bounds));
295        assert!(!frustum.intersects_transformed_aabb(bounds, Mat4::from_translation(Vec3::X * 10.0)));
296        assert!(Frustum::from_view_projection(Mat4::ZERO).is_none());
297        assert!(Aabb::new(Vec3::ONE, Vec3::ZERO).is_none());
298        assert!(bounds.expanded(-1.0).is_none());
299    }
300}
kvas_engine/spatial.rs

kvas_engine/
spatial.rs
