facett-core/src/label_grid.rs
//! **The label-declutter contract — ONE writer, two executions** (GFX_V2 item 4).
//!
//! A map reads as professional when its names do not collide and a street is
//! lettered once rather than seven times. `facett e88969f` bought that with a greedy
//! CPU pass living inside `facett_geomap::osm2d`'s painter: an `O(n²)` rect-intersect
//! loop plus an `O(n²)` same-name distance scan, both re-run from scratch every
//! frame, capped at 48 labels because that is what the quadratic loops could afford.
//!
//! GFX_V2 §3.B replaces it with three compute passes over a fixed spatial grid. This
//! module is the **algorithm**, written once, in ordinary Rust:
//!
//! 1. **clear** the grid,
//! 2. **claim** — every label writes its priority into each grid cell its padded
//! screen box covers, keeping the maximum,
//! 3. **emit** — a label draws iff it still owns *every* cell it claimed and no
//! higher-priority label with the *same name* claimed a nearby repeat cell.
//!
//! `render::gpu::label_collide`'s `label_collide.wgsl` is the device transcription of
//! exactly this, and `cpu_and_gpu_lanes_resolve_the_same_labels` pins the two
//! together. That is the LAW #5 shape: the collision rule has ONE home, so the
//! fail-safe CPU lane cannot drift from the GPU lane the way the width formula did
//! before `e88969f` (CPU `clamp(zoom/50_000,…)` vs GPU `width × 1.0`).
//!
//! ## Why this is not [`crate::legibility::place_labels`]
//!
//! That placer is the right tool for pins and graph nodes and stays in use for them.
//! It cannot be the one writer here, for a reason that is structural rather than
//! stylistic: it **displaces** a colliding label through a five-position ladder and
//! accepts the first slot that is free *given everything placed so far*. Its answer is
//! therefore a function of iteration order, and an order-dependent rule has no
//! transcription onto a device where ten thousand invocations claim cells in an order
//! nobody chose. The rule below was designed backwards from `atomicMax`: the outcome
//! depends only on each label's own priority, so any interleaving yields the same
//! frame. Road names also never displace — a street name belongs on its street — so
//! the ladder has nothing to offer them.
//!
//! ## Why a grid beats the greedy loop
//!
//! The greedy loop's answer depended on iteration order: it kept the first label that
//! happened to clear every box already placed, so inserting one label could change
//! the fate of a distant one. The grid's answer depends only on **priority**, which is
//! constructed to be strictly unique ([`priority`]), so:
//!
//! * the winner of an overlap is *the highest-priority* label, not "whichever was
//! visited first";
//! * the result is order-independent, which is the precondition for computing it with
//! thousands of threads racing on `atomicMax`;
//! * cost is `O(cells covered)` per label instead of `O(labels placed)`.
//!
//! ## What is approximate, stated plainly
//!
//! * **Quantisation.** Two boxes that merely land in the same cell suppress each other
//! even if the rects miss by a few px. Cells are ~10×8 px at 1280×768, the same
//! order as the [`LABEL_PAD_PX`] breathing room `e88969f` already added, so the
//! visible effect is slightly *more* generous spacing, not less.
//! * **Repeat distance is a hash grid.** The CPU pass measured an exact
//! `distance(p, q) < 380 px` circle. Here a name claims one [`REPEAT_CELL_PX`] cell
//! and checks its 3×3 neighbourhood, so the suppression radius is between one and
//! two cells depending on where in its cell the label sits. The key is
//! `hash(name, cell)` over [`NAME_SLOTS`] slots, so two *different* names can alias
//! and one of them lose its repeat slot; with 16384 slots and a few hundred visible
//! labels that is a low-single-digit-percent chance of one label dropped per frame.
//! Both lanes hash identically, so this is a shared approximation, never a drift.
/// Spatial occupancy grid width, in cells. Fixed (not viewport-derived) so the buffer
/// is allocated once and the shader's indexing is a constant.
pub const GRID_W: u32 = 256;
/// Spatial occupancy grid height, in cells.
pub const GRID_H: u32 = 192;
/// Cells in one spatial region of the grid buffer.
pub const GRID_CELLS: u32 = GRID_W * GRID_H;
/// Slots in the **name-repeat** region. Sized well above the label count a viewport can
/// hold so `hash(name, coarse_cell)` rarely aliases.
pub const NAME_SLOTS: u32 = 16384;
/// Word offset of the **claim** region — who is bidding for each cell this round.
/// Cleared every round.
pub const CLAIM_BASE: u32 = 0;
/// Word offset of the **occupied** region — the priority of the label that actually
/// DREW in each cell. Cleared once per frame and never within a frame.
///
/// This region is the fix for the defect that made a single-pass grid unusable, and it
/// is worth naming because the collapse it caused was 16-fold. With only a claim grid, a
/// label is suppressed by *any* higher-priority claimant — including one that itself
/// lost. So A(100) beats B(90), and then C(80), which overlaps only B, loses to B's
/// dead claim. The chain cascades: measured on the real Liechtenstein clip at 4x fit
/// zoom, 48 labels became 3. The greedy pass never had this problem because it tested a
/// candidate against the boxes it had actually PLACED.
pub const OCC_BASE: u32 = GRID_CELLS;
/// Word offset of the **name-claim** region — the best *bid* for each `(name, coarse
/// cell)` this round. Cleared every round, so a label that loses its pixels also
/// releases its hold on its name.
pub const NAME_CLAIM_BASE: u32 = 2 * GRID_CELLS;
/// Word offset of the **name-won** region — the priority of the same-name label that
/// actually DREW in each `(name, coarse cell)`. Cleared once per frame.
///
/// The repeat filter needs both halves, and the first version of the round loop shipped
/// with only the per-round one — which silently disabled repeat suppression altogether.
/// Round 1 kept the best of the rivals and rejected the rest; round 2 then cleared the
/// bids, so the runner-up faced an empty slot and drew. Four rounds let a street print
/// its name four times. A repeat must lose to ink that is already on the paper, and only
/// a region that survives the round clear can say so.
pub const NAME_WON_BASE: u32 = 2 * GRID_CELLS + NAME_SLOTS;
/// Total `u32` words: claim, occupied, name-claim, name-won. ONE buffer for all four so
/// ONE clear pass empties them (a second buffer is a second chance to forget one — see
/// the residue trap in `GFX_V2` item 2). A per-label **retired** region follows on the
/// device, sized to the candidate count.
pub const GRID_WORDS: u32 = 2 * GRID_CELLS + 2 * NAME_SLOTS;
/// How many claim/emit rounds resolve the frame. Each round settles one more link of an
/// overlap chain (A blocks B blocks C ...), and a dense basemap has long chains: measured
/// on the real Liechtenstein clip, distinct names lettered at 4x fit zoom went 14 (4
/// rounds) -> 22 (8) -> 35 (16) -> 41 (32), and 64 rounds gave exactly the same frame as
/// 32. So 32 is the measured plateau, not a guess. A label still contested after the last
/// round simply does not draw.
///
/// The cost is bounded by the per-label state cache: a label settles once and is skipped
/// in O(1) thereafter, so a round costs only the labels still contested — which after
/// round two or three is a small fraction of the candidate set.
pub const LABEL_ROUNDS: u32 = 32;
/// `e88969f`'s repeat distance: a street name may not reappear within this many px of
/// itself.
pub const MIN_REPEAT_PX: f32 = 380.0;
/// Coarse cell edge for the repeat filter, in screen px.
///
/// **Half** [`MIN_REPEAT_PX`], not all of it. A name claims one coarse cell and checks
/// the 3x3 neighbourhood, so the realised suppression radius runs from one cell
/// (guaranteed) to two (possible). At `c = MIN_REPEAT_PX` that reaches 760 px — wider
/// than the CPU rule it replaces and, on a 900 px pane, effectively "one label per name
/// per view"; it cost another 3x of label density on the Liechtenstein clip. At
/// `c = MIN_REPEAT_PX / 2` the radius is 190..380 px, so it never suppresses a pair the
/// exact 380 px circle would have kept.
pub const REPEAT_CELL_PX: f32 = MIN_REPEAT_PX * 0.5;
/// Breathing room added around a label's text extent before the collision test —
/// `e88969f`'s `LABEL_PAD`, kept because non-overlap alone still lets names touch.
pub const LABEL_PAD_PX: [f32; 2] = [10.0, 6.0];
/// Ink budget per frame. Not an algorithmic bound any more (the grid is the bound);
/// it caps VRAM and keeps the paper from turning grey. **Above this count the two
/// lanes may keep different labels** — the CPU lane truncates in priority order, the
/// GPU lane truncates in `atomicAdd` arrival order. Parity fixtures stay under it.
pub const MAX_VISIBLE_LABELS: u32 = 48;
/// Halo taps drawn under each glyph (the 4-offset outline `e88969f` painted).
pub const HALO_TAPS: u32 = 4;
/// Draw instances a single glyph expands to: its halo taps plus the ink pass.
pub const INSTANCES_PER_GLYPH: u32 = HALO_TAPS + 1;
/// The halo tap offsets, in screen px. Mirrored in `label_collide.wgsl`.
pub const HALO_OFFSETS: [[f32; 2]; HALO_TAPS as usize] =
[[1.0, 0.0], [-1.0, 0.0], [0.0, 1.0], [0.0, -1.0]];
/// FNV-1a over the label text — the name identity the repeat filter keys on. A hash
/// (not the string) because the device has no strings; collisions cost at most one
/// suppressed label, and both lanes compute the same one.
#[must_use]
pub fn name_hash(text: &str) -> u32 {
let mut h: u32 = 0x811C_9DC5;
for b in text.as_bytes() {
h ^= u32::from(*b);
h = h.wrapping_mul(0x0100_0193);
}
// Never 0: 0 is the empty-grid sentinel for priorities, and although name slots
// hold priorities rather than hashes, keeping the hash non-zero means an
// unhashed/defaulted label cannot silently share a slot with every other.
if h == 0 { 1 } else { h }
}
/// The collision **priority** of a label: `rank` in the high 8 bits, `order` in the
/// low 24. Strictly monotone in `rank`, and — because `order` is unique per candidate
/// — **strictly unique overall**.
///
/// Uniqueness is load-bearing twice over. `atomicMax` leaves a cell holding one
/// value; the emit pass recognises the winner by `grid[cell] == priority`, so two
/// labels sharing a priority would *both* believe they won and both draw on top of
/// each other. And a tie would make the outcome depend on thread arrival order, i.e.
/// nondeterministic frame to frame.
///
/// `order` is inverted so that a *lower* index wins, reproducing `e88969f`'s
/// `sort_by(rank desc, x asc)` + first-come-wins greedy order.
#[must_use]
pub fn priority(rank: u8, order: u32) -> u32 {
(u32::from(rank) << 24) | (0x00FF_FFFF - order.min(0x00FF_FFFE))
}
/// The rank reserved for **blockers** — boxes that occupy pixels but print nothing
/// (pin markers, pin labels, a scale bar). They outrank every real label, so a street
/// name can never land on one; this is how `e88969f`'s "the address pins reserve
/// their boxes FIRST" survives the move to a device that has no ordering.
pub const BLOCKER_RANK: u8 = 0xFF;
/// One label as the collision pass sees it: a **screen-space** padded box, a unique
/// priority, its name identity, and its LOD tier.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct ScreenLabel {
/// Box centre, screen px.
pub center: [f32; 2],
/// Half extent including [`LABEL_PAD_PX`], screen px.
pub half: [f32; 2],
/// Unique score — see [`priority`].
pub priority: u32,
/// [`name_hash`] of the text, for the repeat filter.
pub name_hash: u32,
/// Zoom tier this label first appears at (0 country, 1 region, 2 city).
pub lod: u32,
/// Reserves its cells and draws nothing (see [`BLOCKER_RANK`]).
pub blocker: bool,
}
/// Per-frame grid geometry: the viewport it is stretched over and the reciprocal cell
/// size.
///
/// The reciprocal is stored, not the cell size, because the shader multiplies by it.
/// If one lane divided and the other multiplied by a reciprocal, a box sitting on a
/// cell boundary could quantise to different cells and the two lanes would disagree
/// for reasons that have nothing to do with the algorithm. Same operation, both sides.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct LabelGridParams {
/// Viewport size in screen px — labels fully outside it are not candidates.
pub viewport: [f32; 2],
/// `[GRID_W / viewport.x, GRID_H / viewport.y]`.
pub inv_cell: [f32; 2],
/// `1 / REPEAT_CELL_PX`.
pub inv_repeat: f32,
/// Viewport LOD tier: labels with `lod > this` are not candidates.
pub lod: u32,
}
impl LabelGridParams {
/// Build from a viewport size in screen px and the frame's LOD tier.
#[must_use]
pub fn new(viewport: [f32; 2], lod: u32) -> Self {
let w = if viewport[0] > 0.0 { viewport[0] } else { 1.0 };
let h = if viewport[1] > 0.0 { viewport[1] } else { 1.0 };
Self {
viewport: [w, h],
inv_cell: [GRID_W as f32 / w, GRID_H as f32 / h],
inv_repeat: 1.0 / REPEAT_CELL_PX,
lod,
}
}
}
/// The cell footprint of one label: its inclusive spatial cell range plus the coarse
/// repeat cell its centre falls in.
#[derive(Clone, Copy, Debug, PartialEq)]
struct Footprint {
cx0: u32,
cy0: u32,
cx1: u32,
cy1: u32,
ncx: i32,
ncy: i32,
}
/// Where a label lands on the grid, or `None` if it is not a candidate this frame
/// (wrong LOD, off-screen, or a degenerate/non-finite box).
///
/// Rejecting off-screen labels *before* clamping matters: clamping first would pile
/// every off-screen label into the edge cells, where they would suppress the visible
/// labels that genuinely live there.
fn footprint(l: &ScreenLabel, p: &LabelGridParams) -> Option<Footprint> {
if l.lod > p.lod {
return None;
}
let (cx, cy, hx, hy) = (l.center[0], l.center[1], l.half[0].abs(), l.half[1].abs());
if !(cx.is_finite() && cy.is_finite() && hx.is_finite() && hy.is_finite()) {
return None;
}
let (x0, y0, x1, y1) = (cx - hx, cy - hy, cx + hx, cy + hy);
if x1 < 0.0 || y1 < 0.0 || x0 > p.viewport[0] || y0 > p.viewport[1] {
return None;
}
let span = |lo: f32, hi: f32, inv: f32, n: u32| -> (u32, u32) {
let top = (n - 1) as f32;
let a = (lo * inv).floor().clamp(0.0, top) as u32;
let b = (hi * inv).floor().clamp(0.0, top) as u32;
(a.min(b), a.max(b))
};
let (cx0, cx1) = span(x0, x1, p.inv_cell[0], GRID_W);
let (cy0, cy1) = span(y0, y1, p.inv_cell[1], GRID_H);
Some(Footprint {
cx0,
cy0,
cx1,
cy1,
ncx: (cx * p.inv_repeat).floor() as i32,
ncy: (cy * p.inv_repeat).floor() as i32,
})
}
/// The name-repeat slot for `(name, coarse cell)`. Integer-only (a finalising xorshift
/// mix so neighbouring cells scatter instead of landing in adjacent slots), so the two
/// lanes agree bit-for-bit.
#[must_use]
pub fn repeat_slot(name_hash: u32, ncx: i32, ncy: i32) -> u32 {
let mut h = name_hash
^ (ncx as u32).wrapping_mul(0x9E37_79B9)
^ (ncy as u32).wrapping_mul(0x85EB_CA6B);
h ^= h >> 15;
h = h.wrapping_mul(0x2C1B_3C6D);
h ^= h >> 12;
h % NAME_SLOTS
}
/// Per-label resolution state — one `u32` per candidate. On the device this is the
/// `retire` region that follows the grid (`RETIRE_BASE + i`); on the CPU it is a plain
/// `Vec`. Caching it is what keeps [`LABEL_ROUNDS`] affordable: a label settles once and
/// is then skipped in O(1) instead of rescanning its cells every round.
pub const LS_PENDING: u32 = 0;
/// The label drew, and its cells are occupied by it.
pub const LS_WON: u32 = 1;
/// Some cell it covers is occupied by another label — it can never draw.
pub const LS_BLOCKED: u32 = 2;
/// It won its pixels but lost the repeat filter. Draws nothing AND occupies nothing, so
/// the paper it held is released (see the zombie note in [`resolve_into`]).
pub const LS_RETIRED: u32 = 3;
/// Is any cell this label covers already occupied by a label that DREW?
///
/// A pending label never occupies anything, so "occupied at all" means "occupied by
/// somebody else" — no priority comparison needed. Early-exits, which matters because
/// this runs once per pending label per round.
fn blocked(grid: &[u32], f: &Footprint) -> bool {
for cy in f.cy0..=f.cy1 {
for cx in f.cx0..=f.cx1 {
if grid[(OCC_BASE + cy * GRID_W + cx) as usize] != 0 {
return true;
}
}
}
false
}
/// Does this label still own every claim cell it bid for?
fn owns_claim(grid: &[u32], f: &Footprint, priority: u32) -> bool {
for cy in f.cy0..=f.cy1 {
for cx in f.cx0..=f.cx1 {
if grid[(CLAIM_BASE + cy * GRID_W + cx) as usize] != priority {
return false;
}
}
}
true
}
/// **The collision rule** — the CPU execution of the compute passes.
///
/// Returns the indices of the labels that draw, in descending priority order (so the
/// [`MAX_VISIBLE_LABELS`] truncation is deterministic on this lane).
///
/// Each round, over the labels still `LS_PENDING`:
///
/// 1. settle anyone whose cells are now occupied (`LS_BLOCKED`),
/// 2. **claim** — bid this priority into every covered cell, keeping the maximum,
/// 3. **name bid** — only labels that still own all their cells compete on their name,
/// 4. **emit** — an owner whose name is clear nearby draws and occupies; an owner whose
/// name is taken is `LS_RETIRED`, releasing its pixels.
///
/// Occupancy persists across rounds, so a later round's losers are contesting ink that
/// is really on the paper rather than a rival's dead bid. Rounds are the price of
/// order-independence: the greedy pass got chain resolution free from its sequential
/// visit order, which is the one property that cannot be transcribed onto a device where
/// thousands of invocations claim cells in an order nobody chose.
///
/// The occupancy writes are batched after the round's scan, not interleaved with it —
/// which is also what makes the device version race-free: two overlapping labels can
/// never both own the claim grid, so a half-written occupancy can only reject a label
/// that was going to be rejected anyway.
///
/// `grid` is passed in rather than allocated so a caller painting every frame does not
/// churn the buffer; it is cleared here.
pub fn resolve_into(labels: &[ScreenLabel], p: &LabelGridParams, grid: &mut Vec<u32>) -> Vec<u32> {
grid.clear();
grid.resize(GRID_WORDS as usize, 0);
// Footprints are position-only, so they are computed once and reused every round.
let fps: Vec<Option<Footprint>> = labels.iter().map(|l| footprint(l, p)).collect();
// Anything that is not a candidate this frame (wrong LOD, off-screen, degenerate)
// starts settled, so it never claims and never costs a rescan.
let mut ls: Vec<u32> =
fps.iter().map(|f| if f.is_some() { LS_PENDING } else { LS_BLOCKED }).collect();
let mut winners: Vec<u32> = Vec::new();
for _round in 0..LABEL_ROUNDS {
// ── clear the claim + name-bid regions (occupancy survives the round) ──
for w in &mut grid[CLAIM_BASE as usize..(CLAIM_BASE + GRID_CELLS) as usize] {
*w = 0;
}
for w in &mut grid[NAME_CLAIM_BASE as usize..NAME_WON_BASE as usize] {
*w = 0;
}
// ── settle whoever the last round's ink blocked, then claim ────────────
let mut pending = 0usize;
for (i, l) in labels.iter().enumerate() {
if ls[i] != LS_PENDING {
continue;
}
let f = fps[i].expect("a pending label has a footprint");
if blocked(grid, &f) {
ls[i] = LS_BLOCKED;
continue;
}
pending += 1;
for cy in f.cy0..=f.cy1 {
for cx in f.cx0..=f.cx1 {
let idx = (CLAIM_BASE + cy * GRID_W + cx) as usize;
grid[idx] = grid[idx].max(l.priority);
}
}
}
if pending == 0 {
break; // converged
}
// ── name bid — ONLY labels that won their pixels compete on their name ─
//
// This ordering IS the repeat filter, and getting it wrong cost most of the
// label density. When every pending label bid during the claim pass, a
// spatially-contested label still held its name slot and suppressed the one
// instance of that street that COULD have drawn. The greedy pass never had the
// problem: its `placed_names` only ever held names it had actually PLACED.
for (i, l) in labels.iter().enumerate() {
if ls[i] != LS_PENDING {
continue;
}
let f = fps[i].expect("a pending label has a footprint");
if !owns_claim(grid, &f, l.priority) {
continue;
}
let s = (NAME_CLAIM_BASE + repeat_slot(l.name_hash, f.ncx, f.ncy)) as usize;
grid[s] = grid[s].max(l.priority);
}
// ── emit ─────────────────────────────────────────────────────────────
let mut round: Vec<u32> = Vec::new();
for (i, l) in labels.iter().enumerate() {
if ls[i] != LS_PENDING {
continue;
}
let f = fps[i].expect("a pending label has a footprint");
if !owns_claim(grid, &f, l.priority) {
continue;
}
// The repeat filter: this name must not have been taken at a HIGHER priority
// in this coarse cell or any of its 8 neighbours — either as a better BID
// this round, or as ink already on the paper.
let mut repeat_clear = true;
for dy in -1i32..=1 {
for dx in -1i32..=1 {
let slot = repeat_slot(l.name_hash, f.ncx + dx, f.ncy + dy);
if grid[(NAME_CLAIM_BASE + slot) as usize] > l.priority
|| grid[(NAME_WON_BASE + slot) as usize] > l.priority
{
repeat_clear = false;
}
}
}
if repeat_clear {
round.push(i as u32);
} else {
// RETIRE it — the fix for the defect that made the repeat filter REDUCE
// the distinct-name count it exists to increase (measured on the real
// Liechtenstein clip at 4x fit zoom: 19 distinct names became 12 when
// the filter was switched on).
//
// A repeat-rejected label owns its pixels but does not draw and does not
// occupy. Left pending it wins the claim again next round, is rejected
// again, and holds that patch of paper against every lower-priority
// label for the whole frame — a zombie. Extra rounds could not help,
// which is why raising LABEL_ROUNDS to 16 changed nothing until this was
// fixed. The greedy pass's `continue` past the repeat test left the
// candidate out of `placed` entirely, so its pixels stayed free.
ls[i] = LS_RETIRED;
}
}
for &i in &round {
let l = &labels[i as usize];
let f = fps[i as usize].expect("a round winner has a footprint");
for cy in f.cy0..=f.cy1 {
for cx in f.cx0..=f.cx1 {
let idx = (OCC_BASE + cy * GRID_W + cx) as usize;
grid[idx] = grid[idx].max(l.priority);
}
}
let ns = (NAME_WON_BASE + repeat_slot(l.name_hash, f.ncx, f.ncy)) as usize;
grid[ns] = grid[ns].max(l.priority);
ls[i as usize] = LS_WON;
// A blocker occupies its pixels and prints nothing.
if !l.blocker {
winners.push(i);
}
}
}
winners.sort_by(|a, b| labels[*b as usize].priority.cmp(&labels[*a as usize].priority));
winners.truncate(MAX_VISIBLE_LABELS as usize);
winners
}
/// [`resolve_into`] with its own scratch grid — the convenient form.
#[must_use]
pub fn resolve(labels: &[ScreenLabel], p: &LabelGridParams) -> Vec<u32> {
let mut grid = Vec::new();
resolve_into(labels, p, &mut grid)
}
// ── The wire types + the ONE projection both lanes use ───────────────────────────
//
// These live here, next to the rule, rather than in `render::gpu`, because the
// fail-safe CPU painter builds the very same candidates and must derive the very same
// screen boxes from them. Only the `bytemuck` derives are feature-gated; the layouts
// are plain `repr(C)` so a build without `wgpu` still sees identical geometry.
/// Bit: [`LabelCandidate::pos`] is already screen px and must not be projected (a pin
/// disc, a legend, anything the CPU already placed).
pub const FLAG_SCREEN_SPACE: u32 = 1;
/// Bit: this candidate reserves its cells and draws nothing (see [`BLOCKER_RANK`]).
pub const FLAG_BLOCKER: u32 = 2;
/// One label as uploaded to the device. 48 bytes; mirrors `Candidate` in
/// `label_collide.wgsl`.
#[repr(C)]
#[derive(Clone, Copy, Debug, Default, PartialEq)]
#[cfg_attr(feature = "wgpu", derive(bytemuck::Pod, bytemuck::Zeroable))]
pub struct LabelCandidate {
/// Origin-local Mercator anchor — or screen px if [`FLAG_SCREEN_SPACE`] is set.
pub pos: [f32; 2],
/// Padded half extent in screen px ([`label_half_extent`]).
pub half_px: [f32; 2],
/// Unique score ([`priority`]).
pub priority: u32,
/// [`name_hash`] of the text.
pub name_hash: u32,
/// First glyph in the shared glyph-template buffer.
pub glyph_start: u32,
/// Glyph count (0 for a blocker).
pub glyph_count: u32,
/// Zoom tier.
pub lod: u32,
/// [`FLAG_SCREEN_SPACE`] | [`FLAG_BLOCKER`].
pub flags: u32,
pub _pad: [u32; 2],
}
/// One glyph of a label, positioned **relative to the label box centre** so the label
/// can be re-anchored every frame on the device without re-laying-out the text. 32
/// bytes; mirrors `GlyphSrc` in `label_collide.wgsl`.
#[repr(C)]
#[derive(Clone, Copy, Debug, Default, PartialEq)]
#[cfg_attr(feature = "wgpu", derive(bytemuck::Pod, bytemuck::Zeroable))]
pub struct GlyphSrc {
pub off_min: [f32; 2],
pub off_max: [f32; 2],
pub uv_min: [f32; 2],
pub uv_max: [f32; 2],
}
/// What the label draw consumes — an absolute screen-px quad, its atlas UV and its
/// colour. **Written only by the emit compute pass**; the CPU never fills this. 48
/// bytes; mirrors `GlyphOut` in `label_collide.wgsl` and the vertex attributes in
/// `label_draw.wgsl`.
#[repr(C)]
#[derive(Clone, Copy, Debug, Default, PartialEq)]
#[cfg_attr(feature = "wgpu", derive(bytemuck::Pod, bytemuck::Zeroable))]
pub struct LabelGlyphInstance {
pub rect_min: [f32; 2],
pub rect_max: [f32; 2],
pub uv_min: [f32; 2],
pub uv_max: [f32; 2],
pub color: [f32; 4],
}
/// The per-frame camera + palette the label lane runs under. Its [`project`] is the
/// CPU twin of `label_collide.wgsl`'s `label_center_px`, which is itself the same
/// subtract-before-scale form `draw.wgsl` applies to way vertices — so a label anchor
/// and the road it names cannot land in different places at street zoom.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct LabelFrame {
/// Per-axis zoom (px per origin-local Mercator unit).
pub zoom: [f32; 2],
/// `camera_center − origin`, origin-local.
pub ref_pos: [f32; 2],
/// Where `ref_pos` lands, in screen px.
pub screen_center: [f32; 2],
/// Viewport size, screen px.
pub viewport: [f32; 2],
/// Viewport LOD tier.
pub lod: u32,
/// Ink colour, linear premultiplied-ready RGBA.
pub ink: [f32; 4],
/// Halo colour.
pub halo: [f32; 4],
}
impl LabelFrame {
/// A frame for **pane-local screen-space** candidates: identity projection, the
/// pane's own size as the viewport, and the palette in shader form.
///
/// This is the shape a 2.5D pane wants. `osm2d` projects its label anchors through
/// `cam.to_px`, which carries the tilt its points and pins are drawn with, so the
/// anchors arrive already in pixels and the shader must not project them again — a
/// label that leaned differently from the road it names would be worse than no
/// label. The Mercator form ([`Self::project`] without [`FLAG_SCREEN_SPACE`]) is
/// for a flat lane that wants pan and zoom to be a uniform update.
#[must_use]
pub fn screen(viewport: [f32; 2], lod: u32, ink: egui::Color32, halo: egui::Color32) -> Self {
Self {
zoom: [1.0, 1.0],
ref_pos: [0.0, 0.0],
screen_center: [0.0, 0.0],
viewport,
lod,
ink: color_rgba(ink),
halo: color_rgba(halo),
}
}
/// Screen-px centre of a candidate's box — the twin of the shader's
/// `label_center_px`.
#[must_use]
pub fn project(&self, c: &LabelCandidate) -> [f32; 2] {
if c.flags & FLAG_SCREEN_SPACE != 0 {
return c.pos;
}
[
(c.pos[0] - self.ref_pos[0]) * self.zoom[0] + self.screen_center[0],
(c.pos[1] - self.ref_pos[1]) * self.zoom[1] + self.screen_center[1],
]
}
/// The grid geometry this frame implies.
#[must_use]
pub fn grid_params(&self) -> LabelGridParams {
LabelGridParams::new(self.viewport, self.lod)
}
}
/// Project a candidate set into the [`ScreenLabel`]s [`resolve`] consumes. **The one
/// bridge**: the fail-safe CPU painter calls this and then [`resolve`]; the device
/// runs `label_collide.wgsl` over the same candidates. Anything that differed between
/// those two would show up as the parity test going red.
#[must_use]
pub fn screen_labels(cands: &[LabelCandidate], frame: &LabelFrame) -> Vec<ScreenLabel> {
cands
.iter()
.map(|c| ScreenLabel {
center: frame.project(c),
half: c.half_px,
priority: c.priority,
name_hash: c.name_hash,
lod: c.lod,
blocker: c.flags & FLAG_BLOCKER != 0,
})
.collect()
}
/// An egui [`Color32`](egui::Color32) as `[r, g, b, a]` in `[0, 1]` — what
/// [`LabelFrame`]'s ink/halo carry to the shader.
///
/// **The one writer** of this mapping: [`crate::render::gpu::color32_to_f32`] delegates
/// here. It used to live only inside the `wgpu`-gated GPU module, which meant a build
/// without the feature — the fail-safe CPU painter's build — could not name the palette
/// it was about to hand to the device.
#[must_use]
pub fn color_rgba(c: egui::Color32) -> [f32; 4] {
let [r, g, b, a] = c.to_array();
[f32::from(r) / 255.0, f32::from(g) / 255.0, f32::from(b) / 255.0, f32::from(a) / 255.0]
}
/// The collision box half-extent for a laid-out text of `text_size` — the text extent
/// plus [`LABEL_PAD_PX`], halved. `e88969f`'s `Rect::from_center_size(p, galley.size()
/// + LABEL_PAD)`, as the one formula both lanes call.
#[must_use]
pub fn label_half_extent(text_size: [f32; 2]) -> [f32; 2] {
[(text_size[0] + LABEL_PAD_PX[0]) * 0.5, (text_size[1] + LABEL_PAD_PX[1]) * 0.5]
}
#[cfg(test)]
mod tests {
use super::*;
fn params() -> LabelGridParams {
LabelGridParams::new([1280.0, 768.0], 2)
}
fn lbl(x: f32, y: f32, rank: u8, order: u32, name: &str) -> ScreenLabel {
ScreenLabel {
center: [x, y],
half: [40.0, 9.0],
priority: priority(rank, order),
name_hash: name_hash(name),
lod: 0,
blocker: false,
}
}
/// The priority packing is **strictly unique** and ordered rank-first — the
/// property the whole `atomicMax` scheme rests on. A duplicate priority would let
/// two labels both pass `grid[cell] == priority` and print on top of each other.
#[test]
fn priority_is_unique_and_rank_dominates_order() {
let mut seen = std::collections::HashSet::new();
for rank in [0u8, 1, 7, 200, BLOCKER_RANK] {
for order in 0..64u32 {
assert!(seen.insert(priority(rank, order)), "priority({rank},{order}) collided");
}
}
// Rank dominates: the WORST order at rank 5 still beats the BEST at rank 4.
assert!(priority(5, 0x00FF_FFFE) > priority(4, 0));
// Within a rank, a lower order wins (mirrors the old greedy first-come rule).
assert!(priority(5, 0) > priority(5, 1));
// Blockers outrank every real label.
assert!(priority(BLOCKER_RANK, 1000) > priority(BLOCKER_RANK - 1, 0));
}
/// **Overlap:** labels stacked on one spot leave exactly ONE survivor, and it is
/// the highest-priority one — not merely "some" one. The ranks are distinct so the
/// test can tell those two outcomes apart.
#[test]
fn stacked_labels_leave_exactly_the_best_one() {
let p = params();
let ls = [
lbl(400.0, 300.0, 3, 10, "a"),
lbl(402.0, 301.0, 9, 11, "b"), // the winner: highest rank
lbl(398.0, 299.0, 5, 12, "c"),
lbl(401.0, 302.0, 1, 13, "d"),
];
let kept = resolve(&ls, &p);
assert_eq!(kept, vec![1], "one survivor, the top-ranked one — got {kept:?}");
}
/// **Non-vacuity:** with no overlap, ALL labels draw. A declutter pass that only
/// ever culls is as broken as one that never culls, and this is the arm that
/// catches it.
#[test]
fn well_separated_labels_all_survive() {
let p = params();
let ls: Vec<ScreenLabel> = (0..6)
.map(|i| lbl(100.0 + i as f32 * 190.0, 80.0 + (i % 2) as f32 * 500.0, 5, i, &format!("n{i}")))
.collect();
let kept = resolve(&ls, &p);
assert_eq!(kept.len(), ls.len(), "nothing overlaps, so nothing may be culled — got {kept:?}");
}
/// **A label blocked only by a LOSER still draws** — the arm that separates the
/// round loop from a single-pass grid, and the reason [`OCC_BASE`] exists.
///
/// A(rank 9) at x=200, B(rank 5) overlapping A, C(rank 1) overlapping B but NOT A.
/// A single claim grid gives `[A]`: B loses to A, and then C loses to B's dead bid.
/// The rule must give `[A, C]` — C collides with nothing that is actually drawn.
///
/// This is the 16-fold collapse in miniature. On the real Liechtenstein clip the
/// single-pass version turned 48 labels into 3.
#[test]
fn a_label_blocked_only_by_a_loser_still_draws() {
let p = params();
// half = [40, 9] from `lbl`, so the boxes are 80 px wide: A 160-240,
// B 210-290, C 285-365. A overlaps B, B overlaps C, A does not reach C —
// and at 10 px cells they share no cell either.
let a = lbl(200.0, 300.0, 9, 0, "A");
let b = lbl(250.0, 300.0, 5, 1, "B");
let c = lbl(325.0, 300.0, 1, 2, "C");
let kept = resolve(&[a, b, c], &p);
assert!(kept.contains(&0), "the top-ranked label draws");
assert!(!kept.contains(&1), "the label overlapping it does not");
assert!(
kept.contains(&2),
"the label that overlaps only the LOSER must still draw — got {kept:?}; \
[0] alone is the single-pass cascade this rule exists to avoid"
);
// And the chain really is a chain: C must genuinely overlap B.
assert!(c.center[0] - c.half[0] < b.center[0] + b.half[0], "the fixture's C overlaps B");
assert!(c.center[0] - c.half[0] > a.center[0] + a.half[0], "…and does NOT overlap A");
}
/// **DENSITY — the guard that was missing.** A crowded pane must still letter a
/// useful number of roads, and every previous defect in this module showed up here
/// and nowhere else. Measured on the real Liechtenstein clip through
/// `osm2d_deckgl_quality`, the counts a broken rule produced were:
///
/// | version | distinct names at 4x fit zoom |
/// |--------------------------------------|-------------------------------|
/// | the greedy pass this replaces | 47 |
/// | single-pass grid, no occupancy | 3 (loser cascade) |
/// | rounds, name bid before spatial test | 12 (zombie name holders) |
/// | rounds + retirement, 4 rounds | 14 |
/// | rounds + retirement, 32 rounds | 41 |
///
/// Every one of those was GREEN on all the other tests in this module: they each
/// kept exactly one of two stacked labels, culled nothing that did not overlap, and
/// thinned repeats. Correctness on four labels says nothing about density on two
/// thousand, and nothing here could see the difference. Hence this test.
#[test]
fn a_crowded_pane_still_letters_most_of_what_fits() {
let p = params();
// 40 streets x 6 ways each = 240 candidates. The six ways of ONE street lie in a
// RUN along it, 60 px apart — which is how OSM actually splits a street, and the
// condition e88969f's repeat filter was written for ("Feldkircher Strasse" x7 in
// one frame). A fixture that scattered the six copies at random never engaged the
// repeat filter, and stayed green with retirement removed and with the name bid
// moved before the spatial test; the run is what makes those defects visible.
let mut seed = 0x2545_F491_4F6C_DD1Du64;
let mut next = || {
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
(seed >> 11) as f32 / (1u64 << 53) as f32
};
const STREETS: u32 = 40;
const WAYS: u32 = 6;
let names: Vec<String> = (0..STREETS).map(|i| format!("Strasse {i}")).collect();
let mut ls: Vec<ScreenLabel> = Vec::new();
for st in 0..STREETS {
let (x0, y0) = (next() * 1000.0, next() * 730.0);
let rank = (next() * 9.0) as u8;
for w in 0..WAYS {
ls.push(ScreenLabel {
center: [x0 + w as f32 * 60.0, y0 + w as f32 * 6.0],
half: label_half_extent([70.0, 13.0]),
priority: priority(rank, st * WAYS + w),
name_hash: name_hash(&names[st as usize]),
lod: 0,
blocker: false,
});
}
}
let kept = resolve(&ls, &p);
let distinct: std::collections::BTreeSet<u32> =
kept.iter().map(|&i| ls[i as usize].name_hash).collect();
// The pane is 1280x768 = 983 040 px; a padded label is 80x19 = 1520 px, so ~646
// would tile it perfectly. A real packing of random placements reaches a
// fraction of that; the floor below is set well under what this rule achieves
// and far above what every broken version produced.
// 44, not 30. A healthy rule saturates the 48-label budget on this fixture, so
// the floor can sit close to it — and it has to, because the interesting failures
// land in the 26..40 band: no retirement gives 26, and dropping LABEL_ROUNDS from
// its measured plateau of 32 back to 4 gives 39. A floor of 30 called both of
// those green.
assert!(
kept.len() >= 44,
"a crowded pane must letter a useful number of roads — got {} of {}. \
26 is the signature of zombie labels holding pixels they never draw on; \
~39 of too few resolution rounds",
kept.len(),
ls.len()
);
// DISTINCT names is the assertion that actually catches a broken repeat filter,
// and the total cannot substitute for it: this fixture saturates
// MAX_VISIBLE_LABELS, so `kept.len()` reads 48 whether the filter works or not.
// The first version of this test asserted only the total and stayed GREEN with
// retirement removed AND with the name bid moved before the spatial test — the
// two defects that between them cost 19 distinct names down to 12 on real data.
assert!(
distinct.len() >= 32,
"the repeat filter must not cost distinct names — {} distinct of {} lettered \
(40 exist). A low distinct count with a full label budget means one street's \
name is being printed where a different street's could have been",
distinct.len(),
kept.len()
);
// …and it must still be culling, or the assertion above is vacuous.
assert!(kept.len() < ls.len() / 2, "and it must genuinely cull: {} of {}", kept.len(), ls.len());
// Every kept label must be pairwise non-overlapping, which is the actual
// contract — a high count achieved by letting labels overlap is worse than a low
// one. Checked on the PADDED boxes the rule was given.
for (ai, a) in kept.iter().enumerate() {
for b in &kept[ai + 1..] {
let (x, y) = (&ls[*a as usize], &ls[*b as usize]);
let overlap = (x.center[0] - y.center[0]).abs() < x.half[0] + y.half[0]
&& (x.center[1] - y.center[1]).abs() < x.half[1] + y.half[1];
assert!(!overlap, "labels {a} and {b} were both kept but their padded boxes overlap");
}
}
eprintln!(
"[label_grid] crowded pane: {} of {} lettered, {} distinct of 40, all pairwise clear",
kept.len(),
ls.len(),
distinct.len()
);
}
/// **Repeat distance:** the same street name at four points along a row keeps only
/// the ones far enough apart, while four DIFFERENT names at the same four points
/// all keep. Same geometry, different text — so the assertion isolates the name
/// filter from the spatial filter.
#[test]
fn same_name_repeats_are_thinned_but_distinct_names_are_not() {
let p = params();
let xs = [80.0f32, 260.0, 440.0, 620.0]; // 180 px apart, inside one repeat cell run
let same: Vec<ScreenLabel> =
xs.iter().enumerate().map(|(i, &x)| lbl(x, 300.0, 5, i as u32, "Feldkircher Strasse")).collect();
let distinct: Vec<ScreenLabel> =
xs.iter().enumerate().map(|(i, &x)| lbl(x, 300.0, 5, i as u32, &format!("Street {i}"))).collect();
let same_kept = resolve(&same, &p);
let distinct_kept = resolve(&distinct, &p);
assert_eq!(distinct_kept.len(), 4, "four different names at these spots all fit: {distinct_kept:?}");
assert!(
same_kept.len() < distinct_kept.len(),
"one street repeated must be thinned ({} kept) below four distinct names ({} kept)",
same_kept.len(),
distinct_kept.len()
);
assert!(!same_kept.is_empty(), "…but the street is still lettered at least once");
}
/// **Blockers** (pin markers) reserve their pixels and print nothing: a label on
/// top of one is dropped, the identical label moved away is kept, and the blocker
/// itself never appears in the output.
#[test]
fn a_blocker_reserves_pixels_and_is_never_drawn() {
let p = params();
let blocker = ScreenLabel {
center: [500.0, 400.0],
half: [22.0, 22.0],
priority: priority(BLOCKER_RANK, 0),
name_hash: name_hash("#pin"),
lod: 0,
blocker: true,
};
let on_top = lbl(505.0, 402.0, 9, 5, "Bahnhofstrasse");
let elsewhere = lbl(1000.0, 120.0, 9, 6, "Bahnhofstrasse2");
let kept = resolve(&[blocker, on_top, elsewhere], &p);
assert!(!kept.contains(&0), "a blocker must never be drawn");
assert!(!kept.contains(&1), "a label over a pin must be suppressed");
assert!(kept.contains(&2), "…and the same label away from the pin must survive");
}
/// The **LOD gate** and the **off-screen gate** both reject before the grid is
/// touched. Without the off-screen reject, clamping would pile distant labels into
/// the edge cells and suppress the visible labels that live there — which is why
/// the second arm places a real label at the very edge.
#[test]
fn lod_and_offscreen_labels_are_not_candidates() {
let mut p = params();
p.lod = 1;
let mut city = lbl(400.0, 300.0, 5, 0, "city street");
city.lod = 2;
assert!(resolve(&[city], &p).is_empty(), "a city-tier label is not a candidate at region LOD");
let edge = lbl(20.0, 300.0, 5, 1, "edge");
let far_left = lbl(-9000.0, 300.0, 9, 2, "far"); // higher rank, would win if it claimed
let kept = resolve(&[edge, far_left], &p);
assert_eq!(kept, vec![0], "the off-screen label must claim nothing; the edge label survives — got {kept:?}");
}
/// The wire layouts are exactly what `label_collide.wgsl` hard-codes as strides,
/// and `LabelGlyphInstance` is what `label_draw.wgsl`'s vertex attributes are laid
/// out against. A silent size change here would make the shader read the next
/// label's bytes as this one's — the failure mode that produces plausible-looking
/// garbage rather than a validation error.
#[test]
fn wire_layouts_match_the_shader_strides() {
assert_eq!(std::mem::size_of::<LabelCandidate>(), 48, "Candidate stride");
assert_eq!(std::mem::size_of::<GlyphSrc>(), 32, "GlyphSrc stride");
assert_eq!(std::mem::size_of::<LabelGlyphInstance>(), 48, "GlyphOut / vertex stride");
// vec4 in a WGSL storage struct needs a 16-aligned offset; `color` sits at 32.
assert_eq!(std::mem::offset_of!(LabelGlyphInstance, color), 32);
assert_eq!(std::mem::offset_of!(LabelCandidate, priority), 16);
assert_eq!(std::mem::offset_of!(LabelCandidate, flags), 36);
assert_eq!(FLAG_SCREEN_SPACE | FLAG_BLOCKER, 3, "the two flag bits are distinct");
}
/// The projection is subtract-before-scale, **per axis**, and screen-space
/// candidates pass through untouched.
///
/// The identity-value trap bites twice here and the first draft of this test fell
/// into it. `zoom = [1, 1]` with `ref = [0, 0]` makes a dead projection
/// indistinguishable from a live one, so the fixture uses a street-level zoom, a
/// non-zero reference, and — the arm that actually catches a real bug —
/// **different zoom on the two axes**, because the realistic mistake in a hand-
/// written projection is a copy-pasted `x` where `y` belongs.
///
/// (The first draft also asserted that the absolute-f32 form drifts >1 px. It
/// drifted 0.11 px: with an origin-local `pos ≈ 0.03` the two forms genuinely
/// agree, so the assertion could not fire for the reason it claimed. That property
/// is `gpu_line_vertex_within_1px_of_f64_reference_at_max_zoom`'s to prove, on
/// absolute Mercator magnitudes these types do not carry.)
#[test]
fn projection_is_subtract_before_scale_per_axis() {
let frame = LabelFrame {
zoom: [8.0e7, 4.0e7], // deliberately unequal
ref_pos: [0.031_25, 0.062_5],
screen_center: [640.0, 384.0],
viewport: [1280.0, 768.0],
lod: 2,
ink: [1.0; 4],
halo: [0.0, 0.0, 0.0, 1.0],
};
let (dx, dy) = (1.0e-5_f32, -2.0e-5_f32);
let merc =
LabelCandidate { pos: [frame.ref_pos[0] + dx, frame.ref_pos[1] + dy], ..Default::default() };
let got = frame.project(&merc);
let want = [640.0 + dx * 8.0e7, 384.0 + dy * 4.0e7];
assert!((got[0] - want[0]).abs() < 1.0, "x = (pos−ref)·zoom_x + centre: want {want:?} got {got:?}");
assert!((got[1] - want[1]).abs() < 1.0, "y uses zoom_Y, not zoom_x: want {want:?} got {got:?}");
// Non-identity, and each axis really moved (a projection that returned `pos`,
// or dropped the scale, or dropped the subtraction, lands nowhere near).
assert!(got[0] != merc.pos[0] && got[1] != merc.pos[1], "the projection is not the identity");
assert!((got[0] - 640.0).abs() > 100.0, "the scale is applied: {} px from centre", got[0] - 640.0);
// Swapping the axes would give y ≈ 384 + dy·8e7 = −1216; the assertion above
// pins 384 + dy·4e7 = −416. Restate the gap so the intent survives a refactor.
assert!(
(got[1] - (384.0 + dy * 8.0e7)).abs() > 100.0,
"y must NOT have used zoom_x ({} vs the swapped {})",
got[1],
384.0 + dy * 8.0e7
);
// A moved reference moves the answer — the subtraction is load-bearing.
let mut shifted = frame;
shifted.ref_pos[0] += 1.0e-5;
assert!(
(shifted.project(&merc)[0] - got[0]).abs() > 100.0,
"moving `ref` must move the projected label"
);
let screen =
LabelCandidate { pos: [123.0, 456.0], flags: FLAG_SCREEN_SPACE, ..Default::default() };
assert_eq!(frame.project(&screen), [123.0, 456.0], "a screen-space candidate is not projected");
}
/// The padded box is the text extent plus [`LABEL_PAD_PX`], halved — the one
/// formula, so the CPU painter and the device cannot pad differently.
#[test]
fn half_extent_adds_the_pad_once() {
assert_eq!(label_half_extent([80.0, 14.0]), [45.0, 10.0]);
// A blocker's own extent is not padded twice by going through here.
assert!(label_half_extent([0.0, 0.0])[0] > 0.0, "the pad alone is still a box");
}
/// `screen_labels` carries every field the rule reads, and marks blockers. The
/// blocker arm matters: `flags` is a bitfield, and testing `== FLAG_BLOCKER`
/// instead of `& FLAG_BLOCKER` would silently un-block a screen-space pin.
#[test]
fn screen_labels_carry_the_rule_inputs_including_combined_flags() {
let frame = LabelFrame {
zoom: [1000.0, 1000.0],
ref_pos: [0.0, 0.0],
screen_center: [100.0, 100.0],
viewport: [1280.0, 768.0],
lod: 1,
ink: [1.0; 4],
halo: [0.0; 4],
};
let pin = LabelCandidate {
pos: [300.0, 200.0],
half_px: [12.0, 12.0],
priority: priority(BLOCKER_RANK, 0),
name_hash: name_hash("#pin"),
lod: 0,
flags: FLAG_SCREEN_SPACE | FLAG_BLOCKER,
..Default::default()
};
let out = screen_labels(&[pin], &frame);
assert_eq!(out[0].center, [300.0, 200.0]);
assert!(out[0].blocker, "a candidate carrying BOTH flags is still a blocker");
assert_eq!(out[0].priority, priority(BLOCKER_RANK, 0));
assert_eq!(out[0].name_hash, name_hash("#pin"));
}
/// The grid buffer is one array with two regions and the spatial region is indexed
/// `cy * GRID_W + cx`, so the two regions cannot overlap. Pins the constants the
/// WGSL hard-codes.
#[test]
fn grid_regions_do_not_overlap() {
assert_eq!(GRID_CELLS, GRID_W * GRID_H);
// Four regions, back to back, no gap and no overlap.
assert_eq!(CLAIM_BASE, 0);
assert_eq!(OCC_BASE, CLAIM_BASE + GRID_CELLS);
assert_eq!(NAME_CLAIM_BASE, OCC_BASE + GRID_CELLS);
assert_eq!(NAME_WON_BASE, NAME_CLAIM_BASE + NAME_SLOTS);
assert_eq!(GRID_WORDS, NAME_WON_BASE + NAME_SLOTS);
assert!(repeat_slot(name_hash("x"), 0, 0) < NAME_SLOTS);
assert!(repeat_slot(name_hash("x"), -7, 12) < NAME_SLOTS);
assert_eq!(INSTANCES_PER_GLYPH, 5);
// The realised repeat radius must never exceed the contract it replaces.
const _: () = assert!(2.0 * REPEAT_CELL_PX <= MIN_REPEAT_PX, "3x3 over REPEAT_CELL_PX cells must stay inside MIN_REPEAT_PX");
const _: () = assert!(LABEL_ROUNDS >= 2, "one round cannot resolve an A-blocks-B-blocks-C chain");
}
}