cadforge_core/
spatial.rs

1//! Spatial indexing.
2//!
3//! An R-tree over element bounds, used for picking, selection-by-region, section boxes, and
4//! the broad phase of clash detection (`docs/ifc-semantics.md` §4.2, §11 Phase 5).
5//!
6//! Bulk-loaded and rebuilt rather than updated in place. A stale index silently returns wrong
7//! answers, which is a far worse failure mode than the cost of a rebuild.
8
9use crate::element::BoundingBox;
10use crate::id::GlobalId;
11use rstar::{RTree, RTreeObject, AABB};
12
13/// An element as the index sees it: an identity and a box, nothing more.
14#[derive(Debug, Clone, PartialEq)]
15pub struct IndexedElement {
16    pub global_id: GlobalId,
17    pub bounds: BoundingBox,
18}
19
20impl RTreeObject for IndexedElement {
21    type Envelope = AABB<[f64; 3]>;
22
23    fn envelope(&self) -> Self::Envelope {
24        AABB::from_corners(self.bounds.min.to_array(), self.bounds.max.to_array())
25    }
26}
27
28/// A spatial index over elements with evaluated geometry.
29#[derive(Debug, Clone, Default)]
30pub struct SpatialIndex {
31    tree: RTree<IndexedElement>,
32}
33
34impl SpatialIndex {
35    pub fn build(elements: impl IntoIterator<Item = IndexedElement>) -> Self {
36        // Bulk loading builds a far better-balanced tree than repeated insertion.
37        Self {
38            tree: RTree::bulk_load(elements.into_iter().collect()),
39        }
40    }
41
42    pub fn len(&self) -> usize {
43        self.tree.size()
44    }
45
46    pub fn is_empty(&self) -> bool {
47        self.tree.size() == 0
48    }
49
50    /// Everything whose bounds intersect the query box.
51    pub fn query(&self, bounds: &BoundingBox) -> Vec<&IndexedElement> {
52        if bounds.is_empty() {
53            return Vec::new();
54        }
55        let envelope = AABB::from_corners(bounds.min.to_array(), bounds.max.to_array());
56        self.tree
57            .locate_in_envelope_intersecting(envelope)
58            .collect()
59    }
60
61    /// Identities of everything intersecting the query box, in stable order.
62    ///
63    /// The R-tree yields results in traversal order, which depends on tree shape. Sorting
64    /// keeps selection results reproducible across rebuilds — which matters for tests and for
65    /// anything user-visible.
66    pub fn query_ids(&self, bounds: &BoundingBox) -> Vec<GlobalId> {
67        let mut ids: Vec<GlobalId> = self
68            .query(bounds)
69            .into_iter()
70            .map(|e| e.global_id.clone())
71            .collect();
72        ids.sort();
73        ids
74    }
75
76    pub fn iter(&self) -> impl Iterator<Item = &IndexedElement> {
77        self.tree.iter()
78    }
79}
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84    use glam::DVec3;
85
86    fn cube_at(x: f64) -> IndexedElement {
87        IndexedElement {
88            global_id: GlobalId::new(),
89            bounds: BoundingBox::new(DVec3::new(x, 0.0, 0.0), DVec3::new(x + 1.0, 1.0, 1.0)),
90        }
91    }
92
93    #[test]
94    fn finds_only_what_overlaps() {
95        let cubes: Vec<_> = (0..10).map(|i| cube_at(i as f64 * 10.0)).collect();
96        let expected = cubes[3].global_id.clone();
97        let index = SpatialIndex::build(cubes);
98        assert_eq!(index.len(), 10);
99
100        let hits = index.query_ids(&BoundingBox::new(
101            DVec3::new(30.2, 0.2, 0.2),
102            DVec3::new(30.8, 0.8, 0.8),
103        ));
104        assert_eq!(hits, vec![expected]);
105    }
106
107    #[test]
108    fn an_empty_query_box_matches_nothing() {
109        let index = SpatialIndex::build((0..5).map(|i| cube_at(i as f64)));
110        assert!(index.query_ids(&BoundingBox::empty()).is_empty());
111    }
112
113    #[test]
114    fn a_box_spanning_everything_matches_everything() {
115        let index = SpatialIndex::build((0..64).map(|i| cube_at(i as f64 * 2.0)));
116        let all = index.query_ids(&BoundingBox::new(
117            DVec3::splat(-1000.0),
118            DVec3::splat(1000.0),
119        ));
120        assert_eq!(all.len(), 64);
121    }
122
123    #[test]
124    fn results_are_order_stable_across_rebuilds() {
125        let cubes: Vec<_> = (0..32).map(|i| cube_at(i as f64)).collect();
126        let query = BoundingBox::new(DVec3::new(4.0, 0.0, 0.0), DVec3::new(9.0, 1.0, 1.0));
127
128        let forward = SpatialIndex::build(cubes.clone()).query_ids(&query);
129        let reversed = SpatialIndex::build(cubes.into_iter().rev()).query_ids(&query);
130        assert_eq!(forward, reversed);
131    }
132
133    #[test]
134    fn an_empty_index_answers_without_panicking() {
135        let index = SpatialIndex::default();
136        assert!(index.is_empty());
137        assert!(index
138            .query_ids(&BoundingBox::new(DVec3::ZERO, DVec3::ONE))
139            .is_empty());
140    }
141}
cadforge_core/spatial.rs

cadforge_core/
spatial.rs
