facett-graphnav/src/legible.rs
//! **Legibility at scale for the NAVIGATOR** — the part that decides what is worth
//! drawing, and the spatial index that makes pointing at it cheap.
//!
//! The navigator is the pane whose whole job is *reading data*, so it is the pane where
//! "as good and better for viewing data" is measured. Three defects it shipped with,
//! each fixed here from the shared `facett-core` primitives (never a private copy, L5):
//!
//! 1. **Hover scanned the dataset.** `render` resolved the hovered node by iterating
//! every node in the graph, projecting it and taking a distance — on every mouse
//! move, including for nodes far off-screen. The paint loop was already
//! viewport-culled, so the *cheap* half of the frame scaled with the screen while
//! the *pointer* half scaled with the dataset: precisely the shape
//! `facett-geomap`'s `PointGrid` was caught in. [`HoverIndex`] replaces it with a
//! [`ScreenGrid`](facett_core::legibility::ScreenGrid) query and reports
//! [`HoverIndex::last_candidates`] so the claim stays checkable.
//! 2. **Labels overplotted.** The rule was "show every label if the graph is small or
//! the zoom is past 1.6". At 100 000 nodes and zoom 1.7 that paints 100 000 labels
//! on top of each other — every one unreadable. Now a collision-avoiding placement
//! picks the labels that fit, ranked by what the user is looking at.
//! 3. **Edges merged into a grey rectangle.** Every visible edge was stroked. A dense
//! graph became one saturated block with no visible structure. Now an ink budget per
//! screen cell keeps the structure and drops the redundant filaments — while the
//! selected path, a highlighted cycle and the hovered node's own edges are never
//! thinned, because those are the answer to the user's question.
//!
//! Plus the **shared instanced GPU cloud** ([`facett_core::render::gpu::graphcloud`],
//! the same renderer `facett-graph3d` installs), opt-in and default OFF.
use egui::{Pos2, Rect, Vec2};
use facett_core::legibility::{
plan_frame, FrameInput, FrameOpts, FramePlan, LabelPlacement, ScreenGrid,
};
use serde::{Deserialize, Serialize};
/// Navigator legibility switches. Serde-round-trippable so they are part of the
/// observable Model a robot can drive.
#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
pub struct LegibilityOpts {
/// Collision-avoiding label placement (drop what will not fit, keep what matters).
pub thin_labels: bool,
/// A per-screen-cell ink budget for edges.
pub thin_edges: bool,
/// Paint the node/edge cloud through the shared instanced GPU renderer. Needs the
/// `wgpu` feature **and** an installed cloud renderer; otherwise the CPU painter
/// runs unchanged (never a blank pane).
pub gpu_cloud: bool,
/// Ink-budget lattice cell in screen px.
pub edge_cell: f32,
/// Edges kept per `(cell, direction)` bucket.
pub keep_per_bucket: usize,
}
impl Default for LegibilityOpts {
/// **Legibility is ON by default** in the navigator, and the GPU is not.
///
/// These are not the same kind of switch. The GPU lane changes *how* pixels are
/// produced and needs a host to install a renderer, so it must be opted into and it
/// must default off to keep every golden byte-identical. Label collision and the
/// edge ink budget change *what is worth drawing*, cost nothing when nothing
/// collides (a small graph places every label and thins no edge, i.e. the output is
/// identical), and are the entire reason the navigator exists. Defaulting them off
/// would ship the unreadable pane and hide the cure behind a flag nobody sets.
fn default() -> Self {
Self {
thin_labels: true,
thin_edges: true,
gpu_cloud: false,
edge_cell: 24.0,
keep_per_bucket: 3,
}
}
}
impl LegibilityOpts {
/// Everything off — the historical painter, for an A/B or a golden.
#[must_use]
pub fn off() -> Self {
Self { thin_labels: false, thin_edges: false, gpu_cloud: false, ..Self::default() }
}
/// Is any legibility cure active? (The GPU lane is not a legibility cure.)
#[must_use]
pub fn any_thinning(&self) -> bool {
self.thin_labels || self.thin_edges
}
}
/// A cached screen-space index over the projected node centres, for hover + pick.
///
/// Rebuilt only when the projection or the node set changed, so dragging the pointer
/// across a static camera costs one neighbourhood query per frame instead of one full
/// scan of the dataset.
#[derive(Default)]
pub struct HoverIndex {
centres: Vec<Pos2>,
/// Which node index each entry of `centres` belongs to (only *visible* nodes are
/// indexed, so an invisible node can never be hovered — same rule as before).
nodes: Vec<usize>,
grid: Option<ScreenGrid>,
key: Option<u64>,
/// Points distance-tested by the last [`hover`](Self::hover) — the honesty field.
/// The pre-index code reported the whole node count here, every mouse move.
pub last_candidates: usize,
/// Index (re)builds so far — a drag must add none (lane M, 2026-10-02).
pub builds: u64,
/// Hover probes so far — a drag must add none.
pub probes: u64,
}
impl HoverIndex {
/// Rebuild if `key` (the caller's projection + visibility fingerprint) changed.
pub fn ensure(&mut self, key: u64, centres: impl Iterator<Item = (usize, Pos2)>) {
if self.key == Some(key) && self.grid.is_some() {
return;
}
self.nodes.clear();
self.centres.clear();
for (i, p) in centres {
self.nodes.push(i);
self.centres.push(p);
}
self.grid = Some(ScreenGrid::build(&self.centres));
self.key = Some(key);
self.builds += 1;
}
/// The visible node index within `radius` px of `probe`, nearest first — the
/// indexed twin of the old "project every node and take the minimum distance".
pub fn hover(&mut self, probe: Pos2, radius: f32) -> Option<usize> {
self.probes += 1;
let grid = self.grid.as_ref()?;
let hit = grid.nearest(&self.centres, probe, radius)?;
self.last_candidates = hit.candidates;
self.nodes.get(hit.index as usize).copied()
}
/// How many nodes are in the index (the visible ones).
#[must_use]
pub fn len(&self) -> usize {
self.centres.len()
}
/// Is the index empty?
#[must_use]
pub fn is_empty(&self) -> bool {
self.centres.is_empty()
}
}
/// What one painted frame's legibility work did.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct NavReport {
/// Did the instanced GPU cloud paint? `false` also covers "opted in but no renderer
/// installed" — which must fall back to the CPU painter, never blank.
pub gpu_cloud: bool,
pub labels_placed: usize,
pub labels_suppressed: usize,
pub labels_considered: usize,
pub edges_drawn: usize,
pub edges_thinned: usize,
pub edge_peak_before: usize,
pub edge_peak_after: usize,
/// Nodes distance-tested by the last hover probe. The pre-index behaviour was the
/// whole node count; a small number here IS the fix.
pub hover_candidates: usize,
/// Nodes in the hover index (the visible ones).
pub hover_indexed: usize,
/// Hover-index (re)builds so far ([`HoverIndex::builds`]): a drag adds none.
pub hover_builds: u64,
/// Hover probes so far ([`HoverIndex::probes`]): a drag adds none — so
/// `hover_candidates` after a drag is the probe BEFORE it (the press), not drag work.
pub hover_probes: u64,
}
impl NavReport {
/// The `state_json` fragment.
#[must_use]
pub fn state_json(&self) -> serde_json::Value {
serde_json::json!({
"gpu_cloud": self.gpu_cloud,
"labels_placed": self.labels_placed,
"labels_suppressed": self.labels_suppressed,
"labels_considered": self.labels_considered,
"edges_drawn": self.edges_drawn,
"edges_thinned": self.edges_thinned,
"edge_peak_before": self.edge_peak_before,
"edge_peak_after": self.edge_peak_after,
"hover_candidates": self.hover_candidates,
"hover_indexed": self.hover_indexed,
"hover_builds": self.hover_builds,
"hover_probes": self.hover_probes,
})
}
}
/// The navigator's frame plan.
pub struct NavPlan {
pub inner: FramePlan,
pub report: NavReport,
}
impl NavPlan {
/// Edge indices to stroke, ascending; `None` = stroke them all.
#[must_use]
pub fn edges(&self) -> Option<&Vec<u32>> {
self.inner.edges.as_ref()
}
/// Label placements; `None` = the historical per-node label rule applies.
#[must_use]
pub fn labels(&self) -> Option<&LabelPlacement> {
self.inner.labels.as_ref()
}
}
/// Everything the navigator knows about the frame, in the shared vocabulary. All slices
/// are index-aligned with the navigator's node / edge lists.
pub struct NavFrame<'a> {
pub centres: &'a [Pos2],
/// Per-node: is it in the visible set? An invisible node offers no label and its
/// edges are not budgeted.
pub visible: &'a [bool],
/// Per-node label text length in characters (0 = no label wanted this frame).
pub label_chars: &'a [usize],
/// Per-node: must this label be drawn? (selection / hover / neighbour / path / hit)
pub label_pinned: &'a [bool],
/// Per-node ranking for contested pixels.
pub label_priority: &'a [f32],
/// Edges as node index pairs; `u32::MAX` for an unresolvable endpoint.
pub edges: &'a [(u32, u32)],
/// Per-edge: never thin (path / cycle / touches the hovered node).
pub edge_always: &'a [bool],
/// Per-edge weight — the heaviest survive a saturated cell.
pub edge_weight: &'a [f32],
pub viewport: Rect,
pub font_px: f32,
}
/// Plan one navigator frame. Pure — no `Ui`, no painter — so `benches/heavy_legibility.rs`
/// times exactly this and `tests/legibility.rs` asserts exactly this.
#[must_use]
pub fn plan_nav(frame: &NavFrame<'_>, opts: LegibilityOpts) -> NavPlan {
let char_px = frame.font_px * 0.58;
let label_size: Vec<Vec2> = frame
.centres
.iter()
.enumerate()
.map(|(i, _)| {
let vis = frame.visible.get(i).copied().unwrap_or(true);
let chars = frame.label_chars.get(i).copied().unwrap_or(0);
if vis && chars > 0 {
Vec2::new((chars as f32 * char_px).max(4.0), frame.font_px)
} else {
Vec2::ZERO
}
})
.collect();
let inner = plan_frame(
&FrameInput {
centres: frame.centres,
label_size: &label_size,
label_priority: frame.label_priority,
label_pinned: frame.label_pinned,
edges: frame.edges,
edge_always: frame.edge_always,
edge_weight: frame.edge_weight,
viewport: frame.viewport,
},
FrameOpts {
thin_labels: opts.thin_labels,
thin_edges: opts.thin_edges,
label_pad: 2.0,
edge_cell: opts.edge_cell,
keep_per_bucket: opts.keep_per_bucket,
},
);
let report = NavReport {
gpu_cloud: false,
labels_placed: inner.report.labels_placed,
labels_suppressed: inner.report.labels_suppressed,
labels_considered: inner.report.labels_considered,
edges_drawn: inner.report.edges_drawn,
edges_thinned: inner.report.edges_thinned,
edge_peak_before: inner.report.edge_peak_before,
edge_peak_after: inner.report.edge_peak_after,
hover_candidates: 0,
hover_indexed: 0,
hover_builds: 0,
hover_probes: 0,
};
NavPlan { inner, report }
}
/// Push the shared instanced GPU cloud, returning whether it drew — the ONE gate the
/// navigator consults before skipping its CPU edge/node loops.
///
/// The install check lives inside
/// [`facett_core::render::gpu::graphcloud::cloud::draw_cloud`], so opting in without an
/// installed renderer falls back to the CPU painter rather than rendering a blank pane.
/// Without the `wgpu` feature this is a compile-time `false`.
#[cfg(feature = "wgpu")]
#[allow(clippy::too_many_arguments)]
pub fn draw_gpu_cloud(
ui: &egui::Ui,
rect: Rect,
centres: &[Pos2],
radii: &[f32],
colors: &[egui::Color32],
visible: &[bool],
edges: &[(u32, u32)],
edge_color: egui::Color32,
use_gpu: bool,
) -> bool {
use facett_core::render::gpu::graphcloud::{cloud, CloudBuilder};
if centres.is_empty() {
return false;
}
cloud::draw_cloud(ui, rect, use_gpu, |px_w, px_h| {
let sx = px_w / rect.width().max(1.0);
let sy = px_h / rect.height().max(1.0);
let to_px = |p: Pos2| Pos2::new((p.x - rect.min.x) * sx, (p.y - rect.min.y) * sy);
let vis = |i: usize| visible.get(i).copied().unwrap_or(true);
CloudBuilder::default().scene(
centres.iter().enumerate().filter(|&(i, _)| vis(i)).map(|(i, &p)| {
(
to_px(p),
radii.get(i).copied().unwrap_or(4.0) * sy,
colors.get(i).copied().unwrap_or(egui::Color32::WHITE),
)
}),
edges.iter().filter_map(|&(a, b)| {
let (ia, ib) = (a as usize, b as usize);
let (pa, pb) = (centres.get(ia)?, centres.get(ib)?);
(vis(ia) && vis(ib)).then(|| (to_px(*pa), to_px(*pb), 1.0, edge_color))
}),
)
})
}
/// No-`wgpu` build: the lane does not exist, so the CPU painter always runs.
#[cfg(not(feature = "wgpu"))]
#[allow(clippy::too_many_arguments, unused_variables)]
pub fn draw_gpu_cloud(
ui: &egui::Ui,
rect: Rect,
centres: &[Pos2],
radii: &[f32],
colors: &[egui::Color32],
visible: &[bool],
edges: &[(u32, u32)],
edge_color: egui::Color32,
use_gpu: bool,
) -> bool {
false
}