parry2d/shape/compound.rs
1//!
2//! Shape composed from the union of primitives.
3//!
4
5use crate::bounding_volume::{Aabb, BoundingSphere, BoundingVolume};
6use crate::math::{Isometry, Real};
7use crate::partitioning::{Bvh, BvhBuildStrategy};
8use crate::query::details::NormalConstraints;
9use crate::shape::{CompositeShape, Shape, SharedShape, TypedCompositeShape};
10#[cfg(feature = "dim2")]
11use crate::shape::{ConvexPolygon, TriMesh, Triangle};
12#[cfg(feature = "dim2")]
13use crate::transformation::hertel_mehlhorn;
14use alloc::vec::Vec;
15
16/// A compound shape with an aabb bounding volume.
17///
18/// A compound shape is a shape composed of the union of several simpler shape. This is
19/// the main way of creating a concave shape from convex parts. Each parts can have its own
20/// delta transformation to shift or rotate it with regard to the other shapes.
21#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
22#[derive(Clone, Debug)]
23pub struct Compound {
24 shapes: Vec<(Isometry<Real>, SharedShape)>,
25 bvh: Bvh,
26 aabbs: Vec<Aabb>,
27 aabb: Aabb,
28}
29
30impl Compound {
31 /// Builds a new compound shape from a collection of sub-shapes.
32 ///
33 /// A compound shape combines multiple primitive shapes into a single composite shape,
34 /// each with its own relative position and orientation. This is the primary way to
35 /// create concave shapes from convex primitives. The compound internally builds a
36 /// Bounding Volume Hierarchy (BVH) for efficient collision detection.
37 ///
38 /// # Arguments
39 ///
40 /// * `shapes` - A vector of (position, shape) pairs. Each pair defines:
41 /// - An [`Isometry`] representing the sub-shape's position and orientation relative to the compound's origin
42 /// - A [`SharedShape`] containing the actual geometry
43 ///
44 /// # Panics
45 ///
46 /// - If the input vector is empty (a compound must contain at least one shape)
47 /// - If any of the provided shapes are themselves composite shapes (nested composites are not allowed)
48 ///
49 /// # Performance
50 ///
51 /// The BVH is built using a binned construction strategy optimized for static scenes.
52 /// For large compounds (100+ shapes), construction may take noticeable time but provides
53 /// excellent query performance.
54 ///
55 /// # Example
56 ///
57 /// ```
58 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
59 /// # use parry3d::shape::{Compound, Ball, Cuboid, SharedShape};
60 /// use parry3d::math::Isometry;
61 /// use nalgebra::Vector3;
62 ///
63 /// // Create a compound shape resembling a dumbbell
64 /// let shapes = vec![
65 /// // Left sphere
66 /// (
67 /// Isometry::translation(-2.0, 0.0, 0.0),
68 /// SharedShape::new(Ball::new(0.5))
69 /// ),
70 /// // Center bar
71 /// (
72 /// Isometry::identity(),
73 /// SharedShape::new(Cuboid::new(Vector3::new(2.0, 0.2, 0.2)))
74 /// ),
75 /// // Right sphere
76 /// (
77 /// Isometry::translation(2.0, 0.0, 0.0),
78 /// SharedShape::new(Ball::new(0.5))
79 /// ),
80 /// ];
81 ///
82 /// let compound = Compound::new(shapes);
83 ///
84 /// // The compound now contains all three shapes
85 /// assert_eq!(compound.shapes().len(), 3);
86 /// # }
87 /// ```
88 ///
89 /// ```
90 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
91 /// # use parry2d::shape::{Compound, Ball, Cuboid, SharedShape};
92 /// # use parry2d::math::Isometry;
93 /// # use nalgebra::Vector2;
94 ///
95 /// // Create an L-shaped compound
96 /// let shapes = vec![
97 /// // Vertical rectangle
98 /// (
99 /// Isometry::translation(0.0, 1.0),
100 /// SharedShape::new(Cuboid::new(Vector2::new(0.5, 1.0)))
101 /// ),
102 /// // Horizontal rectangle
103 /// (
104 /// Isometry::translation(1.0, 0.0),
105 /// SharedShape::new(Cuboid::new(Vector2::new(1.0, 0.5)))
106 /// ),
107 /// ];
108 ///
109 /// let l_shape = Compound::new(shapes);
110 /// assert_eq!(l_shape.shapes().len(), 2);
111 /// # }
112 /// ```
113 pub fn new(shapes: Vec<(Isometry<Real>, SharedShape)>) -> Compound {
114 assert!(
115 !shapes.is_empty(),
116 "A compound shape must contain at least one shape."
117 );
118 let mut aabbs = Vec::new();
119 let mut leaves = Vec::new();
120 let mut aabb = Aabb::new_invalid();
121
122 for (i, (delta, shape)) in shapes.iter().enumerate() {
123 let bv = shape.compute_aabb(delta);
124
125 aabb.merge(&bv);
126 aabbs.push(bv);
127 leaves.push((i, bv));
128
129 if shape.as_composite_shape().is_some() {
130 panic!("Nested composite shapes are not allowed.");
131 }
132 }
133
134 // NOTE: we apply no dilation factor because we won't
135 // update this tree dynamically.
136 let bvh = Bvh::from_iter(BvhBuildStrategy::Binned, leaves);
137
138 Compound {
139 shapes,
140 bvh,
141 aabbs,
142 aabb,
143 }
144 }
145
146 /// Creates a compound shape by decomposing a triangle mesh into convex polygons.
147 ///
148 /// This 2D-only method takes a [`TriMesh`] and merges adjacent triangles into larger
149 /// convex polygons using the Hertel-Mehlhorn algorithm. This is useful for creating
150 /// efficient collision shapes from arbitrary 2D meshes, as the resulting compound
151 /// has fewer sub-shapes than using individual triangles.
152 ///
153 /// The algorithm works by:
154 /// 1. Starting with all triangles from the input mesh
155 /// 2. Merging adjacent triangles if the result is still convex
156 /// 3. Creating a compound from the resulting convex polygons
157 ///
158 /// # Arguments
159 ///
160 /// * `trimesh` - A reference to the triangle mesh to decompose
161 ///
162 /// # Returns
163 ///
164 /// * `Some(Compound)` - A compound shape containing the convex polygons
165 /// * `None` - If any of the created shapes has zero or near-zero area
166 ///
167 /// # Performance
168 ///
169 /// This decomposition is typically much more efficient than using the raw triangle mesh,
170 /// as it reduces the number of shapes from N triangles to potentially N/2 or fewer polygons.
171 ///
172 /// # Example
173 ///
174 /// ```
175 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
176 /// # use parry2d::shape::{Compound, TriMesh};
177 /// # use nalgebra::Point2;
178 ///
179 /// // Create a simple square mesh (2 triangles)
180 /// let vertices = vec![
181 /// Point2::origin(),
182 /// Point2::new(1.0, 0.0),
183 /// Point2::new(1.0, 1.0),
184 /// Point2::new(0.0, 1.0),
185 /// ];
186 ///
187 /// let indices = vec![
188 /// [0, 1, 2], // First triangle
189 /// [0, 2, 3], // Second triangle
190 /// ];
191 ///
192 /// let trimesh = TriMesh::new(vertices, indices).unwrap();
193 ///
194 /// // Decompose into convex polygons
195 /// if let Some(compound) = Compound::decompose_trimesh(&trimesh) {
196 /// // The two triangles should be merged into one or two convex polygons
197 /// assert!(compound.shapes().len() <= 2);
198 /// }
199 /// # }
200 /// ```
201 ///
202 /// # Example: Complex Shape
203 ///
204 /// ```
205 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
206 /// # use parry2d::shape::{Compound, TriMesh};
207 /// # use nalgebra::Point2;
208 ///
209 /// // Create an L-shaped mesh
210 /// let vertices = vec![
211 /// Point2::origin(),
212 /// Point2::new(2.0, 0.0),
213 /// Point2::new(2.0, 1.0),
214 /// Point2::new(1.0, 1.0),
215 /// Point2::new(1.0, 2.0),
216 /// Point2::new(0.0, 2.0),
217 /// ];
218 ///
219 /// let indices = vec![
220 /// [0, 1, 2],
221 /// [0, 2, 3],
222 /// [0, 3, 4],
223 /// [0, 4, 5],
224 /// ];
225 ///
226 /// let trimesh = TriMesh::new(vertices, indices).unwrap();
227 ///
228 /// // Decompose the L-shape into convex polygons
229 /// if let Some(compound) = Compound::decompose_trimesh(&trimesh) {
230 /// // The result will have fewer shapes than the original 4 triangles
231 /// assert!(compound.shapes().len() > 0);
232 /// println!("Decomposed into {} convex polygons", compound.shapes().len());
233 /// }
234 /// # }
235 /// ```
236 #[cfg(feature = "dim2")]
237 pub fn decompose_trimesh(trimesh: &TriMesh) -> Option<Self> {
238 let polygons = hertel_mehlhorn(trimesh.vertices(), trimesh.indices());
239 let shapes: Option<Vec<_>> = polygons
240 .into_iter()
241 .map(|points| {
242 match points.len() {
243 3 => {
244 let triangle = Triangle::new(points[0], points[1], points[2]);
245 Some(SharedShape::new(triangle))
246 }
247 _ => ConvexPolygon::from_convex_polyline(points).map(SharedShape::new),
248 }
249 .map(|shape| (Isometry::identity(), shape))
250 })
251 .collect();
252 Some(Self::new(shapes?))
253 }
254}
255
256impl Compound {
257 /// Returns a slice containing all sub-shapes and their positions in this compound.
258 ///
259 /// Each element in the returned slice is a tuple containing:
260 /// - The sub-shape's position and orientation ([`Isometry`]) relative to the compound's origin
261 /// - The sub-shape itself ([`SharedShape`])
262 ///
263 /// The order of shapes matches the order they were provided to [`Compound::new`].
264 /// The index of each shape in this slice corresponds to its ID used in other operations
265 /// like BVH traversal.
266 ///
267 /// # Returns
268 ///
269 /// A slice of (isometry, shape) pairs representing all sub-shapes in this compound.
270 ///
271 /// # Example
272 ///
273 /// ```
274 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
275 /// # use parry3d::shape::{Compound, Ball, Cuboid, SharedShape};
276 /// use parry3d::math::Isometry;
277 /// use nalgebra::Vector3;
278 ///
279 /// let shapes = vec![
280 /// (Isometry::translation(1.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
281 /// (Isometry::translation(-1.0, 0.0, 0.0), SharedShape::new(Ball::new(0.3))),
282 /// (Isometry::identity(), SharedShape::new(Cuboid::new(Vector3::new(0.5, 0.5, 0.5)))),
283 /// ];
284 ///
285 /// let compound = Compound::new(shapes);
286 ///
287 /// // Access all shapes
288 /// assert_eq!(compound.shapes().len(), 3);
289 ///
290 /// // Inspect individual shapes
291 /// for (i, (position, shape)) in compound.shapes().iter().enumerate() {
292 /// println!("Shape {} at position: {:?}", i, position.translation);
293 ///
294 /// // Check if it's a ball
295 /// if let Some(ball) = shape.as_ball() {
296 /// println!(" Ball with radius: {}", ball.radius);
297 /// }
298 /// }
299 /// # }
300 /// ```
301 ///
302 /// # Example: Modifying Sub-Shape Positions
303 ///
304 /// ```
305 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
306 /// # use parry3d::shape::{Compound, Ball, SharedShape};
307 /// use parry3d::math::Isometry;
308 ///
309 /// let shapes = vec![
310 /// (Isometry::translation(0.0, 0.0, 0.0), SharedShape::new(Ball::new(1.0))),
311 /// (Isometry::translation(2.0, 0.0, 0.0), SharedShape::new(Ball::new(1.0))),
312 /// ];
313 ///
314 /// let compound = Compound::new(shapes);
315 ///
316 /// // Note: To modify positions, you need to create a new compound
317 /// let mut new_shapes: Vec<_> = compound.shapes()
318 /// .iter()
319 /// .map(|(pos, shape)| {
320 /// // Shift all shapes up by 1 unit
321 /// let new_pos = pos * Isometry::translation(0.0, 1.0, 0.0);
322 /// (new_pos, shape.clone())
323 /// })
324 /// .collect();
325 ///
326 /// let shifted_compound = Compound::new(new_shapes);
327 /// assert_eq!(shifted_compound.shapes().len(), 2);
328 /// # }
329 /// ```
330 #[inline]
331 pub fn shapes(&self) -> &[(Isometry<Real>, SharedShape)] {
332 &self.shapes[..]
333 }
334
335 /// Returns the Axis-Aligned Bounding Box (AABB) of this compound in local space.
336 ///
337 /// The local AABB is the smallest axis-aligned box that contains all sub-shapes
338 /// in the compound, computed in the compound's local coordinate system. This AABB
339 /// is automatically computed when the compound is created and encompasses all
340 /// sub-shapes at their specified positions.
341 ///
342 /// # Returns
343 ///
344 /// A reference to the [`Aabb`] representing the compound's bounding box in local space.
345 ///
346 /// # Use Cases
347 ///
348 /// - **Broad-phase collision detection**: Quick rejection tests before detailed queries
349 /// - **Spatial partitioning**: Organizing compounds in larger spatial structures
350 /// - **Culling**: Determining if the compound is visible or relevant to a query
351 /// - **Size estimation**: Getting approximate dimensions of the compound
352 ///
353 /// # Example
354 ///
355 /// ```
356 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
357 /// # use parry3d::shape::{Compound, Ball, SharedShape};
358 /// use parry3d::math::Isometry;
359 /// use nalgebra::Point3;
360 ///
361 /// let shapes = vec![
362 /// (Isometry::translation(-2.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
363 /// (Isometry::translation(2.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
364 /// ];
365 ///
366 /// let compound = Compound::new(shapes);
367 /// let aabb = compound.local_aabb();
368 ///
369 /// // The AABB should contain both balls
370 /// // Left ball extends from -2.5 to -1.5 on X axis
371 /// // Right ball extends from 1.5 to 2.5 on X axis
372 /// assert!(aabb.mins.x <= -2.5);
373 /// assert!(aabb.maxs.x >= 2.5);
374 ///
375 /// // Check if a point is inside the AABB
376 /// assert!(aabb.contains_local_point(&Point3::origin()));
377 /// assert!(!aabb.contains_local_point(&Point3::new(10.0, 0.0, 0.0)));
378 /// # }
379 /// ```
380 ///
381 /// # Example: Computing Compound Dimensions
382 ///
383 /// ```
384 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
385 /// # use parry3d::shape::{Compound, Cuboid, SharedShape};
386 /// use parry3d::math::Isometry;
387 /// use nalgebra::Vector3;
388 ///
389 /// let shapes = vec![
390 /// (Isometry::identity(), SharedShape::new(Cuboid::new(Vector3::new(1.0, 1.0, 1.0)))),
391 /// (Isometry::translation(3.0, 0.0, 0.0), SharedShape::new(Cuboid::new(Vector3::new(0.5, 0.5, 0.5)))),
392 /// ];
393 ///
394 /// let compound = Compound::new(shapes);
395 /// let aabb = compound.local_aabb();
396 ///
397 /// // Calculate the total dimensions
398 /// let dimensions = aabb.maxs - aabb.mins;
399 /// println!("Compound dimensions: {:?}", dimensions);
400 ///
401 /// // The compound extends from -1.0 to 3.5 on the X axis (4.5 units total)
402 /// assert!((dimensions.x - 4.5).abs() < 1e-5);
403 /// # }
404 /// ```
405 #[inline]
406 pub fn local_aabb(&self) -> &Aabb {
407 &self.aabb
408 }
409
410 /// Returns the bounding sphere of this compound in local space.
411 ///
412 /// The bounding sphere is the smallest sphere that contains all sub-shapes in the
413 /// compound. It is computed from the compound's AABB by finding the sphere that
414 /// tightly encloses that box. This provides a simple, rotation-invariant bounding
415 /// volume useful for certain collision detection algorithms.
416 ///
417 /// # Returns
418 ///
419 /// A [`BoundingSphere`] centered in local space that contains the entire compound.
420 ///
421 /// # Performance
422 ///
423 /// This method is very fast as it simply computes the bounding sphere from the
424 /// pre-computed AABB. The bounding sphere is not cached - it's computed on each call.
425 ///
426 /// # Comparison with AABB
427 ///
428 /// - **Bounding Sphere**: Rotation-invariant, simpler intersection tests, but often looser fit
429 /// - **AABB**: Tighter fit for axis-aligned objects, but must be recomputed when rotated
430 ///
431 /// # Example
432 ///
433 /// ```
434 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
435 /// # use parry3d::shape::{Compound, Ball, SharedShape};
436 /// use parry3d::math::Isometry;
437 ///
438 /// let shapes = vec![
439 /// (Isometry::translation(-1.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
440 /// (Isometry::translation(1.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
441 /// ];
442 ///
443 /// let compound = Compound::new(shapes);
444 /// let bounding_sphere = compound.local_bounding_sphere();
445 ///
446 /// // The bounding sphere should contain both balls
447 /// println!("Center: {:?}", bounding_sphere.center());
448 /// println!("Radius: {}", bounding_sphere.radius());
449 ///
450 /// // The center should be near the origin
451 /// assert!(bounding_sphere.center().coords.norm() < 0.1);
452 ///
453 /// // The radius should be at least 1.5 (distance to ball edge: 1.0 + 0.5)
454 /// assert!(bounding_sphere.radius() >= 1.5);
455 /// # }
456 /// ```
457 ///
458 /// # Example: Using Bounding Sphere for Quick Rejection
459 ///
460 /// ```
461 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
462 /// # use parry3d::shape::{Compound, Cuboid, SharedShape};
463 /// use parry3d::math::Isometry;
464 /// use nalgebra::{Vector3, Point3};
465 ///
466 /// let shapes = vec![
467 /// (Isometry::identity(), SharedShape::new(Cuboid::new(Vector3::new(1.0, 1.0, 1.0)))),
468 /// (Isometry::translation(2.0, 0.0, 0.0), SharedShape::new(Cuboid::new(Vector3::new(0.5, 0.5, 0.5)))),
469 /// ];
470 ///
471 /// let compound = Compound::new(shapes);
472 /// let sphere = compound.local_bounding_sphere();
473 ///
474 /// // Quick test: is a point potentially inside the compound?
475 /// let test_point = Point3::new(5.0, 5.0, 5.0);
476 /// let distance_to_center = (test_point - sphere.center()).norm();
477 ///
478 /// if distance_to_center > sphere.radius() {
479 /// println!("Point is definitely outside the compound");
480 /// assert!(distance_to_center > sphere.radius());
481 /// } else {
482 /// println!("Point might be inside - need detailed check");
483 /// }
484 /// # }
485 /// ```
486 #[inline]
487 pub fn local_bounding_sphere(&self) -> BoundingSphere {
488 self.aabb.bounding_sphere()
489 }
490
491 /// Returns a slice of AABBs, one for each sub-shape in this compound.
492 ///
493 /// Each AABB in the returned slice corresponds to the bounding box of a sub-shape,
494 /// transformed to the compound's local coordinate system. The AABBs are stored in
495 /// the same order as the shapes returned by [`Compound::shapes`], so index `i` in
496 /// this slice corresponds to shape `i`.
497 ///
498 /// These AABBs are used internally by the BVH for efficient spatial queries and
499 /// collision detection. They are pre-computed during compound construction.
500 ///
501 /// # Returns
502 ///
503 /// A slice of [`Aabb`] representing the local-space bounding boxes of each sub-shape.
504 ///
505 /// # Use Cases
506 ///
507 /// - Inspecting individual sub-shape bounds without accessing the shapes themselves
508 /// - Custom spatial queries or culling operations
509 /// - Debugging and visualization of the compound's structure
510 /// - Understanding the BVH's leaf nodes
511 ///
512 /// # Example
513 ///
514 /// ```
515 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
516 /// # use parry3d::shape::{Compound, Ball, Cuboid, SharedShape};
517 /// use parry3d::math::Isometry;
518 /// use nalgebra::Vector3;
519 ///
520 /// let shapes = vec![
521 /// (Isometry::translation(-2.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
522 /// (Isometry::identity(), SharedShape::new(Cuboid::new(Vector3::new(1.0, 1.0, 1.0)))),
523 /// (Isometry::translation(3.0, 0.0, 0.0), SharedShape::new(Ball::new(0.3))),
524 /// ];
525 ///
526 /// let compound = Compound::new(shapes);
527 ///
528 /// // Get AABBs for all sub-shapes
529 /// let aabbs = compound.aabbs();
530 /// assert_eq!(aabbs.len(), 3);
531 ///
532 /// // Inspect each AABB
533 /// for (i, aabb) in aabbs.iter().enumerate() {
534 /// println!("Shape {} AABB:", i);
535 /// println!(" Min: {:?}", aabb.mins);
536 /// println!(" Max: {:?}", aabb.maxs);
537 ///
538 /// let center = aabb.center();
539 /// let extents = aabb.half_extents();
540 /// println!(" Center: {:?}", center);
541 /// println!(" Half-extents: {:?}", extents);
542 /// }
543 /// # }
544 /// ```
545 ///
546 /// # Example: Finding Sub-Shapes in a Region
547 ///
548 /// ```
549 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
550 /// # use parry3d::shape::{Compound, Ball, SharedShape};
551 /// use parry3d::math::Isometry;
552 /// use parry3d::bounding_volume::Aabb;
553 /// use nalgebra::Point3;
554 ///
555 /// let shapes = vec![
556 /// (Isometry::translation(-5.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
557 /// (Isometry::translation(0.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
558 /// (Isometry::translation(5.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
559 /// ];
560 ///
561 /// let compound = Compound::new(shapes);
562 ///
563 /// // Define a query point
564 /// let query_point = Point3::origin();
565 ///
566 /// // Find which sub-shapes might contain this point
567 /// let potentially_containing: Vec<usize> = compound.aabbs()
568 /// .iter()
569 /// .enumerate()
570 /// .filter(|(_, aabb)| aabb.contains_local_point(&query_point))
571 /// .map(|(i, _)| i)
572 /// .collect();
573 ///
574 /// // Only the middle shape (index 1) should contain the origin
575 /// assert_eq!(potentially_containing.len(), 1);
576 /// assert_eq!(potentially_containing[0], 1);
577 /// # }
578 /// ```
579 #[inline]
580 pub fn aabbs(&self) -> &[Aabb] {
581 &self.aabbs[..]
582 }
583
584 /// Returns the Bounding Volume Hierarchy (BVH) used for efficient spatial queries.
585 ///
586 /// The BVH is an acceleration structure that organizes the sub-shapes hierarchically
587 /// for fast collision detection and spatial queries. It enables logarithmic-time queries
588 /// instead of linear searches through all sub-shapes. The BVH is automatically built
589 /// when the compound is created using a binned construction strategy.
590 ///
591 /// # Returns
592 ///
593 /// A reference to the [`Bvh`] acceleration structure for this compound.
594 ///
595 /// # Use Cases
596 ///
597 /// - **Custom spatial queries**: Traverse the BVH for specialized collision detection
598 /// - **Ray casting**: Efficiently find which sub-shapes intersect a ray
599 /// - **AABB queries**: Find all sub-shapes intersecting a region
600 /// - **Debugging**: Inspect the BVH structure and quality
601 /// - **Performance analysis**: Understand query performance characteristics
602 ///
603 /// # Performance
604 ///
605 /// The BVH provides O(log n) query performance for most spatial operations, where n
606 /// is the number of sub-shapes. For compounds with many shapes (100+), the BVH
607 /// provides dramatic speedups compared to naive linear searches.
608 ///
609 /// # Example
610 ///
611 /// ```
612 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
613 /// # use parry3d::shape::{Compound, Ball, SharedShape};
614 /// use parry3d::math::Isometry;
615 /// use parry3d::bounding_volume::Aabb;
616 /// use nalgebra::Point3;
617 ///
618 /// let shapes = vec![
619 /// (Isometry::translation(-3.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
620 /// (Isometry::translation(0.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
621 /// (Isometry::translation(3.0, 0.0, 0.0), SharedShape::new(Ball::new(0.5))),
622 /// ];
623 ///
624 /// let compound = Compound::new(shapes);
625 /// let bvh = compound.bvh();
626 ///
627 /// // The BVH provides efficient hierarchical organization
628 /// assert_eq!(bvh.leaf_count(), 3);
629 /// println!("BVH root AABB: {:?}", bvh.root_aabb());
630 /// # }
631 /// ```
632 ///
633 /// # Example: Accessing BVH for Custom Queries
634 ///
635 /// ```
636 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
637 /// # use parry3d::shape::{Compound, Ball, SharedShape};
638 /// use parry3d::math::Isometry;
639 ///
640 /// let mut shapes = vec![];
641 /// for i in 0..10 {
642 /// let x = i as f32 * 2.0;
643 /// shapes.push((
644 /// Isometry::translation(x, 0.0, 0.0),
645 /// SharedShape::new(Ball::new(0.5))
646 /// ));
647 /// }
648 ///
649 /// let compound = Compound::new(shapes);
650 /// let bvh = compound.bvh();
651 ///
652 /// // The BVH organizes 10 shapes hierarchically
653 /// assert_eq!(bvh.leaf_count(), 10);
654 /// assert_eq!(compound.shapes().len(), 10);
655 ///
656 /// // Access the root AABB which bounds all shapes
657 /// let root_aabb = bvh.root_aabb();
658 /// println!("Root AABB spans from {:?} to {:?}", root_aabb.mins, root_aabb.maxs);
659 /// # }
660 /// ```
661 #[inline]
662 pub fn bvh(&self) -> &Bvh {
663 &self.bvh
664 }
665}
666
667impl CompositeShape for Compound {
668 #[inline]
669 fn map_part_at(
670 &self,
671 shape_id: u32,
672 f: &mut dyn FnMut(Option<&Isometry<Real>>, &dyn Shape, Option<&dyn NormalConstraints>),
673 ) {
674 if let Some(shape) = self.shapes.get(shape_id as usize) {
675 f(Some(&shape.0), &*shape.1, None)
676 }
677 }
678
679 #[inline]
680 fn bvh(&self) -> &Bvh {
681 &self.bvh
682 }
683}
684
685impl TypedCompositeShape for Compound {
686 type PartShape = dyn Shape;
687 type PartNormalConstraints = ();
688
689 #[inline(always)]
690 fn map_typed_part_at<T>(
691 &self,
692 i: u32,
693 mut f: impl FnMut(
694 Option<&Isometry<Real>>,
695 &Self::PartShape,
696 Option<&Self::PartNormalConstraints>,
697 ) -> T,
698 ) -> Option<T> {
699 let (part_pos, part) = &self.shapes[i as usize];
700 Some(f(Some(part_pos), &**part, None))
701 }
702
703 #[inline(always)]
704 fn map_untyped_part_at<T>(
705 &self,
706 i: u32,
707 mut f: impl FnMut(
708 Option<&Isometry<Real>>,
709 &Self::PartShape,
710 Option<&dyn NormalConstraints>,
711 ) -> T,
712 ) -> Option<T> {
713 let (part_pos, part) = &self.shapes[i as usize];
714 Some(f(Some(part_pos), &**part, None))
715 }
716}