parry3d/bounding_volume/
bounding_sphere.rs

1//! Bounding sphere.
2
3use crate::bounding_volume::BoundingVolume;
4use crate::math::{Isometry, Point, Real, Vector};
5use na;
6use num::Zero;
7
8#[cfg(feature = "rkyv")]
9use rkyv::{bytecheck, CheckBytes};
10
11/// A Bounding Sphere.
12///
13/// A bounding sphere is a spherical bounding volume defined by a center point and a radius.
14/// Unlike an AABB, a bounding sphere is rotation-invariant, meaning it doesn't need to be
15/// recomputed when an object rotates.
16///
17/// # Structure
18///
19/// - **center**: The center point of the sphere
20/// - **radius**: The distance from the center to any point on the sphere's surface
21///
22/// # Properties
23///
24/// - **Rotation-invariant**: Remains valid under rotation transformations
25/// - **Simple**: Only 4 values (3D: x, y, z, radius; 2D: x, y, radius)
26/// - **Conservative**: Often larger than the actual shape, especially for elongated objects
27/// - **Fast intersection tests**: Only requires distance comparison
28///
29/// # Use Cases
30///
31/// Bounding spheres are useful for:
32///
33/// - **Rotating objects**: No recomputation needed when objects rotate
34/// - **Broad-phase culling**: Quick rejection of distant object pairs
35/// - **View frustum culling**: Simple sphere-frustum tests
36/// - **Level of detail (LOD)**: Distance-based detail switching
37/// - **Physics simulations**: Fast bounds checking for moving/rotating bodies
38///
39/// # Performance
40///
41/// - **Intersection test**: O(1) - Single distance comparison
42/// - **Rotation**: O(1) - Only center needs transformation
43/// - **Contains test**: O(1) - Distance plus radius comparison
44///
45/// # Comparison to AABB
46///
47/// **When to use BoundingSphere:**
48/// - Objects rotate frequently
49/// - Objects are roughly spherical or evenly distributed
50/// - Memory is tight (fewer values to store)
51/// - Rotation-invariant bounds are required
52///
53/// **When to use AABB:**
54/// - Objects are axis-aligned or rarely rotate
55/// - Objects are elongated or box-like
56/// - Tighter bounds are critical
57/// - Building spatial hierarchies (BVH, octree)
58///
59/// # Example
60///
61/// ```rust
62/// # #[cfg(all(feature = "dim3", feature = "f32"))] {
63/// use parry3d::bounding_volume::BoundingSphere;
64/// use nalgebra::Point3;
65///
66/// // Create a bounding sphere with center at origin and radius 2.0
67/// let sphere = BoundingSphere::new(Point3::origin(), 2.0);
68///
69/// // Check basic properties
70/// assert_eq!(*sphere.center(), Point3::origin());
71/// assert_eq!(sphere.radius(), 2.0);
72///
73/// // Test if a point is within the sphere
74/// let point = Point3::new(1.0, 1.0, 0.0);
75/// let distance = (point - sphere.center()).norm();
76/// assert!(distance <= sphere.radius());
77/// # }
78/// ```
79///
80/// ```rust
81/// # #[cfg(all(feature = "dim3", feature = "f32"))] {
82/// use parry3d::bounding_volume::BoundingSphere;
83/// use nalgebra::{Point3, Vector3, Translation3};
84///
85/// // Create a sphere and translate it
86/// let sphere = BoundingSphere::new(Point3::new(1.0, 2.0, 3.0), 1.5);
87/// let translation = Vector3::new(5.0, 0.0, 0.0);
88/// let moved = sphere.translated(&translation);
89///
90/// assert_eq!(*moved.center(), Point3::new(6.0, 2.0, 3.0));
91/// assert_eq!(moved.radius(), 1.5); // Radius unchanged by translation
92/// # }
93/// ```
94///
95/// ```rust
96/// # #[cfg(all(feature = "dim3", feature = "f32"))] {
97/// use parry3d::bounding_volume::{BoundingSphere, BoundingVolume};
98/// use nalgebra::Point3;
99///
100/// // Merge two bounding spheres
101/// let sphere1 = BoundingSphere::new(Point3::origin(), 1.0);
102/// let sphere2 = BoundingSphere::new(Point3::new(4.0, 0.0, 0.0), 1.0);
103///
104/// let merged = sphere1.merged(&sphere2);
105/// // The merged sphere contains both original spheres
106/// assert!(merged.contains(&sphere1));
107/// assert!(merged.contains(&sphere2));
108/// # }
109/// ```
110#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
111#[cfg_attr(feature = "bytemuck", derive(bytemuck::Pod, bytemuck::Zeroable))]
112#[cfg_attr(
113    feature = "rkyv",
114    derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize, CheckBytes),
115    archive(as = "Self")
116)]
117#[derive(Debug, PartialEq, Copy, Clone)]
118#[repr(C)]
119pub struct BoundingSphere {
120    /// The center point of the bounding sphere.
121    pub center: Point<Real>,
122
123    /// The radius of the bounding sphere.
124    ///
125    /// This is the distance from the center to any point on the sphere's surface.
126    /// All points within the bounded object should satisfy: distance(point, center) <= radius
127    pub radius: Real,
128}
129
130impl BoundingSphere {
131    /// Creates a new bounding sphere from a center point and radius.
132    ///
133    /// # Arguments
134    ///
135    /// * `center` - The center point of the sphere
136    /// * `radius` - The radius of the sphere (must be non-negative)
137    ///
138    /// # Example
139    ///
140    /// ```
141    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
142    /// use parry3d::bounding_volume::BoundingSphere;
143    /// use nalgebra::Point3;
144    ///
145    /// // Create a sphere centered at (1, 2, 3) with radius 5.0
146    /// let sphere = BoundingSphere::new(
147    ///     Point3::new(1.0, 2.0, 3.0),
148    ///     5.0
149    /// );
150    ///
151    /// assert_eq!(*sphere.center(), Point3::new(1.0, 2.0, 3.0));
152    /// assert_eq!(sphere.radius(), 5.0);
153    /// # }
154    /// ```
155    pub fn new(center: Point<Real>, radius: Real) -> BoundingSphere {
156        BoundingSphere { center, radius }
157    }
158
159    /// Returns a reference to the center point of this bounding sphere.
160    ///
161    /// # Example
162    ///
163    /// ```
164    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
165    /// use parry3d::bounding_volume::BoundingSphere;
166    /// use nalgebra::Point3;
167    ///
168    /// let sphere = BoundingSphere::new(Point3::new(1.0, 2.0, 3.0), 5.0);
169    /// let center = sphere.center();
170    ///
171    /// assert_eq!(*center, Point3::new(1.0, 2.0, 3.0));
172    /// # }
173    /// ```
174    #[inline]
175    pub fn center(&self) -> &Point<Real> {
176        &self.center
177    }
178
179    /// Returns the radius of this bounding sphere.
180    ///
181    /// The radius is the distance from the center to any point on the sphere's surface.
182    ///
183    /// # Example
184    ///
185    /// ```
186    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
187    /// use parry3d::bounding_volume::BoundingSphere;
188    /// use nalgebra::Point3;
189    ///
190    /// let sphere = BoundingSphere::new(Point3::origin(), 10.0);
191    ///
192    /// assert_eq!(sphere.radius(), 10.0);
193    /// # }
194    /// ```
195    #[inline]
196    pub fn radius(&self) -> Real {
197        self.radius
198    }
199
200    /// Transforms this bounding sphere by the given isometry.
201    ///
202    /// For a bounding sphere, only the center point is affected by the transformation.
203    /// The radius remains unchanged because spheres are rotation-invariant and isometries
204    /// preserve distances.
205    ///
206    /// # Arguments
207    ///
208    /// * `m` - The isometry (rigid transformation) to apply
209    ///
210    /// # Example
211    ///
212    /// ```
213    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
214    /// use parry3d::bounding_volume::BoundingSphere;
215    /// use nalgebra::{Point3, Vector3, Isometry3, UnitQuaternion};
216    ///
217    /// let sphere = BoundingSphere::new(Point3::new(1.0, 0.0, 0.0), 2.0);
218    ///
219    /// // Create a transformation: translate by (5, 0, 0) and rotate 90 degrees around Z
220    /// let translation = Vector3::new(5.0, 0.0, 0.0);
221    /// let rotation = UnitQuaternion::from_euler_angles(0.0, 0.0, std::f32::consts::FRAC_PI_2);
222    /// let transform = Isometry3::from_parts(translation.into(), rotation);
223    ///
224    /// let transformed = sphere.transform_by(&transform);
225    ///
226    /// // The center is transformed
227    /// assert!((*transformed.center() - Point3::new(5.0, 1.0, 0.0)).norm() < 1e-5);
228    /// // The radius is unchanged
229    /// assert_eq!(transformed.radius(), 2.0);
230    /// # }
231    /// ```
232    #[inline]
233    pub fn transform_by(&self, m: &Isometry<Real>) -> BoundingSphere {
234        BoundingSphere::new(m * self.center, self.radius)
235    }
236
237    /// Translates this bounding sphere by the given vector.
238    ///
239    /// This is equivalent to `transform_by` with a pure translation, but more efficient
240    /// as it doesn't involve rotation.
241    ///
242    /// # Arguments
243    ///
244    /// * `translation` - The translation vector to add to the center
245    ///
246    /// # Example
247    ///
248    /// ```
249    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
250    /// use parry3d::bounding_volume::BoundingSphere;
251    /// use nalgebra::{Point3, Vector3};
252    ///
253    /// let sphere = BoundingSphere::new(Point3::origin(), 1.0);
254    /// let translation = Vector3::new(10.0, 5.0, -3.0);
255    ///
256    /// let moved = sphere.translated(&translation);
257    ///
258    /// assert_eq!(*moved.center(), Point3::new(10.0, 5.0, -3.0));
259    /// assert_eq!(moved.radius(), 1.0); // Radius unchanged
260    /// # }
261    /// ```
262    #[inline]
263    pub fn translated(&self, translation: &Vector<Real>) -> BoundingSphere {
264        BoundingSphere::new(self.center + translation, self.radius)
265    }
266}
267
268impl BoundingVolume for BoundingSphere {
269    /// Returns the center point of this bounding sphere.
270    ///
271    /// # Example
272    ///
273    /// ```
274    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
275    /// use parry3d::bounding_volume::{BoundingSphere, BoundingVolume};
276    /// use nalgebra::Point3;
277    ///
278    /// let sphere = BoundingSphere::new(Point3::new(1.0, 2.0, 3.0), 5.0);
279    ///
280    /// // BoundingVolume::center() returns a Point by value
281    /// assert_eq!(BoundingVolume::center(&sphere), Point3::new(1.0, 2.0, 3.0));
282    /// # }
283    /// ```
284    #[inline]
285    fn center(&self) -> Point<Real> {
286        *self.center()
287    }
288
289    /// Tests if this bounding sphere intersects another bounding sphere.
290    ///
291    /// Two spheres intersect if the distance between their centers is less than or equal
292    /// to the sum of their radii.
293    ///
294    /// # Arguments
295    ///
296    /// * `other` - The other bounding sphere to test against
297    ///
298    /// # Example
299    ///
300    /// ```
301    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
302    /// use parry3d::bounding_volume::{BoundingSphere, BoundingVolume};
303    /// use nalgebra::Point3;
304    ///
305    /// let sphere1 = BoundingSphere::new(Point3::origin(), 2.0);
306    /// let sphere2 = BoundingSphere::new(Point3::new(3.0, 0.0, 0.0), 2.0);
307    /// let sphere3 = BoundingSphere::new(Point3::new(10.0, 0.0, 0.0), 1.0);
308    ///
309    /// assert!(sphere1.intersects(&sphere2)); // Distance 3.0 <= sum of radii 4.0
310    /// assert!(!sphere1.intersects(&sphere3)); // Distance 10.0 > sum of radii 3.0
311    /// # }
312    /// ```
313    #[inline]
314    fn intersects(&self, other: &BoundingSphere) -> bool {
315        // TODO: refactor that with the code from narrow_phase::ball_ball::collide(...) ?
316        let delta_pos = other.center - self.center;
317        let distance_squared = delta_pos.norm_squared();
318        let sum_radius = self.radius + other.radius;
319
320        distance_squared <= sum_radius * sum_radius
321    }
322
323    /// Tests if this bounding sphere fully contains another bounding sphere.
324    ///
325    /// A sphere fully contains another sphere if the distance between their centers
326    /// plus the other's radius is less than or equal to this sphere's radius.
327    ///
328    /// # Arguments
329    ///
330    /// * `other` - The other bounding sphere to test
331    ///
332    /// # Example
333    ///
334    /// ```
335    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
336    /// use parry3d::bounding_volume::{BoundingSphere, BoundingVolume};
337    /// use nalgebra::Point3;
338    ///
339    /// let large = BoundingSphere::new(Point3::origin(), 10.0);
340    /// let small = BoundingSphere::new(Point3::new(2.0, 0.0, 0.0), 1.0);
341    /// let outside = BoundingSphere::new(Point3::new(15.0, 0.0, 0.0), 2.0);
342    ///
343    /// assert!(large.contains(&small)); // Small sphere is inside large sphere
344    /// assert!(!large.contains(&outside)); // Outside sphere extends beyond large sphere
345    /// assert!(!small.contains(&large)); // Small cannot contain large
346    /// # }
347    /// ```
348    #[inline]
349    fn contains(&self, other: &BoundingSphere) -> bool {
350        let delta_pos = other.center - self.center;
351        let distance = delta_pos.norm();
352
353        distance + other.radius <= self.radius
354    }
355
356    /// Merges this bounding sphere with another in-place.
357    ///
358    /// After this operation, this sphere will be the smallest sphere that contains
359    /// both the original sphere and the other sphere.
360    ///
361    /// # Arguments
362    ///
363    /// * `other` - The other bounding sphere to merge with
364    ///
365    /// # Example
366    ///
367    /// ```
368    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
369    /// use parry3d::bounding_volume::{BoundingSphere, BoundingVolume};
370    /// use nalgebra::Point3;
371    ///
372    /// let mut sphere1 = BoundingSphere::new(Point3::origin(), 1.0);
373    /// let sphere2 = BoundingSphere::new(Point3::new(4.0, 0.0, 0.0), 1.0);
374    ///
375    /// sphere1.merge(&sphere2);
376    ///
377    /// // The merged sphere now contains both original spheres
378    /// assert!(sphere1.contains(&BoundingSphere::new(Point3::origin(), 1.0)));
379    /// assert!(sphere1.contains(&sphere2));
380    /// # }
381    /// ```
382    #[inline]
383    fn merge(&mut self, other: &BoundingSphere) {
384        let mut dir = *other.center() - *self.center();
385        let norm = dir.normalize_mut();
386
387        if norm.is_zero() {
388            if other.radius > self.radius {
389                self.radius = other.radius
390            }
391        } else {
392            let s_center_dir = self.center.coords.dot(&dir);
393            let o_center_dir = other.center.coords.dot(&dir);
394
395            let right = if s_center_dir + self.radius > o_center_dir + other.radius {
396                self.center + dir * self.radius
397            } else {
398                other.center + dir * other.radius
399            };
400
401            let left = if -s_center_dir + self.radius > -o_center_dir + other.radius {
402                self.center - dir * self.radius
403            } else {
404                other.center - dir * other.radius
405            };
406
407            self.center = na::center(&left, &right);
408            self.radius = na::distance(&right, &self.center);
409        }
410    }
411
412    /// Returns a new bounding sphere that is the merge of this sphere and another.
413    ///
414    /// The returned sphere is the smallest sphere that contains both input spheres.
415    /// This is the non-mutating version of `merge`.
416    ///
417    /// # Arguments
418    ///
419    /// * `other` - The other bounding sphere to merge with
420    ///
421    /// # Example
422    ///
423    /// ```
424    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
425    /// use parry3d::bounding_volume::{BoundingSphere, BoundingVolume};
426    /// use nalgebra::Point3;
427    ///
428    /// let sphere1 = BoundingSphere::new(Point3::origin(), 1.0);
429    /// let sphere2 = BoundingSphere::new(Point3::new(4.0, 0.0, 0.0), 1.0);
430    ///
431    /// let merged = sphere1.merged(&sphere2);
432    ///
433    /// // Original spheres are unchanged
434    /// assert_eq!(sphere1.radius(), 1.0);
435    /// // Merged sphere contains both
436    /// assert!(merged.contains(&sphere1));
437    /// assert!(merged.contains(&sphere2));
438    /// # }
439    /// ```
440    #[inline]
441    fn merged(&self, other: &BoundingSphere) -> BoundingSphere {
442        let mut res = *self;
443
444        res.merge(other);
445
446        res
447    }
448
449    /// Increases the radius of this bounding sphere by the given amount in-place.
450    ///
451    /// This creates a larger sphere with the same center. Useful for adding safety margins
452    /// or creating conservative bounds.
453    ///
454    /// # Arguments
455    ///
456    /// * `amount` - The amount to increase the radius (must be non-negative)
457    ///
458    /// # Panics
459    ///
460    /// Panics if `amount` is negative.
461    ///
462    /// # Example
463    ///
464    /// ```
465    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
466    /// use parry3d::bounding_volume::{BoundingSphere, BoundingVolume};
467    /// use nalgebra::Point3;
468    ///
469    /// let mut sphere = BoundingSphere::new(Point3::origin(), 5.0);
470    /// sphere.loosen(2.0);
471    ///
472    /// assert_eq!(sphere.radius(), 7.0);
473    /// assert_eq!(*sphere.center(), Point3::origin()); // Center unchanged
474    /// # }
475    /// ```
476    #[inline]
477    fn loosen(&mut self, amount: Real) {
478        assert!(amount >= 0.0, "The loosening margin must be positive.");
479        self.radius += amount
480    }
481
482    /// Returns a new bounding sphere with increased radius.
483    ///
484    /// This is the non-mutating version of `loosen`. The returned sphere has the same
485    /// center but a larger radius.
486    ///
487    /// # Arguments
488    ///
489    /// * `amount` - The amount to increase the radius (must be non-negative)
490    ///
491    /// # Panics
492    ///
493    /// Panics if `amount` is negative.
494    ///
495    /// # Example
496    ///
497    /// ```
498    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
499    /// use parry3d::bounding_volume::{BoundingSphere, BoundingVolume};
500    /// use nalgebra::Point3;
501    ///
502    /// let sphere = BoundingSphere::new(Point3::origin(), 5.0);
503    /// let larger = sphere.loosened(3.0);
504    ///
505    /// assert_eq!(sphere.radius(), 5.0); // Original unchanged
506    /// assert_eq!(larger.radius(), 8.0);
507    /// assert_eq!(*larger.center(), Point3::origin());
508    /// # }
509    /// ```
510    #[inline]
511    fn loosened(&self, amount: Real) -> BoundingSphere {
512        assert!(amount >= 0.0, "The loosening margin must be positive.");
513        BoundingSphere::new(self.center, self.radius + amount)
514    }
515
516    /// Decreases the radius of this bounding sphere by the given amount in-place.
517    ///
518    /// This creates a smaller sphere with the same center. Useful for conservative
519    /// collision detection or creating inner bounds.
520    ///
521    /// # Arguments
522    ///
523    /// * `amount` - The amount to decrease the radius (must be non-negative and ≤ radius)
524    ///
525    /// # Panics
526    ///
527    /// Panics if `amount` is negative or greater than the current radius.
528    ///
529    /// # Example
530    ///
531    /// ```
532    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
533    /// use parry3d::bounding_volume::{BoundingSphere, BoundingVolume};
534    /// use nalgebra::Point3;
535    ///
536    /// let mut sphere = BoundingSphere::new(Point3::origin(), 10.0);
537    /// sphere.tighten(3.0);
538    ///
539    /// assert_eq!(sphere.radius(), 7.0);
540    /// assert_eq!(*sphere.center(), Point3::origin()); // Center unchanged
541    /// # }
542    /// ```
543    #[inline]
544    fn tighten(&mut self, amount: Real) {
545        assert!(amount >= 0.0, "The tightening margin must be positive.");
546        assert!(amount <= self.radius, "The tightening margin is to large.");
547        self.radius -= amount
548    }
549
550    /// Returns a new bounding sphere with decreased radius.
551    ///
552    /// This is the non-mutating version of `tighten`. The returned sphere has the same
553    /// center but a smaller radius.
554    ///
555    /// # Arguments
556    ///
557    /// * `amount` - The amount to decrease the radius (must be non-negative and ≤ radius)
558    ///
559    /// # Panics
560    ///
561    /// Panics if `amount` is negative or greater than the current radius.
562    ///
563    /// # Example
564    ///
565    /// ```
566    /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
567    /// use parry3d::bounding_volume::{BoundingSphere, BoundingVolume};
568    /// use nalgebra::Point3;
569    ///
570    /// let sphere = BoundingSphere::new(Point3::origin(), 10.0);
571    /// let smaller = sphere.tightened(4.0);
572    ///
573    /// assert_eq!(sphere.radius(), 10.0); // Original unchanged
574    /// assert_eq!(smaller.radius(), 6.0);
575    /// assert_eq!(*smaller.center(), Point3::origin());
576    /// # }
577    /// ```
578    #[inline]
579    fn tightened(&self, amount: Real) -> BoundingSphere {
580        assert!(amount >= 0.0, "The tightening margin must be positive.");
581        assert!(amount <= self.radius, "The tightening margin is to large.");
582        BoundingSphere::new(self.center, self.radius - amount)
583    }
584}