facett-graphview/src/legible.rs
//! **Legibility at scale + the shared instanced GPU cloud lane** for the graph render
//! engine.
//!
//! `facett-graphview` is the consolidated engine: a `GraphModel` + `Camera` lowered to
//! pixels, either through the CPU rasterizer ([`crate::cpu`]) or an egui pane
//! ([`crate::decorated_view::DecoratedGraphView`]). At 100 000 nodes both of those hit
//! the same two independent walls the whole family hits — the single-core tessellation
//! wall and the *unreadable pane* wall — and both are cured here from the shared
//! `facett-core` primitives, never from a private copy (L5):
//!
//! - [`facett_core::legibility`] — the [`PickIndex`], collision-avoiding label
//! placement, and the per-cell edge ink budget.
//! - [`facett_core::render::gpu::graphcloud`] — the instanced node/edge renderer, the
//! SAME one `facett-graph3d` installs and `facett-graphpan` paints through.
//!
//! Everything here is **opt-in and default off**; `render_to_rgba`, `render_graph_clipped`
//! and `pick` are untouched, so every existing golden and report is byte-identical.
use egui::{Pos2, Rect, Vec2};
use facett_core::legibility::{
plan_frame, FrameInput, FrameOpts, FramePlan, LabelPlacement, ScreenGrid,
};
use crate::model::{Camera, GraphModel, BOX_H, BOX_W};
#[cfg(feature = "gpu-cloud")]
use crate::model::Color;
/// Per-pane legibility + GPU opt-ins. `Default` is **everything off** = the historical
/// pane, so adopting the type cannot change a pixel until a host asks it to.
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct ViewOpts {
/// Paint the node/edge cloud as GPU instances (feature `gpu-cloud` + an installed
/// renderer; falls back to the CPU painter otherwise).
pub gpu_cloud: bool,
/// Place labels with collision avoidance and drop the losers.
pub thin_labels: bool,
/// Apply a per-screen-cell ink budget to the edges.
pub thin_edges: bool,
}
impl ViewOpts {
/// Nothing enabled ⇒ the paint path is bit-identical to the historical one.
#[must_use]
pub fn is_off(&self) -> bool {
!self.gpu_cloud && !self.thin_labels && !self.thin_edges
}
}
/// What one painted frame's legibility work did — the observable published through
/// `state_json` so a robot asserts on numbers, not on prose.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct ViewReport {
/// Did the instanced GPU cloud paint? `false` also covers "opted in but no
/// renderer installed" — the case that must fall back, 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,
/// 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 pane has uploaded to the resident lane so far — constant across
/// camera-only frames, +1 per model / unfold change.
pub resident_uploads: u64,
}
impl ViewReport {
/// 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.
#[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,
})
}
}
/// The projected frame plan for a pane: which edges survive the ink budget and where
/// each surviving label goes. All decisions come from
/// [`facett_core::legibility::plan_frame`] — this only lowers the graphview model into
/// that shared vocabulary (L5).
pub struct ViewPlan {
pub inner: FramePlan,
pub report: ViewReport,
}
impl ViewPlan {
/// Edge indices to draw, ascending; `None` = draw them all.
#[must_use]
pub fn edges(&self) -> Option<&Vec<u32>> {
self.inner.edges.as_ref()
}
/// Label placements; `None` = paint every label as before.
#[must_use]
pub fn labels(&self) -> Option<&LabelPlacement> {
self.inner.labels.as_ref()
}
}
/// Plan one pane frame. `visible` gates folded-away nodes out of both the label ladder
/// and the edge budget; `lit` edges are never thinned; `selected` is pinned.
#[must_use]
#[allow(clippy::too_many_arguments)] // public signature hosts call: kept as is
pub fn plan_view(
model: &GraphModel,
origin: Pos2,
zoom: f32,
viewport: Rect,
visible: &std::collections::BTreeSet<String>,
lit: &std::collections::BTreeSet<String>,
selected: Option<&str>,
opts: ViewOpts,
) -> ViewPlan {
let centres: Vec<Pos2> =
model.nodes.iter().map(|n| origin + egui::vec2(n.pos.x, n.pos.y) * 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 char_px = 6.0 * zoom.clamp(0.7, 1.4);
let label_size: Vec<Vec2> = model
.nodes
.iter()
.map(|n| {
// A folded-away node offers no label at all (zero size = never considered).
if visible.contains(&n.id) {
Vec2::new((n.label.chars().count() as f32 * char_px).max(4.0), 11.0 * zoom.clamp(0.7, 1.4))
} else {
Vec2::ZERO
}
})
.collect();
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();
let edges: Vec<(u32, u32)> = model
.edges
.iter()
.map(|e| {
let vis = visible.contains(&e.from) && visible.contains(&e.to);
if vis {
(
idx.get(e.from.as_str()).copied().unwrap_or(u32::MAX),
idx.get(e.to.as_str()).copied().unwrap_or(u32::MAX),
)
} else {
(u32::MAX, u32::MAX)
}
})
.collect();
let edge_always: Vec<bool> =
model.edges.iter().map(|e| lit.contains(&e.from) && lit.contains(&e.to)).collect();
let inner = 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,
..FrameOpts::default()
},
);
let report = ViewReport {
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,
..ViewReport::default()
};
ViewPlan { inner, report }
}
/// A cached screen-space pick index over the projected chip centres.
///
/// [`crate::clip::pick`] resolves a probe by scanning **every** node in the model and
/// projecting it — `O(n)` per pointer event. That is invisible on a 40-node board and
/// ruinous on a 100 000-node one, especially on hover, where it runs on every mouse
/// move. This builds a [`ScreenGrid`] once per camera and answers from the local
/// neighbourhood.
///
/// The answer is **identical** to `pick`'s — that is asserted directly in
/// `tests/legibility.rs` by sweeping probes across both and comparing, because a fast
/// wrong answer is worse than a slow right one.
#[derive(Default)]
pub struct PickIndex {
centres: Vec<Pos2>,
/// Node index for each entry of `centres` — the *reverse* of `pick`'s scan order,
/// so topmost-wins ties resolve the same way (later nodes draw over earlier ones).
order: Vec<usize>,
grid: Option<ScreenGrid>,
key: Option<(usize, u32, u32, u32)>,
/// Points distance-tested by the last [`pick`](Self::pick). A linear scan would
/// report the node count; this is the honesty field that makes the "cost tracks
/// what is on screen" claim checkable rather than merely written down.
pub last_candidates: usize,
}
impl PickIndex {
/// Rebuild the index if the camera or the model changed; a no-op otherwise.
pub fn ensure(&mut self, model: &GraphModel, camera: &Camera) {
let key = (
model.nodes.len(),
camera.zoom.to_bits(),
camera.pan_x.to_bits(),
camera.pan_y.to_bits(),
);
if self.key == Some(key) && self.grid.is_some() {
return;
}
// Reverse order = `pick`'s topmost-wins scan direction.
self.order = (0..model.nodes.len()).rev().collect();
self.centres = self
.order
.iter()
.map(|&i| {
let (x, y) = camera.project(model.nodes[i].pos);
Pos2::new(x, y)
})
.collect();
self.grid = Some(ScreenGrid::build(&self.centres));
self.key = Some(key);
}
/// The node index whose chip contains `probe`, honouring `rect` — the indexed twin
/// of [`crate::clip::pick`], returning **the identical node**.
///
/// A node's chip is the rect `|probe − centre| ≤ half` componentwise, so every
/// possible winner has its centre inside `probe ± half`: one grid rect query returns
/// a superset, the exact rect test filters it, and the **first candidate in
/// `pick`'s own scan direction** wins. That direction matters — `pick` iterates
/// `.rev()` so a later (topmost-painted) node beats an earlier one, and chips do
/// overlap at low zoom. `centres` is stored in that reversed order, so "lowest
/// index here" is "topmost wins" there. `tests/legibility.rs` sweeps probes across
/// both and demands equality.
pub fn pick(&mut self, camera: &Camera, rect: Rect, probe: Pos2) -> Option<usize> {
if !rect.contains(probe) {
return None;
}
let grid = self.grid.as_ref()?;
let half = Vec2::new(BOX_W, BOX_H) * 0.5 * camera.zoom;
let mut cands: Vec<u32> = Vec::new();
grid.query_rect(Rect::from_center_size(probe, half * 2.0), &mut cands);
self.last_candidates = cands.len();
cands
.into_iter()
.find(|&i| {
let c = self.centres[i as usize];
(probe.x - c.x).abs() <= half.x && (probe.y - c.y).abs() <= half.y
})
.map(|i| self.order[i as usize])
}
}
/// Push the shared instanced GPU cloud for `rect`, returning whether it drew — the ONE
/// gate a pane consults before skipping its CPU chip/edge loops.
///
/// The `use_gpu` opt-in is *not* sufficient on its own and deliberately cannot be: the
/// decision is delegated to
/// [`facett_core::render::gpu::graphcloud::cloud::draw_cloud`], which returns `false`
/// unless a host has actually installed a renderer. Opting in without installing
/// therefore renders the unchanged CPU frame, never a blank pane. Without the `gpu`
/// feature this is a compile-time `false`.
#[cfg(feature = "gpu-cloud")]
pub fn draw_gpu_cloud(
ui: &egui::Ui,
rect: Rect,
model: &GraphModel,
camera: &Camera,
use_gpu: bool,
) -> bool {
use facett_core::render::gpu::graphcloud::{cloud, CloudBuilder};
use std::collections::HashMap;
if model.nodes.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 project = |p: crate::model::Pos| {
let (x, y) = camera.project(p);
Pos2::new((x - rect.min.x) * sx, (y - rect.min.y) * sy)
};
let c32 = |c: Color| egui::Color32::from_rgba_unmultiplied(c.r, c.g, c.b, c.a);
let idx: HashMap<&str, usize> =
model.nodes.iter().enumerate().map(|(i, n)| (n.id.as_str(), i)).collect();
let r = (BOX_H * 0.5 * camera.zoom * sy).max(1.0);
CloudBuilder::default().scene(
model.nodes.iter().map(|n| (project(n.pos), r, c32(n.fill))),
model.edges.iter().filter_map(|e| {
let (&f, &t) = (idx.get(e.from.as_str())?, idx.get(e.to.as_str())?);
Some((project(model.nodes[f].pos), project(model.nodes[t].pos), 1.5, c32(e.color)))
}),
)
})
}
/// No-`gpu-cloud` build: the lane does not exist, so the CPU painter always runs.
#[cfg(not(feature = "gpu-cloud"))]
#[allow(unused_variables)]
pub fn draw_gpu_cloud(
ui: &egui::Ui,
rect: Rect,
model: &GraphModel,
camera: &Camera,
use_gpu: bool,
) -> bool {
false
}