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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

use std::ops::Index;

use glam::Vec2;
use rand::{prelude::SliceRandom, Rng};
use slotmap::*;

use crate::Face;

pub use node::*;
pub use portal::*;
pub use portals::*;

mod node;
mod portal;
mod portals;

type Nodes = SlotMap<NodeIndex, BSPNode>;

new_key_type! {
    /// Represent the index of a [crate::BSPNode]
    pub struct NodeIndex;
}
/// Defines the tree used for navigation
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
pub struct BSPTree {
    nodes: Nodes,
    root: NodeIndex,
    // Bounds
    l: Vec2,
    r: Vec2,
}

impl BSPTree {
    /// Constructs a new tree.
    /// Returns None if there are not faces, and root construction was not possible
    pub fn new(faces: impl Iterator<Item = Face>) -> Option<Self> {
        let faces: Vec<_> = faces.collect();

        Self::new_inner(faces)
    }

    pub fn new_shuffle(faces: impl Iterator<Item = Face>, rng: &mut impl Rng) -> Option<Self> {
        let mut faces: Vec<_> = faces.collect();
        faces.shuffle(rng);

        Self::new_inner(faces)
    }

    fn new_inner(faces: Vec<Face>) -> Option<Self> {
        let mut l = Vec2::new(f32::MAX, f32::MAX);
        let mut r = Vec2::new(f32::MIN, f32::MIN);

        faces.iter().flatten().for_each(|val| {
            l = l.min(val);
            r = r.max(val);
        });

        l -= Vec2::splat(10.0);
        r += Vec2::splat(10.0);

        let mut nodes = SlotMap::with_key();
        let root = BSPNode::from_faces(&mut nodes, &faces, 0)?;

        Some(Self { nodes, root, l, r })
    }

    pub fn node(&self, index: NodeIndex) -> Option<&BSPNode> {
        self.nodes.get(index)
    }

    /// Returns the root index
    pub fn root(&self) -> NodeIndex {
        self.root
    }

    /// Returns a reference to the root node
    pub fn root_node(&self) -> &BSPNode {
        self.node(self.root).expect("Root is always present")
    }

    pub fn descendants(&self) -> Descendants {
        BSPNode::descendants(self.root, &self.nodes)
    }

    /// Returns the containing node and if the point is covered
    pub fn locate(&self, point: Vec2) -> NodePayload {
        let mut index = self.root;

        loop {
            let node = &self.nodes[index];
            let rel = point - node.origin();
            let dot = rel.dot(node.normal());

            let (next, covered) = if dot > 0.0 {
                (node.front(), false)
            } else {
                (node.back(), true)
            };

            if let Some(next) = next {
                index = next
            } else {
                return NodePayload {
                    index,
                    node,
                    covered,
                    depth: -node.normal() * dot,
                };
            }
        }
    }

    /// Get a mutable reference to the bsptree's root.
    pub fn root_mut(&mut self) -> &mut NodeIndex {
        &mut self.root
    }

    /// Get a reference to the bsptree's nodes.
    pub fn nodes(&self) -> &Nodes {
        &self.nodes
    }

    /// Returns clipping planes which contain the scene
    pub fn clipping_planes(&self) -> [Face; 4] {
        [
            Face::new([Vec2::new(self.l.x, self.r.y), self.l]),
            Face::new([self.l, Vec2::new(self.r.x, self.l.y)]),
            Face::new([Vec2::new(self.r.x, self.l.y), self.r]),
            Face::new([self.r, Vec2::new(self.l.x, self.r.y)]),
        ]
    }

    pub fn generate_portals(&self) -> Vec<ClippedFace> {
        let clipping_planes = self.clipping_planes().into_iter().collect();

        let mut portals = Vec::new();
        BSPNode::generate_portals(self.root, &self.nodes, &clipping_planes, &mut portals);
        portals
    }
}

/// Represents the result of [crate::BSPTree::locate]
pub struct NodePayload<'a> {
    pub index: NodeIndex,
    pub node: &'a BSPNode,
    pub covered: bool,
    pub depth: Vec2,
}

impl<'a> NodePayload<'a> {
    /// Get the node payload's node.
    pub fn node(&self) -> &BSPNode {
        self.node
    }

    /// Get the node payload's index.
    pub fn index(&self) -> NodeIndex {
        self.index
    }

    /// Get the node payload's covered.
    pub fn covered(&self) -> bool {
        self.covered
    }

    /// Get the node payload's depth.
    pub fn depth(&self) -> Vec2 {
        self.depth
    }
}

impl Index<NodeIndex> for BSPTree {
    type Output = BSPNode;

    fn index(&self, index: NodeIndex) -> &Self::Output {
        self.node(index).unwrap()
    }
}