facett-core/src/engine/pick.rs
//! **Picking, built ONCE.** The census found three hand-rolled pickers on the
//! map side (`facett-map::hit_test_way`, `facett-geomap`'s pin hit-test,
//! `facett-geomap`'s hotspot select), two more on the graph side
//! (`facett-graphview::PickIndex`, `facett-graphnav::HoverIndex`), **none** in
//! `facett-map3d`, and no primitive at all in `facett-core`. Drill-down is
//! useless without a click, so this is the one.
//!
//! ## Two lanes, one id space
//! * **CPU lane** — a [`ScreenGrid`](crate::legibility::ScreenGrid) over the
//! projected anchors. Exact, deterministic, headless-testable, no GPU.
//! * **GPU lane** — the same [`PickId`] written as a colour into an offscreen
//! `R32Uint` target; a click reads one texel back. This is deck.gl's one
//! remaining lead, and it is the *same 32-bit id* the CPU lane returns, so a
//! test can assert the two lanes agree. (Pass 1 defines the id encoding and
//! the CPU lane; the offscreen target is the shader pass.)
//!
//! ## The id encoding
//! `PickId` is `layer << 24 | feature`, so one buffer serves every layer in the
//! frame — which is what use case 7 (a graph drawn on geography) requires: one
//! click, two position sources, one answer. `0` is reserved for **nothing**, so
//! a cleared target reads as a miss.
use crate::legibility::ScreenGrid;
use egui::{Pos2, Rect, Vec2};
/// **What shape a feature occupies for the purpose of a click.**
///
/// The census found the same click implemented eight times across the graph
/// crates and three more across the map crates, differing only in this enum. A
/// map pin is a radius; a graph chip is a box; a road is a nearest-point. Naming
/// the difference is what lets one index serve them all — and it is load-bearing,
/// not cosmetic: when chips overlap (they do at low zoom, `BOX_W` is 184 px)
/// "nearest centre" and "first box that contains the point" are **different
/// nodes**, so a picker that silently swaps one for the other is wrong in a way
/// no smoke test notices.
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum PickShape {
/// A disc of `r` screen px around the anchor. Nearest wins.
Radius(f32),
/// An axis-aligned box of `half`-extent screen px around the anchor. The
/// **lowest feature index** that contains the probe wins — paint order.
Box(Vec2),
}
impl Default for PickShape {
fn default() -> Self {
Self::Radius(8.0)
}
}
/// Layer slot in a frame. 8 bits — 255 simultaneous layers, `0` reserved.
pub type LayerId = u8;
/// A 32-bit pick identity: `layer << 24 | feature`. `PickId(0)` = nothing.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct PickId(pub u32);
/// Features are 24-bit inside a pick id. A layer with more than this many
/// features must be split — asserted, never silently truncated.
pub const MAX_FEATURE: u32 = (1 << 24) - 1;
impl PickId {
/// Encode. `layer` must be `1..=255` and `feature` `<= MAX_FEATURE`;
/// out-of-range inputs encode as [`PickId::NOTHING`] rather than aliasing
/// onto another feature (a silent alias is a wrong click, forever).
#[must_use]
pub fn new(layer: LayerId, feature: u32) -> Self {
if layer == 0 || feature > MAX_FEATURE {
return Self::NOTHING;
}
Self(((layer as u32) << 24) | feature)
}
/// The reserved "no feature here" id. A cleared GPU target reads as this.
pub const NOTHING: PickId = PickId(0);
#[must_use]
pub fn is_nothing(self) -> bool {
self.0 == 0
}
#[must_use]
pub fn layer(self) -> LayerId {
(self.0 >> 24) as u8
}
#[must_use]
pub fn feature(self) -> u32 {
self.0 & MAX_FEATURE
}
/// The id as the RGBA bytes a colour-encoded GPU target would carry
/// (little-endian, so `R` is the low feature byte). The shader half writes
/// the `u32` directly; this exists so an 8-bit-per-channel readback path and
/// the CPU lane provably agree on the same number.
#[must_use]
pub fn to_rgba(self) -> [u8; 4] {
self.0.to_le_bytes()
}
#[must_use]
pub fn from_rgba(b: [u8; 4]) -> Self {
Self(u32::from_le_bytes(b))
}
}
/// What a pick found, **and how much work it did** — the anti-lie field, same
/// discipline as [`NearestHit`](crate::legibility::NearestHit).
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct PickHit {
pub id: PickId,
/// Screen-space distance in px from the probe to the anchor.
pub dist: f32,
/// Anchors actually distance-tested. A linear scan reports the whole layer.
pub candidates: usize,
}
/// The CPU pick index: one [`ScreenGrid`] per layer over that layer's projected
/// anchors, plus the id map. Rebuilt when the camera or any source's
/// [`generation`](super::source::PositionSource::generation) changes.
#[derive(Debug, Default)]
pub struct PickIndex {
layers: Vec<PickLayer>,
/// The cache key the index was built for (camera epoch ⊕ source generations).
key: u64,
}
#[derive(Debug)]
struct PickLayer {
layer: LayerId,
grid: ScreenGrid,
/// The projected anchors the grid indexes (`ScreenGrid` bins indices, not
/// points, so the points travel alongside it).
anchors: Vec<Pos2>,
/// `grid` point index -> caller feature id.
features: Vec<u32>,
/// What a feature of this layer occupies on screen.
shape: PickShape,
}
impl PickIndex {
/// The key this index was built against — compare before reusing.
#[must_use]
pub fn key(&self) -> u64 {
self.key
}
/// True when the index is already valid for `key` (nothing to rebuild).
#[must_use]
pub fn is_current(&self, key: u64) -> bool {
!self.layers.is_empty() && self.key == key
}
/// Drop everything and start a new frame's index under `key`.
pub fn begin(&mut self, key: u64) {
self.layers.clear();
self.key = key;
}
/// Add one layer's projected anchors. `features[i]` is the caller feature id
/// of `anchors[i]`.
pub fn push_layer(&mut self, layer: LayerId, anchors: &[Pos2], features: Vec<u32>, shape: PickShape) {
debug_assert_eq!(anchors.len(), features.len(), "anchors and features must be index-aligned");
self.layers.push(PickLayer {
layer,
grid: ScreenGrid::build(anchors),
anchors: anchors.to_vec(),
features,
shape,
});
}
/// **The click.** Each layer answers by its own [`PickShape`]; the latest
/// layer wins a tie — so an overlay drawn on top of a map also picks on top
/// of it, which is exactly what use case 7 needs.
#[must_use]
pub fn pick(&self, probe: Pos2) -> PickHit {
let mut best = PickHit::default();
let mut found = false;
for l in &self.layers {
let hit = match l.shape {
PickShape::Radius(r) => l.grid.nearest(&l.anchors, probe, r.max(1.0)).map(|h| {
best.candidates += h.candidates;
(h.index, h.dist)
}),
PickShape::Box(half) => {
// The chip test, index-backed: every possible winner has its
// anchor inside `probe ± half`, so one rect query returns a
// superset, the exact componentwise test filters it, and the
// LOWEST index wins — the paint-order answer a linear
// `find_map` over the feature list returns.
let mut cands: Vec<u32> = Vec::new();
l.grid.query_rect(Rect::from_center_size(probe, half * 2.0), &mut cands);
best.candidates += cands.len();
cands.sort_unstable();
cands
.into_iter()
.find(|&i| {
let c = l.anchors[i as usize];
(probe.x - c.x).abs() <= half.x && (probe.y - c.y).abs() <= half.y
})
.map(|i| (i, (l.anchors[i as usize] - probe).length()))
}
};
let Some((index, dist)) = hit else { continue };
if !found || dist <= best.dist {
found = true;
let feat = l.features.get(index as usize).copied().unwrap_or(u32::MAX);
best.id = PickId::new(l.layer, feat);
best.dist = dist;
}
}
best
}
#[must_use]
pub fn layer_count(&self) -> usize {
self.layers.len()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn id_round_trips_through_rgba_and_fields() {
let id = PickId::new(3, 1_234_567);
assert_eq!(id.layer(), 3);
assert_eq!(id.feature(), 1_234_567);
assert_eq!(PickId::from_rgba(id.to_rgba()), id);
assert!(!id.is_nothing());
}
/// RED-PROVEN: remove the guard in `PickId::new` and this fails — feature
/// `1<<24` would alias onto layer 1 feature 0.
#[test]
fn out_of_range_encodes_as_nothing_never_as_an_alias() {
assert!(PickId::new(0, 5).is_nothing(), "layer 0 is reserved");
assert!(PickId::new(1, MAX_FEATURE + 1).is_nothing(), "a 25-bit feature must not alias");
assert_ne!(PickId::new(1, 0), PickId::NOTHING, "a real feature must not read as a miss");
}
#[test]
fn pick_returns_the_nearest_anchor_and_reports_its_work() {
let anchors: Vec<Pos2> = (0..1000).map(|i| Pos2::new((i % 50) as f32 * 10.0, (i / 50) as f32 * 10.0)).collect();
let mut idx = PickIndex::default();
idx.begin(1);
idx.push_layer(1, &anchors, (0..1000).collect(), PickShape::Radius(8.0));
let hit = idx.pick(Pos2::new(101.0, 60.0));
assert_eq!(hit.id.layer(), 1);
// (100, 60) is column 10, row 6 -> index 6*50 + 10 = 310.
assert_eq!(hit.id.feature(), 310, "picked the wrong anchor");
assert!(hit.dist <= 2.0);
assert!(hit.candidates < 1000, "tested {} of 1000 — that is a linear scan", hit.candidates);
}
#[test]
fn a_click_on_empty_space_is_nothing() {
let anchors = vec![Pos2::new(0.0, 0.0)];
let mut idx = PickIndex::default();
idx.begin(1);
idx.push_layer(1, &anchors, vec![7], PickShape::Radius(4.0));
assert!(idx.pick(Pos2::new(500.0, 500.0)).id.is_nothing());
}
#[test]
fn the_upper_layer_wins_a_contested_pixel() {
let a = vec![Pos2::new(10.0, 10.0)];
let mut idx = PickIndex::default();
idx.begin(1);
idx.push_layer(1, &a, vec![100], PickShape::Radius(12.0)); // the map
idx.push_layer(2, &a, vec![200], PickShape::Radius(12.0)); // the graph on top of it
let hit = idx.pick(Pos2::new(10.0, 10.0));
assert_eq!((hit.id.layer(), hit.id.feature()), (2, 200));
}
/// RED-PROVEN: drop the `cands.sort_unstable()` (or switch `Box` to nearest)
/// and this fails — overlapping chips make "nearest" a *different* node from
/// "first in paint order", and the fast answer would silently be wrong.
#[test]
fn box_shape_matches_the_linear_scan_over_overlapping_chips() {
// Chips 184x28 px on a 40 px pitch: they overlap heavily, like a graph
// board at low zoom.
let half = Vec2::new(92.0, 14.0);
let anchors: Vec<Pos2> = (0..300).map(|i| Pos2::new((i % 20) as f32 * 40.0, (i / 20) as f32 * 18.0)).collect();
let mut idx = PickIndex::default();
idx.begin(1);
idx.push_layer(1, &anchors, (0..300).collect(), PickShape::Box(half));
let reference = |p: Pos2| -> Option<u32> {
anchors.iter().position(|c| (p.x - c.x).abs() <= half.x && (p.y - c.y).abs() <= half.y).map(|i| i as u32)
};
let mut hits = 0;
for gx in 0..30 {
for gy in 0..20 {
let p = Pos2::new(gx as f32 * 27.0 - 40.0, gy as f32 * 15.0 - 20.0);
let got = idx.pick(p);
let want = reference(p);
match want {
Some(w) => {
assert_eq!(got.id.feature(), w, "probe {p:?}: index picked {:?}, scan picked {w}", got.id.feature());
hits += 1;
}
None => assert!(got.id.is_nothing(), "probe {p:?}: index invented a hit"),
}
}
}
assert!(hits > 100, "only {hits} probes landed on a chip — the sweep proves nothing");
}
}