binary_space_partition/
lib.rs

1/*!
2Binary Space Partitioning (BSP)
3
4Provides an abstract `BspNode` structure, which can be seen as a tree.
5Useful for quickly ordering polygons along a particular view vector.
6Is not tied to a particular math library.
7*/
8#![warn(missing_docs)]
9
10use std::cmp;
11
12
13/// The result of one plane being cut by another one.
14/// The "cut" here is an attempt to classify a plane as being
15/// in front or in the back of another one.
16#[derive(Debug)]
17pub enum PlaneCut<T> {
18    /// The planes are one the same geometrical plane.
19    Sibling(T),
20    /// Planes are different, thus we can either determine that
21    /// our plane is completely in front/back of another one,
22    /// or split it into these sub-groups.
23    Cut {
24        /// Sub-planes in front of the base plane.
25        front: Vec<T>,
26        /// Sub-planes in the back of the base plane.
27        back: Vec<T>,
28    },
29}
30
31/// A plane abstracted to the matter of partitioning.
32pub trait Plane: Sized + Clone {
33    /// Try to cut a different plane by this one.
34    fn cut(&self, Self) -> PlaneCut<Self>;
35    /// Check if a different plane is aligned in the same direction
36    /// as this one.
37    fn is_aligned(&self, &Self) -> bool;
38}
39
40/// Add a list of planes to a particular front/end branch of some root node.
41fn add_side<T: Plane>(side: &mut Option<Box<BspNode<T>>>, mut planes: Vec<T>) {
42    if planes.len() != 0 {
43        if side.is_none() {
44            *side = Some(Box::new(BspNode::new()));
45        }
46        let mut node = side.as_mut().unwrap();
47        for p in planes.drain(..) {
48            node.insert(p)
49        }
50    }
51}
52
53
54/// A node in the `BspTree`, which can be considered a tree itself.
55#[derive(Clone, Debug)]
56pub struct BspNode<T> {
57    values: Vec<T>,
58    front: Option<Box<BspNode<T>>>,
59    back: Option<Box<BspNode<T>>>,
60}
61
62impl<T> BspNode<T> {
63    /// Create a new node.
64    pub fn new() -> Self {
65        BspNode {
66            values: Vec::new(),
67            front: None,
68            back: None,
69        }
70    }
71
72    /// Check if this node is a leaf of the tree.
73    pub fn is_leaf(&self) -> bool {
74        self.front.is_none() && self.back.is_none()
75    }
76
77    /// Get the tree depth starting with this node.
78    pub fn get_depth(&self) -> usize {
79        if self.values.is_empty() {
80            return 0
81        }
82        let df = match self.front {
83            Some(ref node) => node.get_depth(),
84            None => 0,
85        };
86        let db = match self.back {
87            Some(ref node) => node.get_depth(),
88            None => 0,
89        };
90        1 + cmp::max(df, db)
91    }
92}
93
94impl<T: Plane> BspNode<T> {
95    /// Insert a value into the sub-tree starting with this node.
96    /// This operation may spawn additional leafs/branches of the tree.
97    pub fn insert(&mut self, value: T) {
98        if self.values.is_empty() {
99            self.values.push(value);
100            return
101        }
102        match self.values[0].cut(value) {
103            PlaneCut::Sibling(value) => self.values.push(value),
104            PlaneCut::Cut { front, back } => {
105                add_side(&mut self.front, front);
106                add_side(&mut self.back, back);
107            }
108        }
109    }
110
111    /// Build the draw order of this sub-tree into an `out` vector,
112    /// so that the contained planes are sorted back to front according
113    /// to the view vector defines as the `base` plane front direction.
114    pub fn order(&self, base: &T, out: &mut Vec<T>) {
115        let (former, latter) = match self.values.first() {
116            None => return,
117            Some(ref first) if base.is_aligned(first) => (&self.front, &self.back),
118            Some(_) => (&self.back, &self.front),
119        };
120
121        if let Some(ref node) = *former {
122            node.order(base, out);
123        }
124
125        out.extend_from_slice(&self.values);
126
127        if let Some(ref node) = *latter {
128            node.order(base, out);
129        }
130    }
131}
132
133
134#[cfg(test)]
135mod tests {
136    extern crate rand;
137    use super::*;
138    use self::rand::Rng;
139
140    #[derive(Clone, Debug, PartialEq)]
141    struct Plane1D(i32, bool);
142
143    impl Plane for Plane1D {
144        fn cut(&self, plane: Self) -> PlaneCut<Self> {
145            if self.0 == plane.0 {
146                PlaneCut::Sibling(plane)
147            } else if (plane.0 > self.0) == self.1 {
148                PlaneCut::Cut {
149                    front: vec![plane],
150                    back: vec![],
151                }
152            } else {
153                PlaneCut::Cut {
154                    front: vec![],
155                    back: vec![plane],
156                }
157            }
158        }
159
160        fn is_aligned(&self, plane: &Self) -> bool {
161            self.1 == plane.1
162        }
163    }
164
165
166    #[test]
167    fn test_add_side() {
168        let mut node_opt = None;
169        let p0: Vec<Plane1D> = Vec::new();
170        add_side(&mut node_opt, p0);
171        assert!(node_opt.is_none());
172
173        let p1 = Plane1D(1, true);
174        add_side(&mut node_opt, vec![p1.clone()]);
175        assert_eq!(node_opt.as_ref().unwrap().values, vec![p1.clone()]);
176        assert!(node_opt.as_ref().unwrap().is_leaf());
177
178        let p23 = vec![Plane1D(0, false), Plane1D(2, false)];
179        add_side(&mut node_opt, p23);
180        let node = node_opt.unwrap();
181        assert_eq!(node.values, vec![p1.clone()]);
182        assert!(node.front.is_some() && node.back.is_some());
183    }
184
185    #[test]
186    fn test_insert_depth() {
187        let mut node = BspNode::new();
188        assert_eq!(node.get_depth(), 0);
189        node.insert(Plane1D(0, true));
190        assert_eq!(node.get_depth(), 1);
191        node.insert(Plane1D(6, true));
192        assert_eq!(node.get_depth(), 2);
193        node.insert(Plane1D(8, true));
194        assert_eq!(node.get_depth(), 3);
195        node.insert(Plane1D(6, true));
196        assert_eq!(node.get_depth(), 3);
197        node.insert(Plane1D(-5, false));
198        assert_eq!(node.get_depth(), 3);
199    }
200
201    #[test]
202    fn test_order() {
203        let mut rng = rand::thread_rng();
204        let mut node = BspNode::new();
205        let mut out = Vec::new();
206
207        node.order(&Plane1D(0, true), &mut out);
208        assert!(out.is_empty());
209
210        for _ in 0 .. 100 {
211            let plane = Plane1D(rng.gen(), rng.gen());
212            node.insert(plane);
213        }
214
215        node.order(&Plane1D(0, true), &mut out);
216        let mut out2 = out.clone();
217        out2.sort_by_key(|p| -p.0);
218        assert_eq!(out, out2);
219    }
220}
binary_space_partition/lib.rs

binary_space_partition/
lib.rs
