mini_collide/
intersection.rs

1use crate::{Capsule, ClosestPoint, Distance, LineSegment, Plane, Ray, Sphere, Triangle};
2use mini_math::Vector3;
3
4/// Trait for determining whether two shapes intersect with one another
5pub trait Intersection<Rhs> {
6    /// Whether this shape intersect with the other
7    fn intersects(&self, rhs: &Rhs) -> bool;
8}
9
10impl Intersection<Ray> for Sphere {
11    fn intersects(&self, ray: &Ray) -> bool {
12        let p = ray.closest_point(&self.center);
13        self.distance(&p) < 0.0
14    }
15}
16
17impl Intersection<Sphere> for Ray {
18    fn intersects(&self, sphere: &Sphere) -> bool {
19        sphere.intersects(self)
20    }
21}
22
23impl Intersection<Capsule> for Ray {
24    fn intersects(&self, rhs: &Capsule) -> bool {
25        self.distance(rhs) < 0.0
26    }
27}
28
29impl Intersection<Ray> for Capsule {
30    fn intersects(&self, rhs: &Ray) -> bool {
31        rhs.intersects(self)
32    }
33}
34
35impl Intersection<Ray> for Plane {
36    fn intersects(&self, ray: &Ray) -> bool {
37        let t =
38            -(self.d + Vector3::from(ray.origin).dot(self.normal)) / ray.direction.dot(self.normal);
39        t >= 0.0
40    }
41}
42
43impl Intersection<Plane> for Ray {
44    fn intersects(&self, plane: &Plane) -> bool {
45        plane.intersects(self)
46    }
47}
48
49impl Intersection<LineSegment> for Sphere {
50    fn intersects(&self, line: &LineSegment) -> bool {
51        let p = line.closest_point(&self.center);
52        self.distance(&p) < 0.0
53    }
54}
55
56impl Intersection<Sphere> for LineSegment {
57    fn intersects(&self, sphere: &Sphere) -> bool {
58        sphere.intersects(self)
59    }
60}
61
62impl Intersection<Sphere> for Plane {
63    fn intersects(&self, sphere: &Sphere) -> bool {
64        self.distance(&sphere.center).abs() <= sphere.radius
65    }
66}
67
68impl Intersection<Plane> for Sphere {
69    fn intersects(&self, plane: &Plane) -> bool {
70        plane.intersects(self)
71    }
72}
73
74impl Intersection<Sphere> for Sphere {
75    fn intersects(&self, sphere: &Sphere) -> bool {
76        let combined_radius = self.radius + sphere.radius;
77        (self.center - sphere.center).magnitude_squared() <= combined_radius * combined_radius
78    }
79}
80
81impl Intersection<Sphere> for Triangle {
82    fn intersects(&self, sphere: &Sphere) -> bool {
83        let plane = Plane::from(self);
84
85        let p = plane.closest_point(&sphere.center);
86        let distance_from_plane_squared = (p - sphere.center).magnitude_squared();
87
88        if distance_from_plane_squared > sphere.radius * sphere.radius {
89            return false;
90        }
91
92        let radius_on_plane = (sphere.radius * sphere.radius - distance_from_plane_squared).sqrt();
93        let coordinates = self.barycentric_coordinates(p);
94
95        coordinates.x > -radius_on_plane
96            && coordinates.y > -radius_on_plane
97            && coordinates.z > -radius_on_plane
98    }
99}
100
101impl Intersection<Triangle> for Sphere {
102    fn intersects(&self, triangle: &Triangle) -> bool {
103        triangle.intersects(self)
104    }
105}
106
107impl Intersection<Ray> for Triangle {
108    fn intersects(&self, ray: &Ray) -> bool {
109        let plane = Plane::from(self);
110
111        let n_dot_r = plane.normal.dot(ray.direction);
112        // early exit if ray parallel to plane
113        if n_dot_r.abs() < std::f32::EPSILON {
114            return false;
115        }
116
117        let d = plane.normal.dot(ray.origin - self.a);
118        let t = -d / n_dot_r;
119
120        // early exit if triangle entirely behind ray
121        if t < 0.0 {
122            return false;
123        }
124
125        let intersection_point = ray.origin + ray.direction * t;
126        self.coplanar_point_inside(intersection_point)
127    }
128}
129
130impl Intersection<Triangle> for Ray {
131    fn intersects(&self, triangle: &Triangle) -> bool {
132        triangle.intersects(self)
133    }
134}
135
136impl Intersection<LineSegment> for Triangle {
137    fn intersects(&self, line: &LineSegment) -> bool {
138        let plane = Plane::from(self);
139
140        let mut direction = line.end - line.start;
141        let length = direction.magnitude();
142        direction /= length;
143
144        let n_dot_r = plane.normal.dot(direction);
145        // early exit if line parallel to plane
146        if n_dot_r.abs() < std::f32::EPSILON {
147            return false;
148        }
149
150        let d = plane.normal.dot(line.start - self.a);
151        let t = -d / n_dot_r;
152
153        // early exit if triangle is entirely in fornt or behind of the line segment
154        if t < 0.0 || t > length {
155            return false;
156        }
157
158        let intersection_point = line.start + direction * t;
159        self.coplanar_point_inside(intersection_point)
160    }
161}
162
163impl Intersection<Triangle> for LineSegment {
164    fn intersects(&self, triangle: &Triangle) -> bool {
165        triangle.intersects(self)
166    }
167}
168
169#[cfg(test)]
170mod tests {
171    use super::*;
172    use mini_math::{Point, Vector3};
173
174    #[test]
175    fn test_ray_sphere_intersects() {
176        let sphere = Sphere::new(Point::new(0.0, 20.0, 0.0), 10.0);
177
178        let ray = Ray::new(Point::new(-20.0, 0.0, 0.0), Vector3::new(1.0, 0.0, 0.0));
179        assert!(!sphere.intersects(&ray));
180        assert!(!ray.intersects(&sphere));
181
182        let ray = Ray::new(Point::new(-20.0, 20.0, 0.0), Vector3::new(1.0, 0.0, 0.0));
183        assert!(sphere.intersects(&ray));
184        assert!(ray.intersects(&sphere));
185    }
186
187    #[test]
188    fn test_segment_sphere_intersects() {
189        let sphere = Sphere::new(Point::new(0.0, 20.0, 0.0), 10.0);
190
191        let segment = LineSegment::new(Point::new(-20.0, 0.0, 0.0), Point::new(-10.0, 0.0, 0.0));
192        assert!(!sphere.intersects(&segment));
193        assert!(!segment.intersects(&sphere));
194
195        let segment = LineSegment::new(Point::new(10.0, 0.0, 0.0), Point::new(20.0, 0.0, 0.0));
196        assert!(!sphere.intersects(&segment));
197        assert!(!segment.intersects(&sphere));
198
199        let segment = LineSegment::new(Point::new(-20.0, 20.0, 0.0), Point::new(20.0, 0.0, 0.0));
200        assert!(sphere.intersects(&segment));
201        assert!(segment.intersects(&sphere));
202    }
203
204    #[test]
205    fn test_ray_plane_intersects() {
206        let plane = Plane::from_points(
207            Point::new(-1.0, 0.0, -1.0),
208            Point::new(1.0, 0.0, -1.0),
209            Point::new(0.0, 0.0, 1.0),
210        );
211
212        let ray = Ray::new(Point::new(0.0, 1.0, 0.0), Vector3::new(0.0, 1.0, 0.0));
213        assert!(!plane.intersects(&ray));
214        assert!(!ray.intersects(&plane));
215
216        let ray = Ray::new(Point::new(0.0, -1.0, 0.0), Vector3::new(0.0, 1.0, 0.0));
217        assert!(plane.intersects(&ray));
218        assert!(ray.intersects(&plane));
219    }
220
221    #[test]
222    fn test_sphere_plane_intersects() {
223        let plane = Plane::from_points(
224            Point::new(-1.0, 0.0, -1.0),
225            Point::new(1.0, 0.0, -1.0),
226            Point::new(0.0, 0.0, 1.0),
227        );
228
229        let sphere = Sphere::new(Point::new(0.0, 10.0, 0.0), 5.0);
230        assert!(!plane.intersects(&sphere));
231        assert!(!sphere.intersects(&plane));
232
233        let sphere = Sphere::new(Point::new(0.0, -10.0, 0.0), 5.0);
234        assert!(!plane.intersects(&sphere));
235        assert!(!sphere.intersects(&plane));
236
237        let sphere = Sphere::new(Point::new(0.0, 2.0, 0.0), 5.0);
238        assert!(plane.intersects(&sphere));
239        assert!(sphere.intersects(&plane));
240    }
241
242    #[test]
243    fn test_sphere_sphere_intersects() {
244        let sphere1 = Sphere::new(Point::new(10.0, 0.0, 0.0), 5.0);
245
246        let sphere2 = Sphere::new(Point::new(-10.0, 00.0, 0.0), 5.0);
247        assert!(!sphere1.intersects(&sphere2));
248        assert!(!sphere2.intersects(&sphere1));
249
250        let sphere2 = Sphere::new(Point::new(0.0, 0.0, 0.0), 7.0);
251        assert!(sphere1.intersects(&sphere2));
252        assert!(sphere2.intersects(&sphere1));
253    }
254
255    #[test]
256    fn test_triangle_sphere_intersects() {
257        let triangle = Triangle::new(
258            Point::new(-1.0, 0.0, 0.0),
259            Point::new(1.0, 0.0, 0.0),
260            Point::new(0.0, 0.0, 1.0),
261        );
262
263        // distance from plane in the positive direction
264        let sphere = Sphere::new(Point::new(0.0, 1.0, 0.0), 0.5);
265        assert!(!triangle.intersects(&sphere));
266        assert!(!sphere.intersects(&triangle));
267
268        // distance from plane in the negative direction
269        let sphere = Sphere::new(Point::new(0.0, -1.0, 0.0), 0.5);
270        assert!(!triangle.intersects(&sphere));
271        assert!(!sphere.intersects(&triangle));
272
273        // distance from the plane in the direction of each edge
274        let sphere = Sphere::new(Point::new(0.0, 0.0, -3.0), 0.5);
275        assert!(!triangle.intersects(&sphere));
276        assert!(!sphere.intersects(&triangle));
277
278        let sphere = Sphere::new(Point::new(3.0, 0.0, 3.0), 0.5);
279        assert!(!triangle.intersects(&sphere));
280        assert!(!sphere.intersects(&triangle));
281
282        let sphere = Sphere::new(Point::new(-3.0, 0.0, 3.0), 0.5);
283        assert!(!triangle.intersects(&sphere));
284        assert!(!sphere.intersects(&triangle));
285
286        // diagonally from an edge
287        let sphere = Sphere::new(Point::new(0.0, 0.3, -0.3), 0.5);
288        assert!(triangle.intersects(&sphere));
289        assert!(sphere.intersects(&triangle));
290
291        // in the middle of the triangle
292        let sphere = Sphere::new(Point::new(0.0, 0.0, 0.0), 0.5);
293        assert!(triangle.intersects(&sphere));
294        assert!(sphere.intersects(&triangle));
295    }
296
297    #[test]
298    fn test_triangle_ray_intersects() {
299        let triangle = Triangle::new(
300            Point::new(-1.0, 0.0, 0.0),
301            Point::new(1.0, 0.0, 0.0),
302            Point::new(0.0, 0.0, 1.0),
303        );
304
305        // parallel
306        let ray = Ray::new(Point::new(0.0, 1.0, 0.0), Vector3::new(0.0, 0.0, 1.0));
307        assert!(!triangle.intersects(&ray));
308
309        // in front
310        let ray = Ray::new(Point::new(0.0, 1.0, 0.0), Vector3::new(0.0, 1.0, 0.0));
311        assert!(!triangle.intersects(&ray));
312
313        // behind
314        let ray = Ray::new(Point::new(0.0, -1.0, 0.0), Vector3::new(0.0, -1.0, 0.0));
315        assert!(!triangle.intersects(&ray));
316
317        // past
318        let ray = Ray::new(Point::new(3.0, 1.0, 3.0), Vector3::new(0.0, -1.0, 0.0));
319        assert!(!triangle.intersects(&ray));
320
321        // straight through
322        let ray = Ray::new(Point::new(0.0, 1.0, 0.0), Vector3::new(0.0, -1.0, 0.0));
323        assert!(triangle.intersects(&ray));
324
325        // diagonally through
326        let ray = Ray::new(
327            Point::new(-0.5, -1.0, 0.0),
328            Vector3::new(0.5, 1.0, 0.0).normalized(),
329        );
330        assert!(triangle.intersects(&ray));
331    }
332
333    #[test]
334    fn test_triangle_ray_intersects_2() {
335        let ray = Ray::new(
336            Point::new(0.0, 2.0, -6.0),
337            Vector3::new(0.0, 0.0, 1.0).normalized(),
338        );
339        let triangle = Triangle::new(
340            Point::new(2.0, 0.0, -1.25),
341            Point::new(0.0, 3.0, 2.5),
342            Point::new(-2.0, 0.0, -1.25),
343        );
344
345        assert!(triangle.intersects(&ray));
346    }
347
348    #[test]
349    fn test_triangle_line_segment_intersects() {
350        let triangle = Triangle::new(
351            Point::new(-1.0, 0.0, 0.0),
352            Point::new(1.0, 0.0, 0.0),
353            Point::new(0.0, 0.0, 1.0),
354        );
355
356        // parallel
357        let line = LineSegment::new(Point::new(0.0, 1.0, 0.0), Point::new(0.0, 1.0, 1.0));
358        assert!(!triangle.intersects(&line));
359
360        // in front
361        let line = LineSegment::new(Point::new(0.0, 1.0, 0.0), Point::new(0.0, 4.0, 0.0));
362        assert!(!triangle.intersects(&line));
363
364        // behind
365        let line = LineSegment::new(Point::new(0.0, -8.0, 0.0), Point::new(0.0, -1.0, 0.0));
366        assert!(!triangle.intersects(&line));
367
368        // past
369        let line = LineSegment::new(Point::new(3.0, 1.0, 3.0), Point::new(3.0, -1.0, 3.0));
370        assert!(!triangle.intersects(&line));
371
372        // straight through
373        let line = LineSegment::new(Point::new(0.0, 1.0, 0.0), Point::new(0.0, -1.0, 0.0));
374        assert!(triangle.intersects(&line));
375
376        // diagonally through
377        let line = LineSegment::new(Point::new(-0.5, -2.0, 0.0), Point::new(0.5, 2.0, 0.0));
378        assert!(triangle.intersects(&line));
379    }
380}
mini_collide/intersection.rs

mini_collide/
intersection.rs
