facett-graphpan/src/legible.rs
//! **Legibility + the GPU cloud lane for the pan/zoom canvas.**
//!
//! The bare canvas ([`crate::draw_graph`]) paints every chip, every edge and every
//! label through `egui::Painter` every frame. That is exactly right for a 40-node
//! architecture board and useless above a few thousand nodes, for two independent
//! reasons that need two independent cures:
//!
//! - **Speed.** egui tessellates on the UI thread, single-core: a 30 000-node cloud is
//! 2.47 M triangles and 33.75 ms/frame, while the projection that feeds it costs
//! 0.02 ms (`facett/.nornir/graph3d-rotate-perf-design.md`). The cure is to stop
//! tessellating — hand the cloud to the shared instanced GPU renderer
//! ([`facett_core::render::gpu::graphcloud`]), the SAME one `Graph3D` installs.
//! - **Legibility.** A GPU that draws 100 000 overlapping labels at 240 fps has drawn
//! an unreadable pane very quickly. The cure is
//! [`facett_core::legibility`]: collision-avoiding label placement, a per-cell ink
//! budget for edges, and a spatial index so picking does not scan the dataset.
//!
//! Both are **opt-in and default OFF** ([`PaintOpts::default`] is all-false), so
//! [`crate::draw_graph`] and every existing golden are byte-for-byte unchanged.
//!
//! # The fail-dangerous shape, and why it cannot happen here
//!
//! Turning the GPU lane on makes the painter *skip* the CPU chip/edge loops. If the
//! host opted in but never installed the renderer, the callback would paint nothing
//! and the pane would render **BLANK** — the exact defect that made `Graph3D`'s cloud
//! look like "the 3D graphs are missing". The skip decision is therefore never taken
//! locally: it is whatever [`facett_core::render::gpu::graphcloud::cloud::draw_cloud`]
//! returns, and that function refuses unless a renderer really exists. Without the
//! `wgpu` feature the whole lane compiles to `false` and the CPU painter always runs.
//! `tests/gpu_fallback.rs` pins both halves on a box with no renderer installed.
use egui::{Color32, Pos2, Rect, Vec2};
use facett_core::legibility::{
plan_frame as core_plan_frame, FrameInput, FrameOpts, FramePlan as CoreFramePlan,
LabelPlacement, ScreenGrid,
};
use crate::{GraphModel, BOX_H, BOX_W};
/// Per-frame paint options. `Default` is **everything off** = the historical canvas,
/// so adopting this type cannot change a single pixel until a host asks it to.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct PaintOpts {
/// Paint the node/edge cloud as GPU instances instead of egui shapes. Requires the
/// `wgpu` feature **and** an installed cloud renderer; without either it silently
/// and safely falls back to the CPU painter, vertex for vertex.
pub gpu_cloud: bool,
/// Place labels with collision avoidance and drop the losers, instead of painting
/// every label on top of every other.
pub thin_labels: bool,
/// Apply a per-screen-cell ink budget to the edges so a hairball keeps its
/// structure. Selected/decoration edges are never thinned.
pub thin_edges: bool,
/// Padding around a label box in px (collision only; the text is unchanged).
pub label_pad: f32,
/// Edge ink-budget lattice cell in px.
pub edge_cell: f32,
/// Edges per `(cell, direction)` bucket.
pub keep_per_bucket: usize,
}
impl Default for PaintOpts {
fn default() -> Self {
Self {
gpu_cloud: false,
thin_labels: false,
thin_edges: false,
label_pad: 2.0,
edge_cell: 24.0,
keep_per_bucket: 3,
}
}
}
impl PaintOpts {
/// Everything legibility-related on (GPU still off — that needs a host install).
#[must_use]
pub fn legible() -> Self {
Self { thin_labels: true, thin_edges: true, ..Self::default() }
}
/// Opt into the instanced GPU cloud.
#[must_use]
pub fn with_gpu(mut self, on: bool) -> Self {
self.gpu_cloud = on;
self
}
/// Is anything at all enabled? (`false` ⇒ the paint path is bit-identical to the
/// historical one, which is what keeps the goldens safe.)
#[must_use]
pub fn is_off(&self) -> bool {
!self.gpu_cloud && !self.thin_labels && !self.thin_edges
}
}
/// What one frame's legibility work actually did — the observable, published through
/// `GraphPanView::state_json` so a robot asserts on numbers rather than on a promise.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct LegibilityReport {
/// Did the instanced GPU cloud paint this frame? `false` means the CPU painter ran
/// — including the case where the host opted in but installed no renderer.
pub gpu_cloud: bool,
/// Labels drawn.
pub labels_placed: usize,
/// Labels dropped because they would have overplotted.
pub labels_suppressed: usize,
/// Labels that were even looked at (on-screen ones).
pub labels_considered: usize,
/// Edges drawn.
pub edges_drawn: usize,
/// Edges dropped by the ink budget.
pub edges_thinned: usize,
/// Peak segments crossing one lattice cell before / after thinning.
pub edge_peak_before: usize,
pub edge_peak_after: usize,
/// Did the cloud paint on the RESIDENT lane (uploaded once per model, the camera per
/// frame) rather than the per-frame instance lane? Implies `gpu_cloud`.
pub resident: bool,
/// Models the painting pane has uploaded to the resident lane so far — constant across
/// camera-only frames, +1 per model change.
pub resident_uploads: u64,
}
impl LegibilityReport {
/// Which lane drew the cloud: `resident`, `per-frame` (the instance lane) or `cpu`.
#[must_use]
pub fn cloud_lane(&self) -> &'static str {
if self.resident {
"resident"
} else if self.gpu_cloud {
"per-frame"
} else {
"cpu"
}
}
/// The `state_json` fragment (`"legibility"`).
#[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,
"cloud_lane": self.cloud_lane(),
"resident_uploads": self.resident_uploads,
})
}
}
// ─────────────────────────────────────────────────────────────────────────────
// Picking through the spatial index
// ─────────────────────────────────────────────────────────────────────────────
/// A cached screen-space pick index over the projected chip centres.
///
/// `hit_test` scans every node on every click — `O(n)` per interaction, which at
/// 100 000 nodes is 100 000 projections and rect tests for one mouse press. This
/// rebuilds a [`ScreenGrid`] only when the projection actually changed (node count,
/// origin or zoom) and answers a pick from the local neighbourhood.
///
/// The rebuild is honestly `O(n)`; the point is that it happens on **pan/zoom**, not on
/// every pointer event, and a hover-per-frame workload pays only the query.
#[derive(Default)]
pub struct PickIndex {
centres: Vec<Pos2>,
grid: Option<ScreenGrid>,
key: Option<(usize, u32, u32, u32)>,
/// Points distance-tested by the last [`pick`](Self::pick) — the honesty field. A
/// linear scan would report the node count.
pub last_candidates: usize,
}
impl PickIndex {
/// Rebuild if the projection changed. Cheap no-op when it did not.
pub fn ensure(&mut self, model: &GraphModel, origin: Pos2, zoom: f32) {
let key = (model.nodes.len(), origin.x.to_bits(), origin.y.to_bits(), zoom.to_bits());
if self.key == Some(key) && self.grid.is_some() {
return;
}
self.centres = model.nodes.iter().map(|n| origin + n.pos.to_vec2() * zoom).collect();
self.grid = Some(ScreenGrid::build(&self.centres));
self.key = Some(key);
}
/// The node index whose chip contains `p`, using the index. Returns `None` outside
/// every chip.
///
/// **Byte-for-byte the same answer as the linear scan it replaces.** A node's chip
/// is the rect `|p − centre| ≤ half` componentwise, so every possible winner has its
/// centre inside `p ± half` — one grid rect query returns a superset of those, the
/// exact rect test filters it, and the **lowest surviving index** wins, which is
/// what `find_map` over the node list returned. Getting that tiebreak wrong is the
/// whole risk of swapping a scan for an index: when chips overlap (they do at low
/// zoom, `BOX_W` is 184 px) "nearest centre" and "first in paint order" are
/// different nodes, and the fast answer would silently be a different one.
/// `tests/gpu_fallback.rs` sweeps 600 probes across both and demands equality.
pub fn pick(&mut self, p: Pos2, zoom: f32) -> Option<usize> {
let grid = self.grid.as_ref()?;
let half = Vec2::new(BOX_W, BOX_H) * 0.5 * zoom;
let mut cands: Vec<u32> = Vec::new();
grid.query_rect(Rect::from_center_size(p, half * 2.0), &mut cands);
self.last_candidates = cands.len();
cands
.into_iter()
.find(|&i| {
let c = self.centres[i as usize];
(p.x - c.x).abs() <= half.x && (p.y - c.y).abs() <= half.y
})
.map(|i| i as usize)
}
}
// ─────────────────────────────────────────────────────────────────────────────
// The GPU cloud lane
// ─────────────────────────────────────────────────────────────────────────────
/// Push the instanced GPU cloud for `rect` and report whether it drew — the ONE gate
/// the painter consults before skipping its CPU chip/edge loops.
///
/// Without the `wgpu` feature this is a compile-time `false`, so a build with no GPU
/// stack keeps the CPU painter and nothing downstream changes shape.
#[cfg(feature = "wgpu")]
pub fn draw_gpu_cloud(
ui: &egui::Ui,
rect: Rect,
model: &GraphModel,
origin: Pos2,
zoom: f32,
use_gpu: bool,
) -> bool {
use facett_core::render::gpu::graphcloud::{cloud, CloudBuilder};
if model.nodes.is_empty() {
return false;
}
cloud::draw_cloud(ui, rect, use_gpu, |px_w, px_h| {
// The offscreen is in PHYSICAL px; the canvas geometry is in points. Scale by
// the same factor egui used, derived from the rect the callback maps onto so
// the two frames cannot drift.
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 project = |p: Pos2| to_px(origin + p.to_vec2() * zoom);
let idx: std::collections::HashMap<&str, usize> =
model.nodes.iter().enumerate().map(|(i, n)| (n.id.as_str(), i)).collect();
let b = CloudBuilder::default();
let r = (BOX_H * 0.5 * zoom * sy).max(1.0);
b.scene(
model.nodes.iter().map(|n| (project(n.pos), r, n.fill)),
model.edges.iter().filter_map(|e| {
let (&fi, &ti) = (idx.get(e.from.as_str())?, idx.get(e.to.as_str())?);
Some((project(model.nodes[fi].pos), project(model.nodes[ti].pos), 1.5, e.color))
}),
)
})
}
/// Could the GPU cloud paint in this process *right now*? `false` when the crate was
/// built without `wgpu`, or when no host has installed a cloud renderer.
///
/// Exposed so a test can state which world it is asserting in (a fallback test is
/// meaningless on a box where the renderer IS installed) and a host can log which lane
/// it got instead of guessing from a frame time.
#[must_use]
pub fn gpu_cloud_available() -> bool {
#[cfg(feature = "wgpu")]
{
facett_core::render::gpu::graphcloud::cloud::cloud_renderer_installed()
}
#[cfg(not(feature = "wgpu"))]
{
false
}
}
/// No-`wgpu` build: the GPU lane does not exist, so the CPU painter always runs.
#[cfg(not(feature = "wgpu"))]
#[allow(clippy::needless_pass_by_value, unused_variables)]
pub fn draw_gpu_cloud(
ui: &egui::Ui,
rect: Rect,
model: &GraphModel,
origin: Pos2,
zoom: f32,
use_gpu: bool,
) -> bool {
false
}
// ─────────────────────────────────────────────────────────────────────────────
// Legibility planning (pure — no painting, so it is headless-testable)
// ─────────────────────────────────────────────────────────────────────────────
/// The per-frame legibility PLAN: which edges to draw and where the labels go, plus the
/// projected chip centres. Pure, so a test can assert it (and a bench can time it) with
/// no `egui::Ui`.
pub struct FramePlan {
/// The shared plan from [`facett_core::legibility::plan_frame`].
pub inner: CoreFramePlan,
/// Projected chip centres, index-aligned with `model.nodes`.
pub centres: Vec<Pos2>,
pub report: LegibilityReport,
}
impl FramePlan {
/// Edge indices to draw, ascending. `None` = draw them all (thinning off).
#[must_use]
pub fn edges(&self) -> Option<&Vec<u32>> {
self.inner.edges.as_ref()
}
/// Label placements, or `None` when thinning is off (paint them all, as before).
#[must_use]
pub fn labels(&self) -> Option<&LabelPlacement> {
self.inner.labels.as_ref()
}
}
/// Plan one frame: project, thin the edges by ink budget, place the labels by
/// collision. `lit` is the downstream-lit set (never thinned), `selected` is pinned.
///
/// The *decisions* all happen in [`facett_core::legibility::plan_frame`] — this
/// function only lowers a [`GraphModel`] into that shared vocabulary (project the
/// chips, measure the labels, rank by "is it on the lit trace"). Two panes therefore
/// cannot end up with two different definitions of readable (L5).
#[must_use]
#[allow(clippy::too_many_arguments)] // public signature hosts call: kept as is
pub fn plan_frame(
model: &GraphModel,
origin: Pos2,
zoom: f32,
viewport: Rect,
selected: Option<&str>,
lit: &std::collections::BTreeSet<String>,
label_px_per_char: f32,
opts: PaintOpts,
) -> FramePlan {
let centres: Vec<Pos2> = model.nodes.iter().map(|n| origin + n.pos.to_vec2() * zoom).collect();
let idx: std::collections::HashMap<&str, u32> =
model.nodes.iter().enumerate().map(|(i, n)| (n.id.as_str(), i as u32)).collect();
let label_size: Vec<Vec2> = model
.nodes
.iter()
.map(|n| {
Vec2::new(
(n.label.chars().count() as f32 * label_px_per_char).max(4.0),
11.0 * zoom.clamp(0.7, 1.4),
)
})
.collect();
// Priority: a lit node outranks an unlit one, then the label that says more
// (a longer name carries more information in a dep graph); ties fall to the input
// order via the placer's index tiebreak.
let label_priority: Vec<f32> = model
.nodes
.iter()
.map(|n| {
(if lit.contains(&n.id) { 1000.0 } else { 0.0 }) + n.label.chars().count() as f32
})
.collect();
let label_pinned: Vec<bool> =
model.nodes.iter().map(|n| selected == Some(n.id.as_str())).collect();
// A dangling endpoint becomes u32::MAX, which `plan_frame` treats as off-screen.
let edges: Vec<(u32, u32)> = model
.edges
.iter()
.map(|e| {
(
idx.get(e.from.as_str()).copied().unwrap_or(u32::MAX),
idx.get(e.to.as_str()).copied().unwrap_or(u32::MAX),
)
})
.collect();
// An edge on the lit trace is the answer to the user's question; never thinned.
let edge_always: Vec<bool> = model
.edges
.iter()
.map(|e| lit.contains(&e.from) && lit.contains(&e.to))
.collect();
let inner = core_plan_frame(
&FrameInput {
centres: ¢res,
label_size: &label_size,
label_priority: &label_priority,
label_pinned: &label_pinned,
edges: &edges,
edge_always: &edge_always,
edge_weight: &[],
viewport,
},
FrameOpts {
thin_labels: opts.thin_labels,
thin_edges: opts.thin_edges,
label_pad: opts.label_pad,
edge_cell: opts.edge_cell,
keep_per_bucket: opts.keep_per_bucket,
},
);
let report = LegibilityReport {
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,
..LegibilityReport::default()
};
FramePlan { inner, centres, report }
}
/// Draw the planned labels. Separated from [`plan_frame`] so the planning half stays
/// pure and testable while this half is the only piece that needs a painter.
pub fn paint_planned_labels(
painter: &egui::Painter,
model: &GraphModel,
plan: &FramePlan,
zoom: f32,
text: Color32,
) {
let Some(p) = plan.labels() else { return };
for pl in &p.placed {
let Some(n) = model.nodes.get(pl.index) else { continue };
painter.text(
pl.rect.center(),
egui::Align2::CENTER_CENTER,
&n.label,
egui::FontId::proportional(11.0 * zoom.clamp(0.7, 1.4)),
text,
);
}
}