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}