all_is_cubes/space/light/
queue.rs

1//! [`LightUpdateQueue`] and other types pertaining to the scheduling of light updates.
2
3use alloc::collections::BTreeSet;
4use core::fmt;
5use euclid::Vector3D;
6
7use hashbrown::hash_map::Entry;
8use hashbrown::HashMap as HbHashMap;
9
10use crate::math::{Cube, GridAab, GridCoordinate, GridIter, GridPoint};
11use crate::space::light::PackedLightScalar;
12
13/// An entry in a [`LightUpdateQueue`], specifying a cubes that needs its light updated.
14#[derive(Clone, Copy, Debug, Eq, PartialEq)]
15pub(crate) struct LightUpdateRequest {
16    pub(crate) priority: Priority,
17    pub(crate) cube: Cube,
18}
19
20impl LightUpdateRequest {
21    /// A priority comparison for entries with equal specified priority:
22    /// prefer cubes closer to the origin. (This is for prettier initial startup:
23    /// assuming the viewpoint starts close to the origin it will see good nearby
24    /// lighting sooner.)
25    fn fallback_priority(&self) -> GridCoordinate {
26        const COORD_OFFSET: GridCoordinate = 0;
27
28        let cube = GridPoint::from(self.cube);
29
30        // Give first priority to a half-resolution grid (8 times faster), then its offset
31        // by 1 copy, then further slices of it.
32        let bits = cube.to_vector().map(|c| c.rem_euclid(2) == 0);
33        #[rustfmt::skip]
34        let boost = match bits {
35            Vector3D {x: false, y: false, z: false, _unit } => 1_000_000,
36            Vector3D {x: true, y: true, z: true, _unit } => 900_000,
37            // Now the other cases in arbitrary order
38            Vector3D {x: true, y: false, z: true, _unit } => 500_000,
39            Vector3D {x: true, y: true, z: false, _unit } => 400_000,
40            Vector3D {x: true, y: false, z: false, _unit } => 300_000,
41            Vector3D {x: false, y: false, z: true, _unit } => 200_000,
42            Vector3D {x: false, y: true, z: false, _unit } => 100_000,
43            Vector3D {x: false, y: true, z: true, _unit } => 0,
44        };
45
46        let GridPoint { x, y, z, _unit } = cube.map(|c| if c > 0 { -c } else { c } + COORD_OFFSET);
47        x.saturating_add(y).saturating_add(z).saturating_add(boost)
48    }
49}
50
51impl Ord for LightUpdateRequest {
52    fn cmp(&self, other: &LightUpdateRequest) -> core::cmp::Ordering {
53        self.priority
54            .cmp(&other.priority)
55            .then_with(|| self.fallback_priority().cmp(&other.fallback_priority()))
56            // To obey Ord's contract we must not return equal ordering when unequal by Eq,
57            // so we must break all ties until only completely identical remains.
58            .then_with(|| self.cube.x.cmp(&other.cube.x))
59            .then_with(|| self.cube.y.cmp(&other.cube.y))
60            .then_with(|| self.cube.z.cmp(&other.cube.z))
61    }
62}
63
64impl PartialOrd for LightUpdateRequest {
65    fn partial_cmp(&self, other: &LightUpdateRequest) -> Option<core::cmp::Ordering> {
66        Some(self.cmp(other))
67    }
68}
69
70/// Priorities a [`LightUpdateRequest`] can have.
71#[derive(Clone, Copy, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
72pub(crate) struct Priority(PackedLightScalar);
73impl Priority {
74    /// The cube used to be [`LightStatus::Opaque`] or [`LightStatus::NoRays`],
75    /// but now needs its light computed because of a change in the space contents.
76    /// This is the highest priority because a player is likely to be looking at it.
77    pub const NEWLY_VISIBLE: Self = Self(250);
78
79    /// The cube has no light data computed yet.
80    pub const UNINIT: Self = Self(210);
81
82    /// An approximation was used; the value may be adequate but it should be recomputed ASAP.
83    pub const ESTIMATED: Self = Self(200);
84
85    /// Minimum possible priority value, which is used as a value that never actually
86    /// appears in the queue.
87    ///
88    /// TODO: eliminate this entirely / make Priority a "nonzero" type?
89    pub const MIN: Self = Self(0);
90
91    pub fn from_difference(d: PackedLightScalar) -> Self {
92        // Use only the values between 1 and 128 inclusive as priorities based on difference.
93        Self(d / 2 + 1)
94    }
95}
96
97impl fmt::Debug for Priority {
98    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
99        if *self == Self::NEWLY_VISIBLE {
100            write!(f, "NEWLY_VISIBLE")
101        } else if *self == Self::UNINIT {
102            write!(f, "UNINIT")
103        } else if *self == Self::ESTIMATED {
104            write!(f, "ESTIMATED")
105        } else {
106            fmt::Display::fmt(&self.0, f)
107        }
108    }
109}
110
111/// A priority queue for [`LightUpdateRequest`]s which contains cubes
112/// at most once, even when added with different priorities.
113pub(crate) struct LightUpdateQueue {
114    /// Sorted storage of queue elements.
115    /// This is a `BTreeSet` rather than a `BinaryHeap` so that items can be removed.
116    queue: BTreeSet<LightUpdateRequest>,
117
118    /// Maps [`Cube`] to priority value. This allows deduplicating entries, including
119    /// removing low-priority entries in favor of high-priority ones
120    table: HbHashMap<Cube, Priority>,
121
122    /// If not `None`, then we are performing an update of **every** cube of the space,
123    /// and this iterator returns the next cube to update at `sweep_priority`.
124    sweep: Option<GridIter>,
125
126    /// Priority with which the `sweep` should be performed.
127    sweep_priority: Priority,
128
129    /// Whether a new sweep is needed after the current one.
130    sweep_again: bool,
131}
132
133impl LightUpdateQueue {
134    pub fn new() -> Self {
135        Self {
136            queue: BTreeSet::new(),
137            table: HbHashMap::new(),
138            sweep: None,
139            sweep_priority: Priority::MIN,
140            sweep_again: false,
141        }
142    }
143
144    #[inline]
145    pub fn contains(&self, cube: Cube) -> bool {
146        self.table.contains_key(&cube)
147            || self
148                .sweep
149                .as_ref()
150                .is_some_and(|sweep| sweep.contains_cube(cube))
151    }
152
153    /// Inserts a queue entry or increases the priority of an existing one.
154    #[inline]
155    pub(crate) fn insert(&mut self, request: LightUpdateRequest) {
156        match self.table.entry(request.cube) {
157            Entry::Occupied(mut e) => {
158                let existing_priority = *e.get();
159                if request.priority > existing_priority {
160                    let removed = self.queue.remove(&LightUpdateRequest {
161                        cube: request.cube,
162                        priority: existing_priority,
163                    });
164                    debug_assert!(removed);
165                    e.insert(request.priority);
166                    self.queue.insert(request);
167                }
168            }
169            Entry::Vacant(e) => {
170                e.insert(request.priority);
171                self.queue.insert(request);
172            }
173        }
174    }
175
176    /// Requests that the queue should produce every cube in `bounds` at `priority`,
177    /// without the cost of designating each cube individually.
178    pub(crate) fn sweep(&mut self, bounds: GridAab, priority: Priority) {
179        if self
180            .sweep
181            .as_ref()
182            .is_some_and(|it| it.bounds().contains_box(bounds))
183            && self.sweep_priority >= priority
184        {
185            self.sweep_again = true;
186            self.sweep_priority = Ord::max(self.sweep_priority, priority);
187        } else if self.sweep.is_some() {
188            // Ideally, if we have an existing higher priority sweep, we'd finish it first
189            // and remember the next one, but not bothering with that now.
190            self.sweep = Some(bounds.interior_iter());
191            self.sweep_priority = Ord::max(self.sweep_priority, priority);
192        } else {
193            // No current sweep, so we can ignore existing priority.
194            self.sweep = Some(bounds.interior_iter());
195            self.sweep_priority = priority;
196        }
197    }
198
199    /// Removes the specified queue entry and returns whether it was present.
200    ///
201    /// Sweeps do not count as present entries.
202    pub fn remove(&mut self, cube: Cube) -> bool {
203        if let Some(priority) = self.table.remove(&cube) {
204            let q_removed = self.queue.remove(&LightUpdateRequest { priority, cube });
205            debug_assert!(q_removed);
206            true
207        } else {
208            false
209        }
210    }
211
212    /// Removes and returns the highest priority queue entry.
213    #[inline]
214    #[mutants::skip] // if it fails to pop, causes hangs
215    pub fn pop(&mut self) -> Option<LightUpdateRequest> {
216        if let Some(sweep) = &mut self.sweep {
217            if peek_priority(&self.queue).is_none_or(|p| self.sweep_priority > p) {
218                if let Some(cube) = sweep.next() {
219                    return Some(LightUpdateRequest {
220                        cube,
221                        priority: self.sweep_priority,
222                    });
223                } else {
224                    // Sweep ended
225                    self.sweep = None;
226                    self.sweep_priority = Priority::MIN;
227                }
228            }
229        }
230
231        let result = self.queue.pop_last();
232        if let Some(request) = result {
233            let removed = self.table.remove(&request.cube);
234            debug_assert!(removed.is_some());
235        }
236        result
237    }
238
239    pub fn clear(&mut self) {
240        self.queue.clear();
241        self.table.clear();
242        self.sweep = None;
243        self.sweep_priority = Priority::MIN;
244        self.sweep_again = false;
245    }
246
247    /// Returns the number of elements that will be produced by [`Self::pop()`].
248    #[inline]
249    #[mutants::skip] // can cause infinite loops
250    pub fn len(&self) -> usize {
251        let sweep_items = match &self.sweep {
252            Some(sweep) => {
253                sweep.len()
254                    + if self.sweep_again {
255                        sweep.bounds().volume().unwrap_or(usize::MAX)
256                    } else {
257                        0
258                    }
259            }
260            None => 0,
261        };
262        self.queue.len() + sweep_items
263    }
264
265    #[inline]
266    pub fn peek_priority(&self) -> Priority {
267        peek_priority(&self.queue).unwrap_or(Priority::MIN)
268    }
269}
270
271#[inline]
272fn peek_priority(queue: &BTreeSet<LightUpdateRequest>) -> Option<Priority> {
273    queue.last().copied().map(|r| r.priority)
274}
275
276#[cfg(test)]
277mod tests {
278    use super::*;
279    use alloc::vec::Vec;
280
281    fn drain(queue: &mut LightUpdateQueue) -> Vec<LightUpdateRequest> {
282        Vec::from_iter(std::iter::from_fn(|| queue.pop()))
283    }
284
285    fn r(cube: [GridCoordinate; 3], priority: PackedLightScalar) -> LightUpdateRequest {
286        let priority = Priority(priority);
287        LightUpdateRequest {
288            cube: Cube::from(cube),
289            priority,
290        }
291    }
292
293    #[test]
294    fn priority_relations() {
295        let least_special_priority = [
296            Priority::ESTIMATED,
297            Priority::NEWLY_VISIBLE,
298            Priority::UNINIT,
299        ]
300        .into_iter()
301        .min()
302        .unwrap();
303
304        assert!(Priority::MIN < Priority::from_difference(0));
305        assert!(Priority::from_difference(255) < least_special_priority);
306    }
307
308    #[test]
309    fn queue_ordering() {
310        let mut queue = LightUpdateQueue::new();
311        queue.insert(r([0, 0, 0], 1));
312        queue.insert(r([2, 0, 0], 1));
313        queue.insert(r([1, 0, 0], 1));
314        queue.insert(r([3, 0, 0], 1));
315        queue.insert(r([4, 0, 0], 1));
316        queue.insert(r([3, 0, 0], 1)); // duplicate
317        queue.insert(r([0, 0, 2], 200));
318        queue.insert(r([0, 0, 1], 100));
319
320        assert_eq!(queue.len(), 7);
321        assert_eq!(
322            drain(&mut queue),
323            vec![
324                // High priorities
325                r([0, 0, 2], 200),
326                r([0, 0, 1], 100),
327                // Half-resolution and distance orderings
328                r([0, 0, 0], 1),
329                r([2, 0, 0], 1),
330                r([4, 0, 0], 1),
331                r([1, 0, 0], 1),
332                r([3, 0, 0], 1),
333            ]
334        );
335        assert_eq!(queue.len(), 0);
336    }
337
338    #[test]
339    fn sweep_basic() {
340        let mut queue = LightUpdateQueue::new();
341
342        queue.insert(LightUpdateRequest {
343            priority: Priority(101),
344            cube: Cube::new(0, 101, 0),
345        });
346        queue.insert(LightUpdateRequest {
347            priority: Priority(100),
348            cube: Cube::new(0, 100, 0),
349        });
350        queue.insert(LightUpdateRequest {
351            priority: Priority(99),
352            cube: Cube::new(0, 99, 0),
353        });
354        queue.sweep(
355            GridAab::from_lower_upper([0, 0, 0], [3, 1, 1]),
356            Priority(100),
357        );
358
359        assert_eq!(queue.len(), 6);
360        assert_eq!(
361            drain(&mut queue),
362            vec![
363                // Higher priority than sweep
364                r([0, 101, 0], 101),
365                // Equal priority explicit elements win
366                r([0, 100, 0], 100),
367                // Sweep elements.
368                // Sweeps don't use the interleaved order, not because we don't want to, but
369                // because that is more complex and thus not implemented.
370                r([0, 0, 0], 100),
371                r([1, 0, 0], 100),
372                r([2, 0, 0], 100),
373                // Lower priority than sweep
374                r([0, 99, 0], 99),
375            ]
376        )
377    }
378
379    #[test]
380    fn sweep_then_clear() {
381        let mut queue = LightUpdateQueue::new();
382        queue.sweep(
383            GridAab::from_lower_upper([0, 0, 0], [3, 1, 1]),
384            Priority(100),
385        );
386
387        queue.clear();
388
389        assert_eq!(queue.len(), 0);
390        assert_eq!(queue.pop(), None);
391    }
392
393    // TODO: Test of changing the priority of existing queue entries
394}
all_is_cubes/space/light/queue.rs

all_is_cubes/space/light/
queue.rs
