broccoli 6.3.0

broadphase collision detection algorithms
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

//!
//! Contains support for verifying query results against naive implementation.
//!

use axgeom::Axis;
use compt::Visitor;

use super::*;

pub(crate) fn into_ptr_usize<T>(a: AabbPin<&mut T>) -> usize {
    let a: &T = &a;
    a as *const T as usize
}

///
/// Easily verifiable naive query algorithms.
///
pub struct Naive<'a, T> {
    pub(crate) inner: AabbPin<&'a mut [T]>,
}
impl<'a, T: Aabb> Naive<'a, T> {
    pub fn new(inner: &'a mut [T]) -> Self {
        Naive {
            inner: AabbPin::from_mut(inner),
        }
    }
    pub fn from_pinned(inner: AabbPin<&'a mut [T]>) -> Self {
        Naive { inner }
    }

    pub fn iter_mut(&mut self) -> AabbPinIter<T> {
        self.inner.borrow_mut().iter_mut()
    }
}

///
/// Compare query results between [`Tree`] and
/// the easily verifiable [`Naive`] versions.
///
pub struct Assert<'a, T> {
    pub(crate) inner: &'a mut [T],
}
impl<'a, T: Aabb> Assert<'a, T> {
    pub fn new(inner: &'a mut [T]) -> Self {
        Assert { inner }
    }
}

///panics if a broken broccoli tree invariant is detected.
///For debugging purposes only.
pub fn assert_tree_invariants<T: Aabb>(tree: &Tree<T>)
where
    T::Num: core::fmt::Debug,
{
    fn inner<A: Axis, T: Aabb>(axis: A, iter: compt::LevelIter<Vistr<Node<T, T::Num>>>)
    where
        T::Num: core::fmt::Debug,
    {
        fn a_bot_has_value<N: Num>(it: impl Iterator<Item = N>, val: N) -> bool {
            for b in it {
                if b == val {
                    return true;
                }
            }
            false
        }

        let ((_depth, nn), rest) = iter.next();
        let axis_next = axis.next();

        assert!(crate::queries::is_sorted_by(&nn.range, |a, b| a
            .range(axis_next)
            .start
            .partial_cmp(&b.range(axis_next).start)));

        if let Some([start, end]) = rest {
            match nn.div {
                Some(div) => {
                    if nn.range.is_empty() {
                        assert_eq!(nn.cont.start, nn.cont.end);
                        let v: T::Num = Default::default();
                        assert_eq!(nn.cont.start, v);
                    } else {
                        let cont = &nn.cont;
                        for bot in nn.range.iter() {
                            assert!(bot.range(axis).contains(div));
                        }

                        assert!(a_bot_has_value(
                            nn.range.iter().map(|b| b.range(axis).start),
                            div
                        ));

                        for bot in nn.range.iter() {
                            assert!(cont.contains_range(bot.range(axis)));
                        }

                        assert!(a_bot_has_value(
                            nn.range.iter().map(|b| b.range(axis).start),
                            cont.start
                        ));
                        assert!(a_bot_has_value(
                            nn.range.iter().map(|b| b.range(axis).end),
                            cont.end
                        ));
                    }

                    inner(axis_next, start);
                    inner(axis_next, end);
                }
                None => {
                    for (_depth, n) in start.dfs_preorder_iter().chain(end.dfs_preorder_iter()) {
                        assert!(n.range.is_empty());
                        //assert!(n.cont.is_none());
                        assert_eq!(n.cont.start, nn.cont.end);
                        let v: T::Num = Default::default();
                        assert_eq!(n.cont.start, v);

                        assert!(n.div.is_none());
                    }
                }
            }
        }
    }

    inner(default_axis(), tree.vistr().with_depth(compt::Depth(0)))
}