bevy_render/primitives/
mod.rs

1use std::borrow::Borrow;
2
3use bevy_ecs::{component::Component, entity::EntityHashMap, reflect::ReflectComponent};
4use bevy_math::{Affine3A, Mat3A, Mat4, Vec3, Vec3A, Vec4, Vec4Swizzles};
5use bevy_reflect::prelude::*;
6
7/// An axis-aligned bounding box, defined by:
8/// - a center,
9/// - the distances from the center to each faces along the axis,
10/// the faces are orthogonal to the axis.
11///
12/// It is typically used as a component on an entity to represent the local space
13/// occupied by this entity, with faces orthogonal to its local axis.
14///
15/// This component is notably used during "frustum culling", a process to determine
16/// if an entity should be rendered by a [`Camera`] if its bounding box intersects
17/// with the camera's [`Frustum`].
18///
19/// It will be added automatically by the systems in [`CalculateBounds`] to entities that:
20/// - could be subject to frustum culling, for example with a [`Handle<Mesh>`]
21/// or `Sprite` component,
22/// - don't have the [`NoFrustumCulling`] component.
23///
24/// It won't be updated automatically if the space occupied by the entity changes,
25/// for example if the vertex positions of a [`Mesh`] inside a `Handle<Mesh>` are
26/// updated.
27///
28/// [`Camera`]: crate::camera::Camera
29/// [`NoFrustumCulling`]: crate::view::visibility::NoFrustumCulling
30/// [`CalculateBounds`]: crate::view::visibility::VisibilitySystems::CalculateBounds
31/// [`Mesh`]: crate::mesh::Mesh
32/// [`Handle<Mesh>`]: crate::mesh::Mesh
33#[derive(Component, Clone, Copy, Debug, Default, Reflect, PartialEq)]
34#[reflect(Component, Default)]
35pub struct Aabb {
36    pub center: Vec3A,
37    pub half_extents: Vec3A,
38}
39
40impl Aabb {
41    #[inline]
42    pub fn from_min_max(minimum: Vec3, maximum: Vec3) -> Self {
43        let minimum = Vec3A::from(minimum);
44        let maximum = Vec3A::from(maximum);
45        let center = 0.5 * (maximum + minimum);
46        let half_extents = 0.5 * (maximum - minimum);
47        Self {
48            center,
49            half_extents,
50        }
51    }
52
53    /// Returns a bounding box enclosing the specified set of points.
54    ///
55    /// Returns `None` if the iterator is empty.
56    ///
57    /// # Examples
58    ///
59    /// ```
60    /// # use bevy_math::{Vec3, Vec3A};
61    /// # use bevy_render::primitives::Aabb;
62    /// let bb = Aabb::enclosing([Vec3::X, Vec3::Z * 2.0, Vec3::Y * -0.5]).unwrap();
63    /// assert_eq!(bb.min(), Vec3A::new(0.0, -0.5, 0.0));
64    /// assert_eq!(bb.max(), Vec3A::new(1.0, 0.0, 2.0));
65    /// ```
66    pub fn enclosing<T: Borrow<Vec3>>(iter: impl IntoIterator<Item = T>) -> Option<Self> {
67        let mut iter = iter.into_iter().map(|p| *p.borrow());
68        let mut min = iter.next()?;
69        let mut max = min;
70        for v in iter {
71            min = Vec3::min(min, v);
72            max = Vec3::max(max, v);
73        }
74        Some(Self::from_min_max(min, max))
75    }
76
77    /// Calculate the relative radius of the AABB with respect to a plane
78    #[inline]
79    pub fn relative_radius(&self, p_normal: &Vec3A, world_from_local: &Mat3A) -> f32 {
80        // NOTE: dot products on Vec3A use SIMD and even with the overhead of conversion are net faster than Vec3
81        let half_extents = self.half_extents;
82        Vec3A::new(
83            p_normal.dot(world_from_local.x_axis),
84            p_normal.dot(world_from_local.y_axis),
85            p_normal.dot(world_from_local.z_axis),
86        )
87        .abs()
88        .dot(half_extents)
89    }
90
91    #[inline]
92    pub fn min(&self) -> Vec3A {
93        self.center - self.half_extents
94    }
95
96    #[inline]
97    pub fn max(&self) -> Vec3A {
98        self.center + self.half_extents
99    }
100}
101
102impl From<Sphere> for Aabb {
103    #[inline]
104    fn from(sphere: Sphere) -> Self {
105        Self {
106            center: sphere.center,
107            half_extents: Vec3A::splat(sphere.radius),
108        }
109    }
110}
111
112#[derive(Clone, Debug, Default)]
113pub struct Sphere {
114    pub center: Vec3A,
115    pub radius: f32,
116}
117
118impl Sphere {
119    #[inline]
120    pub fn intersects_obb(&self, aabb: &Aabb, world_from_local: &Affine3A) -> bool {
121        let aabb_center_world = world_from_local.transform_point3a(aabb.center);
122        let v = aabb_center_world - self.center;
123        let d = v.length();
124        let relative_radius = aabb.relative_radius(&(v / d), &world_from_local.matrix3);
125        d < self.radius + relative_radius
126    }
127}
128
129/// A region of 3D space, specifically an open set whose border is a bisecting 2D plane.
130/// This bisecting plane partitions 3D space into two infinite regions,
131/// the half-space is one of those regions and excludes the bisecting plane.
132///
133/// Each instance of this type is characterized by:
134/// - the bisecting plane's unit normal, normalized and pointing "inside" the half-space,
135/// - the signed distance along the normal from the bisecting plane to the origin of 3D space.
136///
137/// The distance can also be seen as:
138/// - the distance along the inverse of the normal from the origin of 3D space to the bisecting plane,
139/// - the opposite of the distance along the normal from the origin of 3D space to the bisecting plane.
140///
141/// Any point `p` is considered to be within the `HalfSpace` when the length of the projection
142/// of p on the normal is greater or equal than the opposite of the distance,
143/// meaning: if the equation `normal.dot(p) + distance > 0.` is satisfied.
144///
145/// For example, the half-space containing all the points with a z-coordinate lesser
146/// or equal than `8.0` would be defined by: `HalfSpace::new(Vec3::NEG_Z.extend(-8.0))`.
147/// It includes all the points from the bisecting plane towards `NEG_Z`, and the distance
148/// from the plane to the origin is `-8.0` along `NEG_Z`.
149///
150/// It is used to define a [`Frustum`], but is also a useful mathematical primitive for rendering tasks such as  light computation.
151#[derive(Clone, Copy, Debug, Default)]
152pub struct HalfSpace {
153    normal_d: Vec4,
154}
155
156impl HalfSpace {
157    /// Constructs a `HalfSpace` from a 4D vector whose first 3 components
158    /// represent the bisecting plane's unit normal, and the last component is
159    /// the signed distance along the normal from the plane to the origin.
160    /// The constructor ensures the normal vector is normalized and the distance is appropriately scaled.
161    #[inline]
162    pub fn new(normal_d: Vec4) -> Self {
163        Self {
164            normal_d: normal_d * normal_d.xyz().length_recip(),
165        }
166    }
167
168    /// Returns the unit normal vector of the bisecting plane that characterizes the `HalfSpace`.
169    #[inline]
170    pub fn normal(&self) -> Vec3A {
171        Vec3A::from(self.normal_d)
172    }
173
174    /// Returns the signed distance from the bisecting plane to the origin along
175    /// the plane's unit normal vector.
176    #[inline]
177    pub fn d(&self) -> f32 {
178        self.normal_d.w
179    }
180
181    /// Returns the bisecting plane's unit normal vector and the signed distance
182    /// from the plane to the origin.
183    #[inline]
184    pub fn normal_d(&self) -> Vec4 {
185        self.normal_d
186    }
187}
188
189/// A region of 3D space defined by the intersection of 6 [`HalfSpace`]s.
190///
191/// Frustums are typically an apex-truncated square pyramid (a pyramid without the top) or a cuboid.
192///
193/// Half spaces are ordered left, right, top, bottom, near, far. The normal vectors
194/// of the half-spaces point towards the interior of the frustum.
195///
196/// A frustum component is used on an entity with a [`Camera`] component to
197/// determine which entities will be considered for rendering by this camera.
198/// All entities with an [`Aabb`] component that are not contained by (or crossing
199/// the boundary of) the frustum will not be rendered, and not be used in rendering computations.
200///
201/// This process is called frustum culling, and entities can opt out of it using
202/// the [`NoFrustumCulling`] component.
203///
204/// The frustum component is typically added from a bundle, either the `Camera2dBundle`
205/// or the `Camera3dBundle`.
206/// It is usually updated automatically by [`update_frusta`] from the
207/// [`CameraProjection`] component and [`GlobalTransform`] of the camera entity.
208///
209/// [`Camera`]: crate::camera::Camera
210/// [`NoFrustumCulling`]: crate::view::visibility::NoFrustumCulling
211/// [`update_frusta`]: crate::view::visibility::update_frusta
212/// [`CameraProjection`]: crate::camera::CameraProjection
213/// [`GlobalTransform`]: bevy_transform::components::GlobalTransform
214#[derive(Component, Clone, Copy, Debug, Default, Reflect)]
215#[reflect(Component, Default)]
216pub struct Frustum {
217    #[reflect(ignore)]
218    pub half_spaces: [HalfSpace; 6],
219}
220
221impl Frustum {
222    /// Returns a frustum derived from `clip_from_world`.
223    #[inline]
224    pub fn from_clip_from_world(clip_from_world: &Mat4) -> Self {
225        let mut frustum = Frustum::from_clip_from_world_no_far(clip_from_world);
226        frustum.half_spaces[5] = HalfSpace::new(clip_from_world.row(2));
227        frustum
228    }
229
230    /// Returns a frustum derived from `clip_from_world`,
231    /// but with a custom far plane.
232    #[inline]
233    pub fn from_clip_from_world_custom_far(
234        clip_from_world: &Mat4,
235        view_translation: &Vec3,
236        view_backward: &Vec3,
237        far: f32,
238    ) -> Self {
239        let mut frustum = Frustum::from_clip_from_world_no_far(clip_from_world);
240        let far_center = *view_translation - far * *view_backward;
241        frustum.half_spaces[5] =
242            HalfSpace::new(view_backward.extend(-view_backward.dot(far_center)));
243        frustum
244    }
245
246    // NOTE: This approach of extracting the frustum half-space from the view
247    // projection matrix is from Foundations of Game Engine Development 2
248    // Rendering by Lengyel.
249    /// Returns a frustum derived from `view_projection`,
250    /// without a far plane.
251    fn from_clip_from_world_no_far(clip_from_world: &Mat4) -> Self {
252        let row3 = clip_from_world.row(3);
253        let mut half_spaces = [HalfSpace::default(); 6];
254        for (i, half_space) in half_spaces.iter_mut().enumerate().take(5) {
255            let row = clip_from_world.row(i / 2);
256            *half_space = HalfSpace::new(if (i & 1) == 0 && i != 4 {
257                row3 + row
258            } else {
259                row3 - row
260            });
261        }
262        Self { half_spaces }
263    }
264
265    /// Checks if a sphere intersects the frustum.
266    #[inline]
267    pub fn intersects_sphere(&self, sphere: &Sphere, intersect_far: bool) -> bool {
268        let sphere_center = sphere.center.extend(1.0);
269        let max = if intersect_far { 6 } else { 5 };
270        for half_space in &self.half_spaces[..max] {
271            if half_space.normal_d().dot(sphere_center) + sphere.radius <= 0.0 {
272                return false;
273            }
274        }
275        true
276    }
277
278    /// Checks if an Oriented Bounding Box (obb) intersects the frustum.
279    #[inline]
280    pub fn intersects_obb(
281        &self,
282        aabb: &Aabb,
283        world_from_local: &Affine3A,
284        intersect_near: bool,
285        intersect_far: bool,
286    ) -> bool {
287        let aabb_center_world = world_from_local.transform_point3a(aabb.center).extend(1.0);
288        for (idx, half_space) in self.half_spaces.into_iter().enumerate() {
289            if idx == 4 && !intersect_near {
290                continue;
291            }
292            if idx == 5 && !intersect_far {
293                continue;
294            }
295            let p_normal = half_space.normal();
296            let relative_radius = aabb.relative_radius(&p_normal, &world_from_local.matrix3);
297            if half_space.normal_d().dot(aabb_center_world) + relative_radius <= 0.0 {
298                return false;
299            }
300        }
301        true
302    }
303}
304
305#[derive(Component, Clone, Debug, Default, Reflect)]
306#[reflect(Component, Default)]
307pub struct CubemapFrusta {
308    #[reflect(ignore)]
309    pub frusta: [Frustum; 6],
310}
311
312impl CubemapFrusta {
313    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &Frustum> {
314        self.frusta.iter()
315    }
316    pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut Frustum> {
317        self.frusta.iter_mut()
318    }
319}
320
321#[derive(Component, Debug, Default, Reflect, Clone)]
322#[reflect(Component, Default)]
323pub struct CascadesFrusta {
324    #[reflect(ignore)]
325    pub frusta: EntityHashMap<Vec<Frustum>>,
326}
327
328#[cfg(test)]
329mod tests {
330    use super::*;
331
332    // A big, offset frustum
333    fn big_frustum() -> Frustum {
334        Frustum {
335            half_spaces: [
336                HalfSpace::new(Vec4::new(-0.9701, -0.2425, -0.0000, 7.7611)),
337                HalfSpace::new(Vec4::new(-0.0000, 1.0000, -0.0000, 4.0000)),
338                HalfSpace::new(Vec4::new(-0.0000, -0.2425, -0.9701, 2.9104)),
339                HalfSpace::new(Vec4::new(-0.0000, -1.0000, -0.0000, 4.0000)),
340                HalfSpace::new(Vec4::new(-0.0000, -0.2425, 0.9701, 2.9104)),
341                HalfSpace::new(Vec4::new(0.9701, -0.2425, -0.0000, -1.9403)),
342            ],
343        }
344    }
345
346    #[test]
347    fn intersects_sphere_big_frustum_outside() {
348        // Sphere outside frustum
349        let frustum = big_frustum();
350        let sphere = Sphere {
351            center: Vec3A::new(0.9167, 0.0000, 0.0000),
352            radius: 0.7500,
353        };
354        assert!(!frustum.intersects_sphere(&sphere, true));
355    }
356
357    #[test]
358    fn intersects_sphere_big_frustum_intersect() {
359        // Sphere intersects frustum boundary
360        let frustum = big_frustum();
361        let sphere = Sphere {
362            center: Vec3A::new(7.9288, 0.0000, 2.9728),
363            radius: 2.0000,
364        };
365        assert!(frustum.intersects_sphere(&sphere, true));
366    }
367
368    // A frustum
369    fn frustum() -> Frustum {
370        Frustum {
371            half_spaces: [
372                HalfSpace::new(Vec4::new(-0.9701, -0.2425, -0.0000, 0.7276)),
373                HalfSpace::new(Vec4::new(-0.0000, 1.0000, -0.0000, 1.0000)),
374                HalfSpace::new(Vec4::new(-0.0000, -0.2425, -0.9701, 0.7276)),
375                HalfSpace::new(Vec4::new(-0.0000, -1.0000, -0.0000, 1.0000)),
376                HalfSpace::new(Vec4::new(-0.0000, -0.2425, 0.9701, 0.7276)),
377                HalfSpace::new(Vec4::new(0.9701, -0.2425, -0.0000, 0.7276)),
378            ],
379        }
380    }
381
382    #[test]
383    fn intersects_sphere_frustum_surrounding() {
384        // Sphere surrounds frustum
385        let frustum = frustum();
386        let sphere = Sphere {
387            center: Vec3A::new(0.0000, 0.0000, 0.0000),
388            radius: 3.0000,
389        };
390        assert!(frustum.intersects_sphere(&sphere, true));
391    }
392
393    #[test]
394    fn intersects_sphere_frustum_contained() {
395        // Sphere is contained in frustum
396        let frustum = frustum();
397        let sphere = Sphere {
398            center: Vec3A::new(0.0000, 0.0000, 0.0000),
399            radius: 0.7000,
400        };
401        assert!(frustum.intersects_sphere(&sphere, true));
402    }
403
404    #[test]
405    fn intersects_sphere_frustum_intersects_plane() {
406        // Sphere intersects a plane
407        let frustum = frustum();
408        let sphere = Sphere {
409            center: Vec3A::new(0.0000, 0.0000, 0.9695),
410            radius: 0.7000,
411        };
412        assert!(frustum.intersects_sphere(&sphere, true));
413    }
414
415    #[test]
416    fn intersects_sphere_frustum_intersects_2_planes() {
417        // Sphere intersects 2 planes
418        let frustum = frustum();
419        let sphere = Sphere {
420            center: Vec3A::new(1.2037, 0.0000, 0.9695),
421            radius: 0.7000,
422        };
423        assert!(frustum.intersects_sphere(&sphere, true));
424    }
425
426    #[test]
427    fn intersects_sphere_frustum_intersects_3_planes() {
428        // Sphere intersects 3 planes
429        let frustum = frustum();
430        let sphere = Sphere {
431            center: Vec3A::new(1.2037, -1.0988, 0.9695),
432            radius: 0.7000,
433        };
434        assert!(frustum.intersects_sphere(&sphere, true));
435    }
436
437    #[test]
438    fn intersects_sphere_frustum_dodges_1_plane() {
439        // Sphere avoids intersecting the frustum by 1 plane
440        let frustum = frustum();
441        let sphere = Sphere {
442            center: Vec3A::new(-1.7020, 0.0000, 0.0000),
443            radius: 0.7000,
444        };
445        assert!(!frustum.intersects_sphere(&sphere, true));
446    }
447
448    // A long frustum.
449    fn long_frustum() -> Frustum {
450        Frustum {
451            half_spaces: [
452                HalfSpace::new(Vec4::new(-0.9998, -0.0222, -0.0000, -1.9543)),
453                HalfSpace::new(Vec4::new(-0.0000, 1.0000, -0.0000, 45.1249)),
454                HalfSpace::new(Vec4::new(-0.0000, -0.0168, -0.9999, 2.2718)),
455                HalfSpace::new(Vec4::new(-0.0000, -1.0000, -0.0000, 45.1249)),
456                HalfSpace::new(Vec4::new(-0.0000, -0.0168, 0.9999, 2.2718)),
457                HalfSpace::new(Vec4::new(0.9998, -0.0222, -0.0000, 7.9528)),
458            ],
459        }
460    }
461
462    #[test]
463    fn intersects_sphere_long_frustum_outside() {
464        // Sphere outside frustum
465        let frustum = long_frustum();
466        let sphere = Sphere {
467            center: Vec3A::new(-4.4889, 46.9021, 0.0000),
468            radius: 0.7500,
469        };
470        assert!(!frustum.intersects_sphere(&sphere, true));
471    }
472
473    #[test]
474    fn intersects_sphere_long_frustum_intersect() {
475        // Sphere intersects frustum boundary
476        let frustum = long_frustum();
477        let sphere = Sphere {
478            center: Vec3A::new(-4.9957, 0.0000, -0.7396),
479            radius: 4.4094,
480        };
481        assert!(frustum.intersects_sphere(&sphere, true));
482    }
483
484    #[test]
485    fn aabb_enclosing() {
486        assert_eq!(Aabb::enclosing(<[Vec3; 0]>::default()), None);
487        assert_eq!(
488            Aabb::enclosing(vec![Vec3::ONE]).unwrap(),
489            Aabb::from_min_max(Vec3::ONE, Vec3::ONE)
490        );
491        assert_eq!(
492            Aabb::enclosing(&[Vec3::Y, Vec3::X, Vec3::Z][..]).unwrap(),
493            Aabb::from_min_max(Vec3::ZERO, Vec3::ONE)
494        );
495        assert_eq!(
496            Aabb::enclosing([
497                Vec3::NEG_X,
498                Vec3::X * 2.0,
499                Vec3::NEG_Y * 5.0,
500                Vec3::Z,
501                Vec3::ZERO
502            ])
503            .unwrap(),
504            Aabb::from_min_max(Vec3::new(-1.0, -5.0, 0.0), Vec3::new(2.0, 0.0, 1.0))
505        );
506    }
507}
bevy_render/primitives/mod.rs

bevy_render/primitives/
mod.rs
