sectorsync_core/
spatial_index.rs

1//! Low-level cell index for station-local AOI candidate queries.
2
3use std::collections::{HashMap, HashSet};
4
5use crate::ids::EntityHandle;
6use crate::spatial::{Aabb3, Bounds, CellCoord3, GridSpec, Position3};
7
8const MAX_DENSE_DEDUP_SLOTS: usize = 262_144;
9
10/// Occupancy count for one non-empty cell.
11#[derive(Clone, Copy, Debug, PartialEq, Eq)]
12pub struct CellOccupancy {
13    /// Cell coordinate.
14    pub cell: CellCoord3,
15    /// Number of indexed entity handles in the cell.
16    pub entities: usize,
17}
18
19/// Result of inserting or updating one entity in a [`CellIndex`].
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub enum CellIndexUpdate {
22    /// The handle was not indexed and has been inserted.
23    Inserted,
24    /// The handle already occupied the same cells; index storage was untouched.
25    Unchanged,
26    /// The handle moved to a different set of cells.
27    Relocated,
28}
29
30/// Strategy used by the last scratch-backed cell query.
31#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
32pub enum CellQueryStrategy {
33    /// Probe every cell touched by the query bounds.
34    #[default]
35    Grid,
36    /// Scan non-empty cells when the query covers a larger sparse volume.
37    OccupiedCells,
38}
39
40/// Work counters from the last scratch-backed cell query.
41#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
42pub struct CellQueryStats {
43    /// Query strategy selected from query volume and current index occupancy.
44    pub strategy: CellQueryStrategy,
45    /// Grid cells probed directly by a grid query.
46    pub grid_cells_probed: usize,
47    /// Non-empty cells inspected by an occupied-cell scan.
48    pub occupied_cells_scanned: usize,
49    /// Non-empty cells overlapping the query bounds.
50    pub matched_cells: usize,
51    /// Unique candidate handles produced by the query.
52    pub candidate_handles: usize,
53}
54
55/// Reusable scratch storage for allocation-aware cell queries.
56#[derive(Clone, Debug, Default)]
57pub struct CellQueryScratch {
58    seen_dense: Vec<u64>,
59    seen_collisions: Vec<u32>,
60    seen_sparse: HashSet<EntityHandle>,
61    query_epoch: u32,
62    handles: Vec<EntityHandle>,
63    matching_cells: Vec<CellCoord3>,
64    stats: CellQueryStats,
65}
66
67impl CellQueryScratch {
68    /// Clears retained query results while keeping allocated capacity.
69    pub fn clear(&mut self) {
70        self.begin_query();
71        self.handles.clear();
72        self.matching_cells.clear();
73        self.stats = CellQueryStats::default();
74    }
75
76    /// Returns handles produced by the last query.
77    pub fn handles(&self) -> &[EntityHandle] {
78        &self.handles
79    }
80
81    /// Number of handles produced by the last query.
82    pub fn len(&self) -> usize {
83        self.handles.len()
84    }
85
86    /// Returns whether the last query produced no handles.
87    pub fn is_empty(&self) -> bool {
88        self.handles.is_empty()
89    }
90
91    /// Work counters produced by the last query.
92    pub const fn stats(&self) -> CellQueryStats {
93        self.stats
94    }
95
96    /// Capacity retained for unique candidate handles.
97    pub fn handle_capacity(&self) -> usize {
98        self.handles.capacity()
99    }
100
101    /// Capacity retained by the candidate deduplication set.
102    pub fn dedup_capacity(&self) -> usize {
103        self.seen_dense
104            .capacity()
105            .saturating_add(self.seen_collisions.capacity())
106            .saturating_add(self.seen_sparse.capacity())
107    }
108
109    /// Capacity retained for occupied cells matched by sparse queries.
110    pub fn matching_cell_capacity(&self) -> usize {
111        self.matching_cells.capacity()
112    }
113
114    fn begin_query(&mut self) {
115        self.query_epoch = self.query_epoch.wrapping_add(1);
116        if self.query_epoch == 0 {
117            self.seen_dense.fill(0);
118            self.seen_collisions.fill(0);
119            self.query_epoch = 1;
120        }
121        self.seen_sparse.clear();
122    }
123
124    fn insert_seen(&mut self, handle: EntityHandle) -> bool {
125        let Ok(index) = usize::try_from(handle.index()) else {
126            return self.seen_sparse.insert(handle);
127        };
128        if index >= MAX_DENSE_DEDUP_SLOTS {
129            return self.seen_sparse.insert(handle);
130        }
131        if index >= self.seen_dense.len() {
132            self.seen_dense.resize(index + 1, 0);
133            self.seen_collisions.resize(index + 1, 0);
134        }
135        let marker = (u64::from(self.query_epoch) << 32) | u64::from(handle.generation());
136        let previous = self.seen_dense[index];
137        let previous_epoch = u32::try_from(previous >> 32).expect("marker epoch fits u32");
138        if previous_epoch != self.query_epoch {
139            self.seen_dense[index] = marker;
140            true
141        } else if self.seen_collisions[index] == self.query_epoch {
142            self.seen_sparse.insert(handle)
143        } else if previous == marker {
144            false
145        } else {
146            self.seen_collisions[index] = self.query_epoch;
147            let previous_generation =
148                u32::try_from(previous & u64::from(u32::MAX)).expect("marker generation fits u32");
149            self.seen_sparse
150                .insert(EntityHandle::new(handle.index(), previous_generation));
151            self.seen_sparse.insert(handle)
152        }
153    }
154}
155
156/// Internal compact membership representation for point and bounded entities.
157#[derive(Clone, Debug)]
158enum CellMembership {
159    Point(CellCoord3),
160    Multiple(Vec<CellCoord3>),
161}
162
163impl CellMembership {
164    fn as_slice(&self) -> &[CellCoord3] {
165        match self {
166            Self::Point(cell) => std::slice::from_ref(cell),
167            Self::Multiple(cells) => cells,
168        }
169    }
170
171    fn matches_range(&self, min: CellCoord3, max: CellCoord3) -> bool {
172        cells_match_range(self.as_slice(), min, max)
173    }
174}
175
176/// Station-local 3D cell index.
177#[derive(Clone, Debug)]
178pub struct CellIndex {
179    grid: GridSpec,
180    cells: HashMap<CellCoord3, Vec<EntityHandle>>,
181    entity_cells: HashMap<EntityHandle, CellMembership>,
182}
183
184impl CellIndex {
185    /// Creates an empty cell index.
186    pub fn new(grid: GridSpec) -> Self {
187        Self::with_capacity(grid, 0, 0)
188    }
189
190    /// Creates an empty index with explicit entity and occupied-cell capacity.
191    pub fn with_capacity(
192        grid: GridSpec,
193        entity_capacity: usize,
194        occupied_cell_capacity: usize,
195    ) -> Self {
196        Self {
197            grid,
198            cells: HashMap::with_capacity(occupied_cell_capacity),
199            entity_cells: HashMap::with_capacity(entity_capacity),
200        }
201    }
202
203    /// Reserves capacity for additional indexed entities and occupied cells.
204    pub fn reserve(&mut self, additional_entities: usize, additional_cells: usize) {
205        self.entity_cells.reserve(additional_entities);
206        self.cells.reserve(additional_cells);
207    }
208
209    /// Indexed-entity entries currently retained without another rehash.
210    pub fn entity_capacity(&self) -> usize {
211        self.entity_cells.capacity()
212    }
213
214    /// Occupied-cell entries currently retained without another rehash.
215    pub fn occupied_cell_capacity(&self) -> usize {
216        self.cells.capacity()
217    }
218
219    /// Returns the grid spec.
220    pub const fn grid(&self) -> GridSpec {
221        self.grid
222    }
223
224    /// Inserts or updates an entity in all cells touched by its bounds.
225    pub fn upsert(&mut self, handle: EntityHandle, position: Position3, bounds: Bounds) {
226        self.upsert_tracked(handle, position, bounds);
227    }
228
229    /// Inserts or updates an entity and reports whether index membership changed.
230    pub fn upsert_tracked(
231        &mut self,
232        handle: EntityHandle,
233        position: Position3,
234        bounds: Bounds,
235    ) -> CellIndexUpdate {
236        let cells = if bounds == Bounds::Point {
237            let cell = self.grid.cell_at(position);
238            if let Some(old_cell) = self
239                .entity_cells
240                .get(&handle)
241                .and_then(|current| match current {
242                    CellMembership::Point(cell) => Some(*cell),
243                    CellMembership::Multiple(_) => None,
244                })
245            {
246                if old_cell == cell {
247                    return CellIndexUpdate::Unchanged;
248                }
249                self.remove_handle_from_cell(old_cell, handle);
250                self.cells.entry(cell).or_default().push(handle);
251                *self
252                    .entity_cells
253                    .get_mut(&handle)
254                    .expect("indexed point entity retains its cell membership") =
255                    CellMembership::Point(cell);
256                return CellIndexUpdate::Relocated;
257            }
258            CellMembership::Point(cell)
259        } else {
260            let aabb = bounds.to_aabb(position);
261            let min = self.grid.cell_at(aabb.min);
262            let max = self.grid.cell_at(aabb.max);
263            if self
264                .entity_cells
265                .get(&handle)
266                .is_some_and(|current| current.matches_range(min, max))
267            {
268                return CellIndexUpdate::Unchanged;
269            }
270            CellMembership::Multiple(collect_cell_range(min, max))
271        };
272        let existed = self.remove(handle);
273        for cell in cells.as_slice() {
274            self.cells.entry(*cell).or_default().push(handle);
275        }
276        self.entity_cells.insert(handle, cells);
277        if existed {
278            CellIndexUpdate::Relocated
279        } else {
280            CellIndexUpdate::Inserted
281        }
282    }
283
284    /// Removes an entity from the index.
285    pub fn remove(&mut self, handle: EntityHandle) -> bool {
286        let Some(cells) = self.entity_cells.remove(&handle) else {
287            return false;
288        };
289
290        for cell in cells.as_slice() {
291            self.remove_handle_from_cell(*cell, handle);
292        }
293
294        true
295    }
296
297    fn remove_handle_from_cell(&mut self, cell: CellCoord3, handle: EntityHandle) {
298        let remove_cell = if let Some(handles) = self.cells.get_mut(&cell) {
299            if let Some(index) = handles.iter().position(|candidate| *candidate == handle) {
300                handles.remove(index);
301            }
302            handles.is_empty()
303        } else {
304            false
305        };
306        if remove_cell {
307            self.cells.remove(&cell);
308        }
309    }
310
311    /// Queries candidate handles overlapping an AABB.
312    pub fn query_aabb(&self, aabb: Aabb3) -> Vec<EntityHandle> {
313        let mut scratch = CellQueryScratch::default();
314        self.query_aabb_into(aabb, &mut scratch);
315        scratch.handles
316    }
317
318    /// Queries candidate handles overlapping an AABB using caller scratch.
319    pub fn query_aabb_into<'a>(
320        &self,
321        aabb: Aabb3,
322        scratch: &'a mut CellQueryScratch,
323    ) -> &'a [EntityHandle] {
324        scratch.clear();
325        let min = self.grid.cell_at(aabb.min);
326        let max = self.grid.cell_at(aabb.max);
327
328        let grid_cells = query_cell_volume(min, max);
329        if grid_cells <= self.cells.len() {
330            scratch.stats.strategy = CellQueryStrategy::Grid;
331            scratch.stats.grid_cells_probed = grid_cells;
332            for x in min.x..=max.x {
333                for y in min.y..=max.y {
334                    for z in min.z..=max.z {
335                        self.collect_cell(CellCoord3::new(x, y, z), scratch);
336                    }
337                }
338            }
339        } else {
340            scratch.stats.strategy = CellQueryStrategy::OccupiedCells;
341            scratch.stats.occupied_cells_scanned = self.cells.len();
342            scratch.matching_cells.extend(
343                self.cells
344                    .keys()
345                    .copied()
346                    .filter(|cell| cell_in_range(*cell, min, max)),
347            );
348            scratch.matching_cells.sort_unstable();
349            for index in 0..scratch.matching_cells.len() {
350                self.collect_cell(scratch.matching_cells[index], scratch);
351            }
352        }
353
354        scratch.stats.candidate_handles = scratch.handles.len();
355
356        scratch.handles()
357    }
358
359    /// Queries candidate handles inside cells touched by a sphere.
360    pub fn query_sphere(&self, center: Position3, radius: f32) -> Vec<EntityHandle> {
361        self.query_aabb(Bounds::Sphere { radius }.to_aabb(center))
362    }
363
364    /// Queries candidate handles inside cells touched by a sphere using caller scratch.
365    pub fn query_sphere_into<'a>(
366        &self,
367        center: Position3,
368        radius: f32,
369        scratch: &'a mut CellQueryScratch,
370    ) -> &'a [EntityHandle] {
371        self.query_aabb_into(Bounds::Sphere { radius }.to_aabb(center), scratch)
372    }
373
374    fn collect_cell(&self, cell: CellCoord3, scratch: &mut CellQueryScratch) {
375        if let Some(handles) = self.cells.get(&cell) {
376            scratch.stats.matched_cells = scratch.stats.matched_cells.saturating_add(1);
377            for handle in handles {
378                if scratch.insert_seen(*handle) {
379                    scratch.handles.push(*handle);
380                }
381            }
382        }
383    }
384
385    /// Returns handles indexed directly in one cell.
386    pub fn handles_in_cell(&self, cell: CellCoord3) -> Vec<EntityHandle> {
387        self.cells.get(&cell).cloned().unwrap_or_default()
388    }
389
390    /// Returns handles indexed directly in one cell without allocating.
391    pub fn handles_in_cell_slice(&self, cell: CellCoord3) -> &[EntityHandle] {
392        self.cells.get(&cell).map_or(&[], Vec::as_slice)
393    }
394
395    /// Returns cells currently occupied by one entity handle.
396    pub fn cells_for_handle(&self, handle: EntityHandle) -> Option<&[CellCoord3]> {
397        self.entity_cells.get(&handle).map(CellMembership::as_slice)
398    }
399
400    /// Number of indexed entities.
401    pub fn entity_count(&self) -> usize {
402        self.entity_cells.len()
403    }
404
405    /// Number of entities using allocation-free single-cell membership.
406    pub fn point_membership_count(&self) -> usize {
407        self.entity_cells
408            .values()
409            .filter(|membership| matches!(membership, CellMembership::Point(_)))
410            .count()
411    }
412
413    /// Number of non-empty cells.
414    pub fn occupied_cell_count(&self) -> usize {
415        self.cells.len()
416    }
417
418    /// Returns deterministic occupancy counts for all non-empty cells.
419    pub fn cell_occupancy(&self) -> Vec<CellOccupancy> {
420        let mut cells = Vec::with_capacity(self.cells.len());
421        self.cell_occupancy_into(&mut cells);
422        cells
423    }
424
425    /// Writes deterministic occupancy counts into caller-owned reusable storage.
426    pub fn cell_occupancy_into(&self, out: &mut Vec<CellOccupancy>) {
427        out.clear();
428        out.extend(self.cells.iter().map(|(cell, handles)| CellOccupancy {
429            cell: *cell,
430            entities: handles.len(),
431        }));
432        out.sort_by_key(|occupancy| occupancy.cell);
433    }
434}
435
436fn cells_match_range(cells: &[CellCoord3], min: CellCoord3, max: CellCoord3) -> bool {
437    if cells.len() != query_cell_volume(min, max) {
438        return false;
439    }
440    let mut cells = cells.iter();
441    for x in min.x..=max.x {
442        for y in min.y..=max.y {
443            for z in min.z..=max.z {
444                if cells.next() != Some(&CellCoord3::new(x, y, z)) {
445                    return false;
446                }
447            }
448        }
449    }
450    cells.next().is_none()
451}
452
453fn collect_cell_range(min: CellCoord3, max: CellCoord3) -> Vec<CellCoord3> {
454    let mut cells = Vec::with_capacity(query_cell_volume(min, max));
455    for x in min.x..=max.x {
456        for y in min.y..=max.y {
457            for z in min.z..=max.z {
458                cells.push(CellCoord3::new(x, y, z));
459            }
460        }
461    }
462    cells
463}
464
465fn query_cell_volume(min: CellCoord3, max: CellCoord3) -> usize {
466    fn axis_cells(min: i32, max: i32) -> usize {
467        if max < min {
468            return 0;
469        }
470        usize::try_from(i64::from(max) - i64::from(min) + 1).unwrap_or(usize::MAX)
471    }
472
473    axis_cells(min.x, max.x)
474        .saturating_mul(axis_cells(min.y, max.y))
475        .saturating_mul(axis_cells(min.z, max.z))
476}
477
478const fn cell_in_range(cell: CellCoord3, min: CellCoord3, max: CellCoord3) -> bool {
479    cell.x >= min.x
480        && cell.x <= max.x
481        && cell.y >= min.y
482        && cell.y <= max.y
483        && cell.z >= min.z
484        && cell.z <= max.z
485}
486
487#[cfg(test)]
488mod tests {
489    use super::*;
490
491    #[test]
492    fn explicit_index_capacity_is_retained_and_grows_on_request() {
493        let grid = GridSpec::new(10.0).expect("valid grid");
494        let mut index = CellIndex::with_capacity(grid, 8, 4);
495
496        assert!(index.entity_capacity() >= 8);
497        assert!(index.occupied_cell_capacity() >= 4);
498        index.reserve(32, 16);
499        assert!(index.entity_capacity() >= 32);
500        assert!(index.occupied_cell_capacity() >= 16);
501
502        let handle = EntityHandle::new(1, 0);
503        index.upsert(handle, Position3::new(1.0, 2.0, 3.0), Bounds::Point);
504        assert_eq!(
505            index.query_sphere(Position3::new(1.0, 2.0, 3.0), 1.0),
506            vec![handle]
507        );
508    }
509
510    #[test]
511    fn tracked_upsert_skips_same_cell_point_updates() {
512        let grid = GridSpec::new(10.0).expect("valid grid");
513        let mut index = CellIndex::with_capacity(grid, 1, 2);
514        let handle = EntityHandle::new(1, 0);
515        let first_cell = grid.cell_at(Position3::new(1.0, 2.0, 3.0));
516        let second_cell = grid.cell_at(Position3::new(11.0, 2.0, 3.0));
517
518        assert_eq!(
519            index.upsert_tracked(handle, Position3::new(1.0, 2.0, 3.0), Bounds::Point),
520            CellIndexUpdate::Inserted
521        );
522        let entity_capacity = index.entity_capacity();
523        let cell_capacity = index.occupied_cell_capacity();
524        assert_eq!(
525            index.upsert_tracked(handle, Position3::new(9.0, 2.0, 3.0), Bounds::Point),
526            CellIndexUpdate::Unchanged
527        );
528        assert_eq!(index.handles_in_cell_slice(first_cell), &[handle]);
529        assert_eq!(index.entity_capacity(), entity_capacity);
530        assert_eq!(index.occupied_cell_capacity(), cell_capacity);
531
532        assert!(matches!(
533            index.entity_cells.get(&handle),
534            Some(CellMembership::Point(cell)) if *cell == first_cell
535        ));
536        assert_eq!(
537            index.upsert_tracked(handle, Position3::new(11.0, 2.0, 3.0), Bounds::Point),
538            CellIndexUpdate::Relocated
539        );
540        assert!(matches!(
541            index.entity_cells.get(&handle),
542            Some(CellMembership::Point(cell)) if *cell == second_cell
543        ));
544        assert_eq!(index.point_membership_count(), 1);
545        assert!(index.handles_in_cell_slice(first_cell).is_empty());
546        assert_eq!(index.handles_in_cell_slice(second_cell), &[handle]);
547    }
548
549    #[test]
550    fn tracked_upsert_skips_unchanged_multi_cell_bounds() {
551        let grid = GridSpec::new(10.0).expect("valid grid");
552        let mut index = CellIndex::new(grid);
553        let handle = EntityHandle::new(1, 0);
554        let bounds = Bounds::Sphere { radius: 2.0 };
555
556        assert_eq!(
557            index.upsert_tracked(handle, Position3::new(9.0, 0.0, 0.0), bounds),
558            CellIndexUpdate::Inserted
559        );
560        let retained_cells = index
561            .entity_cells
562            .get(&handle)
563            .expect("bounded entity has cells")
564            .as_slice()
565            .as_ptr();
566        assert_eq!(
567            index.upsert_tracked(handle, Position3::new(9.5, 0.0, 0.0), bounds),
568            CellIndexUpdate::Unchanged
569        );
570        assert_eq!(
571            index
572                .entity_cells
573                .get(&handle)
574                .expect("unchanged bounds retain cells")
575                .as_slice()
576                .as_ptr(),
577            retained_cells
578        );
579
580        let relocated_position = Position3::new(12.5, 0.0, 0.0);
581        assert_eq!(
582            index.upsert_tracked(handle, relocated_position, bounds),
583            CellIndexUpdate::Relocated
584        );
585        assert_eq!(
586            index.cells_for_handle(handle),
587            Some(grid.cells_for_bounds(relocated_position, bounds).as_slice())
588        );
589    }
590
591    #[test]
592    fn index_exposes_handles_by_cell() {
593        let grid = GridSpec::new(10.0).expect("valid grid");
594        let mut index = CellIndex::new(grid);
595        let handle = EntityHandle::new(1, 0);
596        index.upsert(handle, Position3::new(1.0, 2.0, 3.0), Bounds::Point);
597        let cell = grid.cell_at(Position3::new(1.0, 2.0, 3.0));
598
599        assert_eq!(index.handles_in_cell(cell), vec![handle]);
600        assert_eq!(index.handles_in_cell_slice(cell), &[handle]);
601        assert!(
602            index
603                .handles_in_cell_slice(CellCoord3::new(99, 99, 99))
604                .is_empty()
605        );
606        assert_eq!(index.cells_for_handle(handle), Some([cell].as_slice()));
607    }
608
609    #[test]
610    fn occupancy_output_is_sorted_and_reuses_capacity() {
611        let grid = GridSpec::new(10.0).expect("valid grid");
612        let mut index = CellIndex::new(grid);
613        let left = EntityHandle::new(1, 0);
614        let right = EntityHandle::new(2, 0);
615        index.upsert(right, Position3::new(21.0, 0.0, 0.0), Bounds::Point);
616        index.upsert(left, Position3::new(-11.0, 0.0, 0.0), Bounds::Point);
617
618        let expected = index.cell_occupancy();
619        let mut occupancy = Vec::new();
620        index.cell_occupancy_into(&mut occupancy);
621        assert_eq!(occupancy, expected);
622        assert!(
623            occupancy
624                .windows(2)
625                .all(|cells| cells[0].cell < cells[1].cell)
626        );
627
628        let retained = occupancy.as_ptr();
629        index.cell_occupancy_into(&mut occupancy);
630        assert_eq!(occupancy, expected);
631        assert_eq!(occupancy.as_ptr(), retained);
632    }
633
634    #[test]
635    fn scratch_query_deduplicates_and_reuses_storage() {
636        let grid = GridSpec::new(10.0).expect("valid grid");
637        let mut index = CellIndex::new(grid);
638        let handle = EntityHandle::new(1, 0);
639        index.upsert(
640            handle,
641            Position3::new(9.0, 0.0, 0.0),
642            Bounds::Sphere { radius: 2.0 },
643        );
644        let mut scratch = CellQueryScratch::default();
645
646        let first = index.query_aabb_into(
647            Bounds::Sphere { radius: 4.0 }.to_aabb(Position3::new(10.0, 0.0, 0.0)),
648            &mut scratch,
649        );
650        assert_eq!(first, &[handle]);
651        assert_eq!(scratch.len(), 1);
652        assert_eq!(scratch.stats().strategy, CellQueryStrategy::Grid);
653        assert_eq!(scratch.stats().candidate_handles, 1);
654        assert!(scratch.handle_capacity() >= 1);
655        assert!(scratch.dedup_capacity() >= 1);
656
657        let second = index.query_aabb_into(
658            Bounds::Point.to_aabb(Position3::new(100.0, 0.0, 0.0)),
659            &mut scratch,
660        );
661        assert!(second.is_empty());
662        assert!(scratch.is_empty());
663    }
664
665    #[test]
666    fn dense_dedup_preserves_generations_and_bounds_sparse_handles() {
667        let grid = GridSpec::new(10.0).expect("valid grid");
668        let mut index = CellIndex::new(grid);
669        let old = EntityHandle::new(7, 1);
670        let current = EntityHandle::new(7, 2);
671        let sparse = EntityHandle::new(u32::MAX, 0);
672        let spanning = Bounds::Sphere { radius: 2.0 };
673        index.upsert(old, Position3::new(9.0, 0.0, 0.0), spanning);
674        index.upsert(current, Position3::new(9.0, 0.0, 0.0), spanning);
675        index.upsert(sparse, Position3::new(9.0, 0.0, 0.0), Bounds::Point);
676        let mut scratch = CellQueryScratch::default();
677
678        let handles = index.query_aabb_into(
679            spanning.to_aabb(Position3::new(10.0, 0.0, 0.0)),
680            &mut scratch,
681        );
682
683        assert_eq!(handles, &[old, current, sparse]);
684        assert!(scratch.dedup_capacity() < MAX_DENSE_DEDUP_SLOTS);
685    }
686
687    #[test]
688    fn sparse_large_query_scans_occupied_cells_deterministically() {
689        let grid = GridSpec::new(10.0).expect("valid grid");
690        let mut index = CellIndex::new(grid);
691        let high = EntityHandle::new(2, 0);
692        let low = EntityHandle::new(1, 0);
693        index.upsert(high, Position3::new(95.0, 0.0, 0.0), Bounds::Point);
694        index.upsert(low, Position3::new(-95.0, 0.0, 0.0), Bounds::Point);
695        let mut scratch = CellQueryScratch::default();
696
697        let handles = index.query_aabb_into(
698            Aabb3::new(
699                Position3::new(-100.0, -100.0, -100.0),
700                Position3::new(100.0, 100.0, 100.0),
701            ),
702            &mut scratch,
703        );
704
705        assert_eq!(handles, &[low, high]);
706        assert_eq!(scratch.stats().strategy, CellQueryStrategy::OccupiedCells);
707        assert_eq!(scratch.stats().occupied_cells_scanned, 2);
708        assert_eq!(scratch.stats().matched_cells, 2);
709        assert_eq!(scratch.stats().candidate_handles, 2);
710        assert!(scratch.matching_cell_capacity() >= 2);
711    }
712}
sectorsync_core/spatial_index.rs

sectorsync_core/
spatial_index.rs
