fart_aabb/
lib.rs

1//! Two dimensional axis-aligned bounding boxes (AABB) and AABB trees.
2//!
3//! Used for fast-but-imprecise collision detection of shapes in a scene. Once
4//! candidates for collision are quickly found using an AABB tree, can determine
5//! if they precisely collide with a more expensive algorithm.
6
7use euclid::Point2D;
8use num_traits::Num;
9use partial_min_max::{max as partial_max, min as partial_min};
10use std::fmt;
11
12/// An axis-aligned bounding box.
13///
14/// * `T` is the numeric type. `i32` or `f64` etc.
15/// * `U` is the unit. `ScreenSpace` or `WorldSpace` etc.
16#[derive(Clone, PartialEq)]
17pub struct Aabb<T, U = euclid::UnknownUnit> {
18    min: Point2D<T, U>,
19    max: Point2D<T, U>,
20}
21
22impl<T, U> fmt::Debug for Aabb<T, U>
23where
24    T: fmt::Debug,
25{
26    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
27        f.debug_struct("Aabb")
28            .field("min", &self.min)
29            .field("max", &self.max)
30            .finish()
31    }
32}
33
34impl<T, U> Aabb<T, U>
35where
36    T: Copy + Num + PartialOrd,
37{
38    /// Construct a new axis-aligned bounding box.
39    ///
40    /// `min`'s `x` and `y` components must be less than or equal to `max`'s.
41    #[inline]
42    pub fn new(min: Point2D<T, U>, max: Point2D<T, U>) -> Aabb<T, U> {
43        assert!(min.x <= max.x);
44        assert!(min.y <= max.y);
45        Aabb { min, max }
46    }
47
48    /// Construct a new axis-aligned bounding box that contains the given set of
49    /// vertices.
50    ///
51    /// # Panics
52    ///
53    /// Panics if `vertices` is empty.
54    pub fn for_vertices<I>(vertices: I) -> Aabb<T, U>
55    where
56        I: IntoIterator<Item = Point2D<T, U>>,
57    {
58        let mut vertices = vertices.into_iter();
59        let first = vertices
60            .next()
61            .expect("Must have at least one vertex to create a bounding box");
62        let mut min = first;
63        let mut max = first;
64        for v in vertices {
65            min.x = partial_min(min.x, v.x);
66            min.y = partial_min(min.y, v.y);
67            max.x = partial_max(max.x, v.x);
68            max.y = partial_max(max.y, v.y);
69        }
70        Aabb::new(min, max)
71    }
72
73    /// Get this AABB's min.
74    #[inline]
75    pub fn min(&self) -> Point2D<T, U> {
76        self.min
77    }
78
79    /// Get this AABB's max.
80    #[inline]
81    pub fn max(&self) -> Point2D<T, U> {
82        self.max
83    }
84
85    /// Get the width of this AABB.
86    #[inline]
87    pub fn width(&self) -> T {
88        self.max.x - self.min.x
89    }
90
91    /// Get the height of this AABB.
92    #[inline]
93    pub fn height(&self) -> T {
94        self.max.y - self.min.y
95    }
96
97    /// Get this AABB's area.
98    #[inline]
99    pub fn area(&self) -> T {
100        (self.max.x - self.min.x) * (self.max.y - self.min.y)
101    }
102
103    /// Return the least upper bound of `self` and `other`.
104    #[inline]
105    pub fn join(&self, other: &Aabb<T, U>) -> Aabb<T, U> {
106        let min = Point2D::new(
107            partial_min(self.min.x, other.min.x),
108            partial_min(self.min.y, other.min.y),
109        );
110        let max = Point2D::new(
111            partial_max(self.max.x, other.max.x),
112            partial_max(self.max.y, other.max.y),
113        );
114        Aabb::new(min, max)
115    }
116
117    /// Does `self` contain `other`?
118    pub fn contains(&self, other: &Aabb<T, U>) -> bool {
119        other.min.x >= self.min.x
120            && other.max.x <= self.max.x
121            && other.min.y >= self.min.y
122            && other.max.y <= self.max.y
123    }
124
125    /// Does `self` contain the point `p`?
126    pub fn contains_point(&self, p: euclid::Point2D<T, U>) -> bool {
127        p.x >= self.min.x && p.x <= self.max.x && p.y >= self.min.y && p.y <= self.max.y
128    }
129
130    /// Does `self` intersect with `other`?
131    pub fn intersects(&self, other: &Aabb<T, U>) -> bool {
132        self.max.x > other.min.x
133            && self.min.x < other.max.x
134            && self.max.y > other.min.y
135            && self.min.y < other.max.y
136    }
137}
138
139/// A tree mapping from axis-aligned bounding boxes to `T` values.
140#[derive(Debug, Default)]
141pub struct AabbTree<T, U, V> {
142    root: Option<AabbTreeNode<T, U, V>>,
143}
144
145#[derive(Debug)]
146enum AabbTreeNode<T, U, V> {
147    Branch(AabbTreeBranch<T, U, V>),
148    Leaf(AabbTreeLeaf<T, U, V>),
149}
150
151#[derive(Debug)]
152struct AabbTreeBranch<T, U, V> {
153    aabb: Aabb<T, U>,
154    children: Box<(AabbTreeNode<T, U, V>, AabbTreeNode<T, U, V>)>,
155}
156
157#[derive(Debug)]
158struct AabbTreeLeaf<T, U, V> {
159    aabb: Aabb<T, U>,
160    value: V,
161}
162
163impl<T, U, V> AabbTree<T, U, V>
164where
165    T: Copy + Num + PartialOrd,
166{
167    /// Construct a new, empty AABB tree.
168    #[inline]
169    pub fn new() -> AabbTree<T, U, V> {
170        AabbTree { root: None }
171    }
172
173    /// Insert the given value into the AABB tree.
174    pub fn insert(&mut self, aabb: Aabb<T, U>, value: V) {
175        let leaf = AabbTreeLeaf { aabb, value };
176        self.root = Some(if let Some(r) = self.root.take() {
177            r.insert(leaf)
178        } else {
179            AabbTreeNode::Leaf(leaf)
180        });
181    }
182
183    /// Iterate over each of the AABB keys and associated values that overlap
184    /// with the given AABB.
185    ///
186    /// Order of iteration is not defined.
187    ///
188    /// ```
189    /// use euclid::Point2D;
190    /// use fart_aabb::{AabbTree, Aabb};
191    ///
192    /// let mut tree = AabbTree::<f64, euclid::UnknownUnit, &str>::new();
193    /// tree.insert(Aabb::new(Point2D::new(0.0, 0.0), Point2D::new(2.0, 2.0)), "Alice");
194    /// tree.insert(Aabb::new(Point2D::new(2.0, 2.0), Point2D::new(4.0, 4.0)), "Bob");
195    /// tree.insert(Aabb::new(Point2D::new(10.0, 10.0), Point2D::new(20.0, 20.0)), "Zed");
196    ///
197    /// let target = Aabb::new(Point2D::new(1.0, 1.0), Point2D::new(3.0, 3.0));
198    /// for (aabb, who) in tree.iter_overlapping(target) {
199    ///     match *who {
200    ///         "Alice" => println!("Found Alice at {:?}", aabb),
201    ///         "Bob" => println!("Found Bob at {:?}", aabb),
202    ///         someone => panic!("Found someone we shouldn't have: {}", someone),
203    ///     }
204    /// }
205    /// ```
206    pub fn iter_overlapping(&self, aabb: Aabb<T, U>) -> IterOverlapping<T, U, V> {
207        let stack = self
208            .root
209            .iter()
210            .filter(|n| n.aabb().intersects(&aabb))
211            .collect();
212        IterOverlapping { aabb, stack }
213    }
214
215    /// Do any of the AABBs in this tree overlap with the give AABB?
216    #[inline]
217    pub fn any_overlap(&self, aabb: Aabb<T, U>) -> bool {
218        self.iter_overlapping(aabb).next().is_some()
219    }
220}
221
222impl<T, U, V> AabbTreeNode<T, U, V>
223where
224    T: Copy + Num + PartialOrd,
225{
226    fn aabb(&self) -> &Aabb<T, U> {
227        match self {
228            AabbTreeNode::Leaf(l) => &l.aabb,
229            AabbTreeNode::Branch(b) => &b.aabb,
230        }
231    }
232
233    fn insert(self, leaf: AabbTreeLeaf<T, U, V>) -> AabbTreeNode<T, U, V> {
234        match self {
235            AabbTreeNode::Leaf(l) => AabbTreeNode::Branch(AabbTreeBranch {
236                aabb: l.aabb.join(&leaf.aabb),
237                children: Box::new((AabbTreeNode::Leaf(l), AabbTreeNode::Leaf(leaf))),
238            }),
239            AabbTreeNode::Branch(branch) => {
240                let combined_aabb = branch.aabb.join(&leaf.aabb);
241                let two = T::one() + T::one();
242                let new_parent_cost = two * combined_aabb.area();
243                let min_push_down_cost = two * (combined_aabb.area() - branch.aabb.area());
244
245                let left_cost = match branch.children.0 {
246                    AabbTreeNode::Leaf(ref l) => {
247                        l.aabb.join(&leaf.aabb).area() + min_push_down_cost
248                    }
249                    AabbTreeNode::Branch(ref b) => {
250                        b.aabb.join(&leaf.aabb).area() - b.aabb.area() + min_push_down_cost
251                    }
252                };
253
254                let right_cost = match branch.children.1 {
255                    AabbTreeNode::Leaf(ref l) => {
256                        l.aabb.join(&leaf.aabb).area() + min_push_down_cost
257                    }
258                    AabbTreeNode::Branch(ref b) => {
259                        b.aabb.join(&leaf.aabb).area() - b.aabb.area() + min_push_down_cost
260                    }
261                };
262
263                AabbTreeNode::Branch(AabbTreeBranch {
264                    aabb: combined_aabb,
265                    children: Box::new(
266                        if new_parent_cost < left_cost && new_parent_cost < right_cost {
267                            (AabbTreeNode::Leaf(leaf), AabbTreeNode::Branch(branch))
268                        } else if left_cost < right_cost {
269                            (branch.children.0.insert(leaf), branch.children.1)
270                        } else {
271                            (branch.children.0, branch.children.1.insert(leaf))
272                        },
273                    ),
274                })
275            }
276        }
277    }
278}
279
280/// An iterator over overlapping AABBs and values in an AABB tree.
281///
282/// See `AabbTree::iter_overlapping`.
283#[derive(Debug, Clone)]
284pub struct IterOverlapping<'a, T, U, V> {
285    aabb: Aabb<T, U>,
286    stack: Vec<&'a AabbTreeNode<T, U, V>>,
287}
288
289impl<'a, T, U, V> Iterator for IterOverlapping<'a, T, U, V>
290where
291    T: Copy + Num + PartialOrd,
292{
293    type Item = (&'a Aabb<T, U>, &'a V);
294
295    fn next(&mut self) -> Option<Self::Item> {
296        loop {
297            match self.stack.pop() {
298                None => return None,
299                Some(AabbTreeNode::Leaf(l)) => {
300                    debug_assert!(l.aabb.intersects(&self.aabb));
301                    return Some((&l.aabb, &l.value));
302                }
303                Some(AabbTreeNode::Branch(b)) => {
304                    if self.aabb.intersects(b.children.0.aabb()) {
305                        self.stack.push(&b.children.0);
306                    }
307                    if self.aabb.intersects(b.children.1.aabb()) {
308                        self.stack.push(&b.children.1);
309                    }
310                }
311            }
312        }
313    }
314}
315
316/// Things that have an axis-aligned bounding box.
317///
318/// While we can construct an AABB from anything with vertices, implementations
319/// of this trait are intended to be the fastest way to get an AABB for the
320/// given `Self` type. For example, we can compute the AABB of a circle
321/// geometrically faster than by sampling points along it and constructing the
322/// AABB of those sampled points.
323pub trait ToAabb<T, U> {
324    /// Get the axis-aligned bounding box for `self`.
325    fn to_aabb(&self) -> Aabb<T, U>;
326}
fart_aabb/lib.rs

fart_aabb/
lib.rs
