plane_split/
bsp.rs

1use crate::{Plane, PlaneCut, Polygon};
2
3use euclid::default::{Point3D, Vector3D};
4use smallvec::SmallVec;
5
6use std::fmt;
7
8#[derive(Copy, Clone, Debug, PartialEq, Eq)]
9pub struct PolygonIdx(usize);
10
11#[derive(Copy, Clone, Debug, PartialEq, Eq)]
12pub struct NodeIdx(usize);
13
14/// Binary Space Partitioning splitter, uses a BSP tree.
15pub struct BspSplitter<A: Copy> {
16    result: Vec<Polygon<A>>,
17    nodes: Vec<BspNode>,
18    polygons: Vec<Polygon<A>>,
19}
20
21impl<A: Copy> BspSplitter<A> {
22    /// Create a new BSP splitter.
23    pub fn new() -> Self {
24        BspSplitter {
25            result: Vec::new(),
26            nodes: vec![BspNode::new()],
27            polygons: Vec::new(),
28        }
29    }
30}
31
32impl<A> BspSplitter<A>
33where
34    A: Copy + fmt::Debug + Default,
35{
36    /// Put the splitter back in it initial state.
37    ///
38    /// Call this at the beginning of every frame when reusing the splitter.
39    pub fn reset(&mut self) {
40        self.polygons.clear();
41        self.nodes.clear();
42        self.nodes.push(BspNode::new());
43    }
44
45    /// Add a polygon to the plane splitter.
46    ///
47    /// This is where most of the expensive computation happens.
48    pub fn add(&mut self, poly: Polygon<A>) {
49        let root = NodeIdx(0);
50        self.insert(root, &poly);
51    }
52
53    /// Sort the added and split polygons against the view vector.
54    ///
55    /// Call this towards the end of the frame after having added all polygons.
56    pub fn sort(&mut self, view: Vector3D<f64>) -> &[Polygon<A>] {
57        //debug!("\t\ttree before sorting {:?}", self.tree);
58        let poly = Polygon {
59            points: [Point3D::origin(); 4],
60            plane: Plane {
61                normal: -view, //Note: BSP `order()` is back to front
62                offset: 0.0,
63            },
64            anchor: A::default(),
65        };
66
67        let root = NodeIdx(0);
68        let mut result = std::mem::take(&mut self.result);
69        result.clear();
70        self.order(root, &poly, &mut result);
71        self.result = result;
72
73        &self.result
74    }
75
76    /// Process a set of polygons at once.
77    pub fn solve(&mut self, input: &[Polygon<A>], view: Vector3D<f64>) -> &[Polygon<A>]
78    where
79        A: Copy,
80    {
81        self.reset();
82        for p in input {
83            self.add(p.clone());
84        }
85        self.sort(view)
86    }
87
88    /// Insert a value into the sub-tree starting with this node.
89    /// This operation may spawn additional leafs/branches of the tree.
90    fn insert(&mut self, node_idx: NodeIdx, value: &Polygon<A>) {
91        let node = &mut self.nodes[node_idx.0];
92        if node.values.is_empty() {
93            node.values.push(add_polygon(&mut self.polygons, value));
94            return;
95        }
96
97        let mut front: SmallVec<[Polygon<A>; 2]> = SmallVec::new();
98        let mut back: SmallVec<[Polygon<A>; 2]> = SmallVec::new();
99        let first = node.values[0].0;
100        match self.polygons[first].cut(value, &mut front, &mut back) {
101            PlaneCut::Sibling => {
102                node.values.push(add_polygon(&mut self.polygons, value));
103            }
104            PlaneCut::Cut => {
105                if front.len() != 0 {
106                    if self.nodes[node_idx.0].front.is_none() {
107                        self.nodes[node_idx.0].front = Some(add_node(&mut self.nodes));
108                    }
109                    let node_front = self.nodes[node_idx.0].front.unwrap();
110                    for p in &front {
111                        self.insert(node_front, p)
112                    }
113                }
114                if back.len() != 0 {
115                    if self.nodes[node_idx.0].back.is_none() {
116                        self.nodes[node_idx.0].back = Some(add_node(&mut self.nodes));
117                    }
118                    let node_back = self.nodes[node_idx.0].back.unwrap();
119                    for p in &back {
120                        self.insert(node_back, p)
121                    }
122                }
123            }
124        }
125    }
126
127    /// Build the draw order of this sub-tree into an `out` vector,
128    /// so that the contained planes are sorted back to front according
129    /// to the view vector defined as the `base` plane front direction.
130    pub fn order(&self, node: NodeIdx, base: &Polygon<A>, out: &mut Vec<Polygon<A>>) {
131        let node = &self.nodes[node.0];
132        let (former, latter) = match node.values.first() {
133            None => return,
134            Some(first) => {
135                if base.is_aligned(&self.polygons[first.0]) {
136                    (node.front, node.back)
137                } else {
138                    (node.back, node.front)
139                }
140            }
141        };
142
143        if let Some(node) = former {
144            self.order(node, base, out);
145        }
146
147        out.reserve(node.values.len());
148        for poly_idx in &node.values {
149            out.push(self.polygons[poly_idx.0].clone());
150        }
151
152        if let Some(node) = latter {
153            self.order(node, base, out);
154        }
155    }
156}
157
158pub fn add_polygon<A: Copy>(polygons: &mut Vec<Polygon<A>>, poly: &Polygon<A>) -> PolygonIdx {
159    let index = PolygonIdx(polygons.len());
160    polygons.push(poly.clone());
161    index
162}
163
164pub fn add_node(nodes: &mut Vec<BspNode>) -> NodeIdx {
165    let index = NodeIdx(nodes.len());
166    nodes.push(BspNode::new());
167    index
168}
169
170/// A node in the `BspTree`, which can be considered a tree itself.
171#[derive(Clone, Debug)]
172pub struct BspNode {
173    values: SmallVec<[PolygonIdx; 4]>,
174    front: Option<NodeIdx>,
175    back: Option<NodeIdx>,
176}
177
178impl BspNode {
179    /// Create a new node.
180    pub fn new() -> Self {
181        BspNode {
182            values: SmallVec::new(),
183            front: None,
184            back: None,
185        }
186    }
187}
plane_split/bsp.rs

plane_split/
bsp.rs
