bevy_mod_bounding/
obb.rs

1use crate::aabb::Aabb;
2use crate::BoundingVolume;
3use bevy::{
4    prelude::*,
5    render::{mesh::VertexAttributeValues, pipeline::PrimitiveTopology},
6};
7use core::panic;
8use std::{convert::TryInto, f32::consts::PI};
9
10/// Defines a bounding box, oriented to minimize the bounded volume. This bounding box is expensive
11/// to compute, but cheap to update.
12///
13/// The volume of an OBB is <= to the AABB of the same mesh. It is similar to an AABB, but the
14/// orientation is determined not by the world axes but with respect to the mesh itself, so the
15/// bounding box definition only changes if the underlying mesh changes. The entire bounding volume
16/// can simply be transformed with the current [GlobalTransform] of the bounded mesh, lazily.
17///
18/// This structure stores the AABB of the mesh in mesh space, with the mesh oriented to minimize
19/// the volume of the bounding box. The properties are stored in mesh space to minimize rounding
20/// error, and make it easy to defer recomputing the bounding volume until the mesh itself is
21/// changed.
22#[derive(Debug, Clone, Default)]
23pub struct Obb {
24    aabb: Aabb,
25    /// The orientation of the mesh that minimizes the AABB.
26    ///
27    /// ## Note
28    /// This is *not* the orientation of the bounding box! You probably want the conjugate of
29    /// this quaternion if that's what you need.
30    mesh_orientation: Quat,
31}
32
33impl Obb {
34    /// Returns an array of the 8 vertices of the bounding box in world space.
35    pub fn vertices(&self, transform: GlobalTransform) -> [Vec3; 8] {
36        let orient = Mat4::from_quat(self.orientation());
37        let transform = transform.compute_matrix() * orient;
38        let transform = GlobalTransform::from_matrix(transform);
39        self.aabb
40            .vertices_mesh_space()
41            .iter()
42            .map(|&vertex| transform * vertex)
43            .collect::<Vec<Vec3>>()
44            .as_slice()
45            .try_into()
46            .unwrap()
47    }
48    pub fn vertices_mesh_space(&self) -> [Vec3; 8] {
49        let orient = Mat4::from_quat(self.orientation());
50        let transform = GlobalTransform::from_matrix(orient);
51        self.aabb.vertices(transform)
52    }
53    pub fn from_aabb_orientation(aabb: Aabb, mesh_orientation: Quat) -> Obb {
54        Obb {
55            aabb,
56            mesh_orientation,
57        }
58    }
59    /// Returns the [AxisAlignedBB] of this [OrientedBB] in ***mesh space***.
60    pub fn mesh_aabb(&self) -> &Aabb {
61        &self.aabb
62    }
63    /// Returns the orientation of the [OrientedBB] in ***mesh space***.
64    ///
65    /// ## Note
66    /// This orientation tells you how to rotate the [AxisAlignedBB] that defines the [OrientedBB]
67    /// so that the bounding box matches its [Mesh]s orientation.
68    pub fn orientation(&self) -> Quat {
69        self.mesh_orientation.conjugate()
70    }
71    /// Returns an [AxisAlignedBB] that contains this [OrientedBB]. In other words, this returns
72    /// the AABB of this OBB.
73    ///
74    /// ## Y tho
75    /// This is much faster than calculating the AABB of a high-poly mesh every time it moves.
76    /// Because the [OrientedBB] only needs to recompute when the mesh itself changes, by taking
77    /// the AABB of the OBB, and not the mesh, we only need to iterate through all mesh vertices
78    /// when the mesh changes, but we still get a bounding box that is aligned to the world axes.
79    /// This comes with a tradeoff - because we are finding the AABB of the OBB, the bounding box
80    /// will be more conservative, and will be larger than the AABB of the mesh itself.
81    pub fn outer_aabb(&self) -> Aabb {
82        let axis_aligned_vertices = self.aabb.vertices_mesh_space();
83        let oriented_vertices: Vec<Vec3> = axis_aligned_vertices
84            .iter()
85            .map(|vertex| self.orientation().mul_vec3(*vertex))
86            .collect();
87        Aabb::compute_aabb(&oriented_vertices)
88    }
89    /// Given a list of mesh vertices, and the orientation of this mesh, constructs an oriented
90    /// bounding box.
91    fn compute_obb(vertices: &[Vec3], orientation: Quat) -> Obb {
92        let mut maximums = Vec3::new(f32::MIN, f32::MIN, f32::MIN);
93        let mut minimums = Vec3::new(f32::MAX, f32::MAX, f32::MAX);
94        let transform = Mat4::from_quat(orientation);
95        for vertex in vertices.iter() {
96            maximums = maximums.max(transform.transform_point3(*vertex));
97            minimums = minimums.min(transform.transform_point3(*vertex));
98        }
99        Obb {
100            aabb: Aabb::from_extents(minimums, maximums),
101            mesh_orientation: orientation,
102        }
103    }
104}
105
106impl BoundingVolume for Obb {
107    fn new(mesh: &Mesh, _transform: &GlobalTransform) -> Self {
108        // Grab a vector of vertex coordinates we can use to iterate through
109        if mesh.primitive_topology() != PrimitiveTopology::TriangleList {
110            panic!("Non-TriangleList mesh supplied for oriented bounding box generation")
111        }
112        let vertices: Vec<Vec3> = match mesh.attribute(Mesh::ATTRIBUTE_POSITION) {
113            None => panic!("Mesh does not contain vertex positions"),
114            Some(vertex_values) => match &vertex_values {
115                VertexAttributeValues::Float3(positions) => positions
116                    .iter()
117                    .map(|coordinates| Vec3::from(*coordinates))
118                    .collect(),
119                _ => panic!("Unexpected vertex types in ATTRIBUTE_POSITION"),
120            },
121        };
122
123        let mut orientation = Quat::IDENTITY;
124        let mut volume = f32::MAX;
125        // Rotate about y-axis  (turntable) until the smallest volume box is found
126        let orientation_temp = orientation;
127        for angle in (0..45).step_by(15) {
128            let new_orientation =
129                orientation_temp * Quat::from_rotation_y(angle as f32 * 2.0 * PI / 360.0);
130            let temp_obb = Obb::compute_obb(&vertices, new_orientation);
131            let diff = temp_obb.mesh_aabb().maximums() - temp_obb.mesh_aabb().minimums();
132            let new_volume = diff.x * diff.y * diff.z;
133            if new_volume < volume {
134                volume = new_volume;
135                orientation = new_orientation;
136            }
137        }
138        let mut obb = Obb::compute_obb(&vertices, orientation);
139        let orientation_temp = orientation;
140        for angle in (0..90).step_by(15) {
141            let new_orientation =
142                orientation_temp * Quat::from_rotation_x(angle as f32 * 2.0 * PI / 360.0);
143            let temp_obb = Obb::compute_obb(&vertices, new_orientation);
144            let diff = temp_obb.mesh_aabb().maximums() - temp_obb.mesh_aabb().minimums();
145            let new_volume = diff.x * diff.y * diff.z;
146            if new_volume < volume {
147                volume = new_volume;
148                obb = temp_obb;
149            }
150        }
151        obb
152    }
153
154    fn new_debug_mesh(&self, _transform: &GlobalTransform) -> Mesh {
155        Mesh::from(self)
156    }
157
158    fn update_on_transform_change(
159        &self,
160        _mesh: &Mesh,
161        _transform: &GlobalTransform,
162    ) -> Option<Self> {
163        // No-op
164        None
165    }
166
167    fn outside_plane(
168        &self,
169        bound_vol_position: &GlobalTransform,
170        point: Vec3,
171        normal: Vec3,
172    ) -> bool {
173        for vertex in self.vertices(*bound_vol_position).iter() {
174            if normal.dot(*vertex) + -normal.dot(point) < 0.0 {
175                // if any point is on the inside of the plane, we can end early.
176                return false;
177            }
178        }
179        true
180    }
181}
bevy_mod_bounding/obb.rs

bevy_mod_bounding/
obb.rs
