embedded_3dgfx/bsp/data.rs
1//! BSP world data structures.
2//!
3//! All lump slices borrow from a `&'static` blob produced by `asset_cli bsp`
4//! (or embedded via `include_bytes!`) — no heap allocation at runtime.
5//!
6//! # Node child encoding
7//! `Node::children[0]` = front child (positive side of splitting plane).
8//! `Node::children[1]` = back child.
9//! Values ≥ 0 are internal node indices; values < 0 encode leaf indices as
10//! `leaf_idx = !child` (one's complement), matching Quake BSP conventions.
11
12/// An axis-aligned splitting plane: `normal · p = dist`.
13#[derive(Clone, Copy, Debug, Default)]
14pub struct Plane {
15 pub normal: [f32; 3],
16 /// Distance from origin along normal.
17 pub dist: f32,
18}
19
20/// Internal BSP node.
21#[derive(Clone, Copy, Debug)]
22pub struct Node {
23 /// Index into `BspWorld::planes`.
24 pub plane: u16,
25 /// Child pointers: ≥0 = node index, <0 = `!leaf_index`.
26 pub children: [i32; 2],
27 /// World-space AABB quantised to i16 for compact storage.
28 pub mins: [i16; 3],
29 pub maxs: [i16; 3],
30 /// Faces associated directly with this node (unused by most renderers).
31 pub first_face: u16,
32 pub num_faces: u16,
33}
34
35/// BSP leaf — the camera lives in exactly one leaf at any moment.
36#[derive(Clone, Copy, Debug)]
37pub struct Leaf {
38 /// PVS cluster id. -1 = no vis data; always visible.
39 pub cluster: i16,
40 pub mins: [i16; 3],
41 pub maxs: [i16; 3],
42 /// Slice into `BspWorld::marksurfaces`.
43 pub first_marksurface: u16,
44 pub num_marksurfaces: u16,
45}
46
47/// One renderable world surface, triangulated into a vertex fan.
48///
49/// The fan spans `world.vertices[first_vert .. first_vert + num_verts]`.
50/// Triangle k (0-based) is `(v0, v[k+1], v[k+2])`.
51#[derive(Clone, Copy, Debug)]
52pub struct Face {
53 /// Start index into `BspWorld::vertices` (and `uvs`, `lm_uvs`).
54 pub first_vert: u32,
55 /// Number of vertices; the face emits `num_verts - 2` triangles.
56 pub num_verts: u16,
57 /// Index into the `TextureManager` (surface albedo).
58 pub texture_id: u32,
59 /// Index into the `TextureManager` for the baked lightmap.
60 /// `0xFFFF` = no lightmap — use full-bright shading.
61 pub lightmap_id: u16,
62 /// Splitting plane this face lies on (for optional back-face skip).
63 pub plane: u16,
64 /// Non-zero if the face's outward normal faces the *back* of `plane`.
65 pub side: u8,
66 /// Optional index into a sector light table.
67 /// `u16::MAX` means "no animated sector light attached".
68 pub sector_light_id: u16,
69}
70
71/// The complete borrowed BSP world.
72///
73/// Construct with [`BspWorld::new`] from your static lumps, then pass a
74/// `&BspWorld` into [`K3dengine::record_bsp`](crate::K3dengine::record_bsp) every frame. No allocator needed.
75pub struct BspWorld<'a> {
76 pub planes: &'a [Plane],
77 pub nodes: &'a [Node],
78 pub leaves: &'a [Leaf],
79 pub faces: &'a [Face],
80 /// Indirection table: `leaves[i].first_marksurface` indexes into this.
81 pub marksurfaces: &'a [u16],
82 pub vertices: &'a [[f32; 3]],
83 /// Per-vertex surface UV coordinates (parallel to `vertices`).
84 pub uvs: &'a [[f32; 2]],
85 /// Per-vertex lightmap UV coordinates (parallel to `vertices`).
86 /// May be empty when lightmaps are unused.
87 pub lm_uvs: &'a [[f32; 2]],
88 /// Quake-style RLE-compressed PVS blob. Empty = always visible.
89 pub vis: &'a [u8],
90 /// `vis_offsets[cluster_id]` = byte offset into `vis` for that cluster.
91 pub vis_offsets: &'a [u32],
92 pub num_clusters: u16,
93}
94
95impl<'a> BspWorld<'a> {
96 #[allow(clippy::too_many_arguments)]
97 pub fn new(
98 planes: &'a [Plane],
99 nodes: &'a [Node],
100 leaves: &'a [Leaf],
101 faces: &'a [Face],
102 marksurfaces: &'a [u16],
103 vertices: &'a [[f32; 3]],
104 uvs: &'a [[f32; 2]],
105 lm_uvs: &'a [[f32; 2]],
106 vis: &'a [u8],
107 vis_offsets: &'a [u32],
108 num_clusters: u16,
109 ) -> Self {
110 Self {
111 planes,
112 nodes,
113 leaves,
114 faces,
115 marksurfaces,
116 vertices,
117 uvs,
118 lm_uvs,
119 vis,
120 vis_offsets,
121 num_clusters,
122 }
123 }
124}
125
126/// A frustum half-space extracted via Gribb-Hartmann.
127///
128/// A world point `p` is *inside* this plane when:
129/// `normal[0]*p.x + normal[1]*p.y + normal[2]*p.z + d >= 0`.
130#[derive(Clone, Copy, Debug)]
131pub struct FrustumPlane {
132 pub normal: [f32; 3],
133 pub d: f32,
134}
135
136#[cfg(test)]
137mod tests {
138 use super::*;
139
140 #[test]
141 fn bsp_world_new_borrows_all_lumps() {
142 let planes = [Plane {
143 normal: [1.0, 0.0, 0.0],
144 dist: 0.0,
145 }];
146 let nodes = [Node {
147 plane: 0,
148 children: [!0i32, !0i32],
149 mins: [-1, -1, -1],
150 maxs: [1, 1, 1],
151 first_face: 0,
152 num_faces: 0,
153 }];
154 let leaves = [Leaf {
155 cluster: 0,
156 mins: [-1, -1, -1],
157 maxs: [1, 1, 1],
158 first_marksurface: 0,
159 num_marksurfaces: 1,
160 }];
161 let faces = [Face {
162 first_vert: 0,
163 num_verts: 3,
164 texture_id: 7,
165 lightmap_id: 0xFFFF,
166 plane: 0,
167 side: 0,
168 sector_light_id: u16::MAX,
169 }];
170 let marksurfaces = [0u16];
171 let vertices = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]];
172 let uvs = [[0.0, 0.0], [1.0, 0.0], [0.0, 1.0]];
173 let lm_uvs = [[0.0, 0.0], [1.0, 0.0], [0.0, 1.0]];
174 let vis = [0b1u8];
175 let vis_offsets = [0u32];
176
177 let world = BspWorld::new(
178 &planes,
179 &nodes,
180 &leaves,
181 &faces,
182 &marksurfaces,
183 &vertices,
184 &uvs,
185 &lm_uvs,
186 &vis,
187 &vis_offsets,
188 1,
189 );
190
191 assert_eq!(world.planes.len(), 1);
192 assert_eq!(world.nodes.len(), 1);
193 assert_eq!(world.leaves.len(), 1);
194 assert_eq!(world.faces[0].texture_id, 7);
195 assert_eq!(world.vertices.len(), 3);
196 assert_eq!(world.uvs.len(), 3);
197 assert_eq!(world.lm_uvs.len(), 3);
198 assert_eq!(world.vis_offsets[0], 0);
199 assert_eq!(world.num_clusters, 1);
200 }
201
202 #[test]
203 fn frustum_plane_inside_test_matches_definition() {
204 let p = FrustumPlane {
205 normal: [1.0, 0.0, 0.0],
206 d: -2.0,
207 };
208 let inside = p.normal[0] * 3.0 + p.normal[1] * 0.0 + p.normal[2] * 0.0 + p.d;
209 let outside = p.normal[0] * 1.0 + p.normal[1] * 0.0 + p.normal[2] * 0.0 + p.d;
210 assert!(inside >= 0.0);
211 assert!(outside < 0.0);
212 }
213}