facett-demo/src/gfx_v2/labels.rs
//! **The GPU label-collision lane** (GFX_V2 item 4) — and its first host.
//!
//! Item 4 landed a complete device lane: three compute passes, a 128×96 spatial
//! grid whose cells are claimed by `atomicMax` on a packed priority, a name-repeat
//! slot table so one place name cannot print twice in the same neighbourhood, and
//! the winners appended by `atomicAdd` onto a `DrawIndirectArgs` that the draw then
//! reads back off the device. What it did **not** land is a caller: grep the tree
//! at `1f782af` and `LabelCollider` appears only inside its own module and its own
//! tests. This is the host that drives it.
//!
//! ## What a host has to supply that the lane cannot
//!
//! The collider takes *laid-out glyphs*, not strings — it has no font machinery and
//! should not have any. So this module owns the one genuinely new piece of work:
//! turning a place name into [`GlyphSrc`] quads addressing **epaint's own font
//! atlas**, so the device draws the same glyphs, from the same texture, that
//! `Painter::text` would have drawn. That adapter is [`glyphs_for`]; it is a
//! candidate to graduate into `facett-core` once a second caller wants it, and it
//! lives here rather than there because item 4's internals belong to another lane
//! of this track.
//!
//! ## The evidence discipline
//!
//! `LabelCollider` deliberately exposes **no live survivor count** — the CPU never
//! learns how many labels drew, exactly as item 2 established for the line lane,
//! because the count lives in the indirect buffer and the draw reads it there. That
//! is the right contract and this host does not break it: nothing on the per-frame
//! path reads back anything.
//!
//! But "the right contract" and "nobody is watching" are how five GFX_V2 items went
//! wrong, so this host keeps three separate device-side witnesses:
//!
//! 1. **`frames`** — bumped inside `draw`, only once the compute callback has been
//! submitted with a real candidate set and a bound atlas. A frame in which the
//! lane declined does not count.
//! 2. **`uploads`** — how many times a label set was actually handed to the device.
//! 3. **[`LabelLane::read_device_stats`]** — an explicit, opt-in, **blocking**
//! readback of the indirect draw buffer: the `instance_count` the draw uses,
//! plus `labels_won` / `labels_drawn` / `glyph_overflow`. It stalls the pipeline,
//! so it is called by tests and by the on-demand button, never from the paint
//! loop.
//!
//! `frames` alone is attribution, not proof — a pass over an empty grid would bump
//! it. It is only meaningful paired with (3), which is why `state_json` reports
//! both and never just the first.
use egui::{Rect, Ui};
use facett_core::label_grid::{
label_half_extent, name_hash, priority, GlyphSrc, LabelCandidate, LabelFrame, MAX_VISIBLE_LABELS,
};
use egui_wgpu::wgpu;
use facett_core::render::gpu::LabelCollider;
use serde_json::json;
use super::scene::{Place, Projected, Scene};
/// Text height for a city name, in points.
const CITY_PT: f32 = 13.0;
/// Text height for an address's kommun name, in points.
const PLACE_PT: f32 = 9.5;
// ─────────────────────────────────────────────────────────────────────────────
// Glyph layout — place name → GlyphSrc quads over epaint's font atlas.
// ─────────────────────────────────────────────────────────────────────────────
/// Lay one label's text out into [`GlyphSrc`] quads, in **label-local points**
/// centred on the label's anchor, addressing epaint's font atlas by normalised UV.
///
/// Returns the quads and the laid-out text's `(width, height)` in points, which is
/// what [`label_half_extent`] needs to build the candidate's collision box. The two
/// must come from the SAME layout: a half-extent computed from an estimated advance
/// while the glyphs come from a real galley is a collision box that does not match
/// the ink, and the symptom is labels that overlap slightly while the grid insists
/// they do not.
///
/// Glyphs with no atlas rectangle (a space) contribute to the advance and produce no
/// quad — including one would give the device a zero-area triangle pair per space,
/// which is invisible, wasteful, and counts against `LABEL_GLYPH_CAPACITY`.
pub fn glyphs_for(ctx: &egui::Context, text: &str, pt: f32, atlas: [u32; 2]) -> (Vec<GlyphSrc>, [f32; 2]) {
let font = egui::FontId::proportional(pt);
let galley = ctx.fonts_mut(|f| f.layout_no_wrap(text.to_owned(), font, egui::Color32::WHITE));
let size = galley.size();
// Centre the run on the anchor, so the collision box and the ink share a centre.
let ox = -size.x * 0.5;
let oy = -size.y * 0.5;
let (aw, ah) = (atlas[0].max(1) as f32, atlas[1].max(1) as f32);
let mut out = Vec::new();
for row in &galley.rows {
for g in &row.glyphs {
let uv = g.uv_rect;
if uv.max[0] <= uv.min[0] || uv.max[1] <= uv.min[1] {
continue; // no ink (space) — advance only
}
let min_x = ox + g.pos.x + row.pos.x + uv.offset.x;
let min_y = oy + g.pos.y + row.pos.y + uv.offset.y;
out.push(GlyphSrc {
off_min: [min_x, min_y],
off_max: [min_x + uv.size.x, min_y + uv.size.y],
uv_min: [uv.min[0] as f32 / aw, uv.min[1] as f32 / ah],
uv_max: [uv.max[0] as f32 / aw, uv.max[1] as f32 / ah],
});
}
}
(out, [size.x, size.y])
}
// ─────────────────────────────────────────────────────────────────────────────
// The candidate set.
// ─────────────────────────────────────────────────────────────────────────────
/// What was uploaded, so the host can tell whether the label set changed without
/// re-laying every glyph. Re-uploading identical candidates every frame would work
/// and would also make `uploads` meaningless as a witness.
#[derive(Clone, PartialEq, Debug, Default)]
struct UploadKey {
places: usize,
atlas: [u32; 2],
/// Ranks depend on which places are on screen, so the visible set is part of
/// the key.
visible: usize,
}
/// Build the candidate + glyph arrays for the visible part of a scene.
///
/// Priorities are **unique by construction**, because the collision rule is
/// `atomicMax` followed by "did the cell keep MY priority" — two candidates sharing
/// a priority would both recognise themselves as the winner and both would draw,
/// which is the exact overlap the pass exists to prevent. `priority(rank, order)`
/// packs a rank byte with a decreasing order field, so passing a distinct `order`
/// per candidate is what makes them unique; `order` here is the index in the
/// candidate array.
fn build(
ctx: &egui::Context,
scene: &Scene,
projected: &[Projected],
rect: &Rect,
atlas: [u32; 2],
) -> (Vec<LabelCandidate>, Vec<GlyphSrc>) {
let mut cands: Vec<LabelCandidate> = Vec::new();
let mut glyphs: Vec<GlyphSrc> = Vec::new();
// Cities first, so their (higher) ranks are also earlier in the array — with
// ties broken by `order`, earlier is stronger, and the two orderings agreeing
// means the priority is not fighting itself.
let mut idx: Vec<usize> = (0..scene.places.len()).collect();
idx.sort_by(|&a, &b| {
let (pa, pb) = (&scene.places[a], &scene.places[b]);
pb.weight.partial_cmp(&pa.weight).unwrap_or(std::cmp::Ordering::Equal).then(a.cmp(&b))
});
for i in idx {
let p: &Place = &scene.places[i];
let pr = projected[i];
if !pr.visible {
continue;
}
// SCREEN-SPACE candidates: the host has already projected through the view
// core, so the device must not project again. Feeding it world positions
// would mean two projections of one scene — the drift item 6 removed.
let sx = pr.x - rect.left();
let sy = pr.y - rect.top();
if sx < 0.0 || sy < 0.0 || sx > rect.width() || sy > rect.height() {
continue;
}
let pt = if p.is_city() { CITY_PT } else { PLACE_PT };
let (gs, text_size) = glyphs_for(ctx, p.name, pt, atlas);
if gs.is_empty() {
continue;
}
let half = label_half_extent(text_size);
// Rank: cities dominate. Within a band, `order` (below) breaks the tie.
let rank: u8 = if p.is_city() { 200 } else { 64 };
let order = cands.len() as u32;
let start = glyphs.len() as u32;
glyphs.extend_from_slice(&gs);
cands.push(LabelCandidate {
pos: [sx, sy],
half_px: half,
priority: priority(rank, order),
name_hash: name_hash(p.name),
glyph_start: start,
glyph_count: gs.len() as u32,
lod: 0,
flags: facett_core::label_grid::FLAG_SCREEN_SPACE,
_pad: [0, 0],
});
}
(cands, glyphs)
}
// ─────────────────────────────────────────────────────────────────────────────
// The lane.
// ─────────────────────────────────────────────────────────────────────────────
/// Host-side state for the label lane: the upload key, the witnesses, and the last
/// device readback.
#[derive(Default)]
pub struct LabelLane {
key: UploadKey,
/// Candidates in the last upload — the ceiling on what could possibly draw.
candidates: u32,
glyphs: u32,
uploads: u64,
/// Frames in which the compute callback was actually submitted.
frames: u64,
/// The last explicit indirect-buffer readback, if one has been taken.
stats: Option<DeviceStats>,
/// Why the lane declined, when it did — so an off lane is never silent.
declined: Option<&'static str>,
}
/// What the device wrote, read back out of the indirect draw buffer.
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct DeviceStats {
/// The `instance_count` the indirect draw actually uses. This is the number the
/// GPU decided; nothing on the CPU chose it.
pub instance_count: u32,
/// Candidates that won a grid cell (before the visible-label ink budget).
pub labels_won: u32,
/// Candidates that won AND fitted in the budget and the glyph buffer — the ones
/// on screen.
pub labels_drawn: u32,
/// Glyphs dropped for want of capacity. Non-zero means the scene overflowed the
/// buffer, and the picture is missing ink.
pub glyph_overflow: u32,
/// The vertex count in the same indirect args, as a wiring check: the label quad
/// is 6 vertices, so anything else means the args were not written by `run`.
pub vertex_count: u32,
}
impl LabelLane {
/// Drive the lane for one pane. Returns **true only if the device took the
/// frame** — which is the sole licence for the caller to skip its CPU painter.
///
/// Returning true optimistically is the flowsim bug precisely: the host skipped
/// its CPU particles, the callback found no renderer, and the overlay was
/// silently missing while every pixel assertion stayed green.
pub fn draw(
&mut self,
ui: &Ui,
rect: &Rect,
scene: &Scene,
projected: &[Projected],
theme: &facett_core::Theme,
) -> bool {
let Some(rs) = super::render_state() else {
self.declined = Some("no render state (host never armed the lane)");
return false;
};
let ppp = ui.ctx().pixels_per_point();
let px_w = rect.width() * ppp;
let px_h = rect.height() * ppp;
if !(px_w >= 1.0 && px_h >= 1.0) {
self.declined = Some("degenerate pane");
return false;
}
// The atlas epaint is actually using this frame. Read every call because
// egui grows and re-packs it as new glyphs are rasterised; a cached size
// would silently start addressing the wrong texels.
let (atlas_size, atlas_rgba) = ui.ctx().fonts(|f| {
let img = f.image();
// `as_raw` IS premultiplied Rgba8Unorm, width*height*4 — exactly what
// `set_atlas` documents. Re-packing it per channel would be a copy that
// could disagree with epaint about premultiplication.
([img.width() as u32, img.height() as u32], img.as_raw().to_vec())
});
let (cands, glyphs) = build(ui.ctx(), scene, projected, rect, atlas_size);
if cands.is_empty() {
self.declined = Some("no visible labels");
return false;
}
let visible = projected.iter().filter(|p| p.visible).count();
let key = UploadKey { places: scene.places.len(), atlas: atlas_size, visible };
// One install for the whole process; `install_renderer` is idempotent and a
// second collider would be a second set of GPU buffers for one device.
facett_core::render::gpu::install_renderer(&rs, LabelCollider::new);
{
let mut r = rs.renderer.write();
let Some(collider) = r.callback_resources.get_mut::<LabelCollider>() else {
self.declined = Some("collider not installed");
return false;
};
if self.key != key || self.candidates == 0 {
collider.set_atlas(&rs.device, &rs.queue, atlas_size, &atlas_rgba);
collider.upload(&rs.device, &rs.queue, &cands, &glyphs);
self.key = key;
self.candidates = cands.len() as u32;
self.glyphs = glyphs.len() as u32;
self.uploads += 1;
}
if !collider.ready() {
self.declined = Some("collider has no atlas or no candidates");
return false;
}
}
// The per-frame work: a paint callback that records the three compute passes
// in `prepare` and the indirect draw in `paint`.
let frame = LabelFrame {
zoom: [1.0, 1.0],
ref_pos: [0.0, 0.0],
// Candidates are already pane-local screen-space, so no re-centring is
// needed — but the viewport must be the PANE in physical pixels, the
// space `pos * ppp` lives in.
screen_center: [0.0, 0.0],
viewport: [px_w, px_h],
lod: 0,
ink: to_rgba(theme.text),
halo: to_rgba(theme.bg),
};
ui.painter().add(egui_wgpu::Callback::new_paint_callback(*rect, LabelCallback { frame, ppp }));
self.frames += 1;
self.declined = None;
true
}
/// **Explicitly** read the indirect draw buffer back off the device.
///
/// Blocking: it submits, waits on `device.poll`, and copies one 32-byte header.
/// That is roughly a frame of latency on the calling thread, so it is a button
/// and a test hook, never part of the paint loop. It is also the only thing in
/// this file that can tell a lane that ran from a lane that merely counted a
/// frame.
pub fn read_device_stats(&mut self) -> Option<DeviceStats> {
let rs = super::render_state()?;
let r = rs.renderer.read();
let collider = r.callback_resources.get::<LabelCollider>()?;
let st = collider.state_readback(&rs.device, &rs.queue);
let s = DeviceStats {
instance_count: st.args.instance_count,
labels_won: st.stats.labels_won,
labels_drawn: st.stats.labels_drawn,
glyph_overflow: st.stats.glyph_overflow,
vertex_count: st.args.vertex_count,
};
self.stats = Some(s);
Some(s)
}
/// Frames in which the compute callback was submitted. Attribution, not proof —
/// see the module docs.
pub fn frames(&self) -> u64 {
self.frames
}
/// Candidates in the last upload.
pub fn candidates(&self) -> u32 {
self.candidates
}
/// The last device readback, if one has been taken.
pub fn device_stats(&self) -> Option<DeviceStats> {
self.stats
}
/// The lane's own account of itself.
pub fn state_json(&self, requested: bool) -> serde_json::Value {
json!({
"lane": if self.frames > 0 { "gpu" } else { "cpu" },
"requested": requested,
"declined": self.declined,
// Host-side: what was offered to the device.
"candidates": self.candidates,
"glyphs": self.glyphs,
"uploads": self.uploads,
// Device-side attribution: frames whose compute callback was submitted.
"frames": self.frames,
"budget": MAX_VISIBLE_LABELS,
// Device-side PROOF, when it has been read: the indirect draw's own
// instance count and the collision tallies.
"device": self.stats.map(|s| json!({
"instance_count": s.instance_count,
"vertex_count": s.vertex_count,
"labels_won": s.labels_won,
"labels_drawn": s.labels_drawn,
"glyph_overflow": s.glyph_overflow,
// The headline: how many candidates the collision pass threw away.
"suppressed": s.labels_won.saturating_sub(s.labels_drawn),
"rejected_by_collision": self.candidates.saturating_sub(s.labels_won),
})),
})
}
}
fn to_rgba(c: egui::Color32) -> [f32; 4] {
let a = c.to_array();
[a[0] as f32 / 255.0, a[1] as f32 / 255.0, a[2] as f32 / 255.0, a[3] as f32 / 255.0]
}
// ─────────────────────────────────────────────────────────────────────────────
// The paint callback.
// ─────────────────────────────────────────────────────────────────────────────
struct LabelCallback {
frame: LabelFrame,
ppp: f32,
}
impl egui_wgpu::CallbackTrait for LabelCallback {
fn prepare(
&self,
_device: &wgpu::Device,
queue: &wgpu::Queue,
_screen: &egui_wgpu::ScreenDescriptor,
encoder: &mut wgpu::CommandEncoder,
resources: &mut egui_wgpu::CallbackResources,
) -> Vec<wgpu::CommandBuffer> {
let Some(collider) = resources.get_mut::<LabelCollider>() else { return vec![] };
if !collider.ready() {
return vec![];
}
collider.run(queue, encoder, &self.frame);
vec![]
}
fn paint(
&self,
_info: egui::PaintCallbackInfo,
pass: &mut wgpu::RenderPass<'static>,
resources: &egui_wgpu::CallbackResources,
) {
let Some(collider) = resources.get::<LabelCollider>() else { return };
// `draw_indirect` reads the instance count out of the buffer the compute
// pass wrote. The CPU does not know it and must not be told: that is the
// contract item 2 set and item 4 kept.
collider.draw_indirect(pass);
let _ = self.ppp;
}
}
#[cfg(test)]
mod tests {
use super::*;
/// An egui context with a warmed font atlas containing the glyphs the tests ask
/// for. `layout_no_wrap` rasterises on demand, but the atlas image is only
/// published after a frame, so the warm-up is not optional.
fn warm_ctx(sample: &str) -> (egui::Context, [u32; 2]) {
let ctx = egui::Context::default();
let s = sample.to_owned();
ctx.run_ui(egui::RawInput::default(), |ui| {
ui.label(&s);
}).textures_delta.clear();
let atlas = ctx.fonts(|f| {
let i = f.image();
[i.width() as u32, i.height() as u32]
});
(ctx, atlas)
}
/// The projected real scene, as every candidate test sees it.
fn projected_scene() -> (Scene, Vec<Projected>, Rect) {
let scene = Scene::sweden();
let rect = Rect::from_min_size(egui::Pos2::ZERO, egui::vec2(900.0, 900.0));
let tab = crate::gfx_v2::GfxV2Tab::default();
let projected = scene.project(&tab.view_2d(450.0), (450.0, 450.0), 450.0);
(scene, projected, rect)
}
/// The glyph adapter produces real atlas quads for a real name, centred on the
/// anchor, with UVs inside the atlas.
///
/// Red-when-broken: a layout that returns an empty run, or UVs outside `0..=1`
/// (the symptom of dividing by the wrong atlas size), fails here rather than
/// drawing garbage on screen.
#[test]
fn glyph_layout_addresses_the_real_font_atlas() {
let (ctx, atlas) = warm_ctx("Stockholm Göteborg Malmö");
assert!(atlas[0] > 0 && atlas[1] > 0, "the atlas exists");
let (gs, size) = glyphs_for(&ctx, "Stockholm", 13.0, atlas);
assert_eq!(gs.len(), 9, "one quad per inked glyph in `Stockholm`");
assert!(size[0] > 20.0 && size[1] > 5.0, "the laid-out text has a real extent, got {size:?}");
for (i, g) in gs.iter().enumerate() {
assert!(g.off_max[0] > g.off_min[0], "glyph {i} has positive width");
assert!(g.off_max[1] > g.off_min[1], "glyph {i} has positive height");
for k in 0..2 {
assert!(
(0.0..=1.0).contains(&g.uv_min[k]) && (0.0..=1.0).contains(&g.uv_max[k]),
"glyph {i} uv[{k}] is normalised into the atlas: {:?}..{:?}",
g.uv_min,
g.uv_max,
);
assert!(g.uv_max[k] > g.uv_min[k], "glyph {i} uv[{k}] is non-degenerate");
}
}
// Centred on the anchor: the run straddles x = 0.
let min_x = gs.iter().map(|g| g.off_min[0]).fold(f32::MAX, f32::min);
let max_x = gs.iter().map(|g| g.off_max[0]).fold(f32::MIN, f32::max);
assert!(min_x < 0.0 && max_x > 0.0, "the glyph run is centred on the anchor: {min_x}..{max_x}");
}
/// A bigger point size must produce bigger ink. This is the "identity value"
/// guard from LAW 2 in its label form: a glyph is four vertices at 6 pt and at
/// 60 pt, so a test that only counts quads cannot tell a working text size from
/// a dead one.
#[test]
fn point_size_actually_reaches_the_glyph_quads() {
let (ctx, atlas) = warm_ctx("Stockholm");
let (small, s_size) = glyphs_for(&ctx, "Stockholm", 8.0, atlas);
let (big, b_size) = glyphs_for(&ctx, "Stockholm", 24.0, atlas);
assert_eq!(small.len(), big.len(), "the same glyphs either way");
assert!(b_size[0] > s_size[0] * 2.0, "24 pt is much wider than 8 pt: {b_size:?} vs {s_size:?}");
let area = |g: &[GlyphSrc]| -> f32 {
g.iter().map(|q| (q.off_max[0] - q.off_min[0]) * (q.off_max[1] - q.off_min[1])).sum()
};
assert!(area(&big) > area(&small) * 2.0, "and the QUADS are bigger, not just the reported extent");
}
/// A space contributes advance but no quad — otherwise every space costs a
/// zero-area triangle pair against `LABEL_GLYPH_CAPACITY`.
#[test]
fn spaces_advance_without_producing_a_quad() {
let (ctx, atlas) = warm_ctx("ab a b");
let (two, size_two) = glyphs_for(&ctx, "ab", 12.0, atlas);
let (spaced, size_spaced) = glyphs_for(&ctx, "a b", 12.0, atlas);
assert_eq!(two.len(), 2);
assert_eq!(spaced.len(), 2, "`a b` is still two inked glyphs");
assert!(size_spaced[0] > size_two[0], "but it is wider — the space advanced");
}
/// **Every candidate priority is unique.** The collision rule is `atomicMax`
/// plus "did the cell keep MY priority", so a tie makes both labels recognise
/// themselves as the winner and both draw — the exact overlap the pass exists
/// to remove, and invisible in any test that only counts survivors.
#[test]
fn candidate_priorities_are_unique_over_the_whole_real_scene() {
let (ctx, atlas) = warm_ctx("Stockholm Göteborg Malmö Umeå Luleå");
let (scene, projected, rect) = projected_scene();
let (cands, glyphs) = build(&ctx, &scene, &projected, &rect, atlas);
assert!(cands.len() > 100, "the real scene offers many candidates, got {}", cands.len());
let mut pr: Vec<u32> = cands.iter().map(|c| c.priority).collect();
let n = pr.len();
pr.sort_unstable();
pr.dedup();
assert_eq!(pr.len(), n, "no two candidates share a priority");
// Cities outrank addresses, so a city can never lose a cell to an address.
let ncity = cands.iter().filter(|c| c.priority >> 24 == 200).count();
assert!(ncity > 0, "some cities are on screen");
let city_min = cands.iter().take(ncity).map(|c| c.priority).min().unwrap();
let rest_max = cands.iter().skip(ncity).map(|c| c.priority).max().unwrap_or(0);
assert!(city_min > rest_max, "every city outranks every address: {city_min} > {rest_max}");
// Glyph ranges are in-bounds and contiguous — an off-by-one here draws
// another label's letters.
let mut expect = 0u32;
for (i, c) in cands.iter().enumerate() {
assert_eq!(c.glyph_start, expect, "candidate {i} starts where the previous ended");
assert!(c.glyph_count > 0, "candidate {i} has glyphs");
expect += c.glyph_count;
}
assert_eq!(expect as usize, glyphs.len(), "the glyph array is exactly the sum of the runs");
// Screen-space is declared, so the device must not project again.
for c in &cands {
assert_eq!(
c.flags & facett_core::label_grid::FLAG_SCREEN_SPACE,
facett_core::label_grid::FLAG_SCREEN_SPACE,
"candidates are screen-space — the host already projected through the view core",
);
}
}
/// The scene really does put many candidates in one collision cell — otherwise
/// "the collision pass works" would be a claim about a scene with nothing to
/// collide. Measured with the collider's OWN plain-Rust twin, so this is the
/// same rule the shader runs.
#[test]
fn the_real_scene_makes_the_collision_rule_reject_most_candidates() {
let (ctx, atlas) = warm_ctx("Stockholm Göteborg Malmö Umeå Luleå");
let (scene, projected, rect) = projected_scene();
let (cands, _) = build(&ctx, &scene, &projected, &rect, atlas);
let frame = LabelFrame {
zoom: [1.0, 1.0],
ref_pos: [0.0, 0.0],
screen_center: [0.0, 0.0],
viewport: [rect.width(), rect.height()],
lod: 0,
ink: [1.0; 4],
halo: [0.0; 4],
};
let screen = facett_core::label_grid::screen_labels(&cands, &frame);
let survivors = facett_core::label_grid::resolve(&screen, &frame.grid_params());
assert!(
survivors.len() < cands.len() / 2,
"the rule must throw most of the {} candidates away, kept {}",
cands.len(),
survivors.len(),
);
assert!(!survivors.is_empty(), "but not all of them — something must still be readable");
}
}