bsp_tree/bsp/
selector.rs

1//! Plane selection strategies for BSP tree construction.
2//!
3//! The choice of splitting plane affects tree balance and the number of
4//! polygon splits during construction. Different strategies offer different
5//! trade-offs between build time and tree quality.
6
7use crate::Polygon;
8
9/// Strategy for selecting which polygon's plane to use for splitting.
10///
11/// The selected polygon's plane becomes the splitting plane for a BSP node.
12/// Different strategies can optimize for:
13/// - Build speed (simple selection)
14/// - Tree balance (minimize depth)
15/// - Minimal splits (preserve original polygons)
16pub trait PlaneSelector {
17    /// Select a polygon from the slice to use as the splitting plane.
18    ///
19    /// Returns `None` if the slice is empty.
20    /// The returned reference must be to an element in the provided slice.
21    fn select<'a>(&self, polygons: &'a [Polygon]) -> Option<&'a Polygon>;
22}
23
24/// Selects the first polygon in the list.
25///
26/// This is the simplest and fastest selector, but may produce unbalanced
27/// trees depending on input order. Good for prototyping and when input
28/// order is already randomized.
29#[derive(Debug, Clone, Copy, Default)]
30pub struct FirstPolygon;
31
32impl PlaneSelector for FirstPolygon {
33    fn select<'a>(&self, polygons: &'a [Polygon]) -> Option<&'a Polygon> {
34        polygons.first()
35    }
36}
37
38#[cfg(test)]
39mod tests {
40    use super::*;
41    use nalgebra::Point3;
42
43    fn make_triangle(a: [f32; 3], b: [f32; 3], c: [f32; 3]) -> Polygon {
44        Polygon::new(vec![
45            Point3::new(a[0], a[1], a[2]),
46            Point3::new(b[0], b[1], b[2]),
47            Point3::new(c[0], c[1], c[2]),
48        ])
49    }
50
51    #[test]
52    fn first_polygon_empty_list() {
53        let selector = FirstPolygon;
54        let polygons: Vec<Polygon> = vec![];
55        assert!(selector.select(&polygons).is_none());
56    }
57
58    #[test]
59    fn first_polygon_single() {
60        let selector = FirstPolygon;
61        let poly = make_triangle([0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]);
62        let polygons = vec![poly.clone()];
63
64        let selected = selector.select(&polygons);
65        assert!(selected.is_some());
66        assert_eq!(selected.unwrap(), &poly);
67    }
68
69    #[test]
70    fn first_polygon_multiple() {
71        let selector = FirstPolygon;
72        let poly1 = make_triangle([0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]);
73        let poly2 = make_triangle([0.0, 0.0, 1.0], [1.0, 0.0, 1.0], [0.0, 1.0, 1.0]);
74        let polygons = vec![poly1.clone(), poly2];
75
76        let selected = selector.select(&polygons);
77        assert!(selected.is_some());
78        assert_eq!(selected.unwrap(), &poly1);
79    }
80}
bsp_tree/bsp/selector.rs

bsp_tree/bsp/
selector.rs
