phys_geom/
obb3.rs

1// Copyright (C) 2020-2025 phys-geom authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15mod sat;
16mod trim;
17
18pub use trim::trim_according_overlapping;
19
20use crate::math::*;
21use crate::Aabb3;
22
23/// An oriented bounding box.
24#[derive(Debug, Clone, Copy, PartialEq)]
25pub struct OrientedBoundingBox3 {
26    /// The center of the OBB.
27    pub center: Point3,
28    /// The rotation of the OBB.
29    pub orientation: UnitQuat,
30    extents: Vec3,
31}
32
33impl OrientedBoundingBox3 {
34    /// Create a new OBB from the given center, orientation, and extents.
35    #[inline]
36    #[must_use]
37    pub fn new(center: Point3, orientation: UnitQuat, extents: Vec3) -> Self {
38        Self {
39            center,
40            orientation,
41            extents,
42        }
43    }
44
45    /// Extents of the OBB along the x, y, and z axes. Always half of size.
46    #[inline]
47    #[must_use]
48    pub fn extents(&self) -> Vec3 {
49        self.extents
50    }
51
52    /// Returns the size of the OBB.
53    #[inline]
54    #[must_use]
55    pub fn size(&self) -> Vec3 {
56        self.extents * 2.0
57    }
58
59    /// Returns the x-axis of the OBB in world space.
60    #[inline]
61    #[must_use]
62    pub fn x_axis(&self) -> UnitVec3 {
63        self.orientation * Vec3::x_axis()
64    }
65
66    /// Returns the y-axis of the OBB in world space.
67    #[inline]
68    #[must_use]
69    pub fn y_axis(&self) -> UnitVec3 {
70        self.orientation * Vec3::y_axis()
71    }
72
73    /// Returns the z-axis of the OBB in world space.
74    #[inline]
75    #[must_use]
76    pub fn z_axis(&self) -> UnitVec3 {
77        self.orientation * Vec3::z_axis()
78    }
79
80    /// Move the OBB by the given translation
81    #[inline]
82    pub fn translate(&mut self, translation: Vec3) {
83        self.center += translation;
84    }
85
86    /// Calculate the axis aligned bounding box of the OBB
87    #[must_use]
88    pub fn axis_aligned_bounding_box(&self) -> Aabb3 {
89        // Convert UnitVec3 to Vec3 once to avoid repeated into_inner() calls
90        let x_axis = self.x_axis().into_inner();
91        let y_axis = self.y_axis().into_inner();
92        let z_axis = self.z_axis().into_inner();
93
94        let mut points = [Vec3::zeros(); 8];
95        points[0] = x_axis * self.extents.x + y_axis * self.extents.y + z_axis * self.extents.z;
96        points[1] = x_axis * self.extents.x + y_axis * self.extents.y - z_axis * self.extents.z;
97        points[2] = x_axis * self.extents.x - y_axis * self.extents.y + z_axis * self.extents.z;
98        points[3] = x_axis * self.extents.x - y_axis * self.extents.y - z_axis * self.extents.z;
99        points[4] = -x_axis * self.extents.x + y_axis * self.extents.y + z_axis * self.extents.z;
100        points[5] = -x_axis * self.extents.x + y_axis * self.extents.y - z_axis * self.extents.z;
101        points[6] = -x_axis * self.extents.x - y_axis * self.extents.y + z_axis * self.extents.z;
102        points[7] = -x_axis * self.extents.x - y_axis * self.extents.y - z_axis * self.extents.z;
103
104        let mut min = points[0];
105        let mut max = points[0];
106        for p in points.iter().copied().skip(1) {
107            min = min.inf(&p);
108            max = max.sup(&p);
109        }
110
111        min += self.center.coords;
112        max += self.center.coords;
113        Aabb3::new_unchecked(Point3::from(min), Point3::from(max))
114    }
115
116    /// Calculate the 8 vertices of the OBB in world space.
117    ///
118    /// # Note
119    ///
120    /// The order of the vertices is:
121    ///
122    /// ```text
123    /// 
124    ///   3-------7
125    ///  /|      /|
126    /// 2-------6 |
127    /// | |     | |
128    /// | 1-----|-5
129    /// |/      |/
130    /// 0-------4
131    /// y   z
132    /// | /
133    ///  -- x
134    /// ```
135    #[must_use]
136    pub fn vertices(&self) -> [Point3; 8] {
137        // Convert UnitVec3 to Vec3 once to avoid repeated into_inner() calls
138        let x_axis = self.x_axis().into_inner();
139        let y_axis = self.y_axis().into_inner();
140        let z_axis = self.z_axis().into_inner();
141
142        // Pre-calculate scaled axis vectors
143        let x_extent = x_axis * self.extents.x;
144        let y_extent = y_axis * self.extents.y;
145        let z_extent = z_axis * self.extents.z;
146
147        [
148            self.center + (-x_extent - y_extent - z_extent), // 0
149            self.center + (-x_extent - y_extent + z_extent), // 1
150            self.center + (-x_extent + y_extent - z_extent), // 2
151            self.center + (-x_extent + y_extent + z_extent), // 3
152            self.center + (x_extent - y_extent - z_extent),  // 4
153            self.center + (x_extent - y_extent + z_extent),  // 5
154            self.center + (x_extent + y_extent - z_extent),  // 6
155            self.center + (x_extent + y_extent + z_extent),  // 7
156        ]
157    }
158
159    /// Overlap test for two OBB by using the separating axis theorem.
160    pub fn overlaps(&self, other: &Self) -> bool {
161        let (a, b) = (self, other);
162
163        // 3 separating axes of a
164        let axes_a = [a.x_axis(), a.y_axis(), a.z_axis()];
165
166        let vertices_b = b.vertices();
167
168        for (index, axis) in axes_a.iter().enumerate() {
169            let o = a.center.coords.dot(axis);
170            let overlap = sat::is_vertices_overlap_inerval_on_axis(
171                *axis,
172                vertices_b.iter().map(|p| p.coords),
173                o - a.extents()[index],
174                o + a.extents()[index],
175            );
176            if !overlap {
177                return false;
178            }
179        }
180
181        // 3 separating axes of b
182        let axes_b = [b.x_axis(), b.y_axis(), b.z_axis()];
183
184        let vertices_a = a.vertices();
185
186        for (index, axis) in axes_b.iter().enumerate() {
187            let o = b.center.coords.dot(axis);
188            let overlap = sat::is_vertices_overlap_inerval_on_axis(
189                *axis,
190                vertices_a.iter().map(|p| p.coords),
191                o - b.extents()[index],
192                o + b.extents()[index],
193            );
194            if !overlap {
195                return false;
196            }
197        }
198
199        //9 separating axes of a x b
200        let axes_cross = [
201            axes_a[0].cross(&axes_b[0]),
202            axes_a[0].cross(&axes_b[1]),
203            axes_a[0].cross(&axes_b[2]),
204            axes_a[1].cross(&axes_b[0]),
205            axes_a[1].cross(&axes_b[1]),
206            axes_a[1].cross(&axes_b[2]),
207            axes_a[2].cross(&axes_b[0]),
208            axes_a[2].cross(&axes_b[1]),
209            axes_a[2].cross(&axes_b[2]),
210        ];
211        let axes_cross = axes_cross.map(|v| UnitVec3::try_new(v, 1e-5));
212
213        for axis in axes_cross.iter().copied().flatten() {
214            let (min_a, max_a) =
215                sat::compute_vertices_interval_on_axis(axis, vertices_a.iter().map(|v| v.coords));
216            let (min_b, max_b) =
217                sat::compute_vertices_interval_on_axis(axis, vertices_b.iter().map(|v| v.coords));
218
219            let overlap = min_a <= max_b && min_b <= max_a;
220            if !overlap {
221                return false;
222            }
223        }
224
225        true
226    }
227}
228
229#[cfg(test)]
230mod tests {
231    use approx::assert_relative_eq;
232    use wasm_bindgen_test::*;
233
234    use super::*;
235
236    wasm_bindgen_test_configure!(run_in_browser);
237
238    #[test]
239    #[wasm_bindgen_test]
240    fn test_obb3() {
241        let rotation = UnitQuat::from_axis_angle(&Vec3::y_axis(), (30.0 as Real).to_radians());
242        let extents = Vec3::new(2.0, 3.0, 4.0);
243        let obb = OrientedBoundingBox3::new(Point3::new(1.0, 2.0, 3.0), rotation, extents);
244
245        assert_relative_eq!(obb.extents(), extents);
246        assert_relative_eq!(obb.size(), extents * 2.0);
247
248        assert_relative_eq!(obb.x_axis(), rotation * Vec3::x_axis());
249        assert_relative_eq!(obb.y_axis(), rotation * Vec3::y_axis());
250        assert_relative_eq!(obb.z_axis(), rotation * Vec3::z_axis());
251
252        let aabb = obb.axis_aligned_bounding_box();
253        assert_relative_eq!(
254            aabb.min(),
255            Point3::new(-2.732051, -1.000000, -1.464102),
256            epsilon = 1e-5
257        );
258        assert_relative_eq!(
259            aabb.max(),
260            Point3::new(4.732051, 5.000000, 7.464102),
261            epsilon = 1e-5
262        );
263
264        let vertices = obb.vertices();
265
266        let expect_vertices = [
267            Point3::new(-2.7321, -1.0000, 0.5359),
268            Point3::new(1.2680, -1.0000, 7.4641),
269            Point3::new(-2.7321, 5.0000, 0.5359),
270            Point3::new(1.2680, 5.0000, 7.4641),
271            Point3::new(0.7321, -1.0000, -1.4641),
272            Point3::new(4.7321, -1.0000, 5.4641),
273            Point3::new(0.7321, 5.0000, -1.4641),
274            Point3::new(4.7321, 5.0000, 5.4641),
275        ];
276
277        for (actual, expect) in vertices.iter().zip(expect_vertices.iter()) {
278            assert_relative_eq!(actual, expect, epsilon = 1e-4);
279        }
280    }
281
282    #[test]
283    #[wasm_bindgen_test]
284    fn test_obb3_overlaps() {
285        let obb_1 = OrientedBoundingBox3::new(
286            point3(1.0, 2.0, 3.0),
287            UnitQuat::from_axis_angle(&Vec3::y_axis(), 30f32.to_radians()),
288            vec3(2.0, 3.0, 4.0),
289        );
290        let mut obb_2 = OrientedBoundingBox3::new(
291            point3(-1.46, 0.0, -1.11),
292            UnitQuat::from_axis_angle(
293                &vec3(0.679, 0.679, -0.281).normalize_to_unit(),
294                62.79941f32.to_radians(),
295            ),
296            Vec3::repeat(0.5),
297        );
298
299        assert!(obb_1.overlaps(&obb_2));
300        obb_2.translate(-obb_2.z_axis().into_inner() * 0.1);
301        assert!(!obb_1.overlaps(&obb_2));
302
303        let mut obb_3 = OrientedBoundingBox3::new(
304            point3(1.07, -1.42, -1.567),
305            UnitQuat::from_axis_angle(
306                &vec3(0.580, 0.760, -0.293).normalize_to_unit(),
307                126.9181f32.to_radians(),
308            ),
309            Vec3::repeat(0.5),
310        );
311
312        assert!(!obb_1.overlaps(&obb_3));
313
314        obb_3.translate(-obb_3.z_axis().into_inner() * 0.1);
315        assert!(obb_1.overlaps(&obb_3));
316
317        let mut obb_4 = OrientedBoundingBox3::new(
318            point3(0.96, -0.085, -2.128),
319            UnitQuat::from_axis_angle(
320                &vec3(0.580, 0.760, -0.293).normalize_to_unit(),
321                126.9181f32.to_radians(),
322            ),
323            Vec3::repeat(0.5),
324        );
325
326        assert!(!obb_1.overlaps(&obb_4));
327        obb_4.translate(-obb_4.x_axis().into_inner() * 0.1);
328        assert!(obb_1.overlaps(&obb_4));
329    }
330}
phys_geom/obb3.rs

phys_geom/
obb3.rs
