blockworx/widget/
spatial.rs

1//! A spatial index over a level's hittable objects, shared by viewport culling
2//! and hit-testing.
3//!
4//! Every shape (block, port, text, image, area) and route on the current
5//! level is stored in one `rstar` R*-tree keyed by its coarse
6//! [`Bounded::bounds`](crate::render::bounds::Bounded) box. Both broad phases —
7//! "which objects are on screen?" (culling) and "which objects are under the
8//! cursor?" (hit-testing) — resolve to an `in_rect` / `at_point` query returning
9//! candidate [`HitId`]s; the caller then runs its exact fine-phase test on the
10//! few candidates instead of scanning the whole level.
11//!
12//! The index owns copies of each object's bounds + id (it holds no reference into
13//! the document), so it can be cached across frames and rebuilt whenever the
14//! document value ([`DocStamp`]) or the current level changes. Because the bounds
15//! already include a query margin, a point query is just a degenerate-rect
16//! `in_rect`.
17
18use blockworx_geom::Rect;
19use rstar::{AABB, RTree, RTreeObject};
20
21use crate::path::{BlockPath, Scope};
22use crate::render::bounds::{Bounded, route_bounds};
23use crate::shape::ShapeId;
24use crate::widget::drawing::Drawing;
25use blockworx_doc::{
26    document::{DocIndex, Document},
27    id::RouteId,
28    rev::DocStamp,
29};
30
31/// A hittable object on the current level: either a shape (blocks, ports, texts,
32/// images, areas — all carried by [`ShapeId`]) or a route.
33#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
34pub enum HitId {
35    Shape(ShapeId),
36    Route(RouteId),
37}
38
39struct Entry {
40    envelope: AABB<[f32; 2]>,
41    id: HitId,
42}
43
44impl RTreeObject for Entry {
45    type Envelope = AABB<[f32; 2]>;
46    fn envelope(&self) -> Self::Envelope {
47        self.envelope
48    }
49}
50
51fn aabb(r: Rect) -> AABB<[f32; 2]> {
52    AABB::from_corners([r.min.x, r.min.y], [r.max.x, r.max.y])
53}
54
55/// R*-tree over the current level's hittables. Built with [`Self::from_drawing`]
56/// and queried with [`Self::in_rect`].
57pub struct SpatialIndex {
58    tree: RTree<Entry>,
59}
60
61impl SpatialIndex {
62    /// Bulk-load an index over every shape, area, and route on `drawing`'s
63    /// current level.
64    pub fn from_drawing(drawing: &Drawing) -> Self {
65        let mut entries = Vec::new();
66        for (id, shape) in drawing
67            .shapes()
68            .chain(drawing.areas())
69            .chain(drawing.icons())
70        {
71            entries.push(Entry {
72                envelope: aabb(shape.bounds()),
73                id: HitId::Shape(id),
74            });
75        }
76        // A route with no solved geometry has no footprint to index.
77        for (id, route) in drawing.auto_routes() {
78            if let Some(geometry) = drawing.route_geometry(id) {
79                entries.push(Entry {
80                    envelope: aabb(route_bounds(&route, geometry)),
81                    id: HitId::Route(id),
82                });
83            }
84        }
85        Self {
86            tree: RTree::bulk_load(entries),
87        }
88    }
89
90    /// Ids whose bounds intersect `query` (world space). Order is unspecified —
91    /// callers that need a stable tie-break re-sort (see
92    /// [`Drawing::route_candidates`](crate::widget::drawing::Drawing)). A point
93    /// query is a degenerate `query` (`Rect::from_min_max(p, p)`); each entry's
94    /// bounds already carry `QUERY_MARGIN`, so no extra expansion is needed.
95    pub fn in_rect(&self, query: Rect) -> impl Iterator<Item = HitId> + '_ {
96        self.tree
97            .locate_in_envelope_intersecting(aabb(query))
98            .map(|e| e.id)
99    }
100}
101
102/// What an index was built from: the level it covers and the document value it
103/// saw. The index contents are a pure function of this pair, so an index whose
104/// key still matches cannot be stale.
105#[derive(Clone, Copy, PartialEq, Eq)]
106struct BuiltFrom {
107    level: Scope,
108    stamp: DocStamp,
109}
110
111/// The [`SpatialIndex`] cached across frames. [`Self::get`] rebuilds it whenever
112/// a fold produced a new document value (a fresh [`DocStamp`]) or the current
113/// level changed, so no mutation site has to remember to invalidate anything.
114#[derive(Default)]
115pub struct CachedIndex {
116    cached: Option<(BuiltFrom, SpatialIndex)>,
117}
118
119impl CachedIndex {
120    /// The index for `path`, rebuilt from `doc` unless the cached one was
121    /// built from the same level and the same document value. Building the whole
122    /// 50×50 grid's index is ~2ms, so an occasional extra rebuild is cheap.
123    ///
124    /// Takes the owned [`DocIndex`] rather than a view because it needs the
125    /// view only while building — the returned borrow is of the cache alone,
126    /// so the caller can take its own view for the drawing that follows.
127    /// The sink is local: indexing authors nothing.
128    pub fn get<'s>(
129        &'s mut self,
130        doc_index: &mut DocIndex,
131        doc: &Document,
132        path: &BlockPath,
133        presentation: &mut crate::presentation::Presentation,
134    ) -> &'s SpatialIndex {
135        let key = BuiltFrom {
136            level: path.scope(),
137            stamp: doc.stamp(),
138        };
139        if self.cached.as_ref().is_some_and(|(built, _)| *built != key) {
140            self.cached = None;
141        }
142        &self
143            .cached
144            .get_or_insert_with(|| {
145                let mut gesture = crate::gesture::Gesture::idle();
146                let drawing = Drawing::new(doc_index.view(doc), path, presentation, &mut gesture);
147                (key, SpatialIndex::from_drawing(&drawing))
148            })
149            .1
150    }
151}
152
153#[cfg(test)]
154mod tests {
155    use super::*;
156    use crate::widget::test_fixtures as fx;
157    use blockworx_doc::fixtures::block_id;
158    use blockworx_geom::pos2;
159
160    /// The ids the cache reports around `probe`, going through the same `get`
161    /// the app's render and hit-test paths use.
162    fn ids_near(cache: &mut CachedIndex, scene: &mut fx::Scene, probe: Rect) -> Vec<HitId> {
163        let fx::Scene {
164            doc,
165            index,
166            presentation,
167            path,
168            ..
169        } = scene;
170        cache
171            .get(index, doc, path, presentation)
172            .in_rect(probe)
173            .collect()
174    }
175
176    #[test]
177    fn a_commit_regenerates_the_index_with_no_explicit_invalidation() {
178        let mut scene = fx::Scene::new(vec![fx::block(1, 0.0)]);
179        let mut cache = CachedIndex::default();
180        let probe = Rect::from_min_max(pos2(400.0, 400.0), pos2(410.0, 410.0));
181
182        assert!(
183            ids_near(&mut cache, &mut scene, probe).is_empty(),
184            "nothing is there yet, or the test proves nothing"
185        );
186
187        // A fold produces a new document value — no cache in sight.
188        scene.apply(vec![fx::block_in(
189            2,
190            Scope::Root,
191            Rect::from_min_max(pos2(390.0, 390.0), probe.max),
192        )]);
193
194        assert!(
195            ids_near(&mut cache, &mut scene, probe)
196                .contains(&HitId::Shape(ShapeId::Rect(block_id(2)))),
197            "the cached index must not survive a commit it was never told about"
198        );
199    }
200
201    #[test]
202    fn building_the_index_does_not_itself_change_the_document_value() {
203        // Otherwise every `get` would see a fresh stamp and rebuild forever.
204        let mut scene = fx::Scene::new(vec![fx::block(1, 0.0)]);
205        let mut cache = CachedIndex::default();
206        let probe = Rect::from_min_max(pos2(0.0, 0.0), pos2(10.0, 10.0));
207
208        let before = scene.doc.stamp();
209        let _ = ids_near(&mut cache, &mut scene, probe);
210
211        assert_eq!(scene.doc.stamp(), before);
212    }
213
214    #[test]
215    fn entering_a_block_indexes_that_block_instead() {
216        let (outer_block, nested) = (block_id(1), block_id(2));
217        let ops = vec![
218            fx::block_in(
219                1,
220                Scope::Root,
221                Rect::from_min_max(pos2(0.0, 0.0), pos2(400.0, 400.0)),
222            ),
223            fx::block_in(
224                2,
225                Scope::Block(outer_block),
226                Rect::from_min_max(pos2(40.0, 40.0), pos2(80.0, 80.0)),
227            ),
228        ];
229        let mut cache = CachedIndex::default();
230        let probe = Rect::from_min_max(pos2(50.0, 50.0), pos2(60.0, 60.0));
231
232        let mut scene = fx::Scene::new(ops);
233        assert_eq!(scene.path.scope(), Scope::Root, "the root scope");
234        let on_root = ids_near(&mut cache, &mut scene, probe);
235        assert!(on_root.contains(&HitId::Shape(ShapeId::Rect(outer_block))));
236        assert!(!on_root.contains(&HitId::Shape(ShapeId::Rect(nested))));
237
238        // Navigating changes the level without touching the document at all —
239        // same value, same stamp, so only the level can have re-keyed it.
240        let stamp = scene.doc.stamp();
241        scene.path.push(outer_block);
242        let on_inner = ids_near(&mut cache, &mut scene, probe);
243        assert_eq!(scene.doc.stamp(), stamp, "the document never changed");
244        assert!(on_inner.contains(&HitId::Shape(ShapeId::Rect(nested))));
245    }
246}
blockworx/widget/spatial.rs

blockworx/widget/
spatial.rs
