bevy_picking/mesh_picking/ray_cast/
intersections.rs

1use bevy_math::{bounding::Aabb3d, Dir3, Mat4, Ray3d, Vec3, Vec3A};
2use bevy_mesh::{Indices, Mesh, PrimitiveTopology};
3use bevy_reflect::Reflect;
4
5use super::Backfaces;
6
7/// Hit data for an intersection between a ray and a mesh.
8#[derive(Debug, Clone, Reflect)]
9#[reflect(Clone)]
10pub struct RayMeshHit {
11    /// The point of intersection in world space.
12    pub point: Vec3,
13    /// The normal vector of the triangle at the point of intersection. Not guaranteed to be normalized for scaled meshes.
14    pub normal: Vec3,
15    /// The barycentric coordinates of the intersection.
16    pub barycentric_coords: Vec3,
17    /// The distance from the ray origin to the intersection point.
18    pub distance: f32,
19    /// The vertices of the triangle that was hit.
20    pub triangle: Option<[Vec3; 3]>,
21    /// The index of the triangle that was hit.
22    pub triangle_index: Option<usize>,
23}
24
25/// Hit data for an intersection between a ray and a triangle.
26#[derive(Default, Debug)]
27pub struct RayTriangleHit {
28    pub distance: f32,
29    pub barycentric_coords: (f32, f32),
30}
31
32/// Casts a ray on a mesh, and returns the intersection.
33pub(super) fn ray_intersection_over_mesh(
34    mesh: &Mesh,
35    transform: &Mat4,
36    ray: Ray3d,
37    culling: Backfaces,
38) -> Option<RayMeshHit> {
39    if mesh.primitive_topology() != PrimitiveTopology::TriangleList {
40        return None; // ray_mesh_intersection assumes vertices are laid out in a triangle list
41    }
42    // Vertex positions are required
43    let positions = mesh.attribute(Mesh::ATTRIBUTE_POSITION)?.as_float3()?;
44
45    // Normals are optional
46    let normals = mesh
47        .attribute(Mesh::ATTRIBUTE_NORMAL)
48        .and_then(|normal_values| normal_values.as_float3());
49
50    match mesh.indices() {
51        Some(Indices::U16(indices)) => {
52            ray_mesh_intersection(ray, transform, positions, normals, Some(indices), culling)
53        }
54        Some(Indices::U32(indices)) => {
55            ray_mesh_intersection(ray, transform, positions, normals, Some(indices), culling)
56        }
57        None => ray_mesh_intersection::<usize>(ray, transform, positions, normals, None, culling),
58    }
59}
60
61/// Checks if a ray intersects a mesh, and returns the nearest intersection if one exists.
62pub fn ray_mesh_intersection<I: TryInto<usize> + Clone + Copy>(
63    ray: Ray3d,
64    mesh_transform: &Mat4,
65    positions: &[[f32; 3]],
66    vertex_normals: Option<&[[f32; 3]]>,
67    indices: Option<&[I]>,
68    backface_culling: Backfaces,
69) -> Option<RayMeshHit> {
70    let world_to_mesh = mesh_transform.inverse();
71
72    let ray = Ray3d::new(
73        world_to_mesh.transform_point3(ray.origin),
74        Dir3::new(world_to_mesh.transform_vector3(*ray.direction)).ok()?,
75    );
76
77    let closest_hit = if let Some(indices) = indices {
78        // The index list must be a multiple of three. If not, the mesh is malformed and the raycast
79        // result might be nonsensical.
80        if indices.len() % 3 != 0 {
81            return None;
82        }
83
84        indices
85            .chunks_exact(3)
86            .enumerate()
87            .fold(
88                (f32::MAX, None),
89                |(closest_distance, closest_hit), (tri_idx, triangle)| {
90                    let [Ok(a), Ok(b), Ok(c)] = [
91                        triangle[0].try_into(),
92                        triangle[1].try_into(),
93                        triangle[2].try_into(),
94                    ] else {
95                        return (closest_distance, closest_hit);
96                    };
97
98                    let tri_vertices = match [positions.get(a), positions.get(b), positions.get(c)]
99                    {
100                        [Some(a), Some(b), Some(c)] => {
101                            [Vec3::from(*a), Vec3::from(*b), Vec3::from(*c)]
102                        }
103                        _ => return (closest_distance, closest_hit),
104                    };
105
106                    match ray_triangle_intersection(&ray, &tri_vertices, backface_culling) {
107                        Some(hit) if hit.distance >= 0. && hit.distance < closest_distance => {
108                            (hit.distance, Some((tri_idx, hit)))
109                        }
110                        _ => (closest_distance, closest_hit),
111                    }
112                },
113            )
114            .1
115    } else {
116        positions
117            .chunks_exact(3)
118            .enumerate()
119            .fold(
120                (f32::MAX, None),
121                |(closest_distance, closest_hit), (tri_idx, triangle)| {
122                    let tri_vertices = [
123                        Vec3::from(triangle[0]),
124                        Vec3::from(triangle[1]),
125                        Vec3::from(triangle[2]),
126                    ];
127
128                    match ray_triangle_intersection(&ray, &tri_vertices, backface_culling) {
129                        Some(hit) if hit.distance >= 0. && hit.distance < closest_distance => {
130                            (hit.distance, Some((tri_idx, hit)))
131                        }
132                        _ => (closest_distance, closest_hit),
133                    }
134                },
135            )
136            .1
137    };
138
139    closest_hit.and_then(|(tri_idx, hit)| {
140        let [a, b, c] = match indices {
141            Some(indices) => {
142                let triangle = indices.get((tri_idx * 3)..(tri_idx * 3 + 3))?;
143
144                let [Ok(a), Ok(b), Ok(c)] = [
145                    triangle[0].try_into(),
146                    triangle[1].try_into(),
147                    triangle[2].try_into(),
148                ] else {
149                    return None;
150                };
151
152                [a, b, c]
153            }
154            None => [tri_idx * 3, tri_idx * 3 + 1, tri_idx * 3 + 2],
155        };
156
157        let tri_vertices = match [positions.get(a), positions.get(b), positions.get(c)] {
158            [Some(a), Some(b), Some(c)] => [Vec3::from(*a), Vec3::from(*b), Vec3::from(*c)],
159            _ => return None,
160        };
161
162        let tri_normals = vertex_normals.and_then(|normals| {
163            let [Some(a), Some(b), Some(c)] = [normals.get(a), normals.get(b), normals.get(c)]
164            else {
165                return None;
166            };
167            Some([Vec3::from(*a), Vec3::from(*b), Vec3::from(*c)])
168        });
169
170        let point = ray.get_point(hit.distance);
171        let u = hit.barycentric_coords.0;
172        let v = hit.barycentric_coords.1;
173        let w = 1.0 - u - v;
174        let barycentric = Vec3::new(u, v, w);
175
176        let normal = if let Some(normals) = tri_normals {
177            normals[1] * u + normals[2] * v + normals[0] * w
178        } else {
179            (tri_vertices[1] - tri_vertices[0])
180                .cross(tri_vertices[2] - tri_vertices[0])
181                .normalize()
182        };
183
184        Some(RayMeshHit {
185            point: mesh_transform.transform_point3(point),
186            normal: mesh_transform.transform_vector3(normal),
187            barycentric_coords: barycentric,
188            distance: mesh_transform
189                .transform_vector3(ray.direction * hit.distance)
190                .length(),
191            triangle: Some(tri_vertices.map(|v| mesh_transform.transform_point3(v))),
192            triangle_index: Some(tri_idx),
193        })
194    })
195}
196
197/// Takes a ray and triangle and computes the intersection.
198#[inline]
199fn ray_triangle_intersection(
200    ray: &Ray3d,
201    triangle: &[Vec3; 3],
202    backface_culling: Backfaces,
203) -> Option<RayTriangleHit> {
204    // Source: https://www.scratchapixel.com/lessons/3d-basic-rendering/ray-tracing-rendering-a-triangle/moller-trumbore-ray-triangle-intersection
205    let vector_v0_to_v1: Vec3 = triangle[1] - triangle[0];
206    let vector_v0_to_v2: Vec3 = triangle[2] - triangle[0];
207    let p_vec: Vec3 = ray.direction.cross(vector_v0_to_v2);
208    let determinant: f32 = vector_v0_to_v1.dot(p_vec);
209
210    match backface_culling {
211        Backfaces::Cull => {
212            // if the determinant is negative the triangle is back facing
213            // if the determinant is close to 0, the ray misses the triangle
214            // This test checks both cases
215            if determinant < f32::EPSILON {
216                return None;
217            }
218        }
219        Backfaces::Include => {
220            // ray and triangle are parallel if det is close to 0
221            if determinant.abs() < f32::EPSILON {
222                return None;
223            }
224        }
225    }
226
227    let determinant_inverse = 1.0 / determinant;
228
229    let t_vec = ray.origin - triangle[0];
230    let u = t_vec.dot(p_vec) * determinant_inverse;
231    if !(0.0..=1.0).contains(&u) {
232        return None;
233    }
234
235    let q_vec = t_vec.cross(vector_v0_to_v1);
236    let v = (*ray.direction).dot(q_vec) * determinant_inverse;
237    if v < 0.0 || u + v > 1.0 {
238        return None;
239    }
240
241    // The distance between ray origin and intersection is t.
242    let t: f32 = vector_v0_to_v2.dot(q_vec) * determinant_inverse;
243
244    Some(RayTriangleHit {
245        distance: t,
246        barycentric_coords: (u, v),
247    })
248}
249
250// TODO: It'd be nice to reuse `RayCast3d::aabb_intersection_at`, but it assumes a normalized ray.
251//       In our case, the ray is transformed to model space, which could involve scaling.
252/// Checks if the ray intersects with the AABB of a mesh, returning the distance to the point of intersection.
253/// The distance is zero if the ray starts inside the AABB.
254pub fn ray_aabb_intersection_3d(ray: Ray3d, aabb: &Aabb3d, model_to_world: &Mat4) -> Option<f32> {
255    // Transform the ray to model space
256    let world_to_model = model_to_world.inverse();
257    let ray_direction: Vec3A = world_to_model.transform_vector3a((*ray.direction).into());
258    let ray_direction_recip = ray_direction.recip();
259    let ray_origin: Vec3A = world_to_model.transform_point3a(ray.origin.into());
260
261    // Check if the ray intersects the mesh's AABB. It's useful to work in model space
262    // because we can do an AABB intersection test, instead of an OBB intersection test.
263
264    // NOTE: This is largely copied from `RayCast3d::aabb_intersection_at`.
265    let positive = ray_direction.signum().cmpgt(Vec3A::ZERO);
266    let min = Vec3A::select(positive, aabb.min, aabb.max);
267    let max = Vec3A::select(positive, aabb.max, aabb.min);
268
269    // Calculate the minimum/maximum time for each axis based on how much the direction goes that
270    // way. These values can get arbitrarily large, or even become NaN, which is handled by the
271    // min/max operations below
272    let tmin = (min - ray_origin) * ray_direction_recip;
273    let tmax = (max - ray_origin) * ray_direction_recip;
274
275    // An axis that is not relevant to the ray direction will be NaN. When one of the arguments
276    // to min/max is NaN, the other argument is used.
277    // An axis for which the direction is the wrong way will return an arbitrarily large
278    // negative value.
279    let tmin = tmin.max_element().max(0.0);
280    let tmax = tmax.min_element();
281
282    if tmin <= tmax {
283        Some(tmin)
284    } else {
285        None
286    }
287}
288
289#[cfg(test)]
290mod tests {
291    use bevy_math::Vec3;
292    use bevy_transform::components::GlobalTransform;
293
294    use super::*;
295
296    // Triangle vertices to be used in a left-hand coordinate system
297    const V0: [f32; 3] = [1.0, -1.0, 2.0];
298    const V1: [f32; 3] = [1.0, 2.0, -1.0];
299    const V2: [f32; 3] = [1.0, -1.0, -1.0];
300
301    #[test]
302    fn ray_cast_triangle_mt() {
303        let triangle = [V0.into(), V1.into(), V2.into()];
304        let ray = Ray3d::new(Vec3::ZERO, Dir3::X);
305        let result = ray_triangle_intersection(&ray, &triangle, Backfaces::Include);
306        assert!(result.unwrap().distance - 1.0 <= f32::EPSILON);
307    }
308
309    #[test]
310    fn ray_cast_triangle_mt_culling() {
311        let triangle = [V2.into(), V1.into(), V0.into()];
312        let ray = Ray3d::new(Vec3::ZERO, Dir3::X);
313        let result = ray_triangle_intersection(&ray, &triangle, Backfaces::Cull);
314        assert!(result.is_none());
315    }
316
317    #[test]
318    fn ray_mesh_intersection_simple() {
319        let ray = Ray3d::new(Vec3::ZERO, Dir3::X);
320        let mesh_transform = GlobalTransform::IDENTITY.compute_matrix();
321        let positions = &[V0, V1, V2];
322        let vertex_normals = None;
323        let indices: Option<&[u16]> = None;
324        let backface_culling = Backfaces::Cull;
325
326        let result = ray_mesh_intersection(
327            ray,
328            &mesh_transform,
329            positions,
330            vertex_normals,
331            indices,
332            backface_culling,
333        );
334
335        assert!(result.is_some());
336    }
337
338    #[test]
339    fn ray_mesh_intersection_indices() {
340        let ray = Ray3d::new(Vec3::ZERO, Dir3::X);
341        let mesh_transform = GlobalTransform::IDENTITY.compute_matrix();
342        let positions = &[V0, V1, V2];
343        let vertex_normals = None;
344        let indices: Option<&[u16]> = Some(&[0, 1, 2]);
345        let backface_culling = Backfaces::Cull;
346
347        let result = ray_mesh_intersection(
348            ray,
349            &mesh_transform,
350            positions,
351            vertex_normals,
352            indices,
353            backface_culling,
354        );
355
356        assert!(result.is_some());
357    }
358
359    #[test]
360    fn ray_mesh_intersection_indices_vertex_normals() {
361        let ray = Ray3d::new(Vec3::ZERO, Dir3::X);
362        let mesh_transform = GlobalTransform::IDENTITY.compute_matrix();
363        let positions = &[V0, V1, V2];
364        let vertex_normals: Option<&[[f32; 3]]> =
365            Some(&[[-1., 0., 0.], [-1., 0., 0.], [-1., 0., 0.]]);
366        let indices: Option<&[u16]> = Some(&[0, 1, 2]);
367        let backface_culling = Backfaces::Cull;
368
369        let result = ray_mesh_intersection(
370            ray,
371            &mesh_transform,
372            positions,
373            vertex_normals,
374            indices,
375            backface_culling,
376        );
377
378        assert!(result.is_some());
379    }
380
381    #[test]
382    fn ray_mesh_intersection_vertex_normals() {
383        let ray = Ray3d::new(Vec3::ZERO, Dir3::X);
384        let mesh_transform = GlobalTransform::IDENTITY.compute_matrix();
385        let positions = &[V0, V1, V2];
386        let vertex_normals: Option<&[[f32; 3]]> =
387            Some(&[[-1., 0., 0.], [-1., 0., 0.], [-1., 0., 0.]]);
388        let indices: Option<&[u16]> = None;
389        let backface_culling = Backfaces::Cull;
390
391        let result = ray_mesh_intersection(
392            ray,
393            &mesh_transform,
394            positions,
395            vertex_normals,
396            indices,
397            backface_culling,
398        );
399
400        assert!(result.is_some());
401    }
402
403    #[test]
404    fn ray_mesh_intersection_missing_vertex_normals() {
405        let ray = Ray3d::new(Vec3::ZERO, Dir3::X);
406        let mesh_transform = GlobalTransform::IDENTITY.compute_matrix();
407        let positions = &[V0, V1, V2];
408        let vertex_normals: Option<&[[f32; 3]]> = Some(&[]);
409        let indices: Option<&[u16]> = None;
410        let backface_culling = Backfaces::Cull;
411
412        let result = ray_mesh_intersection(
413            ray,
414            &mesh_transform,
415            positions,
416            vertex_normals,
417            indices,
418            backface_culling,
419        );
420
421        assert!(result.is_some());
422    }
423
424    #[test]
425    fn ray_mesh_intersection_indices_missing_vertex_normals() {
426        let ray = Ray3d::new(Vec3::ZERO, Dir3::X);
427        let mesh_transform = GlobalTransform::IDENTITY.compute_matrix();
428        let positions = &[V0, V1, V2];
429        let vertex_normals: Option<&[[f32; 3]]> = Some(&[]);
430        let indices: Option<&[u16]> = Some(&[0, 1, 2]);
431        let backface_culling = Backfaces::Cull;
432
433        let result = ray_mesh_intersection(
434            ray,
435            &mesh_transform,
436            positions,
437            vertex_normals,
438            indices,
439            backface_culling,
440        );
441
442        assert!(result.is_some());
443    }
444
445    #[test]
446    fn ray_mesh_intersection_not_enough_indices() {
447        let ray = Ray3d::new(Vec3::ZERO, Dir3::X);
448        let mesh_transform = GlobalTransform::IDENTITY.compute_matrix();
449        let positions = &[V0, V1, V2];
450        let vertex_normals = None;
451        let indices: Option<&[u16]> = Some(&[0]);
452        let backface_culling = Backfaces::Cull;
453
454        let result = ray_mesh_intersection(
455            ray,
456            &mesh_transform,
457            positions,
458            vertex_normals,
459            indices,
460            backface_culling,
461        );
462
463        assert!(result.is_none());
464    }
465
466    #[test]
467    fn ray_mesh_intersection_bad_indices() {
468        let ray = Ray3d::new(Vec3::ZERO, Dir3::X);
469        let mesh_transform = GlobalTransform::IDENTITY.compute_matrix();
470        let positions = &[V0, V1, V2];
471        let vertex_normals = None;
472        let indices: Option<&[u16]> = Some(&[0, 1, 3]);
473        let backface_culling = Backfaces::Cull;
474
475        let result = ray_mesh_intersection(
476            ray,
477            &mesh_transform,
478            positions,
479            vertex_normals,
480            indices,
481            backface_culling,
482        );
483
484        assert!(result.is_none());
485    }
486}
bevy_picking/mesh_picking/ray_cast/intersections.rs

bevy_picking/mesh_picking/ray_cast/
intersections.rs
