avian2d/spatial_query/pipeline.rs
1use alloc::sync::Arc;
2
3use crate::prelude::*;
4use bevy::prelude::*;
5use parry::{
6 bounding_volume::{Aabb, BoundingVolume},
7 math::Isometry,
8 partitioning::{Bvh, BvhBuildStrategy, BvhNode},
9 query::{
10 DefaultQueryDispatcher, QueryDispatcher, RayCast, ShapeCastOptions,
11 details::NormalConstraints,
12 },
13 shape::{CompositeShape, CompositeShapeRef, Shape, TypedCompositeShape},
14};
15
16// TODO: It'd be nice not to store so much duplicate data.
17// Should we just query the ECS?
18#[derive(Clone)]
19pub(crate) struct BvhProxyData {
20 pub entity: Entity,
21 pub isometry: Isometry<Scalar>,
22 pub collider: Collider,
23 pub layers: CollisionLayers,
24}
25
26/// A resource for the spatial query pipeline.
27///
28/// The pipeline maintains a quaternary bounding volume hierarchy `Bvh` of the world's colliders
29/// as an acceleration structure for spatial queries.
30#[derive(Resource, Clone)]
31pub struct SpatialQueryPipeline {
32 pub(crate) bvh: Bvh,
33 pub(crate) dispatcher: Arc<dyn QueryDispatcher>,
34 // TODO: Store the proxies as `Bvh` leaf data.
35 pub(crate) proxies: Vec<BvhProxyData>,
36}
37
38impl Default for SpatialQueryPipeline {
39 fn default() -> Self {
40 Self {
41 bvh: Bvh::new(),
42 dispatcher: Arc::new(DefaultQueryDispatcher),
43 proxies: Vec::default(),
44 }
45 }
46}
47
48impl SpatialQueryPipeline {
49 /// Creates a new [`SpatialQueryPipeline`].
50 pub fn new() -> SpatialQueryPipeline {
51 SpatialQueryPipeline::default()
52 }
53
54 pub(crate) fn as_composite_shape_internal<'a>(
55 &'a self,
56 query_filter: &'a SpatialQueryFilter,
57 ) -> QueryPipelineAsCompositeShape<'a> {
58 QueryPipelineAsCompositeShape {
59 pipeline: self,
60 query_filter,
61 }
62 }
63
64 /// Creates a parry [`TypedCompositeShape`] for this pipeline.
65 /// Can be used to implement custom spatial queries
66 pub fn as_composite_shape<'a>(
67 &'a self,
68 query_filter: &'a SpatialQueryFilter,
69 ) -> impl TypedCompositeShape {
70 self.as_composite_shape_internal(query_filter)
71 }
72
73 pub(crate) fn as_composite_shape_with_predicate_internal<'a: 'b, 'b>(
74 &'a self,
75 query_filter: &'a SpatialQueryFilter,
76 predicate: &'a dyn Fn(Entity) -> bool,
77 ) -> QueryPipelineAsCompositeShapeWithPredicate<'a, 'b> {
78 QueryPipelineAsCompositeShapeWithPredicate {
79 pipeline: self,
80 query_filter,
81 predicate,
82 }
83 }
84
85 /// Creates a parry [`TypedCompositeShape`] for this pipeline, with a predicate.
86 /// Can be used to implement custom spatial queries
87 pub fn as_composite_shape_with_predicate<'a>(
88 &'a self,
89 query_filter: &'a SpatialQueryFilter,
90 predicate: &'a dyn Fn(Entity) -> bool,
91 ) -> impl TypedCompositeShape {
92 self.as_composite_shape_with_predicate_internal(query_filter, predicate)
93 }
94
95 /// Updates the associated acceleration structures with a new set of entities.
96 pub fn update<'a>(
97 &mut self,
98 colliders: impl Iterator<
99 Item = (
100 Entity,
101 &'a Position,
102 &'a Rotation,
103 &'a Collider,
104 &'a CollisionLayers,
105 ),
106 >,
107 ) {
108 self.update_internal(
109 colliders.map(
110 |(entity, position, rotation, collider, layers)| BvhProxyData {
111 entity,
112 isometry: make_isometry(position.0, *rotation),
113 collider: collider.clone(),
114 layers: *layers,
115 },
116 ),
117 )
118 }
119
120 // TODO: Incremental updates.
121 fn update_internal(&mut self, proxies: impl Iterator<Item = BvhProxyData>) {
122 self.proxies.clear();
123 self.proxies.extend(proxies);
124
125 let aabbs = self.proxies.iter().enumerate().map(|(i, proxy)| {
126 (
127 i,
128 proxy.collider.shape_scaled().compute_aabb(&proxy.isometry),
129 )
130 });
131
132 self.bvh = Bvh::from_iter(BvhBuildStrategy::Binned, aabbs);
133 }
134
135 /// Get the entity corresponding to a given index in the pipeline
136 pub fn entity(&self, index: usize) -> Entity {
137 self.proxies[index].entity
138 }
139
140 /// Get a dyn reference to the query dispatcher used in this pipeline
141 pub fn dispatcher_ref(&self) -> &dyn QueryDispatcher {
142 self.dispatcher.as_ref()
143 }
144
145 /// Casts a [ray](spatial_query#raycasting) and computes the closest [hit](RayHitData) with a collider.
146 /// If there are no hits, `None` is returned.
147 ///
148 /// # Arguments
149 ///
150 /// - `origin`: Where the ray is cast from.
151 /// - `direction`: What direction the ray is cast in.
152 /// - `max_distance`: The maximum distance the ray can travel.
153 /// - `solid`: If true *and* the ray origin is inside of a collider, the hit point will be the ray origin itself.
154 /// Otherwise, the collider will be treated as hollow, and the hit point will be at its boundary.
155 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
156 ///
157 /// # Related Methods
158 ///
159 /// - [`SpatialQueryPipeline::cast_ray_predicate`]
160 /// - [`SpatialQueryPipeline::ray_hits`]
161 /// - [`SpatialQueryPipeline::ray_hits_callback`]
162 pub fn cast_ray(
163 &self,
164 origin: Vector,
165 direction: Dir,
166 max_distance: Scalar,
167 solid: bool,
168 filter: &SpatialQueryFilter,
169 ) -> Option<RayHitData> {
170 self.cast_ray_predicate(origin, direction, max_distance, solid, filter, &|_| true)
171 }
172
173 /// Casts a [ray](spatial_query#raycasting) and computes the closest [hit](RayHitData) with a collider.
174 /// If there are no hits, `None` is returned.
175 ///
176 /// # Arguments
177 ///
178 /// - `origin`: Where the ray is cast from.
179 /// - `direction`: What direction the ray is cast in.
180 /// - `max_distance`: The maximum distance the ray can travel.
181 /// - `solid`: If true *and* the ray origin is inside of a collider, the hit point will be the ray origin itself.
182 /// Otherwise, the collider will be treated as hollow, and the hit point will be at its boundary.
183 /// - `predicate`: A function called on each entity hit by the ray. The ray keeps travelling until the predicate returns `true`.
184 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
185 ///
186 /// # Related Methods
187 ///
188 /// - [`SpatialQueryPipeline::cast_ray`]
189 /// - [`SpatialQueryPipeline::ray_hits`]
190 /// - [`SpatialQueryPipeline::ray_hits_callback`]
191 pub fn cast_ray_predicate(
192 &self,
193 origin: Vector,
194 direction: Dir,
195 max_distance: Scalar,
196 solid: bool,
197 filter: &SpatialQueryFilter,
198 predicate: &dyn Fn(Entity) -> bool,
199 ) -> Option<RayHitData> {
200 let composite = self.as_composite_shape_with_predicate(filter, predicate);
201 let pipeline_shape = CompositeShapeRef(&composite);
202 let ray = parry::query::Ray::new(origin.into(), direction.adjust_precision().into());
203
204 pipeline_shape
205 .cast_local_ray_and_get_normal(&ray, max_distance, solid)
206 .map(|(index, hit)| RayHitData {
207 entity: self.proxies[index as usize].entity,
208 distance: hit.time_of_impact,
209 normal: hit.normal.into(),
210 })
211 }
212
213 /// Casts a [ray](spatial_query#raycasting) and computes all [hits](RayHitData) until `max_hits` is reached.
214 ///
215 /// Note that the order of the results is not guaranteed, and if there are more hits than `max_hits`,
216 /// some hits will be missed.
217 ///
218 /// # Arguments
219 ///
220 /// - `origin`: Where the ray is cast from.
221 /// - `direction`: What direction the ray is cast in.
222 /// - `max_distance`: The maximum distance the ray can travel.
223 /// - `max_hits`: The maximum number of hits. Additional hits will be missed.
224 /// - `solid`: If true *and* the ray origin is inside of a collider, the hit point will be the ray origin itself.
225 /// Otherwise, the collider will be treated as hollow, and the hit point will be at its boundary.
226 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
227 ///
228 /// # Related Methods
229 ///
230 /// - [`SpatialQueryPipeline::cast_ray`]
231 /// - [`SpatialQueryPipeline::cast_ray_predicate`]
232 /// - [`SpatialQueryPipeline::ray_hits_callback`]
233 pub fn ray_hits(
234 &self,
235 origin: Vector,
236 direction: Dir,
237 max_distance: Scalar,
238 max_hits: u32,
239 solid: bool,
240 filter: &SpatialQueryFilter,
241 ) -> Vec<RayHitData> {
242 let mut hits = Vec::with_capacity(10);
243 self.ray_hits_callback(origin, direction, max_distance, solid, filter, |hit| {
244 hits.push(hit);
245 (hits.len() as u32) < max_hits
246 });
247 hits
248 }
249
250 /// Casts a [ray](spatial_query#raycasting) and computes all [hits](RayHitData), calling the given `callback`
251 /// for each hit. The raycast stops when `callback` returns false or all hits have been found.
252 ///
253 /// Note that the order of the results is not guaranteed.
254 ///
255 /// # Arguments
256 ///
257 /// - `origin`: Where the ray is cast from.
258 /// - `direction`: What direction the ray is cast in.
259 /// - `max_distance`: The maximum distance the ray can travel.
260 /// - `solid`: If true *and* the ray origin is inside of a collider, the hit point will be the ray origin itself.
261 /// Otherwise, the collider will be treated as hollow, and the hit point will be at its boundary.
262 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
263 /// - `callback`: A callback function called for each hit.
264 ///
265 /// # Related Methods
266 ///
267 /// - [`SpatialQueryPipeline::cast_ray`]
268 /// - [`SpatialQueryPipeline::cast_ray_predicate`]
269 /// - [`SpatialQueryPipeline::ray_hits`]
270 pub fn ray_hits_callback(
271 &self,
272 origin: Vector,
273 direction: Dir,
274 max_distance: Scalar,
275 solid: bool,
276 filter: &SpatialQueryFilter,
277 // TODO: Just return an iterator
278 mut callback: impl FnMut(RayHitData) -> bool,
279 ) {
280 let proxies = &self.proxies;
281
282 let ray = parry::query::Ray::new(origin.into(), direction.adjust_precision().into());
283
284 let hits = self
285 .bvh
286 .leaves(move |node: &BvhNode| node.aabb().intersects_local_ray(&ray, max_distance))
287 .filter_map(move |leaf| {
288 let proxy = proxies.get(leaf as usize)?;
289
290 if !filter.test(proxy.entity, proxy.layers) {
291 return None;
292 }
293
294 let hit = proxy.collider.shape_scaled().cast_ray_and_get_normal(
295 &proxy.isometry,
296 &ray,
297 max_distance,
298 solid,
299 )?;
300
301 Some(RayHitData {
302 entity: proxy.entity,
303 distance: hit.time_of_impact,
304 normal: hit.normal.into(),
305 })
306 });
307
308 for hit in hits {
309 if !callback(hit) {
310 break;
311 }
312 }
313 }
314
315 /// Casts a [shape](spatial_query#shapecasting) with a given rotation and computes the closest [hit](ShapeHits)
316 /// with a collider. If there are no hits, `None` is returned.
317 ///
318 /// For a more ECS-based approach, consider using the [`ShapeCaster`] component instead.
319 ///
320 /// # Arguments
321 ///
322 /// - `shape`: The shape being cast represented as a [`Collider`].
323 /// - `origin`: Where the shape is cast from.
324 /// - `shape_rotation`: The rotation of the shape being cast.
325 /// - `direction`: What direction the shape is cast in.
326 /// - `config`: A [`ShapeCastConfig`] that determines the behavior of the cast.
327 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
328 ///
329 /// # Related Methods
330 ///
331 /// - [`SpatialQueryPipeline::cast_shape_predicate`]
332 /// - [`SpatialQueryPipeline::shape_hits`]
333 /// - [`SpatialQueryPipeline::shape_hits_callback`]
334 #[allow(clippy::too_many_arguments)]
335 pub fn cast_shape(
336 &self,
337 shape: &Collider,
338 origin: Vector,
339 shape_rotation: RotationValue,
340 direction: Dir,
341 config: &ShapeCastConfig,
342 filter: &SpatialQueryFilter,
343 ) -> Option<ShapeHitData> {
344 self.cast_shape_predicate(
345 shape,
346 origin,
347 shape_rotation,
348 direction,
349 config,
350 filter,
351 &|_| true,
352 )
353 }
354
355 /// Casts a [shape](spatial_query#shapecasting) with a given rotation and computes the closest [hit](ShapeHits)
356 /// with a collider. If there are no hits, `None` is returned.
357 ///
358 /// For a more ECS-based approach, consider using the [`ShapeCaster`] component instead.
359 ///
360 /// # Arguments
361 ///
362 /// - `shape`: The shape being cast represented as a [`Collider`].
363 /// - `origin`: Where the shape is cast from.
364 /// - `shape_rotation`: The rotation of the shape being cast.
365 /// - `direction`: What direction the shape is cast in.
366 /// - `config`: A [`ShapeCastConfig`] that determines the behavior of the cast.
367 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
368 /// - `predicate`: A function called on each entity hit by the shape. The shape keeps travelling until the predicate returns `true`.
369 ///
370 /// # Related Methods
371 ///
372 /// - [`SpatialQueryPipeline::cast_shape`]
373 /// - [`SpatialQueryPipeline::shape_hits`]
374 /// - [`SpatialQueryPipeline::shape_hits_callback`]
375 #[allow(clippy::too_many_arguments)]
376 pub fn cast_shape_predicate(
377 &self,
378 shape: &Collider,
379 origin: Vector,
380 shape_rotation: RotationValue,
381 direction: Dir,
382 config: &ShapeCastConfig,
383 filter: &SpatialQueryFilter,
384 predicate: &dyn Fn(Entity) -> bool,
385 ) -> Option<ShapeHitData> {
386 let rotation: Rotation;
387 #[cfg(feature = "2d")]
388 {
389 rotation = Rotation::radians(shape_rotation);
390 }
391 #[cfg(feature = "3d")]
392 {
393 rotation = Rotation::from(shape_rotation);
394 }
395
396 let shape_isometry = make_isometry(origin, rotation);
397 let shape_direction = direction.adjust_precision().into();
398 let composite = self.as_composite_shape_with_predicate(filter, predicate);
399 let pipeline_shape = CompositeShapeRef(&composite);
400
401 pipeline_shape
402 .cast_shape(
403 self.dispatcher.as_ref(),
404 &shape_isometry,
405 &shape_direction,
406 shape.shape_scaled().as_ref(),
407 ShapeCastOptions {
408 max_time_of_impact: config.max_distance,
409 stop_at_penetration: !config.ignore_origin_penetration,
410 compute_impact_geometry_on_penetration: config.compute_contact_on_penetration,
411 ..default()
412 },
413 )
414 .map(|(index, hit)| ShapeHitData {
415 entity: self.proxies[index as usize].entity,
416 distance: hit.time_of_impact,
417 point1: hit.witness1.into(),
418 point2: hit.witness2.into(),
419 normal1: hit.normal1.into(),
420 normal2: hit.normal2.into(),
421 })
422 }
423
424 /// Casts a [shape](spatial_query#shapecasting) with a given rotation and computes computes all [hits](ShapeHitData)
425 /// in the order of distance until `max_hits` is reached.
426 ///
427 /// # Arguments
428 ///
429 /// - `shape`: The shape being cast represented as a [`Collider`].
430 /// - `origin`: Where the shape is cast from.
431 /// - `shape_rotation`: The rotation of the shape being cast.
432 /// - `direction`: What direction the shape is cast in.
433 /// - `max_hits`: The maximum number of hits. Additional hits will be missed.
434 /// - `config`: A [`ShapeCastConfig`] that determines the behavior of the cast.
435 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
436 ///
437 /// # Related Methods
438 ///
439 /// - [`SpatialQueryPipeline::cast_shape`]
440 /// - [`SpatialQueryPipeline::cast_shape_predicate`]
441 /// - [`SpatialQueryPipeline::shape_hits_callback`]
442 #[allow(clippy::too_many_arguments)]
443 pub fn shape_hits(
444 &self,
445 shape: &Collider,
446 origin: Vector,
447 shape_rotation: RotationValue,
448 direction: Dir,
449 max_hits: u32,
450 config: &ShapeCastConfig,
451 filter: &SpatialQueryFilter,
452 ) -> Vec<ShapeHitData> {
453 let mut hits = Vec::with_capacity(10);
454 self.shape_hits_callback(
455 shape,
456 origin,
457 shape_rotation,
458 direction,
459 config,
460 filter,
461 |hit| {
462 hits.push(hit);
463 (hits.len() as u32) < max_hits
464 },
465 );
466 hits
467 }
468
469 /// Casts a [shape](spatial_query#shapecasting) with a given rotation and computes computes all [hits](ShapeHitData)
470 /// in the order of distance, calling the given `callback` for each hit. The shapecast stops when
471 /// `callback` returns false or all hits have been found.
472 ///
473 /// # Arguments
474 ///
475 /// - `shape`: The shape being cast represented as a [`Collider`].
476 /// - `origin`: Where the shape is cast from.
477 /// - `shape_rotation`: The rotation of the shape being cast.
478 /// - `direction`: What direction the shape is cast in.
479 /// - `config`: A [`ShapeCastConfig`] that determines the behavior of the cast.
480 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
481 /// - `callback`: A callback function called for each hit.
482 ///
483 /// # Related Methods
484 ///
485 /// - [`SpatialQueryPipeline::cast_shape`]
486 /// - [`SpatialQueryPipeline::cast_shape_predicate`]
487 /// - [`SpatialQueryPipeline::shape_hits`]
488 #[allow(clippy::too_many_arguments)]
489 pub fn shape_hits_callback(
490 &self,
491 shape: &Collider,
492 origin: Vector,
493 shape_rotation: RotationValue,
494 direction: Dir,
495 config: &ShapeCastConfig,
496 filter: &SpatialQueryFilter,
497 mut callback: impl FnMut(ShapeHitData) -> bool,
498 ) {
499 // TODO: This clone is here so that the excluded entities in the original `query_filter` aren't modified.
500 // We could remove this if shapecasting could compute multiple hits without just doing casts in a loop.
501 // See https://github.com/Jondolf/avian/issues/403.
502 let mut query_filter = filter.clone();
503
504 let shape_cast_options = ShapeCastOptions {
505 max_time_of_impact: config.max_distance,
506 target_distance: config.target_distance,
507 stop_at_penetration: !config.ignore_origin_penetration,
508 compute_impact_geometry_on_penetration: config.compute_contact_on_penetration,
509 };
510
511 let rotation: Rotation;
512 #[cfg(feature = "2d")]
513 {
514 rotation = Rotation::radians(shape_rotation);
515 }
516 #[cfg(feature = "3d")]
517 {
518 rotation = Rotation::from(shape_rotation);
519 }
520
521 let shape_isometry = make_isometry(origin, rotation);
522 let shape_direction = direction.adjust_precision().into();
523
524 loop {
525 let composite = self.as_composite_shape_internal(&query_filter);
526 let pipeline_shape = CompositeShapeRef(&composite);
527
528 let hit = pipeline_shape
529 .cast_shape(
530 self.dispatcher.as_ref(),
531 &shape_isometry,
532 &shape_direction,
533 shape.shape_scaled().as_ref(),
534 shape_cast_options,
535 )
536 .map(|(index, hit)| ShapeHitData {
537 entity: self.proxies[index as usize].entity,
538 distance: hit.time_of_impact,
539 point1: hit.witness1.into(),
540 point2: hit.witness2.into(),
541 normal1: hit.normal1.into(),
542 normal2: hit.normal2.into(),
543 });
544
545 if let Some(hit) = hit {
546 query_filter.excluded_entities.insert(hit.entity);
547
548 if !callback(hit) {
549 break;
550 }
551 } else {
552 break;
553 }
554 }
555 }
556
557 /// Finds the [projection](spatial_query#point-projection) of a given point on the closest [collider](Collider).
558 /// If one isn't found, `None` is returned.
559 ///
560 /// # Arguments
561 ///
562 /// - `point`: The point that should be projected.
563 /// - `solid`: If true and the point is inside of a collider, the projection will be at the point.
564 /// Otherwise, the collider will be treated as hollow, and the projection will be at the collider's boundary.
565 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
566 ///
567 /// # Related Methods
568 ///
569 /// - [`SpatialQueryPipeline::project_point_predicate`]
570 pub fn project_point(
571 &self,
572 point: Vector,
573 solid: bool,
574 filter: &SpatialQueryFilter,
575 ) -> Option<PointProjection> {
576 self.project_point_predicate(point, solid, filter, &|_| true)
577 }
578
579 /// Finds the [projection](spatial_query#point-projection) of a given point on the closest [collider](Collider).
580 /// If one isn't found, `None` is returned.
581 ///
582 /// # Arguments
583 ///
584 /// - `point`: The point that should be projected.
585 /// - `solid`: If true and the point is inside of a collider, the projection will be at the point.
586 /// Otherwise, the collider will be treated as hollow, and the projection will be at the collider's boundary.
587 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
588 /// - `predicate`: A function for filtering which entities are considered in the query. The projection will be on the closest collider for which the `predicate` returns `true`
589 ///
590 /// # Related Methods
591 ///
592 /// - [`SpatialQueryPipeline::project_point`]
593 pub fn project_point_predicate(
594 &self,
595 point: Vector,
596 solid: bool,
597 filter: &SpatialQueryFilter,
598 predicate: &dyn Fn(Entity) -> bool,
599 ) -> Option<PointProjection> {
600 if self.proxies.is_empty() {
601 return None;
602 }
603
604 let point = point.into();
605 let composite = self.as_composite_shape_with_predicate(filter, predicate);
606 let pipeline_shape = CompositeShapeRef(&composite);
607
608 let (index, projection) = pipeline_shape.project_local_point(&point, solid);
609
610 Some(PointProjection {
611 entity: self.proxies[index as usize].entity,
612 point: projection.point.into(),
613 is_inside: projection.is_inside,
614 })
615 }
616
617 /// An [intersection test](spatial_query#intersection-tests) that finds all entities with a [collider](Collider)
618 /// that contains the given point.
619 ///
620 /// # Arguments
621 ///
622 /// - `point`: The point that intersections are tested against.
623 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
624 ///
625 /// # Related Methods
626 ///
627 /// - [`SpatialQueryPipeline::point_intersections_callback`]
628 pub fn point_intersections(&self, point: Vector, filter: &SpatialQueryFilter) -> Vec<Entity> {
629 let mut intersections = vec![];
630
631 self.point_intersections_callback(point, filter, |e| {
632 intersections.push(e);
633 true
634 });
635
636 intersections
637 }
638
639 /// An [intersection test](spatial_query#intersection-tests) that finds all entities with a [collider](Collider)
640 /// that contains the given point, calling the given `callback` for each intersection.
641 /// The search stops when `callback` returns `false` or all intersections have been found.
642 ///
643 /// # Arguments
644 ///
645 /// - `point`: The point that intersections are tested against.
646 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
647 /// - `callback`: A callback function called for each intersection.
648 ///
649 /// # Related Methods
650 ///
651 /// - [`SpatialQueryPipeline::point_intersections`]
652 pub fn point_intersections_callback(
653 &self,
654 point: Vector,
655 filter: &SpatialQueryFilter,
656 mut callback: impl FnMut(Entity) -> bool,
657 ) {
658 let point = point.into();
659
660 let intersecting_entities = self
661 .bvh
662 .leaves(|node: &BvhNode| node.aabb().contains_local_point(&point))
663 .filter_map(move |leaf| {
664 let proxy = self.proxies.get(leaf as usize)?;
665
666 if filter.test(proxy.entity, proxy.layers)
667 && proxy
668 .collider
669 .shape_scaled()
670 .contains_point(&proxy.isometry, &point)
671 {
672 Some(proxy.entity)
673 } else {
674 None
675 }
676 });
677
678 for entity in intersecting_entities {
679 if !callback(entity) {
680 break;
681 }
682 }
683 }
684
685 /// An [intersection test](spatial_query#intersection-tests) that finds all entities with a [`ColliderAabb`]
686 /// that is intersecting the given `aabb`.
687 ///
688 /// # Related Methods
689 ///
690 /// - [`SpatialQueryPipeline::aabb_intersections_with_aabb_callback`]
691 pub fn aabb_intersections_with_aabb(&self, aabb: ColliderAabb) -> Vec<Entity> {
692 let mut intersections = vec![];
693
694 self.aabb_intersections_with_aabb_callback(aabb, |e| {
695 intersections.push(e);
696 true
697 });
698
699 intersections
700 }
701
702 /// An [intersection test](spatial_query#intersection-tests) that finds all entities with a [`ColliderAabb`]
703 /// that is intersecting the given `aabb`, calling `callback` for each intersection.
704 /// The search stops when `callback` returns `false` or all intersections have been found.
705 ///
706 /// # Related Methods
707 ///
708 /// - [`SpatialQueryPipeline::aabb_intersections_with_aabb`]
709 pub fn aabb_intersections_with_aabb_callback(
710 &self,
711 aabb: ColliderAabb,
712 mut callback: impl FnMut(Entity) -> bool,
713 ) {
714 let aabb = Aabb {
715 mins: aabb.min.into(),
716 maxs: aabb.max.into(),
717 };
718
719 let intersecting_entities = self
720 .bvh
721 .leaves(move |node: &BvhNode| node.aabb().intersects(&aabb))
722 .filter_map(move |leaf| self.proxies.get(leaf as usize).map(|p| p.entity));
723
724 for entity in intersecting_entities {
725 if !callback(entity) {
726 break;
727 }
728 }
729 }
730
731 /// An [intersection test](spatial_query#intersection-tests) that finds all entities with a [`Collider`]
732 /// that is intersecting the given `shape` with a given position and rotation.
733 ///
734 /// # Arguments
735 ///
736 /// - `shape`: The shape that intersections are tested against represented as a [`Collider`].
737 /// - `shape_position`: The position of the shape.
738 /// - `shape_rotation`: The rotation of the shape.
739 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
740 ///
741 /// # Related Methods
742 ///
743 /// - [`SpatialQueryPipeline::shape_intersections_callback`]
744 pub fn shape_intersections(
745 &self,
746 shape: &Collider,
747 shape_position: Vector,
748 shape_rotation: RotationValue,
749 filter: &SpatialQueryFilter,
750 ) -> Vec<Entity> {
751 let mut intersections = vec![];
752 self.shape_intersections_callback(shape, shape_position, shape_rotation, filter, |e| {
753 intersections.push(e);
754 true
755 });
756 intersections
757 }
758
759 /// An [intersection test](spatial_query#intersection-tests) that finds all entities with a [`Collider`]
760 /// that is intersecting the given `shape` with a given position and rotation, calling `callback` for each
761 /// intersection. The search stops when `callback` returns `false` or all intersections have been found.
762 ///
763 /// # Arguments
764 ///
765 /// - `shape`: The shape that intersections are tested against represented as a [`Collider`].
766 /// - `shape_position`: The position of the shape.
767 /// - `shape_rotation`: The rotation of the shape.
768 /// - `filter`: A [`SpatialQueryFilter`] that determines which colliders are taken into account in the query.
769 /// - `callback`: A callback function called for each intersection.
770 ///
771 /// # Related Methods
772 ///
773 /// - [`SpatialQueryPipeline::shape_intersections`]
774 pub fn shape_intersections_callback(
775 &self,
776 shape: &Collider,
777 shape_position: Vector,
778 shape_rotation: RotationValue,
779 filter: &SpatialQueryFilter,
780 mut callback: impl FnMut(Entity) -> bool,
781 ) {
782 let proxies = &self.proxies;
783 let rotation: Rotation;
784 #[cfg(feature = "2d")]
785 {
786 rotation = Rotation::radians(shape_rotation);
787 }
788 #[cfg(feature = "3d")]
789 {
790 rotation = Rotation::from(shape_rotation);
791 }
792
793 let shape_isometry = make_isometry(shape_position, rotation);
794 let inverse_shape_isometry = shape_isometry.inverse();
795
796 let dispatcher = &*self.dispatcher;
797
798 let shape_aabb = shape.shape_scaled().compute_aabb(&shape_isometry);
799 let entities = self
800 .bvh
801 .leaves(move |node: &BvhNode| node.aabb().intersects(&shape_aabb))
802 .filter_map(move |leaf| {
803 let proxy = proxies.get(leaf as usize)?;
804
805 if !filter.test(proxy.entity, proxy.layers) {
806 return None;
807 }
808
809 let isometry = inverse_shape_isometry * proxy.isometry;
810 let intersects = dispatcher
811 .intersection_test(
812 &isometry,
813 shape.shape_scaled().as_ref(),
814 proxy.collider.shape_scaled().as_ref(),
815 )
816 .is_ok_and(|b| b);
817
818 intersects.then_some(proxy.entity)
819 });
820
821 for entity in entities {
822 if !callback(entity) {
823 break;
824 }
825 }
826 }
827}
828
829pub(crate) struct QueryPipelineAsCompositeShape<'a> {
830 pipeline: &'a SpatialQueryPipeline,
831 query_filter: &'a SpatialQueryFilter,
832}
833
834impl CompositeShape for QueryPipelineAsCompositeShape<'_> {
835 fn map_part_at(
836 &self,
837 shape_id: u32,
838 f: &mut dyn FnMut(Option<&Isometry<Scalar>>, &dyn Shape, Option<&dyn NormalConstraints>),
839 ) {
840 self.map_untyped_part_at(shape_id, f);
841 }
842
843 fn bvh(&self) -> &Bvh {
844 &self.pipeline.bvh
845 }
846}
847
848impl TypedCompositeShape for QueryPipelineAsCompositeShape<'_> {
849 type PartNormalConstraints = ();
850 type PartShape = dyn Shape;
851
852 fn map_typed_part_at<T>(
853 &self,
854 shape_id: u32,
855 mut f: impl FnMut(
856 Option<&Isometry<Scalar>>,
857 &Self::PartShape,
858 Option<&Self::PartNormalConstraints>,
859 ) -> T,
860 ) -> Option<T> {
861 let proxy = self.pipeline.proxies.get(shape_id as usize)?;
862
863 if self.query_filter.test(proxy.entity, proxy.layers) {
864 Some(f(
865 Some(&proxy.isometry),
866 proxy.collider.shape_scaled().as_ref(),
867 None,
868 ))
869 } else {
870 None
871 }
872 }
873
874 fn map_untyped_part_at<T>(
875 &self,
876 shape_id: u32,
877 mut f: impl FnMut(Option<&Isometry<Scalar>>, &dyn Shape, Option<&dyn NormalConstraints>) -> T,
878 ) -> Option<T> {
879 let proxy = self.pipeline.proxies.get(shape_id as usize)?;
880
881 if self.query_filter.test(proxy.entity, proxy.layers) {
882 Some(f(
883 Some(&proxy.isometry),
884 proxy.collider.shape_scaled().as_ref(),
885 None,
886 ))
887 } else {
888 None
889 }
890 }
891}
892
893pub(crate) struct QueryPipelineAsCompositeShapeWithPredicate<'a, 'b> {
894 pipeline: &'a SpatialQueryPipeline,
895 query_filter: &'a SpatialQueryFilter,
896 predicate: &'b dyn Fn(Entity) -> bool,
897}
898
899impl CompositeShape for QueryPipelineAsCompositeShapeWithPredicate<'_, '_> {
900 fn map_part_at(
901 &self,
902 shape_id: u32,
903 f: &mut dyn FnMut(Option<&Isometry<Scalar>>, &dyn Shape, Option<&dyn NormalConstraints>),
904 ) {
905 self.map_untyped_part_at(shape_id, f);
906 }
907
908 fn bvh(&self) -> &Bvh {
909 &self.pipeline.bvh
910 }
911}
912
913impl TypedCompositeShape for QueryPipelineAsCompositeShapeWithPredicate<'_, '_> {
914 type PartNormalConstraints = ();
915 type PartShape = dyn Shape;
916
917 fn map_typed_part_at<T>(
918 &self,
919 shape_id: u32,
920 mut f: impl FnMut(
921 Option<&Isometry<Scalar>>,
922 &Self::PartShape,
923 Option<&Self::PartNormalConstraints>,
924 ) -> T,
925 ) -> Option<T> {
926 if let Some(proxy) = self.pipeline.proxies.get(shape_id as usize)
927 && self.query_filter.test(proxy.entity, proxy.layers)
928 && (self.predicate)(proxy.entity)
929 {
930 Some(f(
931 Some(&proxy.isometry),
932 proxy.collider.shape_scaled().as_ref(),
933 None,
934 ))
935 } else {
936 None
937 }
938 }
939
940 fn map_untyped_part_at<T>(
941 &self,
942 shape_id: u32,
943 mut f: impl FnMut(Option<&Isometry<Scalar>>, &dyn Shape, Option<&dyn NormalConstraints>) -> T,
944 ) -> Option<T> {
945 if let Some(proxy) = self.pipeline.proxies.get(shape_id as usize)
946 && self.query_filter.test(proxy.entity, proxy.layers)
947 && (self.predicate)(proxy.entity)
948 {
949 Some(f(
950 Some(&proxy.isometry),
951 proxy.collider.shape_scaled().as_ref(),
952 None,
953 ))
954 } else {
955 None
956 }
957 }
958}
959
960/// The result of a [point projection](spatial_query#point-projection) on a [collider](Collider).
961#[derive(Clone, Debug, PartialEq, Reflect)]
962#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
963#[cfg_attr(feature = "serialize", reflect(Serialize, Deserialize))]
964#[reflect(Debug, PartialEq)]
965pub struct PointProjection {
966 /// The entity of the collider that the point was projected onto.
967 pub entity: Entity,
968 /// The point where the point was projected.
969 pub point: Vector,
970 /// True if the point was inside of the collider.
971 pub is_inside: bool,
972}