spatialrust_lod/
planner.rs

1use std::collections::BTreeSet;
2
3use spatialrust_math::Vec3;
4use spatialrust_viz::{Camera, Projection};
5
6use crate::{LodBudgets, LodError, LodIndex, LodResult, NodeId};
7
8/// Screen-space refinement and hysteresis settings.
9#[derive(Clone, Copy, Debug, PartialEq)]
10pub struct LodPlannerOptions {
11    /// Enter refinement above this projected error in pixels.
12    pub refine_enter_pixels: f32,
13    /// Leave refinement below this lower projected error in pixels.
14    pub refine_exit_pixels: f32,
15    /// Logical viewport height in pixels.
16    pub viewport_height: u32,
17}
18
19impl LodPlannerOptions {
20    /// Validates positive thresholds with exit below enter.
21    pub fn validate(self) -> LodResult<()> {
22        if !self.refine_enter_pixels.is_finite()
23            || !self.refine_exit_pixels.is_finite()
24            || self.refine_exit_pixels <= 0.0
25            || self.refine_enter_pixels <= self.refine_exit_pixels
26            || self.viewport_height == 0
27        {
28            return Err(LodError::InvalidPlanner(
29                "refinement thresholds require 0 < exit < enter and a non-zero viewport".into(),
30            ));
31        }
32        Ok(())
33    }
34}
35
36/// One deterministic camera-driven LOD decision.
37#[derive(Clone, Debug, Default, PartialEq, Eq)]
38pub struct LodPlan {
39    /// Camera-visible nodes admitted by point/request budgets.
40    pub desired: Vec<NodeId>,
41    /// Resident desired nodes or resident ancestors retained for continuity.
42    pub display: Vec<NodeId>,
43    /// Desired nodes that must be requested.
44    pub request: Vec<NodeId>,
45    /// Obsolete in-flight nodes to cancel.
46    pub cancel: Vec<NodeId>,
47    /// Visible candidates denied by hard plan budgets.
48    pub denied: Vec<NodeId>,
49    /// Monotonic plan generation.
50    pub generation: u64,
51}
52
53/// Stateful planner retaining only hysteresis/refinement state.
54#[derive(Clone, Debug)]
55pub struct LodPlanner {
56    options: LodPlannerOptions,
57    refined: BTreeSet<NodeId>,
58    generation: u64,
59}
60
61impl LodPlanner {
62    /// Creates a validated planner.
63    pub fn try_new(options: LodPlannerOptions) -> LodResult<Self> {
64        options.validate()?;
65        Ok(Self { options, refined: BTreeSet::new(), generation: 0 })
66    }
67
68    /// Plans selection, requests, cancellation, and progressive display.
69    ///
70    /// `resident` and `in_flight` are snapshots owned by the caller's explicit
71    /// residency/source layer. Traversal order in the source index cannot affect
72    /// the result.
73    pub fn plan(
74        &mut self,
75        index: &LodIndex,
76        camera: &Camera,
77        aspect: f32,
78        budgets: LodBudgets,
79        resident: &BTreeSet<NodeId>,
80        in_flight: &BTreeSet<NodeId>,
81    ) -> LodResult<LodPlan> {
82        self.options.validate()?;
83        budgets.validate()?;
84        Camera::try_new(camera.eye, camera.target, camera.up, camera.projection)
85            .map_err(|error| LodError::InvalidPlanner(error.to_string()))?;
86        if !aspect.is_finite() || aspect <= 0.0 {
87            return Err(LodError::InvalidPlanner(
88                "camera aspect must be finite and positive".into(),
89            ));
90        }
91        self.generation = self
92            .generation
93            .checked_add(1)
94            .ok_or_else(|| LodError::InvalidPlanner("LOD plan generation overflow".into()))?;
95
96        let view = CameraView::try_new(*camera, aspect, self.options.viewport_height)?;
97        let mut candidates = Vec::new();
98        let mut next_refined = BTreeSet::new();
99        for root in index.roots() {
100            self.collect(index, *root, &view, &mut candidates, &mut next_refined)?;
101        }
102        self.refined = next_refined;
103
104        candidates.sort_by(|a, b| {
105            b.screen_error.total_cmp(&a.screen_error).then_with(|| a.id.cmp(&b.id))
106        });
107        let mut desired = Vec::new();
108        let mut denied = Vec::new();
109        let mut points = 0_u64;
110        let mut request_bytes = 0_u64;
111        let mut new_requests = 0_usize;
112        for candidate in candidates {
113            let node = index.node(candidate.id).expect("candidate comes from index");
114            let next_points = points.checked_add(node.point_count);
115            let needs_request = !resident.contains(&node.id) && !in_flight.contains(&node.id);
116            let next_request_bytes =
117                request_bytes.checked_add(if needs_request { node.upload_bytes } else { 0 });
118            let next_requests = new_requests + usize::from(needs_request);
119            if next_points.map_or(true, |value| value > budgets.max_points)
120                || next_request_bytes
121                    .map_or(true, |value| value > budgets.max_upload_bytes_per_frame)
122                || next_requests > budgets.max_in_flight
123            {
124                denied.push(node.id);
125                continue;
126            }
127            points = next_points.expect("checked above");
128            request_bytes = next_request_bytes.expect("checked above");
129            new_requests = next_requests;
130            desired.push(node.id);
131        }
132        desired.sort_unstable();
133        denied.sort_unstable();
134
135        let desired_set: BTreeSet<_> = desired.iter().copied().collect();
136        let request = desired
137            .iter()
138            .copied()
139            .filter(|id| !resident.contains(id) && !in_flight.contains(id))
140            .collect();
141        let cancel = in_flight.iter().copied().filter(|id| !desired_set.contains(id)).collect();
142        let mut display = BTreeSet::new();
143        for id in &desired {
144            if let Some(display_id) =
145                index.nearest_ancestor(*id, |candidate| resident.contains(&candidate))
146            {
147                display.insert(display_id);
148            }
149        }
150        Ok(LodPlan {
151            desired,
152            display: display.into_iter().collect(),
153            request,
154            cancel,
155            denied,
156            generation: self.generation,
157        })
158    }
159
160    fn collect(
161        &self,
162        index: &LodIndex,
163        id: NodeId,
164        view: &CameraView,
165        candidates: &mut Vec<Candidate>,
166        refined: &mut BTreeSet<NodeId>,
167    ) -> LodResult<()> {
168        let node = index.node(id).ok_or(LodError::UnknownNode(id.0))?;
169        let Some(screen_error) = view.screen_error(node.bounds, node.geometric_error) else {
170            return Ok(());
171        };
172        let threshold = if self.refined.contains(&id) {
173            self.options.refine_exit_pixels
174        } else {
175            self.options.refine_enter_pixels
176        };
177        if !node.children.is_empty() && screen_error > threshold {
178            refined.insert(id);
179            for child in &node.children {
180                self.collect(index, *child, view, candidates, refined)?;
181            }
182        } else {
183            candidates.push(Candidate { id, screen_error });
184        }
185        Ok(())
186    }
187}
188
189#[derive(Clone, Copy)]
190struct Candidate {
191    id: NodeId,
192    screen_error: f32,
193}
194
195struct CameraView {
196    eye: Vec3<f32>,
197    forward: Vec3<f32>,
198    right: Vec3<f32>,
199    up: Vec3<f32>,
200    tan_half_vertical: f32,
201    aspect: f32,
202    near: f32,
203    far: f32,
204    viewport_height: f32,
205    orthographic_span: Option<f32>,
206}
207
208impl CameraView {
209    fn try_new(camera: Camera, aspect: f32, viewport_height: u32) -> LodResult<Self> {
210        let forward = subtract(camera.target, camera.eye).normalize();
211        let right = forward.cross(camera.up).normalize();
212        let up = right.cross(forward).normalize();
213        let (tan_half_vertical, near, far, orthographic_span) = match camera.projection {
214            Projection::Perspective { vertical_fov_radians, near, far } => {
215                ((vertical_fov_radians * 0.5).tan(), near, far, None)
216            }
217            Projection::Orthographic { vertical_span, near, far } => {
218                (0.0, near, far, Some(vertical_span))
219            }
220        };
221        Ok(Self {
222            eye: camera.eye,
223            forward,
224            right,
225            up,
226            tan_half_vertical,
227            aspect,
228            near,
229            far,
230            viewport_height: viewport_height as f32,
231            orthographic_span,
232        })
233    }
234
235    fn screen_error(&self, bounds: crate::LodBounds, geometric_error: f32) -> Option<f32> {
236        let center = bounds.center();
237        let radius = bounds.radius();
238        let relative = subtract(center, self.eye);
239        let depth = relative.dot(self.forward);
240        if depth + radius < self.near || depth - radius > self.far {
241            return None;
242        }
243        let horizontal = relative.dot(self.right).abs();
244        let vertical = relative.dot(self.up).abs();
245        if let Some(span) = self.orthographic_span {
246            if vertical - radius > span * 0.5 || horizontal - radius > span * self.aspect * 0.5 {
247                return None;
248            }
249            return Some(geometric_error * self.viewport_height / span);
250        }
251        if depth + radius <= 0.0
252            || vertical - radius > depth.max(0.0) * self.tan_half_vertical
253            || horizontal - radius > depth.max(0.0) * self.tan_half_vertical * self.aspect
254        {
255            return None;
256        }
257        Some(
258            geometric_error * self.viewport_height
259                / (2.0 * depth.max(self.near) * self.tan_half_vertical),
260        )
261    }
262}
263
264fn subtract(lhs: Vec3<f32>, rhs: Vec3<f32>) -> Vec3<f32> {
265    Vec3::new(lhs.x - rhs.x, lhs.y - rhs.y, lhs.z - rhs.z)
266}
267
268#[cfg(test)]
269mod tests {
270    use std::collections::BTreeSet;
271
272    use spatialrust_math::Vec3;
273    use spatialrust_viz::{Camera, Projection};
274
275    use crate::{LodBounds, LodBudgets, LodIndex, LodNode, LodPlanner, LodPlannerOptions, NodeId};
276
277    fn index(reverse_children: bool) -> LodIndex {
278        let bounds =
279            LodBounds::try_new(Vec3::new(-1.0, -1.0, -1.0), Vec3::new(1.0, 1.0, 1.0)).unwrap();
280        let mut children = vec![NodeId(2), NodeId(1)];
281        if !reverse_children {
282            children.reverse();
283        }
284        LodIndex::try_new([
285            LodNode {
286                id: NodeId(0),
287                parent: None,
288                children,
289                bounds,
290                geometric_error: 1.0,
291                point_count: 100,
292                host_bytes: 400,
293                upload_bytes: 400,
294                gpu_bytes: 400,
295            },
296            LodNode {
297                id: NodeId(1),
298                parent: Some(NodeId(0)),
299                children: Vec::new(),
300                bounds: LodBounds::try_new(Vec3::new(-1.0, -1.0, -1.0), Vec3::new(0.0, 1.0, 1.0))
301                    .unwrap(),
302                geometric_error: 0.05,
303                point_count: 40,
304                host_bytes: 160,
305                upload_bytes: 160,
306                gpu_bytes: 160,
307            },
308            LodNode {
309                id: NodeId(2),
310                parent: Some(NodeId(0)),
311                children: Vec::new(),
312                bounds: LodBounds::try_new(Vec3::new(0.0, -1.0, -1.0), Vec3::new(1.0, 1.0, 1.0))
313                    .unwrap(),
314                geometric_error: 0.05,
315                point_count: 60,
316                host_bytes: 240,
317                upload_bytes: 240,
318                gpu_bytes: 240,
319            },
320        ])
321        .unwrap()
322    }
323
324    fn camera(z: f32) -> Camera {
325        Camera::try_new(
326            Vec3::new(0.0, 0.0, z),
327            Vec3::new(0.0, 0.0, 0.0),
328            Vec3::new(0.0, 1.0, 0.0),
329            Projection::Perspective { vertical_fov_radians: 1.0, near: 0.1, far: 100.0 },
330        )
331        .unwrap()
332    }
333
334    fn budgets() -> LodBudgets {
335        LodBudgets {
336            max_points: 1_000,
337            max_host_bytes: 1_000,
338            max_gpu_bytes: 1_000,
339            max_upload_bytes_per_frame: 1_000,
340            max_in_flight: 8,
341        }
342    }
343
344    #[test]
345    fn selection_is_traversal_order_independent_and_progressive() {
346        let options = LodPlannerOptions {
347            refine_enter_pixels: 20.0,
348            refine_exit_pixels: 15.0,
349            viewport_height: 600,
350        };
351        let resident = BTreeSet::from([NodeId(0)]);
352        let mut a = LodPlanner::try_new(options).unwrap();
353        let mut b = LodPlanner::try_new(options).unwrap();
354        let first = a
355            .plan(&index(false), &camera(5.0), 1.0, budgets(), &resident, &BTreeSet::new())
356            .unwrap();
357        let second = b
358            .plan(&index(true), &camera(5.0), 1.0, budgets(), &resident, &BTreeSet::new())
359            .unwrap();
360        assert_eq!(first.desired, second.desired);
361        assert_eq!(first.request, vec![NodeId(1), NodeId(2)]);
362        assert_eq!(first.display, vec![NodeId(0)]);
363    }
364
365    #[test]
366    fn hysteresis_resists_small_camera_jitter_and_cancels_obsolete_requests() {
367        let options = LodPlannerOptions {
368            refine_enter_pixels: 60.0,
369            refine_exit_pixels: 45.0,
370            viewport_height: 600,
371        };
372        let mut planner = LodPlanner::try_new(options).unwrap();
373        let index = index(false);
374        let first = planner
375            .plan(&index, &camera(8.0), 1.0, budgets(), &BTreeSet::new(), &BTreeSet::new())
376            .unwrap();
377        let in_flight: BTreeSet<_> = first.request.iter().copied().collect();
378        let jittered = planner
379            .plan(&index, &camera(8.1), 1.0, budgets(), &BTreeSet::new(), &in_flight)
380            .unwrap();
381        assert_eq!(first.desired, jittered.desired);
382        let far = planner
383            .plan(&index, &camera(40.0), 1.0, budgets(), &BTreeSet::new(), &in_flight)
384            .unwrap();
385        assert_eq!(far.desired, vec![NodeId(0)]);
386        assert_eq!(far.cancel, vec![NodeId(1), NodeId(2)]);
387    }
388
389    #[test]
390    fn point_upload_and_inflight_budgets_fail_before_admission() {
391        let mut planner = LodPlanner::try_new(LodPlannerOptions {
392            refine_enter_pixels: 20.0,
393            refine_exit_pixels: 10.0,
394            viewport_height: 600,
395        })
396        .unwrap();
397        let mut limited = budgets();
398        limited.max_points = 50;
399        limited.max_upload_bytes_per_frame = 200;
400        limited.max_in_flight = 1;
401        let plan = planner
402            .plan(&index(false), &camera(5.0), 1.0, limited, &BTreeSet::new(), &BTreeSet::new())
403            .unwrap();
404        assert_eq!(plan.desired, vec![NodeId(1)]);
405        assert_eq!(plan.denied, vec![NodeId(2)]);
406    }
407}
spatialrust_lod/planner.rs

spatialrust_lod/
planner.rs
