collision/algorithm/broad_phase/
brute_force.rs

1use crate::prelude::*;
2
3/// Broad phase collision detection brute force implementation.
4///
5/// Will simply do bounding box intersection tests for all shape combinations.
6#[derive(Debug, Default)]
7pub struct BruteForce;
8
9impl BruteForce {
10    /// Find all potentially colliding pairs of shapes.
11    ///
12    /// ## Parameters
13    ///
14    /// - `shapes`: Shapes to do find potential collisions for
15    ///
16    /// ## Returns
17    ///
18    /// Returns tuples with the into the shapes list, of all potentially colliding pairs.
19    /// The first value in the tuple will always be first in the list.
20    pub fn find_collider_pairs<A>(&self, shapes: &[A]) -> Vec<(usize, usize)>
21    where
22        A: HasBound,
23        A::Bound: Discrete<A::Bound>,
24    {
25        let mut pairs = Vec::default();
26        if shapes.len() <= 1 {
27            return pairs;
28        }
29
30        for left_index in 0..(shapes.len() - 1) {
31            let left = &shapes[left_index];
32            for right_index in (left_index + 1)..shapes.len() {
33                if left.bound().intersects(shapes[right_index].bound()) {
34                    pairs.push((left_index, right_index));
35                }
36            }
37        }
38        pairs
39    }
40}
41
42#[cfg(test)]
43mod tests {
44    use cgmath::Point2;
45
46    use super::*;
47    use crate::Aabb2;
48
49    #[derive(Debug, Clone, PartialEq)]
50    pub struct BroadCollisionInfo2 {
51        /// The id
52        pub id: u32,
53
54        /// The bounding volume
55        pub bound: Aabb2<f32>,
56        index: usize,
57    }
58
59    impl BroadCollisionInfo2 {
60        /// Create a new collision info
61        pub fn new(id: u32, bound: Aabb2<f32>) -> Self {
62            Self {
63                id,
64                bound,
65                index: 0,
66            }
67        }
68    }
69
70    impl HasBound for BroadCollisionInfo2 {
71        type Bound = Aabb2<f32>;
72
73        fn bound(&self) -> &Aabb2<f32> {
74            &self.bound
75        }
76    }
77
78    #[test]
79    fn no_intersection_for_miss() {
80        let left = coll(1, 8., 8., 10., 11.);
81
82        let right = coll(2, 12., 13., 18., 18.);
83
84        let brute = BruteForce::default();
85        let potentials = brute.find_collider_pairs(&vec![left, right]);
86        assert_eq!(0, potentials.len());
87    }
88
89    #[test]
90    fn no_intersection_for_miss_unsorted() {
91        let left = coll(1, 8., 8., 10., 11.);
92
93        let right = coll(2, 12., 13., 18., 18.);
94
95        let brute = BruteForce::default();
96        let potentials = brute.find_collider_pairs(&vec![right, left]);
97        assert_eq!(0, potentials.len());
98    }
99
100    #[test]
101    fn intersection_for_hit() {
102        let left = coll(1, 8., 8., 10., 11.);
103
104        let right = coll(2, 9., 10., 18., 18.);
105
106        let brute = BruteForce::default();
107        let potentials = brute.find_collider_pairs(&vec![left.clone(), right.clone()]);
108        assert_eq!(1, potentials.len());
109        assert_eq!((0, 1), potentials[0]);
110    }
111
112    #[test]
113    fn intersection_for_hit_unsorted() {
114        let left = coll(1, 8., 8., 10., 11.);
115
116        let right = coll(222, 9., 10., 18., 18.);
117
118        let brute = BruteForce::default();
119        let potentials = brute.find_collider_pairs(&vec![right.clone(), left.clone()]);
120        assert_eq!(1, potentials.len());
121        assert_eq!((0, 1), potentials[0]);
122    }
123
124    // util
125    fn coll(id: u32, min_x: f32, min_y: f32, max_x: f32, max_y: f32) -> BroadCollisionInfo2 {
126        BroadCollisionInfo2::new(id, bound(min_x, min_y, max_x, max_y))
127    }
128
129    fn bound(min_x: f32, min_y: f32, max_x: f32, max_y: f32) -> Aabb2<f32> {
130        Aabb2::new(Point2::new(min_x, min_y), Point2::new(max_x, max_y))
131    }
132}
collision/algorithm/broad_phase/brute_force.rs

collision/algorithm/broad_phase/
brute_force.rs
