1use std::collections::{HashMap, HashSet};
2
3#[derive(Debug, Clone, Copy, PartialEq)]
5pub struct CameraPose {
6 pub x: f64,
7 pub y: f64,
8 pub z: f64,
9 pub yaw: f64,
10 pub pitch: f64,
11}
12
13#[derive(Debug, Clone, Copy, PartialEq, Eq)]
15pub struct StreamBudget {
16 pub max_tiles: usize,
17 pub timestamp: u64,
18}
19
20#[derive(Debug, Clone, PartialEq, Eq)]
22pub struct StreamPlan {
23 pub required_tiles: Vec<u64>,
25 pub evict_tiles: Vec<u64>,
27}
28
29pub struct SceneStreamingPlanner {
31 pub pyramid: TilePyramid,
32 pub predictor: FrustumPredictor,
33 pub eviction: VramBudgetEviction,
34 pub active_lod: u8,
36}
37
38impl SceneStreamingPlanner {
39 pub fn new(
41 pyramid: TilePyramid,
42 predictor: FrustumPredictor,
43 max_tiles: usize,
44 active_lod: u8,
45 ) -> Self {
46 Self {
47 pyramid,
48 predictor,
49 eviction: VramBudgetEviction::new(max_tiles),
50 active_lod,
51 }
52 }
53
54 pub fn plan_stream(&mut self, camera_pose: &CameraPose, budget: &StreamBudget) -> StreamPlan {
56 self.eviction.max_tiles = budget.max_tiles;
57
58 let predicted = self.predictor.predict_intersecting_tiles(
59 camera_pose.x,
60 camera_pose.y,
61 camera_pose.z,
62 camera_pose.yaw,
63 camera_pose.pitch,
64 );
65
66 let mut required_tiles = Vec::new();
67 for tile_id in predicted {
68 if !self.pyramid.has_tile(self.active_lod, tile_id) {
69 continue;
70 }
71 if !self.eviction.active_tiles.contains_key(&tile_id) {
72 required_tiles.push(tile_id);
73 }
74 self.eviction.access_tile(tile_id, budget.timestamp);
75 }
76
77 required_tiles.sort_unstable();
78 required_tiles.dedup();
79
80 let mut evict_tiles = self.eviction.enforce_budget();
81 evict_tiles.sort_unstable();
82
83 StreamPlan {
84 required_tiles,
85 evict_tiles,
86 }
87 }
88}
89
90pub struct FrustumPredictor {
93 pub fov_degrees: f64,
94 pub aspect_ratio: f64,
95 pub near_clip: f64,
96 pub far_clip: f64,
97}
98
99#[inline]
101pub fn point_to_tile_id(x: f64, y: f64, z: f64) -> u64 {
102 ((x / 100.0).floor() as u64) ^ ((y / 100.0).floor() as u64) ^ ((z / 100.0).floor() as u64)
103}
104
105impl FrustumPredictor {
106 pub fn new(fov: f64, aspect: f64, near: f64, far: f64) -> Self {
108 Self {
109 fov_degrees: fov,
110 aspect_ratio: aspect,
111 near_clip: near,
112 far_clip: far,
113 }
114 }
115
116 pub fn predict_intersecting_tiles(
121 &self,
122 camera_x: f64,
123 camera_y: f64,
124 camera_z: f64,
125 yaw: f64,
126 pitch: f64,
127 ) -> Vec<u64> {
128 let mut tiles = HashSet::new();
129
130 let center_tile = point_to_tile_id(camera_x, camera_y, camera_z);
132 tiles.insert(center_tile);
133
134 let yaw_rad = if yaw.abs() > 2.0 * std::f64::consts::PI {
136 yaw.to_radians()
137 } else {
138 yaw
139 };
140 let pitch_rad = if pitch.abs() > 2.0 * std::f64::consts::PI {
141 pitch.to_radians()
142 } else {
143 pitch
144 };
145
146 let cos_p = pitch_rad.cos();
149 let sin_p = pitch_rad.sin();
150 let cos_y = yaw_rad.cos();
151 let sin_y = yaw_rad.sin();
152
153 let fwd = (cos_p * sin_y, sin_p, cos_p * cos_y);
154 let right = (cos_y, 0.0, -sin_y);
155 let up = (
157 right.1 * fwd.2 - right.2 * fwd.1,
158 right.2 * fwd.0 - right.0 * fwd.2,
159 right.0 * fwd.1 - right.1 * fwd.0,
160 );
161
162 let fov_rad = self.fov_degrees.to_radians();
163 let tan_half_fov = (fov_rad * 0.5).tan();
164
165 let near = self.near_clip.max(0.1);
167 let far = self.far_clip.max(near + 1.0);
168 let depth_steps = 8;
169 let uv_samples = [-1.0, -0.5, 0.0, 0.5, 1.0];
170
171 for i in 0..=depth_steps {
172 let t = i as f64 / depth_steps as f64;
173 let d = near + t * (far - near);
174 let half_h = d * tan_half_fov;
175 let half_w = half_h * self.aspect_ratio;
176
177 for &u in &uv_samples {
178 for &v in &uv_samples {
179 let px = camera_x + d * fwd.0 + (u * half_w) * right.0 + (v * half_h) * up.0;
180 let py = camera_y + d * fwd.1 + (u * half_w) * right.1 + (v * half_h) * up.1;
181 let pz = camera_z + d * fwd.2 + (u * half_w) * right.2 + (v * half_h) * up.2;
182
183 tiles.insert(point_to_tile_id(px, py, pz));
184 }
185 }
186 }
187
188 let mut res: Vec<u64> = tiles.into_iter().collect();
189 res.sort_unstable();
190 res
191 }
192
193 pub fn predict_intersecting_pyramid_tiles(
195 &self,
196 camera_pose: &CameraPose,
197 pyramid: &TilePyramid,
198 active_lod: u8,
199 ) -> Vec<u64> {
200 let predicted = self.predict_intersecting_tiles(
201 camera_pose.x,
202 camera_pose.y,
203 camera_pose.z,
204 camera_pose.yaw,
205 camera_pose.pitch,
206 );
207 predicted
208 .into_iter()
209 .filter(|&id| pyramid.has_tile(active_lod, id))
210 .collect()
211 }
212}
213
214pub struct VramBudgetEviction {
216 pub max_tiles: usize,
217 pub active_tiles: HashMap<u64, u64>, }
219
220impl VramBudgetEviction {
221 pub fn new(max_tiles: usize) -> Self {
223 Self {
224 max_tiles,
225 active_tiles: HashMap::new(),
226 }
227 }
228
229 pub fn access_tile(&mut self, tile_id: u64, timestamp: u64) {
231 self.active_tiles.insert(tile_id, timestamp);
232 }
233
234 pub fn enforce_budget(&mut self) -> Vec<u64> {
236 if self.active_tiles.len() <= self.max_tiles {
237 return vec![];
238 }
239
240 let mut sorted: Vec<_> = self.active_tiles.iter().collect();
241 sorted.sort_by_key(|&(_, ts)| *ts);
243
244 let to_evict_count = self.active_tiles.len() - self.max_tiles;
245 let mut evicted = Vec::with_capacity(to_evict_count);
246
247 for (id, _) in sorted.into_iter().take(to_evict_count) {
248 evicted.push(*id);
249 }
250
251 for id in &evicted {
252 self.active_tiles.remove(id);
253 }
254
255 evicted
256 }
257}
258
259pub struct TilePyramid {
261 pub layers: HashMap<u8, HashSet<u64>>, }
263
264impl TilePyramid {
265 pub fn new() -> Self {
267 Self {
268 layers: HashMap::new(),
269 }
270 }
271
272 pub fn register_tile(&mut self, lod: u8, tile_id: u64) {
274 self.layers.entry(lod).or_default().insert(tile_id);
275 }
276
277 pub fn has_tile(&self, lod: u8, tile_id: u64) -> bool {
279 self.layers
280 .get(&lod)
281 .map_or(false, |s| s.contains(&tile_id))
282 }
283}
284
285#[cfg(test)]
286mod tests {
287 use super::*;
288
289 fn tile_id_at(x: f64, y: f64, z: f64) -> u64 {
290 ((x / 100.0).floor() as u64) ^ ((y / 100.0).floor() as u64) ^ ((z / 100.0).floor() as u64)
291 }
292
293 #[test]
294 fn vram_eviction_drops_oldest_first() {
295 let mut evict = VramBudgetEviction::new(2);
296 evict.access_tile(10, 1);
297 evict.access_tile(20, 2);
298 evict.access_tile(30, 3);
299 let dropped = evict.enforce_budget();
300 assert_eq!(dropped, vec![10]);
301 assert!(!evict.active_tiles.contains_key(&10));
302 }
303
304 #[test]
305 fn scene_streaming_planner_requests_missing_tiles() {
306 let mut pyramid = TilePyramid::new();
307 let pose = CameraPose {
308 x: 150.0,
309 y: 250.0,
310 z: 50.0,
311 yaw: 0.0,
312 pitch: 0.0,
313 };
314 let center = tile_id_at(pose.x, pose.y, pose.z);
315 pyramid.register_tile(0, center);
316 pyramid.register_tile(0, center.wrapping_add(1));
317
318 let mut planner = SceneStreamingPlanner::new(
319 pyramid,
320 FrustumPredictor::new(60.0, 16.0 / 9.0, 0.1, 1000.0),
321 8,
322 0,
323 );
324
325 let plan = planner.plan_stream(
326 &pose,
327 &StreamBudget {
328 max_tiles: 8,
329 timestamp: 100,
330 },
331 );
332
333 assert!(plan.required_tiles.contains(¢er));
334 assert!(plan.evict_tiles.is_empty());
335 }
336
337 #[test]
338 fn scene_streaming_planner_evicts_when_over_budget() {
339 let mut pyramid = TilePyramid::new();
340 let pose = CameraPose {
341 x: 100.0,
342 y: 200.0,
343 z: 0.0,
344 yaw: 0.0,
345 pitch: 0.0,
346 };
347 let center = tile_id_at(pose.x, pose.y, pose.z);
348 pyramid.register_tile(0, center);
349 pyramid.register_tile(0, center.wrapping_add(1));
350 pyramid.register_tile(0, center.wrapping_sub(1));
351
352 let mut planner =
353 SceneStreamingPlanner::new(pyramid, FrustumPredictor::new(90.0, 1.0, 0.1, 500.0), 2, 0);
354
355 planner.eviction.access_tile(999, 1);
357 planner.eviction.access_tile(888, 2);
358
359 let plan = planner.plan_stream(
360 &pose,
361 &StreamBudget {
362 max_tiles: 2,
363 timestamp: 50,
364 },
365 );
366
367 assert!(!plan.required_tiles.is_empty());
368 assert!(!plan.evict_tiles.is_empty());
369 assert!(plan.evict_tiles.contains(&999));
370 }
371
372 #[test]
373 fn scene_streaming_planner_skips_unregistered_tiles() {
374 let pyramid = TilePyramid::new();
375 let mut planner = SceneStreamingPlanner::new(
376 pyramid,
377 FrustumPredictor::new(60.0, 16.0 / 9.0, 0.1, 1000.0),
378 4,
379 0,
380 );
381 let plan = planner.plan_stream(
382 &CameraPose {
383 x: 0.0,
384 y: 0.0,
385 z: 0.0,
386 yaw: 0.0,
387 pitch: 0.0,
388 },
389 &StreamBudget {
390 max_tiles: 4,
391 timestamp: 1,
392 },
393 );
394 assert!(plan.required_tiles.is_empty());
395 }
396
397 #[test]
398 fn frustum_predictor_orients_with_yaw_and_pitch() {
399 let predictor = FrustumPredictor::new(60.0, 1.0, 10.0, 500.0);
400 let tiles_north = predictor.predict_intersecting_tiles(0.0, 0.0, 0.0, 0.0, 0.0);
402 let tiles_south =
403 predictor.predict_intersecting_tiles(0.0, 0.0, 0.0, std::f64::consts::PI, 0.0);
404
405 let origin = point_to_tile_id(0.0, 0.0, 0.0);
407 assert!(tiles_north.contains(&origin));
408 assert!(tiles_south.contains(&origin));
409
410 assert_ne!(tiles_north, tiles_south);
412 }
413}