Skip to main content

qualia_core_db/specialized_libs/computational_geometry/
distance.rs

1//! Distance and intersection primitive family for 2D and 3D geometry.
2//!
3//! Provides allocation-free distance computations and exact/filtered
4//! intersection tests for the spatial query layer (BVH, kd-tree, box joins).
5//!
6//! All functions are `#[inline]`, zero-heap, and deterministic. Intersection
7//! tests return an enum classifying the result (including degenerate cases:
8//! collinear, coplanar, touching, zero-length, ray-grazes-edge).
9
10use super::primitives::{Point2, Point3};
11
12// ---------------------------------------------------------------------------
13// Distance: 2D
14// ---------------------------------------------------------------------------
15
16/// Squared Euclidean distance between two 2D points.
17#[inline]
18pub fn distance_sq_2d(a: Point2, b: Point2) -> f64 {
19    let dx = a.x - b.x;
20    let dy = a.y - b.y;
21    dx * dx + dy * dy
22}
23
24/// Euclidean distance between two 2D points.
25#[inline]
26pub fn distance_2d(a: Point2, b: Point2) -> f64 {
27    distance_sq_2d(a, b).sqrt()
28}
29
30/// Squared distance from point `p` to segment `ab` in 2D.
31#[inline]
32pub fn point_segment_distance_sq_2d(p: Point2, a: Point2, b: Point2) -> f64 {
33    let abx = b.x - a.x;
34    let aby = b.y - a.y;
35    let apx = p.x - a.x;
36    let apy = p.y - a.y;
37    let ab_sq = abx * abx + aby * aby;
38    if ab_sq == 0.0 {
39        // Degenerate segment (a == b).
40        return apx * apx + apy * apy;
41    }
42    let t = (apx * abx + apy * aby) / ab_sq;
43    let t = t.clamp(0.0, 1.0);
44    let cx = a.x + t * abx;
45    let cy = a.y + t * aby;
46    let dx = p.x - cx;
47    let dy = p.y - cy;
48    dx * dx + dy * dy
49}
50
51/// Distance from point `p` to segment `ab` in 2D.
52#[inline]
53pub fn point_segment_distance_2d(p: Point2, a: Point2, b: Point2) -> f64 {
54    point_segment_distance_sq_2d(p, a, b).sqrt()
55}
56
57/// Squared distance from point `p` to the line through `a` and `b` (infinite line) in 2D.
58#[inline]
59pub fn point_line_distance_sq_2d(p: Point2, a: Point2, b: Point2) -> f64 {
60    let abx = b.x - a.x;
61    let aby = b.y - a.y;
62    let ab_sq = abx * abx + aby * aby;
63    if ab_sq == 0.0 {
64        let dx = p.x - a.x;
65        let dy = p.y - a.y;
66        return dx * dx + dy * dy;
67    }
68    let cross = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
69    cross * cross / ab_sq
70}
71
72// ---------------------------------------------------------------------------
73// Distance: 3D
74// ---------------------------------------------------------------------------
75
76/// Squared Euclidean distance between two 3D points.
77#[inline]
78pub fn distance_sq_3d(a: Point3, b: Point3) -> f64 {
79    let dx = a.x - b.x;
80    let dy = a.y - b.y;
81    let dz = a.z - b.z;
82    dx * dx + dy * dy + dz * dz
83}
84
85/// Euclidean distance between two 3D points.
86#[inline]
87pub fn distance_3d(a: Point3, b: Point3) -> f64 {
88    distance_sq_3d(a, b).sqrt()
89}
90
91/// Squared distance from point `p` to segment `ab` in 3D.
92#[inline]
93pub fn point_segment_distance_sq_3d(p: Point3, a: Point3, b: Point3) -> f64 {
94    let abx = b.x - a.x;
95    let aby = b.y - a.y;
96    let abz = b.z - a.z;
97    let apx = p.x - a.x;
98    let apy = p.y - a.y;
99    let apz = p.z - a.z;
100    let ab_sq = abx * abx + aby * aby + abz * abz;
101    if ab_sq == 0.0 {
102        return apx * apx + apy * apy + apz * apz;
103    }
104    let t = (apx * abx + apy * aby + apz * abz) / ab_sq;
105    let t = t.clamp(0.0, 1.0);
106    let cx = a.x + t * abx;
107    let cy = a.y + t * aby;
108    let cz = a.z + t * abz;
109    let dx = p.x - cx;
110    let dy = p.y - cy;
111    let dz = p.z - cz;
112    dx * dx + dy * dy + dz * dz
113}
114
115/// Squared distance from point `p` to triangle `abc` in 3D.
116///
117/// Projects `p` onto the triangle plane, classifies the projection relative to
118/// the triangle edges, and returns the squared distance to the closest feature
119/// (vertex, edge, or interior).
120pub fn point_triangle_distance_sq_3d(p: Point3, a: Point3, b: Point3, c: Point3) -> f64 {
121    let ab = Point3::new(b.x - a.x, b.y - a.y, b.z - a.z);
122    let ac = Point3::new(c.x - a.x, c.y - a.y, c.z - a.z);
123    let ap = Point3::new(p.x - a.x, p.y - a.y, p.z - a.z);
124
125    let d1 = dot_3d(ab, ap);
126    let d2 = dot_3d(ac, ap);
127    if d1 <= 0.0 && d2 <= 0.0 {
128        // Closest to vertex a.
129        return dot_3d(ap, ap);
130    }
131
132    let bp = Point3::new(p.x - b.x, p.y - b.y, p.z - b.z);
133    let d3 = dot_3d(ab, bp);
134    let d4 = dot_3d(ac, bp);
135    if d3 >= 0.0 && d4 <= d3 {
136        // Closest to vertex b.
137        return dot_3d(bp, bp);
138    }
139
140    let cp = Point3::new(p.x - c.x, p.y - c.y, p.z - c.z);
141    let d5 = dot_3d(ab, cp);
142    let d6 = dot_3d(ac, cp);
143    if d6 >= 0.0 && d5 <= d6 {
144        // Closest to vertex c.
145        return dot_3d(cp, cp);
146    }
147
148    // Edge ab.
149    let vc = d1 * d4 - d3 * d2;
150    if vc <= 0.0 && d1 >= 0.0 && d3 <= 0.0 {
151        let t = d1 / (d1 - d3);
152        let cx = a.x + t * ab.x;
153        let cy = a.y + t * ab.y;
154        let cz = a.z + t * ab.z;
155        let dx = p.x - cx;
156        let dy = p.y - cy;
157        let dz = p.z - cz;
158        return dx * dx + dy * dy + dz * dz;
159    }
160
161    // Edge ac.
162    let vb = d5 * d2 - d1 * d6;
163    if vb <= 0.0 && d2 >= 0.0 && d6 <= 0.0 {
164        let t = d2 / (d2 - d6);
165        let cx = a.x + t * ac.x;
166        let cy = a.y + t * ac.y;
167        let cz = a.z + t * ac.z;
168        let dx = p.x - cx;
169        let dy = p.y - cy;
170        let dz = p.z - cz;
171        return dx * dx + dy * dy + dz * dz;
172    }
173
174    // Edge bc.
175    let va = d3 * d6 - d5 * d4;
176    if va <= 0.0 && (d4 - d3) >= 0.0 && (d5 - d6) >= 0.0 {
177        let t = (d4 - d3) / ((d4 - d3) + (d5 - d6));
178        let bcx = c.x - b.x;
179        let bcy = c.y - b.y;
180        let bcz = c.z - b.z;
181        let cx = b.x + t * bcx;
182        let cy = b.y + t * bcy;
183        let cz = b.z + t * bcz;
184        let dx = p.x - cx;
185        let dy = p.y - cy;
186        let dz = p.z - cz;
187        return dx * dx + dy * dy + dz * dz;
188    }
189
190    // Interior of the triangle: project onto plane.
191    let denom = 1.0 / (va + vb + vc);
192    let v = vb * denom;
193    let w = vc * denom;
194    let cx = a.x + ab.x * v + ac.x * w;
195    let cy = a.y + ab.y * v + ac.y * w;
196    let cz = a.z + ab.z * v + ac.z * w;
197    let dx = p.x - cx;
198    let dy = p.y - cy;
199    let dz = p.z - cz;
200    dx * dx + dy * dy + dz * dz
201}
202
203#[inline]
204fn dot_3d(a: Point3, b: Point3) -> f64 {
205    a.x * b.x + a.y * b.y + a.z * b.z
206}
207
208// ---------------------------------------------------------------------------
209// Intersection: 2D segment-segment
210// ---------------------------------------------------------------------------
211
212/// Result of a 2D segment-segment intersection test.
213#[derive(Debug, Clone, Copy, PartialEq, Eq)]
214pub enum SegmentIntersection2d {
215    /// Segments do not intersect.
216    Disjoint,
217    /// Segments intersect at a single point.
218    Point,
219    /// Segments overlap over an interval (collinear overlap).
220    Overlap,
221    /// Segments share an endpoint (touching).
222    Touching,
223}
224
225/// Test whether two 2D segments `ab` and `cd` intersect.
226///
227/// Uses orientation predicates for the general case and direct coordinate
228/// comparison for degenerate (collinear) cases. Returns the intersection type.
229pub fn segment_segment_intersect_2d(
230    a: Point2,
231    b: Point2,
232    c: Point2,
233    d: Point2,
234) -> SegmentIntersection2d {
235    use super::primitives::orientation_2;
236
237    let o1 = orientation_2(a, b, c);
238    let o2 = orientation_2(a, b, d);
239    let o3 = orientation_2(c, d, a);
240    let o4 = orientation_2(c, d, b);
241
242    // General case: proper intersection.
243    if o1 != o2 && o3 != o4 {
244        return SegmentIntersection2d::Point;
245    }
246
247    // Degenerate: collinear cases.
248    if o1 == super::primitives::Orientation::Collinear
249        && o2 == super::primitives::Orientation::Collinear
250    {
251        // All four points are collinear. Check for overlap.
252        // Project onto the dominant axis.
253        let (a_t, b_t) = if (b.x - a.x).abs() >= (b.y - a.y).abs() {
254            (a.x, b.x)
255        } else {
256            (a.y, b.y)
257        };
258        let (c_t, d_t) = if (b.x - a.x).abs() >= (b.y - a.y).abs() {
259            (c.x, d.x)
260        } else {
261            (c.y, d.y)
262        };
263
264        let (lo_ab, hi_ab) = (a_t.min(b_t), a_t.max(b_t));
265        let (lo_cd, hi_cd) = (c_t.min(d_t), c_t.max(d_t));
266
267        if hi_ab < lo_cd || hi_cd < lo_ab {
268            return SegmentIntersection2d::Disjoint;
269        }
270        // Check if they just touch at an endpoint.
271        if hi_ab == lo_cd || hi_cd == lo_ab {
272            return SegmentIntersection2d::Touching;
273        }
274        return SegmentIntersection2d::Overlap;
275    }
276
277    // One endpoint lies on the other segment.
278    if o1 == super::primitives::Orientation::Collinear && on_segment_2d(a, b, c) {
279        return SegmentIntersection2d::Touching;
280    }
281    if o2 == super::primitives::Orientation::Collinear && on_segment_2d(a, b, d) {
282        return SegmentIntersection2d::Touching;
283    }
284    if o3 == super::primitives::Orientation::Collinear && on_segment_2d(c, d, a) {
285        return SegmentIntersection2d::Touching;
286    }
287    if o4 == super::primitives::Orientation::Collinear && on_segment_2d(c, d, b) {
288        return SegmentIntersection2d::Touching;
289    }
290
291    SegmentIntersection2d::Disjoint
292}
293
294/// Check if point `p` lies on segment `ab` (assuming collinearity).
295#[inline]
296fn on_segment_2d(a: Point2, b: Point2, p: Point2) -> bool {
297    p.x >= a.x.min(b.x) && p.x <= a.x.max(b.x) && p.y >= a.y.min(b.y) && p.y <= a.y.max(b.y)
298}
299
300// ---------------------------------------------------------------------------
301// Intersection: 3D ray-triangle (Möller–Trumbore)
302// ---------------------------------------------------------------------------
303
304/// Result of a 3D ray-triangle intersection test.
305#[derive(Debug, Clone, Copy, PartialEq)]
306pub struct RayTriangleHit {
307    /// Ray parameter `t` at the hit point: `origin + t * direction`.
308    pub t: f64,
309    /// Barycentric coordinate u.
310    pub u: f64,
311    /// Barycentric coordinate v.
312    pub v: f64,
313}
314
315/// Result of a 3D ray-triangle intersection.
316#[derive(Debug, Clone, Copy, PartialEq)]
317pub enum RayTriangleResult {
318    /// Ray hits the triangle at the given parameters.
319    Hit(RayTriangleHit),
320    /// Ray misses the triangle.
321    Miss,
322    /// Ray is parallel to the triangle plane (grazes).
323    Parallel,
324    /// Degenerate triangle (zero area).
325    DegenerateTriangle,
326}
327
328/// Test intersection of a 3D ray with a triangle using the Möller–Trumbore algorithm.
329///
330/// - `origin`: ray origin.
331/// - `direction`: ray direction (need not be normalized; `t` is in units of `direction`).
332/// - `a, b, c`: triangle vertices.
333///
334/// Zero-heap. Deterministic.
335pub fn ray_triangle_intersect_3d(
336    origin: Point3,
337    direction: Point3,
338    a: Point3,
339    b: Point3,
340    c: Point3,
341) -> RayTriangleResult {
342    let edge1 = Point3::new(b.x - a.x, b.y - a.y, b.z - a.z);
343    let edge2 = Point3::new(c.x - a.x, c.y - a.y, c.z - a.z);
344
345    let h = cross_3d(direction, edge2);
346    let det = dot_3d(edge1, h);
347
348    // Back-face culling tolerance: if det is near zero, ray is parallel.
349    if det.abs() < f64::EPSILON {
350        // Check for degenerate triangle.
351        let edge1_sq = dot_3d(edge1, edge1);
352        let edge2_sq = dot_3d(edge2, edge2);
353        if edge1_sq == 0.0 || edge2_sq == 0.0 {
354            return RayTriangleResult::DegenerateTriangle;
355        }
356        return RayTriangleResult::Parallel;
357    }
358
359    let inv_det = 1.0 / det;
360    let s = Point3::new(origin.x - a.x, origin.y - a.y, origin.z - a.z);
361    let u = inv_det * dot_3d(s, h);
362
363    if u < 0.0 || u > 1.0 {
364        return RayTriangleResult::Miss;
365    }
366
367    let q = cross_3d(s, edge1);
368    let v = inv_det * dot_3d(direction, q);
369
370    if v < 0.0 || u + v > 1.0 {
371        return RayTriangleResult::Miss;
372    }
373
374    let t = inv_det * dot_3d(edge2, q);
375    RayTriangleResult::Hit(RayTriangleHit { t, u, v })
376}
377
378#[inline]
379fn cross_3d(a: Point3, b: Point3) -> Point3 {
380    Point3::new(
381        a.y * b.z - a.z * b.y,
382        a.z * b.x - a.x * b.z,
383        a.x * b.y - a.y * b.x,
384    )
385}
386
387// ---------------------------------------------------------------------------
388// Intersection: 3D AABB overlap
389// ---------------------------------------------------------------------------
390
391/// Axis-aligned bounding box in 3D.
392#[derive(Debug, Clone, Copy, PartialEq)]
393pub struct Aabb {
394    pub min: Point3,
395    pub max: Point3,
396}
397
398impl Aabb {
399    #[inline]
400    /// Creates `Aabb` with the given state.
401    pub fn new(min: Point3, max: Point3) -> Self {
402        Self { min, max }
403    }
404
405    #[inline]
406    /// `Aabb::overlaps`.
407    pub fn overlaps(&self, other: &Aabb) -> bool {
408        self.min.x <= other.max.x
409            && self.max.x >= other.min.x
410            && self.min.y <= other.max.y
411            && self.max.y >= other.min.y
412            && self.min.z <= other.max.z
413            && self.max.z >= other.min.z
414    }
415
416    #[inline]
417    /// `Aabb::contains_point`.
418    pub fn contains_point(&self, p: Point3) -> bool {
419        p.x >= self.min.x
420            && p.x <= self.max.x
421            && p.y >= self.min.y
422            && p.y <= self.max.y
423            && p.z >= self.min.z
424            && p.z <= self.max.z
425    }
426
427    /// Squared distance from point `p` to this AABB (0 if inside).
428    #[inline]
429    pub fn distance_sq_to_point(&self, p: Point3) -> f64 {
430        let dx = (self.min.x - p.x).max(0.0).max(p.x - self.max.x);
431        let dy = (self.min.y - p.y).max(0.0).max(p.y - self.max.y);
432        let dz = (self.min.z - p.z).max(0.0).max(p.z - self.max.z);
433        dx * dx + dy * dy + dz * dz
434    }
435
436    /// Center point.
437    #[inline]
438    pub fn center(&self) -> Point3 {
439        Point3::new(
440            0.5 * (self.min.x + self.max.x),
441            0.5 * (self.min.y + self.max.y),
442            0.5 * (self.min.z + self.max.z),
443        )
444    }
445
446    /// Surface area (used for SAH-based BVH construction).
447    #[inline]
448    pub fn surface_area(&self) -> f64 {
449        let dx = self.max.x - self.min.x;
450        let dy = self.max.y - self.min.y;
451        let dz = self.max.z - self.min.z;
452        2.0 * (dx * dy + dy * dz + dz * dx)
453    }
454
455    /// Union of two AABBs.
456    #[inline]
457    pub fn union(&self, other: &Aabb) -> Aabb {
458        Aabb::new(
459            Point3::new(
460                self.min.x.min(other.min.x),
461                self.min.y.min(other.min.y),
462                self.min.z.min(other.min.z),
463            ),
464            Point3::new(
465                self.max.x.max(other.max.x),
466                self.max.y.max(other.max.y),
467                self.max.z.max(other.max.z),
468            ),
469        )
470    }
471}
472
473// ---------------------------------------------------------------------------
474// Tests
475// ---------------------------------------------------------------------------
476
477#[cfg(test)]
478mod tests {
479    use super::*;
480
481    // --- 2D distance ---
482
483    #[test]
484    fn distance_2d_basic() {
485        let a = Point2::new(0.0, 0.0);
486        let b = Point2::new(3.0, 4.0);
487        assert_eq!(distance_2d(a, b), 5.0);
488        assert_eq!(distance_sq_2d(a, b), 25.0);
489    }
490
491    #[test]
492    fn point_segment_distance_2d_interior() {
493        let p = Point2::new(0.5, 1.0);
494        let a = Point2::new(0.0, 0.0);
495        let b = Point2::new(1.0, 0.0);
496        assert!((point_segment_distance_2d(p, a, b) - 1.0).abs() < 1e-12);
497    }
498
499    #[test]
500    fn point_segment_distance_2d_endpoint() {
501        let p = Point2::new(2.0, 0.0);
502        let a = Point2::new(0.0, 0.0);
503        let b = Point2::new(1.0, 0.0);
504        assert!((point_segment_distance_2d(p, a, b) - 1.0).abs() < 1e-12);
505    }
506
507    #[test]
508    fn point_segment_distance_2d_degenerate() {
509        let p = Point2::new(1.0, 1.0);
510        let a = Point2::new(0.0, 0.0);
511        let b = Point2::new(0.0, 0.0); // zero-length segment
512        assert!((point_segment_distance_2d(p, a, b) - 2.0f64.sqrt()).abs() < 1e-12);
513    }
514
515    #[test]
516    fn point_line_distance_2d() {
517        let p = Point2::new(0.0, 1.0);
518        let a = Point2::new(-1.0, 0.0);
519        let b = Point2::new(1.0, 0.0);
520        assert!((point_line_distance_sq_2d(p, a, b) - 1.0).abs() < 1e-12);
521    }
522
523    // --- 3D distance ---
524
525    #[test]
526    fn distance_3d_basic() {
527        let a = Point3::new(0.0, 0.0, 0.0);
528        let b = Point3::new(1.0, 2.0, 2.0);
529        assert!((distance_3d(a, b) - 3.0).abs() < 1e-12);
530    }
531
532    #[test]
533    fn point_segment_distance_3d() {
534        let p = Point3::new(0.5, 0.0, 1.0);
535        let a = Point3::new(0.0, 0.0, 0.0);
536        let b = Point3::new(1.0, 0.0, 0.0);
537        assert!((point_segment_distance_sq_3d(p, a, b) - 1.0).abs() < 1e-12);
538    }
539
540    #[test]
541    fn point_triangle_distance_3d_interior() {
542        // Point directly above the centroid of a triangle.
543        let a = Point3::new(0.0, 0.0, 0.0);
544        let b = Point3::new(1.0, 0.0, 0.0);
545        let c = Point3::new(0.0, 1.0, 0.0);
546        let p = Point3::new(1.0 / 3.0, 1.0 / 3.0, 2.0);
547        assert!((point_triangle_distance_sq_3d(p, a, b, c) - 4.0).abs() < 1e-12);
548    }
549
550    #[test]
551    fn point_triangle_distance_3d_vertex() {
552        let a = Point3::new(0.0, 0.0, 0.0);
553        let b = Point3::new(1.0, 0.0, 0.0);
554        let c = Point3::new(0.0, 1.0, 0.0);
555        let p = Point3::new(-1.0, -1.0, 0.0);
556        let d = point_triangle_distance_sq_3d(p, a, b, c);
557        assert!((d - 2.0).abs() < 1e-12, "d={d}");
558    }
559
560    // --- 2D segment intersection ---
561
562    #[test]
563    fn segments_cross_properly() {
564        let a = Point2::new(0.0, 0.0);
565        let b = Point2::new(1.0, 1.0);
566        let c = Point2::new(0.0, 1.0);
567        let d = Point2::new(1.0, 0.0);
568        assert_eq!(
569            segment_segment_intersect_2d(a, b, c, d),
570            SegmentIntersection2d::Point
571        );
572    }
573
574    #[test]
575    fn segments_disjoint() {
576        let a = Point2::new(0.0, 0.0);
577        let b = Point2::new(1.0, 0.0);
578        let c = Point2::new(2.0, 0.0);
579        let d = Point2::new(3.0, 0.0);
580        assert_eq!(
581            segment_segment_intersect_2d(a, b, c, d),
582            SegmentIntersection2d::Disjoint
583        );
584    }
585
586    #[test]
587    fn segments_collinear_overlap() {
588        let a = Point2::new(0.0, 0.0);
589        let b = Point2::new(2.0, 0.0);
590        let c = Point2::new(1.0, 0.0);
591        let d = Point2::new(3.0, 0.0);
592        assert_eq!(
593            segment_segment_intersect_2d(a, b, c, d),
594            SegmentIntersection2d::Overlap
595        );
596    }
597
598    #[test]
599    fn segments_collinear_touching() {
600        let a = Point2::new(0.0, 0.0);
601        let b = Point2::new(1.0, 0.0);
602        let c = Point2::new(1.0, 0.0);
603        let d = Point2::new(2.0, 0.0);
604        assert_eq!(
605            segment_segment_intersect_2d(a, b, c, d),
606            SegmentIntersection2d::Touching
607        );
608    }
609
610    #[test]
611    fn segments_collinear_disjoint() {
612        let a = Point2::new(0.0, 0.0);
613        let b = Point2::new(1.0, 0.0);
614        let c = Point2::new(2.0, 0.0);
615        let d = Point2::new(3.0, 0.0);
616        assert_eq!(
617            segment_segment_intersect_2d(a, b, c, d),
618            SegmentIntersection2d::Disjoint
619        );
620    }
621
622    #[test]
623    fn segments_touching_at_endpoint() {
624        // Two segments sharing endpoint b=c, not collinear.
625        // The intersection is a single point (the shared endpoint).
626        let a = Point2::new(0.0, 0.0);
627        let b = Point2::new(1.0, 0.0);
628        let c = Point2::new(1.0, 0.0);
629        let d = Point2::new(1.0, 1.0);
630        // When segments share an endpoint and diverge, the orientation test
631        // sees o1≠o2 and o3≠o4 → Point (proper crossing at the shared vertex).
632        assert_eq!(
633            segment_segment_intersect_2d(a, b, c, d),
634            SegmentIntersection2d::Point
635        );
636    }
637
638    // --- 3D ray-triangle ---
639
640    #[test]
641    fn ray_hits_triangle() {
642        let origin = Point3::new(0.0, 0.0, 1.0);
643        let dir = Point3::new(0.0, 0.0, -1.0);
644        let a = Point3::new(-1.0, -1.0, 0.0);
645        let b = Point3::new(1.0, -1.0, 0.0);
646        let c = Point3::new(0.0, 1.0, 0.0);
647        match ray_triangle_intersect_3d(origin, dir, a, b, c) {
648            RayTriangleResult::Hit(hit) => {
649                assert!((hit.t - 1.0).abs() < 1e-12);
650                assert!(hit.u >= 0.0 && hit.u <= 1.0);
651                assert!(hit.v >= 0.0 && hit.u + hit.v <= 1.0);
652            }
653            _ => panic!("expected hit"),
654        }
655    }
656
657    #[test]
658    fn ray_misses_triangle() {
659        let origin = Point3::new(5.0, 5.0, 1.0);
660        let dir = Point3::new(0.0, 0.0, -1.0);
661        let a = Point3::new(-1.0, -1.0, 0.0);
662        let b = Point3::new(1.0, -1.0, 0.0);
663        let c = Point3::new(0.0, 1.0, 0.0);
664        assert_eq!(
665            ray_triangle_intersect_3d(origin, dir, a, b, c),
666            RayTriangleResult::Miss
667        );
668    }
669
670    #[test]
671    fn ray_parallel_to_triangle() {
672        let origin = Point3::new(0.0, 0.0, 1.0);
673        let dir = Point3::new(1.0, 0.0, 0.0); // parallel to triangle plane
674        let a = Point3::new(-1.0, -1.0, 0.0);
675        let b = Point3::new(1.0, -1.0, 0.0);
676        let c = Point3::new(0.0, 1.0, 0.0);
677        assert_eq!(
678            ray_triangle_intersect_3d(origin, dir, a, b, c),
679            RayTriangleResult::Parallel
680        );
681    }
682
683    #[test]
684    fn ray_hits_degenerate_triangle() {
685        let origin = Point3::new(0.0, 0.0, 1.0);
686        let dir = Point3::new(0.0, 0.0, -1.0);
687        let a = Point3::new(0.0, 0.0, 0.0);
688        let b = Point3::new(0.0, 0.0, 0.0); // degenerate
689        let c = Point3::new(1.0, 0.0, 0.0);
690        assert_eq!(
691            ray_triangle_intersect_3d(origin, dir, a, b, c),
692            RayTriangleResult::DegenerateTriangle
693        );
694    }
695
696    // --- AABB ---
697
698    #[test]
699    fn aabb_overlaps() {
700        let a = Aabb::new(Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0));
701        let b = Aabb::new(Point3::new(0.5, 0.5, 0.5), Point3::new(2.0, 2.0, 2.0));
702        assert!(a.overlaps(&b));
703    }
704
705    #[test]
706    fn aabb_disjoint() {
707        let a = Aabb::new(Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0));
708        let b = Aabb::new(Point3::new(2.0, 2.0, 2.0), Point3::new(3.0, 3.0, 3.0));
709        assert!(!a.overlaps(&b));
710    }
711
712    #[test]
713    fn aabb_touching_overlaps() {
714        // Touching faces should overlap (<=, >=).
715        let a = Aabb::new(Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0));
716        let b = Aabb::new(Point3::new(1.0, 0.0, 0.0), Point3::new(2.0, 1.0, 1.0));
717        assert!(a.overlaps(&b));
718    }
719
720    #[test]
721    fn aabb_contains_point() {
722        let a = Aabb::new(Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0));
723        assert!(a.contains_point(Point3::new(0.5, 0.5, 0.5)));
724        assert!(!a.contains_point(Point3::new(1.5, 0.5, 0.5)));
725    }
726
727    #[test]
728    fn aabb_distance_sq_to_point_inside() {
729        let a = Aabb::new(Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0));
730        assert_eq!(a.distance_sq_to_point(Point3::new(0.5, 0.5, 0.5)), 0.0);
731    }
732
733    #[test]
734    fn aabb_distance_sq_to_point_outside() {
735        let a = Aabb::new(Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0));
736        let d = a.distance_sq_to_point(Point3::new(2.0, 0.5, 0.5));
737        assert!((d - 1.0).abs() < 1e-12);
738    }
739
740    #[test]
741    fn aabb_surface_area() {
742        let a = Aabb::new(Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 2.0, 3.0));
743        // 2*(1*2 + 2*3 + 3*1) = 2*(2+6+3) = 22
744        assert!((a.surface_area() - 22.0).abs() < 1e-12);
745    }
746
747    #[test]
748    fn aabb_union() {
749        let a = Aabb::new(Point3::new(0.0, 0.0, 0.0), Point3::new(1.0, 1.0, 1.0));
750        let b = Aabb::new(Point3::new(0.5, 0.5, 0.5), Point3::new(2.0, 2.0, 2.0));
751        let u = a.union(&b);
752        assert_eq!(u.min, Point3::new(0.0, 0.0, 0.0));
753        assert_eq!(u.max, Point3::new(2.0, 2.0, 2.0));
754    }
755}