blockworx_editor/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 _s = tracing::info_span!("spatial_index").entered();
146                let mut gesture = crate::gesture::Gesture::idle();
147                let drawing = Drawing::new(doc_index.view(doc), path, presentation, &mut gesture);
148                (key, SpatialIndex::from_drawing(&drawing))
149            })
150            .1
151    }
152}
153
154#[cfg(test)]
155mod tests {
156    use super::*;
157    use crate::widget::test_fixtures as fx;
158    use blockworx_doc::fixtures::block_id;
159    use blockworx_geom::pos2;
160
161    /// The ids the cache reports around `probe`, going through the same `get`
162    /// the app's render and hit-test paths use.
163    fn ids_near(cache: &mut CachedIndex, scene: &mut fx::Scene, probe: Rect) -> Vec<HitId> {
164        let fx::Scene {
165            doc,
166            index,
167            presentation,
168            path,
169            ..
170        } = scene;
171        cache
172            .get(index, doc, path, presentation)
173            .in_rect(probe)
174            .collect()
175    }
176
177    #[test]
178    fn a_commit_regenerates_the_index_with_no_explicit_invalidation() {
179        let mut scene = fx::Scene::new(vec![fx::block(1, 0.0)]);
180        let mut cache = CachedIndex::default();
181        let probe = Rect::from_min_max(pos2(400.0, 400.0), pos2(410.0, 410.0));
182
183        assert!(
184            ids_near(&mut cache, &mut scene, probe).is_empty(),
185            "nothing is there yet, or the test proves nothing"
186        );
187
188        // A fold produces a new document value — no cache in sight.
189        scene.apply(vec![fx::block_in(
190            2,
191            Scope::Root,
192            Rect::from_min_max(pos2(390.0, 390.0), probe.max),
193        )]);
194
195        assert!(
196            ids_near(&mut cache, &mut scene, probe)
197                .contains(&HitId::Shape(ShapeId::Rect(block_id(2)))),
198            "the cached index must not survive a commit it was never told about"
199        );
200    }
201
202    #[test]
203    fn building_the_index_does_not_itself_change_the_document_value() {
204        // Otherwise every `get` would see a fresh stamp and rebuild forever.
205        let mut scene = fx::Scene::new(vec![fx::block(1, 0.0)]);
206        let mut cache = CachedIndex::default();
207        let probe = Rect::from_min_max(pos2(0.0, 0.0), pos2(10.0, 10.0));
208
209        let before = scene.doc.stamp();
210        let _ = ids_near(&mut cache, &mut scene, probe);
211
212        assert_eq!(scene.doc.stamp(), before);
213    }
214
215    #[test]
216    fn entering_a_block_indexes_that_block_instead() {
217        let (outer_block, nested) = (block_id(1), block_id(2));
218        let ops = vec![
219            fx::block_in(
220                1,
221                Scope::Root,
222                Rect::from_min_max(pos2(0.0, 0.0), pos2(400.0, 400.0)),
223            ),
224            fx::block_in(
225                2,
226                Scope::Block(outer_block),
227                Rect::from_min_max(pos2(40.0, 40.0), pos2(80.0, 80.0)),
228            ),
229        ];
230        let mut cache = CachedIndex::default();
231        let probe = Rect::from_min_max(pos2(50.0, 50.0), pos2(60.0, 60.0));
232
233        let mut scene = fx::Scene::new(ops);
234        assert_eq!(scene.path.scope(), Scope::Root, "the root scope");
235        let on_root = ids_near(&mut cache, &mut scene, probe);
236        assert!(on_root.contains(&HitId::Shape(ShapeId::Rect(outer_block))));
237        assert!(!on_root.contains(&HitId::Shape(ShapeId::Rect(nested))));
238
239        // Navigating changes the level without touching the document at all —
240        // same value, same stamp, so only the level can have re-keyed it.
241        let stamp = scene.doc.stamp();
242        scene.path.push(outer_block);
243        let on_inner = ids_near(&mut cache, &mut scene, probe);
244        assert_eq!(scene.doc.stamp(), stamp, "the document never changed");
245        assert!(on_inner.contains(&HitId::Shape(ShapeId::Rect(nested))));
246    }
247}
blockworx_editor/widget/spatial.rs

blockworx_editor/widget/
spatial.rs
