eightfold 0.1.0

3D space partitioning library
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

use num_traits::AsPrimitive;

use crate::{Error, Octree, ProxyData, TreeIndex};

/// Define how to merge two leaves at the same depth into a single instance, to allow collapsing [Octree] branches.
pub trait LeafMerge: Sized {
    /// Merge two leafs into a single leaf.
    fn leaf_merge(a: Self, b: Self) -> Self;
}

impl<T: LeafMerge, Idx: TreeIndex> Octree<T, Idx> {
    fn internal_merge_branch(&mut self, children_idx: Idx) -> Option<T> {
        debug_assert!(self.branch_data.is_init(children_idx.as_()));
        let mut res: Option<T> = None;
        for c in unsafe { self.branch_data.remove_at_unchecked(children_idx.as_()) }.unwrap() {
            match unsafe { self.proxies.remove_at_unchecked(c.as_()) }
                .unwrap()
                .data
            {
                ProxyData::Void => {}
                ProxyData::Leaf(l_idx) => match res {
                    Some(r) => {
                        res = Some(T::leaf_merge(
                            r,
                            unsafe { self.leaf_data.remove_at_unchecked(l_idx.as_()) }.unwrap(),
                        ))
                    }
                    None => {
                        res = Some(
                            unsafe { self.leaf_data.remove_at_unchecked(l_idx.as_()) }.unwrap(),
                        )
                    }
                },
                ProxyData::Branch(b_idx) => {
                    let data = match self.internal_merge_branch(b_idx) {
                        Some(d) => d,
                        None => continue,
                    };
                    match res {
                        Some(r) => res = Some(T::leaf_merge(r, data)),
                        None => res = Some(data),
                    }
                }
            }
        }
        res
    }

    /// Collapse a branch into a leaf by merging all descendant leaf data.
    ///
    /// All merges occur between leaf data at the same depth.
    pub fn merge_branch(&mut self, branch_idx: Idx) -> Result<&T, Error<Idx>>
    where
        usize: AsPrimitive<Idx>,
    {
        match self
            .proxies
            .get(branch_idx.as_())
            .ok_or(Error::InvalidIndex(branch_idx))?
            .data
        {
            crate::ProxyData::Branch(ch_idx) => match self.internal_merge_branch(ch_idx) {
                Some(r) => {
                    let l_idx = self.leaf_data.push(r);
                    self.proxies[branch_idx.as_()].data = ProxyData::Leaf(l_idx.as_());
                    Ok(&self.leaf_data[l_idx])
                }
                None => {
                    self.proxies[branch_idx.as_()].data = ProxyData::Void;
                    Err(Error::NoLeafs(branch_idx))
                }
            },
            _ => Err(Error::NotABranch(branch_idx)),
        }
    }
}

impl<T> LeafMerge for Vec<T> {
    fn leaf_merge(mut a: Self, mut b: Self) -> Self {
        a.append(&mut b);
        a
    }
}