embedded_3dgfx/bsp/
pvs.rs

1//! PVS (Potentially Visible Set) queries on a [`BspWorld`].
2//!
3//! Two operations are provided:
4//! - [`BspWorld::leaf_for_point`] — O(log N) camera-leaf location.
5//! - [`BspWorld::cluster_visible`] — O(N/8) RLE vis decode to test whether
6//!   one cluster can see another.
7
8use super::data::BspWorld;
9
10impl<'a> BspWorld<'a> {
11    /// Walk the BSP tree to find which leaf contains world-space point `p`.
12    ///
13    /// Iterative — zero stack usage beyond the function call frame.
14    /// Handles degenerate trees (0 nodes) by returning leaf 0.
15    pub fn leaf_for_point(&self, p: [f32; 3]) -> usize {
16        if self.nodes.is_empty() {
17            return 0;
18        }
19        let mut node = 0i32;
20        while node >= 0 {
21            let ni = node as usize;
22            if ni >= self.nodes.len() {
23                break;
24            }
25            let n = &self.nodes[ni];
26            if n.plane as usize >= self.planes.len() {
27                break;
28            }
29            let pl = &self.planes[n.plane as usize];
30            let d = pl.normal[0] * p[0] + pl.normal[1] * p[1] + pl.normal[2] * p[2] - pl.dist;
31            node = n.children[if d >= 0.0 { 0 } else { 1 }];
32        }
33        (!node) as usize
34    }
35
36    /// Test whether `test_cluster` is potentially visible from `from_cluster`.
37    ///
38    /// Returns `true` unconditionally when:
39    /// - `from_cluster < 0` (leaf with no PVS — Quake convention: always visible), **or**
40    /// - The PVS blob is empty (no vis data compiled — developer/test use), **or**
41    /// - `test_cluster == from_cluster` (every cluster sees itself).
42    ///
43    /// Otherwise decodes Quake-style RLE: the vis row for `from_cluster`
44    /// is a stream of non-zero bytes (each byte is 8 cluster bits) and zero
45    /// runs encoded as `[0x00, count]` (skips `count * 8` clusters).
46    pub fn cluster_visible(&self, from_cluster: i16, test_cluster: i16) -> bool {
47        // Always-visible cases
48        if from_cluster < 0 {
49            return true;
50        }
51        if self.vis.is_empty() {
52            return true;
53        }
54        if test_cluster < 0 {
55            return false;
56        }
57        if from_cluster == test_cluster {
58            return true;
59        }
60
61        let fc = from_cluster as usize;
62        if fc >= self.vis_offsets.len() {
63            return false;
64        }
65
66        let mut v = self.vis_offsets[fc] as usize;
67        let mut c = 0i32;
68        let target = test_cluster as i32;
69
70        while c < self.num_clusters as i32 {
71            if v >= self.vis.len() {
72                return false;
73            }
74            if self.vis[v] == 0 {
75                // RLE zero-run: next byte = count of zero bytes to skip
76                if v + 1 >= self.vis.len() {
77                    return false;
78                }
79                c += 8 * self.vis[v + 1] as i32;
80                v += 2;
81            } else {
82                // Non-zero byte: test each of 8 cluster bits
83                let byte = self.vis[v];
84                for bit in 0u8..8 {
85                    if c == target {
86                        return byte & (1 << bit) != 0;
87                    }
88                    c += 1;
89                }
90                v += 1;
91            }
92        }
93        false
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    extern crate std;
100    use super::*;
101    use crate::bsp::data::{Leaf, Node, Plane};
102
103    // Minimal two-leaf BSP: root node splits on X=0.
104    // Plane normal=[1,0,0], dist=0:  d = p.x
105    //   d >= 0 → right side (Room B) → children[0] = !1  (leaf 1)
106    //   d <  0 → left  side (Room A) → children[1] = !0  (leaf 0)
107    static PLANES: [Plane; 1] = [Plane {
108        normal: [1.0, 0.0, 0.0],
109        dist: 0.0,
110    }];
111    static NODES: [Node; 1] = [Node {
112        plane: 0,
113        children: [!1i32, !0i32], // front(d>=0)→leaf1=RoomB, back(d<0)→leaf0=RoomA
114        mins: [-5, -2, -3],
115        maxs: [5, 2, 3],
116        first_face: 0,
117        num_faces: 0,
118    }];
119    static LEAVES: [Leaf; 2] = [
120        Leaf {
121            cluster: 0,
122            mins: [-5, -2, -3],
123            maxs: [0, 2, 3],
124            first_marksurface: 0,
125            num_marksurfaces: 0,
126        },
127        Leaf {
128            cluster: 1,
129            mins: [0, -2, -3],
130            maxs: [5, 2, 3],
131            first_marksurface: 0,
132            num_marksurfaces: 0,
133        },
134    ];
135
136    fn make_world_no_vis<'a>() -> BspWorld<'a> {
137        BspWorld::new(
138            &PLANES,
139            &NODES,
140            &LEAVES,
141            &[],
142            &[],
143            &[],
144            &[],
145            &[],
146            &[],
147            &[],
148            2,
149        )
150    }
151
152    #[test]
153    fn leaf_for_point_room_a() {
154        let w = make_world_no_vis();
155        // d = -2 < 0 → children[1] = !0 → leaf 0
156        let leaf = w.leaf_for_point([-2.0, 0.0, 0.0]);
157        assert_eq!(leaf, 0);
158    }
159
160    #[test]
161    fn leaf_for_point_room_b() {
162        let w = make_world_no_vis();
163        // d = 2 >= 0 → children[0] = !1 → leaf 1
164        let leaf = w.leaf_for_point([2.0, 0.0, 0.0]);
165        assert_eq!(leaf, 1);
166    }
167
168    #[test]
169    fn leaf_for_point_on_plane_goes_front() {
170        let w = make_world_no_vis();
171        let leaf = w.leaf_for_point([0.0, 0.0, 0.0]);
172        assert_eq!(leaf, 1); // d=0 → front child → leaf 1
173    }
174
175    #[test]
176    fn cluster_visible_empty_vis_always_true() {
177        let w = make_world_no_vis();
178        assert!(w.cluster_visible(0, 1));
179        assert!(w.cluster_visible(1, 0));
180    }
181
182    #[test]
183    fn cluster_visible_negative_from_always_true() {
184        let w = make_world_no_vis();
185        assert!(w.cluster_visible(-1, 0));
186        assert!(w.cluster_visible(-1, 99));
187    }
188
189    #[test]
190    fn cluster_visible_same_cluster() {
191        let w = make_world_no_vis();
192        assert!(w.cluster_visible(0, 0));
193        assert!(w.cluster_visible(1, 1));
194    }
195
196    // PVS with 2 clusters, fully visible (no zero runs):
197    // Cluster 0 row: byte 0b00000011 → clusters 0 and 1 visible
198    // Cluster 1 row: byte 0b00000011 → clusters 0 and 1 visible
199    static VIS_FULL: [u8; 2] = [0b00000011, 0b00000011];
200    static VIS_OFFSETS_FULL: [u32; 2] = [0, 1];
201
202    fn make_world_full_vis<'a>() -> BspWorld<'a> {
203        BspWorld::new(
204            &PLANES,
205            &NODES,
206            &LEAVES,
207            &[],
208            &[],
209            &[],
210            &[],
211            &[],
212            &VIS_FULL,
213            &VIS_OFFSETS_FULL,
214            2,
215        )
216    }
217
218    #[test]
219    fn cluster_visible_rle_full_vis() {
220        let w = make_world_full_vis();
221        assert!(w.cluster_visible(0, 0));
222        assert!(w.cluster_visible(0, 1));
223        assert!(w.cluster_visible(1, 0));
224        assert!(w.cluster_visible(1, 1));
225    }
226
227    // PVS where cluster 0 can see itself but NOT cluster 1:
228    // Cluster 0 row: byte 0b00000001 → only cluster 0 visible
229    // Cluster 1 row: byte 0b00000011 → both visible
230    static VIS_PARTIAL: [u8; 2] = [0b00000001, 0b00000011];
231    static VIS_OFFSETS_PARTIAL: [u32; 2] = [0, 1];
232
233    fn make_world_partial_vis<'a>() -> BspWorld<'a> {
234        BspWorld::new(
235            &PLANES,
236            &NODES,
237            &LEAVES,
238            &[],
239            &[],
240            &[],
241            &[],
242            &[],
243            &VIS_PARTIAL,
244            &VIS_OFFSETS_PARTIAL,
245            2,
246        )
247    }
248
249    #[test]
250    fn cluster_visible_rle_partial_vis() {
251        let w = make_world_partial_vis();
252        assert!(w.cluster_visible(0, 0)); // same-cluster shortcut
253        assert!(!w.cluster_visible(0, 1)); // bit 1 not set in row 0
254        assert!(w.cluster_visible(1, 0)); // bit 0 set in row 1
255        assert!(w.cluster_visible(1, 1)); // bit 1 set in row 1
256    }
257
258    // PVS with RLE zero-run: 16 clusters, row 0 visible only in cluster 0.
259    // Encoding: [0x01, 0x00, 0x00] — first byte 0x01 (cluster 0 visible),
260    // then RLE run [0x00, 0x01] skips 8 clusters (1..8), rest don't matter.
261    // Total clusters: 9, cluster 0 in row 0 visible only.
262    static VIS_RLE: [u8; 3] = [0b00000001, 0x00, 0x01];
263    static VIS_OFFSETS_RLE: [u32; 1] = [0];
264
265    fn make_world_rle<'a>() -> BspWorld<'a> {
266        BspWorld::new(
267            &PLANES,
268            &NODES,
269            &LEAVES,
270            &[],
271            &[],
272            &[],
273            &[],
274            &[],
275            &VIS_RLE,
276            &VIS_OFFSETS_RLE,
277            9,
278        )
279    }
280
281    #[test]
282    fn cluster_visible_rle_zero_run() {
283        let w = make_world_rle();
284        assert!(w.cluster_visible(0, 0));
285        // Clusters 1-8 should be invisible (zero run covers them)
286        assert!(!w.cluster_visible(0, 1));
287        assert!(!w.cluster_visible(0, 5));
288        assert!(!w.cluster_visible(0, 8));
289    }
290}
embedded_3dgfx/bsp/pvs.rs

embedded_3dgfx/bsp/
pvs.rs
