khora_core/math/
geometry.rs

1// Copyright 2025 eraflo
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Provides geometric primitive shapes for spatial calculations.
16//!
17//! This module contains common geometric structures used in collision detection,
18//! culling, and other spatial reasoning tasks within the engine.
19
20use super::{Mat4, Vec3, Vec4, EPSILON};
21
22/// Represents an Axis-Aligned Bounding Box (AABB).
23///
24/// An AABB is a rectangular prism aligned with the coordinate axes, defined by its
25/// minimum and maximum corner points. It is a simple but highly efficient volume
26/// for broad-phase collision detection and visibility culling.
27#[derive(Debug, Clone, Copy, PartialEq)]
28#[repr(C)]
29pub struct Aabb {
30    /// The corner of the box with the smallest coordinates on all axes.
31    pub min: Vec3,
32    /// The corner of the box with the largest coordinates on all axes.
33    pub max: Vec3,
34}
35
36impl Aabb {
37    /// An invalid `Aabb` where `min` components are positive infinity and `max` are negative infinity.
38    ///
39    /// This is useful as a neutral starting point for merging operations. Merging any
40    /// valid `Aabb` with `INVALID` will result in that valid `Aabb`.
41    pub const INVALID: Self = Self {
42        min: Vec3::new(f32::INFINITY, f32::INFINITY, f32::INFINITY),
43        max: Vec3::new(f32::NEG_INFINITY, f32::NEG_INFINITY, f32::NEG_INFINITY),
44    };
45
46    /// Creates a new `Aabb` from two corner points.
47    ///
48    /// This constructor automatically ensures that the `min` field holds the
49    /// component-wise minimum and `max` holds the component-wise maximum,
50    /// regardless of the order the points are passed in.
51    #[inline]
52    pub fn from_min_max(min_pt: Vec3, max_pt: Vec3) -> Self {
53        Self {
54            min: Vec3::new(
55                min_pt.x.min(max_pt.x),
56                min_pt.y.min(max_pt.y),
57                min_pt.z.min(max_pt.z),
58            ),
59            max: Vec3::new(
60                min_pt.x.max(max_pt.x),
61                min_pt.y.max(max_pt.y),
62                min_pt.z.max(max_pt.z),
63            ),
64        }
65    }
66
67    /// Creates a new `Aabb` from a center point and its half-extents.
68    ///
69    /// The half-extents represent the distance from the center to the faces of the box.
70    /// The provided `half_extents` will be made non-negative.
71    #[inline]
72    pub fn from_center_half_extents(center: Vec3, half_extents: Vec3) -> Self {
73        let safe_half_extents = half_extents.abs();
74        Self {
75            min: center - safe_half_extents,
76            max: center + safe_half_extents,
77        }
78    }
79
80    /// Creates a new `Aabb` centered at the origin with the given half-extents.
81    #[inline]
82    pub fn from_half_extents(half_extents: Vec3) -> Self {
83        let safe_half_extents = half_extents.abs();
84        Self {
85            min: -safe_half_extents,
86            max: safe_half_extents,
87        }
88    }
89
90    /// Creates a degenerate `Aabb` containing a single point (min and max are the same).
91    #[inline]
92    pub fn from_point(point: Vec3) -> Self {
93        Self {
94            min: point,
95            max: point,
96        }
97    }
98
99    /// Creates an `Aabb` that tightly encloses a given set of points.
100    ///
101    /// # Returns
102    ///
103    /// Returns `Some(Aabb)` if the input slice is not empty, otherwise `None`.
104    pub fn from_points(points: &[Vec3]) -> Option<Self> {
105        if points.is_empty() {
106            return None;
107        }
108
109        let mut min_pt = points[0];
110        let mut max_pt = points[0];
111
112        for point in points.iter().skip(1) {
113            min_pt.x = min_pt.x.min(point.x);
114            min_pt.y = min_pt.y.min(point.y);
115            min_pt.z = min_pt.z.min(point.z);
116
117            max_pt.x = max_pt.x.max(point.x);
118            max_pt.y = max_pt.y.max(point.y);
119            max_pt.z = max_pt.z.max(point.z);
120        }
121
122        Some(Self {
123            min: min_pt,
124            max: max_pt,
125        })
126    }
127
128    /// Calculates the center point of the `Aabb`.
129    #[inline]
130    pub fn center(&self) -> Vec3 {
131        (self.min + self.max) * 0.5
132    }
133
134    /// Calculates the half-extents (half the size on each axis) of the `Aabb`.
135    #[inline]
136    pub fn half_extents(&self) -> Vec3 {
137        (self.max - self.min) * 0.5
138    }
139
140    /// Calculates the full size (width, height, depth) of the `Aabb`.
141    #[inline]
142    pub fn size(&self) -> Vec3 {
143        self.max - self.min
144    }
145
146    /// Checks if the `Aabb` is valid (i.e., `min` <= `max` on all axes).
147    /// Degenerate boxes where `min == max` are considered valid.
148    #[inline]
149    pub fn is_valid(&self) -> bool {
150        self.min.x <= self.max.x && self.min.y <= self.max.y && self.min.z <= self.max.z
151    }
152
153    /// Checks if a point is contained within or on the boundary of the `Aabb`.
154    #[inline]
155    pub fn contains_point(&self, point: Vec3) -> bool {
156        point.x >= self.min.x
157            && point.x <= self.max.x
158            && point.y >= self.min.y
159            && point.y <= self.max.y
160            && point.z >= self.min.z
161            && point.z <= self.max.z
162    }
163
164    /// Checks if this `Aabb` intersects with another `Aabb`.
165    ///
166    /// Two `Aabb`s intersect if they overlap on all three axes. Boxes that only
167    /// touch at the boundary are considered to be intersecting.
168    #[inline]
169    pub fn intersects_aabb(&self, other: &Aabb) -> bool {
170        (self.min.x <= other.max.x && self.max.x >= other.min.x)
171            && (self.min.y <= other.max.y && self.max.y >= other.min.y)
172            && (self.min.z <= other.max.z && self.max.z >= other.min.z)
173    }
174
175    /// Creates a new `Aabb` that encompasses both this `Aabb` and another one.
176    #[inline]
177    pub fn merge(&self, other: &Aabb) -> Self {
178        Self {
179            min: Vec3::new(
180                self.min.x.min(other.min.x),
181                self.min.y.min(other.min.y),
182                self.min.z.min(other.min.z),
183            ),
184            max: Vec3::new(
185                self.max.x.max(other.max.x),
186                self.max.y.max(other.max.y),
187                self.max.z.max(other.max.z),
188            ),
189        }
190    }
191
192    /// Creates a new `Aabb` that encompasses both this `Aabb` and an additional point.
193    #[inline]
194    pub fn merged_with_point(&self, point: Vec3) -> Self {
195        Self {
196            min: Vec3::new(
197                self.min.x.min(point.x),
198                self.min.y.min(point.y),
199                self.min.z.min(point.z),
200            ),
201            max: Vec3::new(
202                self.max.x.max(point.x),
203                self.max.y.max(point.y),
204                self.max.z.max(point.z),
205            ),
206        }
207    }
208
209    /// Computes the bounding box that encloses this `Aabb` after a transformation.
210    ///
211    /// This method is more efficient than transforming all 8 corners of the box for
212    /// affine transformations. It works by transforming the center of the box and
213    /// then calculating the new extents by projecting the original extents onto
214    /// the axes of the transformed space.
215    ///
216    /// # Note
217    /// This method is designed for affine transformations (like rotation, translation, scale).
218    /// It may not produce the tightest-fitting box for transformations involving perspective.
219    pub fn transform(&self, matrix: &Mat4) -> Self {
220        let center = self.center();
221        let half_extents = self.half_extents();
222        let transformed_center_v4 = *matrix * Vec4::from_vec3(center, 1.0);
223
224        let transformed_center = if (transformed_center_v4.w - 1.0).abs() > EPSILON
225            && transformed_center_v4.w.abs() > EPSILON
226        {
227            transformed_center_v4.truncate() / transformed_center_v4.w
228        } else {
229            transformed_center_v4.truncate()
230        };
231
232        let x_abs_col = Vec3::new(
233            matrix.cols[0][0].abs(),
234            matrix.cols[0][1].abs(),
235            matrix.cols[0][2].abs(),
236        );
237        let y_abs_col = Vec3::new(
238            matrix.cols[1][0].abs(),
239            matrix.cols[1][1].abs(),
240            matrix.cols[1][2].abs(),
241        );
242        let z_abs_col = Vec3::new(
243            matrix.cols[2][0].abs(),
244            matrix.cols[2][1].abs(),
245            matrix.cols[2][2].abs(),
246        );
247
248        let new_half_extents =
249            x_abs_col * half_extents.x + y_abs_col * half_extents.y + z_abs_col * half_extents.z;
250
251        Aabb::from_center_half_extents(transformed_center, new_half_extents)
252    }
253
254    /// Calculates the surface area of the `Aabb`.
255    ///
256    /// Useful for SAH (Surface Area Heuristic) in BVH construction.
257    #[inline]
258    pub fn surface_area(&self) -> f32 {
259        let d = self.max - self.min;
260        2.0 * (d.x * d.y + d.y * d.z + d.z * d.x)
261    }
262
263    /// Checks if this `Aabb` fully contains another `Aabb`.
264    #[inline]
265    pub fn contains_aabb(&self, other: &Aabb) -> bool {
266        self.min.x <= other.min.x
267            && self.max.x >= other.max.x
268            && self.min.y <= other.min.y
269            && self.max.y >= other.max.y
270            && self.min.z <= other.min.z
271            && self.max.z >= other.max.z
272    }
273
274    /// Intersection test against a ray using the Slab Method.
275    ///
276    /// `inv_dir` should be `1.0 / ray.direction`. If a component of direction is zero, `inv_dir` should be infinity.
277    /// Returns the distance to the intersection point if it occurs.
278    pub fn intersect_ray(&self, origin: Vec3, inv_dir: Vec3) -> Option<f32> {
279        let t1 = (self.min.x - origin.x) * inv_dir.x;
280        let t2 = (self.max.x - origin.x) * inv_dir.x;
281        let t3 = (self.min.y - origin.y) * inv_dir.y;
282        let t4 = (self.max.y - origin.y) * inv_dir.y;
283        let t5 = (self.min.z - origin.z) * inv_dir.z;
284        let t6 = (self.max.z - origin.z) * inv_dir.z;
285
286        let tmin = t1.min(t2).max(t3.min(t4)).max(t5.min(t6));
287        let tmax = t1.max(t2).min(t3.max(t4)).min(t5.max(t6));
288
289        if tmax < 0.0 || tmin > tmax {
290            return None;
291        }
292
293        Some(tmin)
294    }
295}
296
297impl Default for Aabb {
298    /// Returns the default `Aabb`, which is `Aabb::INVALID`.
299    #[inline]
300    fn default() -> Self {
301        Self::INVALID
302    }
303}
304
305// --- Tests ---
306#[cfg(test)]
307mod tests {
308    use super::*;
309    use crate::math::{approx_eq, matrix::Mat4, vector::Vec3}; // Use helpers from parent
310    use std::f32::consts::PI;
311
312    fn vec3_approx_eq(a: Vec3, b: Vec3) -> bool {
313        approx_eq(a.x, b.x) && approx_eq(a.y, b.y) && approx_eq(a.z, b.z)
314    }
315
316    // Helper for AABB comparison
317    fn aabb_approx_eq(a: Aabb, b: Aabb) -> bool {
318        vec3_approx_eq(a.min, b.min) && vec3_approx_eq(a.max, b.max)
319    }
320
321    #[test]
322    fn test_aabb_from_min_max() {
323        let aabb = Aabb::from_min_max(Vec3::new(1.0, 2.0, 3.0), Vec3::new(4.0, 5.0, 6.0));
324        assert_eq!(aabb.min, Vec3::new(1.0, 2.0, 3.0));
325        assert_eq!(aabb.max, Vec3::new(4.0, 5.0, 6.0));
326
327        // Test swapped min/max
328        let aabb_swapped = Aabb::from_min_max(Vec3::new(4.0, 5.0, 6.0), Vec3::new(1.0, 2.0, 3.0));
329        assert_eq!(aabb_swapped.min, Vec3::new(1.0, 2.0, 3.0));
330        assert_eq!(aabb_swapped.max, Vec3::new(4.0, 5.0, 6.0));
331    }
332
333    #[test]
334    fn test_aabb_from_center_half_extents() {
335        let center = Vec3::new(10.0, 20.0, 30.0);
336        let half_extents = Vec3::new(1.0, 2.0, 3.0);
337        let aabb = Aabb::from_center_half_extents(center, half_extents);
338
339        assert_eq!(aabb.min, Vec3::new(9.0, 18.0, 27.0));
340        assert_eq!(aabb.max, Vec3::new(11.0, 22.0, 33.0));
341        assert!(aabb_approx_eq(aabb, Aabb::from_min_max(aabb.min, aabb.max)));
342    }
343
344    #[test]
345    fn test_aabb_from_point() {
346        let p = Vec3::new(5.0, 6.0, 7.0);
347        let aabb = Aabb::from_point(p);
348
349        assert_eq!(aabb.min, p);
350        assert_eq!(aabb.max, p);
351        assert!(aabb.is_valid());
352    }
353
354    #[test]
355    fn test_aabb_from_points() {
356        assert!(Aabb::from_points(&[]).is_none());
357
358        let points = [
359            Vec3::new(1.0, 5.0, -1.0),
360            Vec3::new(0.0, 2.0, 3.0),
361            Vec3::new(4.0, 8.0, 0.0),
362        ];
363        let aabb = Aabb::from_points(&points).unwrap();
364
365        assert_eq!(aabb.min, Vec3::new(0.0, 2.0, -1.0));
366        assert_eq!(aabb.max, Vec3::new(4.0, 8.0, 3.0));
367    }
368
369    #[test]
370    fn test_aabb_utils() {
371        let aabb = Aabb::from_min_max(Vec3::new(-1.0, 0.0, 1.0), Vec3::new(3.0, 2.0, 5.0));
372
373        assert!(vec3_approx_eq(aabb.center(), Vec3::new(1.0, 1.0, 3.0)));
374        assert!(vec3_approx_eq(aabb.size(), Vec3::new(4.0, 2.0, 4.0)));
375        assert!(vec3_approx_eq(
376            aabb.half_extents(),
377            Vec3::new(2.0, 1.0, 2.0)
378        ));
379        assert!(aabb.is_valid());
380        assert!(!Aabb::INVALID.is_valid());
381        assert!(Aabb::from_point(Vec3::ZERO).is_valid());
382    }
383
384    #[test]
385    fn test_aabb_contains_point() {
386        let aabb = Aabb::from_min_max(Vec3::new(0.0, 0.0, 0.0), Vec3::new(1.0, 1.0, 1.0));
387        // Inside
388        assert!(aabb.contains_point(Vec3::new(0.5, 0.5, 0.5)));
389
390        // On boundary
391        assert!(aabb.contains_point(Vec3::new(0.0, 0.5, 0.5)));
392        assert!(aabb.contains_point(Vec3::new(1.0, 0.5, 0.5)));
393        assert!(aabb.contains_point(Vec3::new(0.5, 0.0, 0.5)));
394        assert!(aabb.contains_point(Vec3::new(0.5, 1.0, 0.5)));
395        assert!(aabb.contains_point(Vec3::new(0.5, 0.5, 0.0)));
396        assert!(aabb.contains_point(Vec3::new(0.5, 0.5, 1.0)));
397        assert!(aabb.contains_point(Vec3::new(0.0, 0.0, 0.0)));
398        assert!(aabb.contains_point(Vec3::new(1.0, 1.0, 1.0)));
399
400        // Outside
401        assert!(!aabb.contains_point(Vec3::new(1.1, 0.5, 0.5)));
402        assert!(!aabb.contains_point(Vec3::new(-0.1, 0.5, 0.5)));
403        assert!(!aabb.contains_point(Vec3::new(0.5, 1.1, 0.5)));
404        assert!(!aabb.contains_point(Vec3::new(0.5, -0.1, 0.5)));
405        assert!(!aabb.contains_point(Vec3::new(0.5, 0.5, 1.1)));
406        assert!(!aabb.contains_point(Vec3::new(0.5, 0.5, -0.1)));
407    }
408
409    #[test]
410    fn test_aabb_intersects_aabb() {
411        let aabb1 = Aabb::from_min_max(Vec3::new(0.0, 0.0, 0.0), Vec3::new(2.0, 2.0, 2.0));
412
413        // Identical
414        let aabb2 = Aabb::from_min_max(Vec3::new(0.0, 0.0, 0.0), Vec3::new(2.0, 2.0, 2.0));
415        assert!(aabb1.intersects_aabb(&aabb2));
416
417        // Overlapping
418        let aabb3 = Aabb::from_min_max(Vec3::new(1.0, 1.0, 1.0), Vec3::new(3.0, 3.0, 3.0));
419        assert!(aabb1.intersects_aabb(&aabb3));
420        assert!(aabb3.intersects_aabb(&aabb1));
421
422        // Touching boundary
423        let aabb4 = Aabb::from_min_max(Vec3::new(2.0, 0.0, 0.0), Vec3::new(3.0, 2.0, 2.0));
424        assert!(aabb1.intersects_aabb(&aabb4));
425        assert!(aabb4.intersects_aabb(&aabb1));
426
427        // Containing
428        let aabb5 = Aabb::from_min_max(Vec3::new(0.5, 0.5, 0.5), Vec3::new(1.5, 1.5, 1.5));
429        assert!(aabb1.intersects_aabb(&aabb5));
430        assert!(aabb5.intersects_aabb(&aabb1));
431
432        // Non-overlapping X
433        let aabb6 = Aabb::from_min_max(Vec3::new(2.1, 0.0, 0.0), Vec3::new(3.0, 2.0, 2.0));
434        assert!(!aabb1.intersects_aabb(&aabb6));
435        assert!(!aabb6.intersects_aabb(&aabb1));
436
437        // Non-overlapping Y
438        let aabb7 = Aabb::from_min_max(Vec3::new(0.0, 2.1, 0.0), Vec3::new(2.0, 3.0, 2.0));
439        assert!(!aabb1.intersects_aabb(&aabb7));
440        assert!(!aabb7.intersects_aabb(&aabb1));
441
442        // Non-overlapping Z
443        let aabb8 = Aabb::from_min_max(Vec3::new(0.0, 0.0, 2.1), Vec3::new(2.0, 2.0, 3.0));
444        assert!(!aabb1.intersects_aabb(&aabb8));
445        assert!(!aabb8.intersects_aabb(&aabb1));
446    }
447
448    #[test]
449    fn test_aabb_contains_aabb() {
450        let aabb1 = Aabb::from_min_max(Vec3::new(0.0, 0.0, 0.0), Vec3::new(10.0, 10.0, 10.0));
451
452        // Fully inside
453        let aabb2 = Aabb::from_min_max(Vec3::new(2.0, 2.0, 2.0), Vec3::new(8.0, 8.0, 8.0));
454        assert!(aabb1.contains_aabb(&aabb2));
455        assert!(!aabb2.contains_aabb(&aabb1));
456
457        // Overlapping but not contained
458        let aabb3 = Aabb::from_min_max(Vec3::new(5.0, 5.0, 5.0), Vec3::new(15.0, 15.0, 15.0));
459        assert!(aabb1.intersects_aabb(&aabb3));
460        assert!(!aabb1.contains_aabb(&aabb3));
461
462        // Identical
463        assert!(aabb1.contains_aabb(&aabb1));
464    }
465
466    #[test]
467    fn test_aabb_merge() {
468        let aabb1 = Aabb::from_min_max(Vec3::new(0.0, 0.0, 0.0), Vec3::new(1.0, 1.0, 1.0));
469        let aabb2 = Aabb::from_min_max(Vec3::new(0.5, 0.5, 0.5), Vec3::new(1.5, 1.5, 1.5));
470        let merged_aabb = aabb1.merge(&aabb2);
471
472        assert_eq!(merged_aabb.min, Vec3::new(0.0, 0.0, 0.0));
473        assert_eq!(merged_aabb.max, Vec3::new(1.5, 1.5, 1.5));
474
475        let point = Vec3::new(-1.0, 0.5, 2.0);
476        let merged_point = aabb1.merged_with_point(point);
477
478        assert_eq!(merged_point.min, Vec3::new(-1.0, 0.0, 0.0));
479        assert_eq!(merged_point.max, Vec3::new(1.0, 1.0, 2.0));
480
481        // Test merging with invalid starts correctly
482        let merged_with_invalid = Aabb::INVALID.merge(&aabb1);
483        assert!(aabb_approx_eq(merged_with_invalid, aabb1));
484
485        let merged_with_invalid_pt = Aabb::INVALID.merged_with_point(point);
486        assert!(aabb_approx_eq(
487            merged_with_invalid_pt,
488            Aabb::from_point(point)
489        ));
490    }
491
492    #[test]
493    fn test_aabb_transform() {
494        let aabb = Aabb::from_min_max(Vec3::new(-1.0, -1.0, -1.0), Vec3::new(1.0, 1.0, 1.0)); // Unit cube centered at origin
495        let matrix = Mat4::from_translation(Vec3::new(10.0, 0.0, 0.0)); // Translate +10 on X
496        let transformed_aabb = aabb.transform(&matrix);
497        let expected_aabb =
498            Aabb::from_min_max(Vec3::new(9.0, -1.0, -1.0), Vec3::new(11.0, 1.0, 1.0));
499
500        assert!(aabb_approx_eq(transformed_aabb, expected_aabb));
501
502        // Test with rotation (resulting AABB will be larger)
503        let matrix_rot = Mat4::from_rotation_y(PI / 4.0); // Rotate 45 deg around Y
504        let transformed_rot_aabb = aabb.transform(&matrix_rot);
505
506        // The exact min/max are harder to calculate manually, but it should contain the original corners rotated
507        // Max extent along X/Z should now be sqrt(1^2 + 1^2) = sqrt(2)
508        let sqrt2 = 2.0f32.sqrt();
509
510        assert!(approx_eq(transformed_rot_aabb.min.x, -sqrt2));
511        assert!(approx_eq(transformed_rot_aabb.max.x, sqrt2));
512        assert!(approx_eq(transformed_rot_aabb.min.y, -1.0)); // Y extent shouldn't change
513        assert!(approx_eq(transformed_rot_aabb.max.y, 1.0));
514        assert!(approx_eq(transformed_rot_aabb.min.z, -sqrt2));
515        assert!(approx_eq(transformed_rot_aabb.max.z, sqrt2));
516
517        // Test with scaling
518        let matrix_scale = Mat4::from_scale(Vec3::new(2.0, 1.0, 0.5));
519        let transformed_scale_aabb = aabb.transform(&matrix_scale);
520        let expected_scale_aabb =
521            Aabb::from_min_max(Vec3::new(-2.0, -1.0, -0.5), Vec3::new(2.0, 1.0, 0.5));
522
523        assert!(aabb_approx_eq(transformed_scale_aabb, expected_scale_aabb));
524    }
525}
khora_core/math/geometry.rs

khora_core/math/
geometry.rs
