bsp-tree 0.2.1

Binary Space Partitioning (BSP) tree useful for 3D rendering. Works with flat polygons (triangles, quads, etc.).
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

//! Visitor pattern for BSP tree traversal.
//!
//! Visitors allow custom processing of polygons during tree traversal
//! without coupling traversal logic to specific use cases.

use crate::Polygon;

/// Visitor for processing polygons during BSP tree traversal.
///
/// Implement this trait to define custom behavior when traversing the tree.
/// Common uses include:
/// - Rendering (painter's algorithm)
/// - Collecting polygons in sorted order
/// - Computing visibility
pub trait BspVisitor {
    /// Called for each group of coplanar polygons during traversal.
    ///
    /// The polygons passed to this method are all coplanar with each other
    /// and belong to the same BSP node.
    fn visit(&mut self, polygons: &[Polygon]);
}

/// A simple visitor that collects all visited polygons.
#[derive(Debug, Default)]
pub struct CollectingVisitor {
    collected: Vec<Polygon>,
}

impl CollectingVisitor {
    /// Creates a new empty collecting visitor.
    pub fn new() -> Self {
        Self::default()
    }

    /// Returns the collected polygons.
    pub fn into_polygons(self) -> Vec<Polygon> {
        self.collected
    }

    /// Returns a reference to the collected polygons.
    pub fn polygons(&self) -> &[Polygon] {
        &self.collected
    }
}

impl BspVisitor for CollectingVisitor {
    fn visit(&mut self, polygons: &[Polygon]) {
        self.collected.extend(polygons.iter().cloned());
    }
}

/// A visitor that calls a closure for each polygon group.
pub struct FnVisitor<F>
where
    F: FnMut(&[Polygon]),
{
    func: F,
}

impl<F> FnVisitor<F>
where
    F: FnMut(&[Polygon]),
{
    /// Creates a new visitor from a closure.
    pub fn new(func: F) -> Self {
        Self { func }
    }
}

impl<F> BspVisitor for FnVisitor<F>
where
    F: FnMut(&[Polygon]),
{
    fn visit(&mut self, polygons: &[Polygon]) {
        (self.func)(polygons);
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use nalgebra::Point3;

    fn make_triangle(a: [f32; 3], b: [f32; 3], c: [f32; 3]) -> Polygon {
        Polygon::new(vec![
            Point3::new(a[0], a[1], a[2]),
            Point3::new(b[0], b[1], b[2]),
            Point3::new(c[0], c[1], c[2]),
        ])
    }

    #[test]
    fn collecting_visitor_empty() {
        let visitor = CollectingVisitor::new();
        assert!(visitor.polygons().is_empty());
    }

    #[test]
    fn collecting_visitor_collects() {
        let mut visitor = CollectingVisitor::new();
        let poly1 = make_triangle([0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]);
        let poly2 = make_triangle([0.0, 0.0, 1.0], [1.0, 0.0, 1.0], [0.0, 1.0, 1.0]);

        visitor.visit(&[poly1.clone()]);
        visitor.visit(&[poly2.clone()]);

        let collected = visitor.into_polygons();
        assert_eq!(collected.len(), 2);
        assert_eq!(collected[0], poly1);
        assert_eq!(collected[1], poly2);
    }

    #[test]
    fn fn_visitor_calls_closure() {
        let mut count = 0;
        {
            let mut visitor = FnVisitor::new(|polys: &[Polygon]| {
                count += polys.len();
            });

            let poly = make_triangle([0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]);
            visitor.visit(&[poly.clone(), poly]);
        }
        assert_eq!(count, 2);
    }
}