dotloom_render/

text.rs

//! Text: font loading, signed-distance-field glyph atlas and layout.
//!
//! Glyph outlines are read from the TrueType `glyf` table with `read-fonts` (simple
//! and composite glyphs), rasterized once at [`RASTER_PX`] by a small coverage
//! rasterizer, converted to a signed distance field and packed into
//! a single-channel atlas. The SDF stays sharp from a few pixels up to large zoom
//! levels, so text never needs to be re-rasterized while zooming.
//!
//! Layout follows the scene contract (`Text::height` is the cap-to-descender
//! height; lines are `1.2 × height` apart). With the default font, glyph positions
//! come from [`Text::line_pens`] — the advance widths and pair kerning shared with
//! `dotloom-geometry` — so drawn text and the engine's text boxes (hit-testing,
//! culling) agree exactly. Other fonts are laid out with their own advances.

use std::collections::HashMap;

use dotloom_geometry::{HAlign, Text, VAlign};
use read_fonts::{
    FontRef, TableProvider,
    tables::glyf::{Anchor, CompositeGlyphFlags, CurvePoint, Glyph},
    types::GlyphId,
};

use crate::RenderError;

/// The default font: a subset of Inter Regular (SIL OFL 1.1, see `assets/`).
pub const DEFAULT_FONT: &[u8] = include_bytes!("../assets/Inter-Regular-subset.ttf");

/// Rasterization size of atlas glyphs (pixels per em).
pub const RASTER_PX: f32 = 48.0;
/// SDF spread and glyph padding in raster pixels.
pub const SPREAD: usize = 6;
/// Atlas edge length (fits WebGL2's guaranteed 2048 texture limit).
pub const ATLAS_SIZE: usize = 2048;

/// Line distance relative to the text height (scene contract).
const LINE_SPACING: f64 = Text::LINE_SPACING;
/// Ascent used for vertical alignment (scene contract: top ≈ 0.8 h above baseline).
const TOP_ABOVE_BASELINE: f64 = Text::TOP_ABOVE_BASELINE;
/// Curve flattening tolerance in raster pixels.
const FLATTEN_TOLERANCE: f32 = 0.1;

/// A glyph in the atlas.
#[derive(Debug, Clone, Copy)]
pub(crate) struct GlyphSlot {
    /// Atlas UV rectangle `[u0, v0, u1, v1]` (v down); `None` for blank glyphs.
    pub uv: Option<[f32; 4]>,
    /// Quad in em units relative to the pen position on the baseline (y up):
    /// `[x0, y0, x1, y1]`.
    pub quad: [f32; 4],
    /// Advance in em units.
    pub advance: f32,
}

/// One positioned glyph (text-local model units before rotation, y up).
#[derive(Debug, Clone, Copy)]
pub(crate) struct PlacedGlyph {
    pub x0: f64,
    pub y0: f64,
    pub x1: f64,
    pub y1: f64,
    pub uv: [f32; 4],
}

/// Dirty atlas region to upload.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct DirtyRect {
    pub x: usize,
    pub y: usize,
    pub w: usize,
    pub h: usize,
}

struct Shelf {
    y: usize,
    h: usize,
    x: usize,
}

/// Font, atlas and glyph cache.
pub struct TextSystem {
    /// Font file (validated by [`TextSystem::new`]).
    font: Vec<u8>,
    /// The default font: positions come from the shared layout tables.
    shared_layout: bool,
    /// Text height → em size factor: `em = height / height_per_em`.
    height_per_em: f64,
    glyphs: HashMap<u32, GlyphSlot>,
    pub(crate) atlas: Vec<u8>,
    shelves: Vec<Shelf>,
    pub(crate) dirty: Option<DirtyRect>,
    /// Incremented when the atlas is cleared; cached text meshes become stale.
    pub(crate) generation: u64,
}

impl std::fmt::Debug for TextSystem {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("TextSystem").field("glyphs", &self.glyphs.len()).field("generation", &self.generation).finish()
    }
}

/// Receives glyph outlines (y up).
trait OutlinePen {
    fn move_to(&mut self, x: f32, y: f32);
    fn line_to(&mut self, x: f32, y: f32);
    fn quad_to(&mut self, cx0: f32, cy0: f32, x: f32, y: f32);
    fn close(&mut self);
}

/// Bounding box of an outline (raster pixels, y up).
#[derive(Default)]
struct Bounds {
    min: (f32, f32),
    max: (f32, f32),
    any: bool,
}

impl OutlinePen for Bounds {
    fn move_to(&mut self, x: f32, y: f32) {
        self.add(x, y);
    }
    fn line_to(&mut self, x: f32, y: f32) {
        self.add(x, y);
    }
    fn quad_to(&mut self, cx0: f32, cy0: f32, x: f32, y: f32) {
        // The control polygon contains the curve.
        self.add(cx0, cy0);
        self.add(x, y);
    }
    fn close(&mut self) {}
}

impl Bounds {
    fn add(&mut self, x: f32, y: f32) {
        if !self.any {
            self.min = (x, y);
            self.max = (x, y);
            self.any = true;
        }
        self.min = (self.min.0.min(x), self.min.1.min(y));
        self.max = (self.max.0.max(x), self.max.1.max(y));
    }
}

/// Coverage rasterizer: signed-area accumulation (the approach of font-rs). Each
/// line segment adds the area it covers to the cells it crosses; a running sum
/// over every row turns the deltas into non-zero winding coverage.
struct Raster {
    w: usize,
    h: usize,
    /// Accumulation cells (`w × h` plus slack for the cell right of a row).
    acc: Vec<f32>,
    /// Offset from outline coordinates (y up) to raster pixels (y down).
    origin: (f32, f32),
    start: (f32, f32),
    cur: (f32, f32),
}

impl Raster {
    fn new(w: usize, h: usize, origin: (f32, f32)) -> Self {
        Self { w, h, acc: vec![0.0; w * h + 2], origin, start: (0.0, 0.0), cur: (0.0, 0.0) }
    }

    fn to_px(&self, x: f32, y: f32) -> (f32, f32) {
        (x - self.origin.0, self.origin.1 - y)
    }

    fn add(&mut self, i: isize, v: f32) {
        if let Some(cell) = usize::try_from(i).ok().and_then(|i| self.acc.get_mut(i)) {
            *cell += v;
        }
    }

    fn line(&mut self, p0: (f32, f32), p1: (f32, f32)) {
        if p0.1 == p1.1 || !(p0.0.is_finite() && p0.1.is_finite() && p1.0.is_finite() && p1.1.is_finite()) {
            return;
        }
        let (dir, p0, p1) = if p0.1 < p1.1 { (1.0f32, p0, p1) } else { (-1.0f32, p1, p0) };
        let dxdy = (p1.0 - p0.0) / (p1.1 - p0.1);
        let y_start = p0.1.max(0.0);
        let y_end = p1.1.min(self.h as f32);
        let mut x = p0.0 + (y_start - p0.1) * dxdy;
        let mut y = y_start.floor();
        while y < y_end {
            let row = y as isize * self.w as isize;
            let dy = (y + 1.0).min(y_end) - y.max(y_start);
            let x_next = x + dxdy * dy;
            let d = dy * dir;
            let (x0, x1) = if x < x_next { (x, x_next) } else { (x_next, x) };
            let x0 = x0.clamp(0.0, self.w as f32);
            let x1 = x1.clamp(0.0, self.w as f32);
            let x0_floor = x0.floor();
            let x0i = x0_floor as isize;
            let x1_ceil = x1.ceil();
            let x1i = x1_ceil as isize;
            if x1i <= x0i + 1 {
                // The segment stays within one cell in this row.
                let xm = 0.5 * (x0 + x1) - x0_floor;
                self.add(row + x0i, d - d * xm);
                self.add(row + x0i + 1, d * xm);
            } else {
                let s = (x1 - x0).recip();
                let x0f = x0 - x0_floor;
                let a0 = 0.5 * s * (1.0 - x0f) * (1.0 - x0f);
                let x1f = x1 - x1_ceil + 1.0;
                let am = 0.5 * s * x1f * x1f;
                self.add(row + x0i, d * a0);
                if x1i == x0i + 2 {
                    self.add(row + x0i + 1, d * (1.0 - a0 - am));
                } else {
                    let a1 = s * (1.5 - x0f);
                    self.add(row + x0i + 1, d * (a1 - a0));
                    for xi in x0i + 2..x1i - 1 {
                        self.add(row + xi, d * s);
                    }
                    let a2 = a1 + (x1i - x0i - 3) as f32 * s;
                    self.add(row + x1i - 1, d * (1.0 - a2 - am));
                }
                self.add(row + x1i, d * am);
            }
            x = x_next;
            y += 1.0;
        }
    }

    fn line_to_px(&mut self, p: (f32, f32)) {
        let from = self.cur;
        self.line(from, p);
        self.cur = p;
    }

    fn coverage(&self) -> Vec<u8> {
        let mut sum = 0.0f32;
        self.acc
            .iter()
            .take(self.w * self.h)
            .map(|a| {
                sum += a;
                (sum.abs().min(1.0) * 255.0).round() as u8
            })
            .collect()
    }
}

impl OutlinePen for Raster {
    fn move_to(&mut self, x: f32, y: f32) {
        let p = self.to_px(x, y);
        self.start = p;
        self.cur = p;
    }
    fn line_to(&mut self, x: f32, y: f32) {
        let p = self.to_px(x, y);
        self.line_to_px(p);
    }
    fn quad_to(&mut self, cx0: f32, cy0: f32, x: f32, y: f32) {
        let (p0, c, p2) = (self.cur, self.to_px(cx0, cy0), self.to_px(x, y));
        let dd = ((p0.0 - 2.0 * c.0 + p2.0).powi(2) + (p0.1 - 2.0 * c.1 + p2.1).powi(2)).sqrt();
        let n = ((dd / FLATTEN_TOLERANCE).sqrt().ceil() as usize).clamp(1, 64);
        for i in 1..=n {
            let t = i as f32 / n as f32;
            let mt = 1.0 - t;
            let p = (
                mt * mt * p0.0 + 2.0 * mt * t * c.0 + t * t * p2.0,
                mt * mt * p0.1 + 2.0 * mt * t * c.1 + t * t * p2.1,
            );
            self.line_to_px(p);
        }
    }
    fn close(&mut self) {
        let start = self.start;
        self.line_to_px(start);
    }
}

impl TextSystem {
    /// Load a TrueType/OpenType font.
    ///
    /// # Errors
    /// [`RenderError::Font`] when the font cannot be parsed or lacks metrics.
    pub fn new(font_bytes: &[u8]) -> Result<Self, RenderError> {
        let font = FontRef::new(font_bytes).map_err(|e| RenderError::Font(e.to_string()))?;
        let err = |e: read_fonts::ReadError| RenderError::Font(e.to_string());
        let upm = f32::from(font.head().map_err(err)?.units_per_em());
        let hhea = font.hhea().map_err(err)?;
        font.glyf().map_err(err)?;
        font.hmtx().map_err(err)?;
        if upm <= 0.0 {
            return Err(RenderError::Font("font has no units per em".into()));
        }
        let ascent = f32::from(hhea.ascender().to_i16());
        let cap = map_char(&font, 'H').and_then(|g| outline_bounds(&font, g, upm)).map_or(ascent * 0.75, |b| b.max.1);
        let descent = (-f32::from(hhea.descender().to_i16())).max(0.0);
        let shared_layout = font_bytes == DEFAULT_FONT;
        // The default font is scaled exactly like `dotloom-geometry` measures it.
        let height_per_em = if shared_layout { 1.0 / Text::em_size(1.0) } else { f64::from((cap + descent) / upm) };
        if !(height_per_em.is_finite() && height_per_em > 0.1) {
            return Err(RenderError::Font("implausible font metrics".into()));
        }
        Ok(Self {
            font: font_bytes.to_vec(),
            shared_layout,
            height_per_em,
            glyphs: HashMap::new(),
            atlas: vec![0; ATLAS_SIZE * ATLAS_SIZE],
            shelves: Vec::new(),
            dirty: None,
            generation: 0,
        })
    }

    /// The built-in font.
    ///
    /// # Errors
    /// Never for the bundled font; see [`TextSystem::new`].
    pub fn with_default_font() -> Result<Self, RenderError> {
        Self::new(DEFAULT_FONT)
    }

    /// Number of glyphs in the atlas.
    #[must_use]
    pub fn cached_glyphs(&self) -> usize {
        self.glyphs.len()
    }

    fn clear_atlas(&mut self) {
        self.glyphs.clear();
        self.shelves.clear();
        self.atlas.fill(0);
        self.dirty = Some(DirtyRect { x: 0, y: 0, w: ATLAS_SIZE, h: ATLAS_SIZE });
        self.generation += 1;
    }

    fn mark_dirty(&mut self, r: DirtyRect) {
        self.dirty = Some(match self.dirty {
            None => r,
            Some(d) => {
                let x0 = d.x.min(r.x);
                let y0 = d.y.min(r.y);
                let x1 = (d.x + d.w).max(r.x + r.w);
                let y1 = (d.y + d.h).max(r.y + r.h);
                DirtyRect { x: x0, y: y0, w: x1 - x0, h: y1 - y0 }
            }
        });
    }

    fn allocate(&mut self, w: usize, h: usize) -> Option<(usize, usize)> {
        if w > ATLAS_SIZE || h > ATLAS_SIZE {
            return None;
        }
        for s in &mut self.shelves {
            if h <= s.h && s.x + w <= ATLAS_SIZE {
                let at = (s.x, s.y);
                s.x += w + 1;
                return Some(at);
            }
        }
        let y = self.shelves.last().map_or(0, |s| s.y + s.h + 1);
        if y + h > ATLAS_SIZE {
            return None;
        }
        self.shelves.push(Shelf { y, h, x: w + 1 });
        Some((0, y))
    }

    /// Glyph of a character, with the shared substitutions; `.notdef` if missing.
    fn glyph_index(&self, c: char) -> u32 {
        let Ok(font) = FontRef::new(&self.font) else { return 0 };
        let substitute = match c {
            '\u{2300}' => Some('\u{2205}'),
            '\u{00a0}' | '\u{2007}' | '\u{202f}' => Some(' '),
            _ => None,
        };
        map_char(&font, c)
            .or_else(|| substitute.and_then(|s| map_char(&font, s)))
            .or_else(|| map_char(&font, '\u{fffd}'))
            .map_or(0, GlyphId::to_u32)
    }

    /// Get or rasterize a glyph. Returns `None` only when the atlas is full even
    /// after clearing it (more distinct glyphs than fit in one atlas).
    fn glyph(&mut self, index: u32) -> Option<GlyphSlot> {
        if let Some(g) = self.glyphs.get(&index) {
            return Some(*g);
        }
        let font = FontRef::new(&self.font).ok()?;
        let gid = GlyphId::new(index);
        let upm = f32::from(font.head().ok()?.units_per_em());
        let advance = f32::from(font.hmtx().ok()?.advance(gid).unwrap_or(0)) / upm;
        let bounds = outline_bounds(&font, gid, RASTER_PX);
        let Some(b) = bounds.filter(|b| b.max.0 > b.min.0 && b.max.1 > b.min.1) else {
            let slot = GlyphSlot { uv: None, quad: [0.0; 4], advance };
            self.glyphs.insert(index, slot);
            return Some(slot);
        };
        let (xmin, ymin) = (b.min.0.floor(), b.min.1.floor());
        let (gw, gh) = ((b.max.0.ceil() - xmin) as usize, (b.max.1.ceil() - ymin) as usize);
        let mut raster = Raster::new(gw, gh, (xmin, ymin + gh as f32));
        let s = RASTER_PX / upm;
        draw_glyph(&font, gid, [s, 0.0, 0.0, s, 0.0, 0.0], 0, &mut raster)?;
        let coverage = raster.coverage();
        let (w, h) = (gw + 2 * SPREAD, gh + 2 * SPREAD);
        let at = match self.allocate(w, h) {
            Some(at) => at,
            None => {
                self.clear_atlas();
                self.allocate(w, h)?
            }
        };
        let sdf = signed_distance_field(&coverage, gw, gh, SPREAD);
        for row in 0..h {
            let dst = (at.1 + row) * ATLAS_SIZE + at.0;
            self.atlas[dst..dst + w].copy_from_slice(&sdf[row * w..(row + 1) * w]);
        }
        self.mark_dirty(DirtyRect { x: at.0, y: at.1, w, h });
        let size = ATLAS_SIZE as f32;
        let pad = SPREAD as f32;
        let slot = GlyphSlot {
            uv: Some([at.0 as f32 / size, at.1 as f32 / size, (at.0 + w) as f32 / size, (at.1 + h) as f32 / size]),
            quad: [
                (xmin - pad) / RASTER_PX,
                (ymin - pad) / RASTER_PX,
                (xmin + gw as f32 + pad) / RASTER_PX,
                (ymin + gh as f32 + pad) / RASTER_PX,
            ],
            advance,
        };
        self.glyphs.insert(index, slot);
        Some(slot)
    }

    /// Characters of one line with their pen positions in em units, and the line's
    /// advance in em units. Returns `None` if the atlas overflowed.
    fn pens(&mut self, line: &str) -> Option<(Vec<(char, f64)>, f64)> {
        if self.shared_layout {
            let units = 1.0 / Text::FONT_UNITS_PER_EM;
            let (pens, width) = Text::line_pens(line);
            return Some((pens.into_iter().map(|(c, x)| (c, x * units)).collect(), width * units));
        }
        let mut pens = Vec::with_capacity(line.len());
        let mut pen = 0.0;
        for c in line.trim_end_matches('\r').chars().filter_map(normalize_char) {
            pens.push((c, pen));
            pen += f64::from(self.glyph(self.glyph_index(c))?.advance);
        }
        Some((pens, pen))
    }

    /// Measure the advance width of one line in model units.
    #[cfg(test)]
    pub(crate) fn line_width(&mut self, line: &str, height: f64) -> f64 {
        let em = height / self.height_per_em;
        self.pens(line).map_or(0.0, |p| p.1) * em
    }

    /// Lay out text into glyph quads (text-local coordinates, y up, before
    /// rotation and translation). Returns `None` if the atlas overflowed while
    /// laying out (caller retries after the generation change).
    pub(crate) fn layout(&mut self, t: &Text) -> Option<Vec<PlacedGlyph>> {
        let h = t.height;
        if !(h.is_finite() && h > 0.0) {
            return Some(Vec::new());
        }
        let em = h / self.height_per_em;
        let lines: Vec<&str> = t.content.split('\n').collect();
        let n = lines.len().max(1) as f64;
        let block_h = h * (1.0 + (n - 1.0) * LINE_SPACING);
        let first_baseline = match t.valign {
            VAlign::Baseline => 0.0,
            VAlign::Top => -TOP_ABOVE_BASELINE * h,
            VAlign::Middle => block_h * 0.5 - TOP_ABOVE_BASELINE * h,
            VAlign::Bottom => block_h - TOP_ABOVE_BASELINE * h,
        };
        let generation = self.generation;
        let mut out = Vec::with_capacity(t.content.len());
        for (i, line) in lines.iter().enumerate() {
            let (pens, width) = self.pens(line)?;
            let width = width * em;
            let start = match t.halign {
                HAlign::Left => 0.0,
                HAlign::Center => -width * 0.5,
                HAlign::Right => -width,
            };
            let baseline = first_baseline - i as f64 * LINE_SPACING * h;
            for (c, x) in pens {
                let g = self.glyph(self.glyph_index(c))?;
                if self.generation != generation {
                    return None;
                }
                if let Some(uv) = g.uv {
                    let pen = start + x * em;
                    out.push(PlacedGlyph {
                        x0: pen + f64::from(g.quad[0]) * em,
                        y0: baseline + f64::from(g.quad[1]) * em,
                        x1: pen + f64::from(g.quad[2]) * em,
                        y1: baseline + f64::from(g.quad[3]) * em,
                        uv,
                    });
                }
            }
        }
        Some(out)
    }
}

/// Outline bounds of a glyph at `size` pixels per em (y up).
fn outline_bounds(font: &FontRef<'_>, gid: GlyphId, size: f32) -> Option<Bounds> {
    let s = size / f32::from(font.head().ok()?.units_per_em());
    let mut b = Bounds::default();
    draw_glyph(font, gid, [s, 0.0, 0.0, s, 0.0, 0.0], 0, &mut b)?;
    b.any.then_some(b)
}

/// The nominal glyph of a character.
fn map_char(font: &FontRef<'_>, c: char) -> Option<GlyphId> {
    font.cmap().ok()?.map_codepoint(c).filter(|g| g.to_u32() != 0)
}

/// Draw a `glyf` glyph through an affine map `[xx, yx, xy, yy, dx, dy]`
/// (`x' = xx·x + xy·y + dx`, `y' = yx·x + yy·y + dy`). Composite glyphs are drawn
/// component by component (nesting is bounded).
fn draw_glyph(font: &FontRef<'_>, gid: GlyphId, m: [f32; 6], depth: u8, pen: &mut impl OutlinePen) -> Option<()> {
    if depth > 8 {
        return None;
    }
    let glyf = font.glyf().ok()?;
    let glyph = font.loca(None).ok()?.get(gid, &glyf)?.into_glyph();
    match glyph {
        None => Some(()),
        Some(Glyph::Simple(g)) => {
            let points: Vec<CurvePoint> = g.points().collect();
            let mut first = 0usize;
            for end in g.end_pts_of_contours() {
                let end = usize::from(end.get());
                draw_contour(points.get(first..=end)?, m, pen);
                first = end + 1;
            }
            Some(())
        }
        Some(Glyph::Composite(g)) => {
            for c in g.components() {
                let t = c.transform;
                let (a, b, cc, d) = (t.xx.to_f32(), t.yx.to_f32(), t.xy.to_f32(), t.yy.to_f32());
                let (mut ox, mut oy) = match c.anchor {
                    Anchor::Offset { x, y } => (f32::from(x), f32::from(y)),
                    // Point-matched placement is not used by the bundled font.
                    Anchor::Point { .. } => (0.0, 0.0),
                };
                if c.flags.contains(CompositeGlyphFlags::SCALED_COMPONENT_OFFSET) {
                    (ox, oy) = (a * ox + cc * oy, b * ox + d * oy);
                }
                // Child map: parent ∘ (component matrix, then offset).
                let child = [
                    m[0] * a + m[2] * b,
                    m[1] * a + m[3] * b,
                    m[0] * cc + m[2] * d,
                    m[1] * cc + m[3] * d,
                    m[0] * ox + m[2] * oy + m[4],
                    m[1] * ox + m[3] * oy + m[5],
                ];
                draw_glyph(font, GlyphId::from(c.glyph), child, depth + 1, pen)?;
            }
            Some(())
        }
    }
}

/// One TrueType contour: on-curve points are ends, off-curve points are quadratic
/// controls, and two consecutive controls imply an on-curve midpoint.
fn draw_contour(points: &[CurvePoint], m: [f32; 6], pen: &mut impl OutlinePen) {
    let n = points.len();
    if n == 0 {
        return;
    }
    let map = |p: &CurvePoint| {
        let (x, y) = (f32::from(p.x), f32::from(p.y));
        (m[0] * x + m[2] * y + m[4], m[1] * x + m[3] * y + m[5])
    };
    let mid = |a: (f32, f32), b: (f32, f32)| (0.5 * (a.0 + b.0), 0.5 * (a.1 + b.1));
    let (start, first) = match points.iter().position(|p| p.on_curve) {
        Some(i) => (points.get(i).map_or((0.0, 0.0), map), i),
        None => (mid(points.get(n - 1).map_or((0.0, 0.0), map), points.first().map_or((0.0, 0.0), map)), n - 1),
    };
    pen.move_to(start.0, start.1);
    let mut control: Option<(f32, f32)> = None;
    for k in 1..=n {
        let Some(p) = points.get((first + k) % n) else { continue };
        let q = map(p);
        if p.on_curve {
            match control.take() {
                Some(c) => pen.quad_to(c.0, c.1, q.0, q.1),
                None => pen.line_to(q.0, q.1),
            }
        } else {
            if let Some(c) = control {
                let implied = mid(c, q);
                pen.quad_to(c.0, c.1, implied.0, implied.1);
            }
            control = Some(q);
        }
    }
    if let Some(c) = control {
        pen.quad_to(c.0, c.1, start.0, start.1);
    }
    pen.close();
}

/// Map control characters: tabs become spaces, other controls are dropped.
fn normalize_char(c: char) -> Option<char> {
    match c {
        '\t' => Some(' '),
        c if c.is_control() => None,
        c => Some(c),
    }
}

/// 1-D squared Euclidean distance transform (Felzenszwalb & Huttenlocher).
fn edt_1d(f: &[f32], d: &mut [f32], v: &mut [usize], z: &mut [f32]) {
    let n = f.len();
    if n == 0 {
        return;
    }
    let mut k = 0usize;
    v[0] = 0;
    z[0] = f32::NEG_INFINITY;
    z[1] = f32::INFINITY;
    for q in 1..n {
        let fq = f[q] + (q * q) as f32;
        // z[0] is -∞, so the loop always stops at k = 0.
        let mut s;
        loop {
            let p = v[k];
            s = (fq - (f[p] + (p * p) as f32)) / (2.0 * q as f32 - 2.0 * p as f32);
            if s <= z[k] && k > 0 {
                k -= 1;
            } else {
                break;
            }
        }
        k += 1;
        v[k] = q;
        z[k] = s;
        z[k + 1] = f32::INFINITY;
    }
    k = 0;
    for (q, out) in d.iter_mut().enumerate().take(n) {
        while z[k + 1] < q as f32 {
            k += 1;
        }
        let p = v[k];
        let dq = q as f32 - p as f32;
        *out = dq * dq + f[p];
    }
}

/// 2-D squared distance to the nearest pixel where `feature` is true.
fn edt_2d(feature: &[bool], w: usize, h: usize) -> Vec<f32> {
    const INF: f32 = 1e20;
    let mut grid: Vec<f32> = feature.iter().map(|&b| if b { 0.0 } else { INF }).collect();
    let n = w.max(h);
    let (mut f, mut d) = (vec![0.0f32; n], vec![0.0f32; n]);
    let (mut v, mut z) = (vec![0usize; n], vec![0.0f32; n + 1]);
    for x in 0..w {
        for y in 0..h {
            f[y] = grid[y * w + x];
        }
        edt_1d(&f[..h], &mut d[..h], &mut v, &mut z);
        for y in 0..h {
            grid[y * w + x] = d[y];
        }
    }
    for y in 0..h {
        f[..w].copy_from_slice(&grid[y * w..(y + 1) * w]);
        edt_1d(&f[..w], &mut d[..w], &mut v, &mut z);
        grid[y * w..(y + 1) * w].copy_from_slice(&d[..w]);
    }
    grid
}

/// Signed distance field of a coverage bitmap, padded by `spread` on each side.
/// Encoded as `0.5` on the outline, increasing inside; `spread` pixels map to ±0.5.
pub(crate) fn signed_distance_field(coverage: &[u8], w: usize, h: usize, spread: usize) -> Vec<u8> {
    let (pw, ph) = (w + 2 * spread, h + 2 * spread);
    let mut cov = vec![0u8; pw * ph];
    for y in 0..h {
        let dst = (y + spread) * pw + spread;
        cov[dst..dst + w].copy_from_slice(&coverage[y * w..(y + 1) * w]);
    }
    let inside: Vec<bool> = cov.iter().map(|&c| c >= 128).collect();
    let outside: Vec<bool> = inside.iter().map(|&b| !b).collect();
    let to_inside = edt_2d(&inside, pw, ph);
    let to_outside = edt_2d(&outside, pw, ph);
    let s = spread as f32;
    cov.iter()
        .enumerate()
        .map(|(i, &c)| {
            // Signed distance in pixels, positive inside.
            let sd = if c > 0 && c < 255 {
                f32::from(c) / 255.0 - 0.5
            } else if inside[i] {
                to_outside[i].sqrt() - 0.5
            } else {
                -(to_inside[i].sqrt() - 0.5)
            };
            ((0.5 + sd / (2.0 * s)).clamp(0.0, 1.0) * 255.0).round() as u8
        })
        .collect()
}

#[cfg(test)]
mod tests {
    use dotloom_geometry::Point;

    use super::*;

    /// Rasterize closed polygons (raster pixels, y down: the origin maps y = 0 to row 0).
    fn raster(w: usize, h: usize, polys: &[&[(f32, f32)]]) -> Vec<u8> {
        let mut r = Raster::new(w, h, (0.0, 0.0));
        for poly in polys {
            r.move_to(poly[0].0, -poly[0].1);
            for p in &poly[1..] {
                r.line_to(p.0, -p.1);
            }
            r.close();
        }
        r.coverage()
    }

    #[test]
    fn rasterizer_coverage_area_and_winding() {
        // A 7 × 7 square on half-pixel boundaries: 49 px of area, half-covered edges.
        let sq: &[(f32, f32)] = &[(1.5, 1.5), (8.5, 1.5), (8.5, 8.5), (1.5, 8.5)];
        let cov = raster(10, 10, &[sq]);
        let area: f32 = cov.iter().map(|&c| f32::from(c) / 255.0).sum();
        assert!((area - 49.0).abs() < 0.1, "area {area}");
        assert_eq!(cov[5 * 10 + 5], 255);
        assert_eq!(cov[5 * 10 + 1], 128);
        assert_eq!(cov[0], 0);
        // Same direction twice (winding 2): the inside stays fully covered (non-zero
        // rule, clamped), the outside stays empty.
        let twice = raster(10, 10, &[sq, sq]);
        for i in 0..100 {
            if cov[i] == 255 || cov[i] == 0 {
                assert_eq!(twice[i], cov[i], "pixel {i}");
            }
        }
        // An inner square in the opposite direction cuts a hole.
        let hole: &[(f32, f32)] = &[(3.0, 3.0), (3.0, 7.0), (7.0, 7.0), (7.0, 3.0)];
        let ring = raster(10, 10, &[sq, hole]);
        assert_eq!(ring[5 * 10 + 5], 0);
        let ring_area: f32 = ring.iter().map(|&c| f32::from(c) / 255.0).sum();
        assert!((ring_area - 33.0).abs() < 0.1, "ring {ring_area}");
        // A diagonal edge: the triangle below the diagonal covers half the square.
        let tri: &[(f32, f32)] = &[(0.0, 0.0), (10.0, 10.0), (0.0, 10.0)];
        let t: f32 = raster(10, 10, &[tri]).iter().map(|&c| f32::from(c) / 255.0).sum();
        assert!((t - 50.0).abs() < 0.1, "triangle {t}");
    }

    #[test]
    fn outlines_match_the_glyph_boxes_of_the_font() {
        // Every glyph, simple or composite, drawn in font units has exactly the
        // bounding box stored in its glyf header (which counts all points).
        let font = FontRef::new(DEFAULT_FONT).unwrap();
        let upm = f32::from(font.head().unwrap().units_per_em());
        let glyf = font.glyf().unwrap();
        let loca = font.loca(None).unwrap();
        let (mut simple, mut composite) = (0, 0);
        for id in 0..font.maxp().unwrap().num_glyphs() {
            let gid = GlyphId::new(u32::from(id));
            let Some(glyph) = loca.get(gid, &glyf).unwrap().into_glyph() else { continue };
            let header = [glyph.x_min(), glyph.y_min(), glyph.x_max(), glyph.y_max()].map(f32::from);
            match glyph {
                Glyph::Simple(_) => simple += 1,
                Glyph::Composite(_) => composite += 1,
            }
            let b = outline_bounds(&font, gid, upm).unwrap();
            assert_eq!([b.min.0, b.min.1, b.max.0, b.max.1], header, "glyph {id}");
        }
        assert!(simple > 300 && composite > 100, "{simple} simple, {composite} composite");
    }

    #[test]
    fn glyph_rasters_have_counters_and_plausible_ink() {
        let font = FontRef::new(DEFAULT_FONT).unwrap();
        // "O" has a counter: empty in the middle, inked on its sides.
        let gid = map_char(&font, 'O').unwrap();
        let b = outline_bounds(&font, gid, RASTER_PX).unwrap();
        let (xmin, ymin) = (b.min.0.floor(), b.min.1.floor());
        let (w, h) = ((b.max.0.ceil() - xmin) as usize, (b.max.1.ceil() - ymin) as usize);
        let mut r = Raster::new(w, h, (xmin, ymin + h as f32));
        let s = RASTER_PX / f32::from(font.head().unwrap().units_per_em());
        draw_glyph(&font, gid, [s, 0.0, 0.0, s, 0.0, 0.0], 0, &mut r).unwrap();
        let cov = r.coverage();
        assert_eq!(cov[(h / 2) * w + w / 2], 0, "counter");
        assert!(cov[(h / 2) * w + 1] > 200, "left stroke");
        assert!(cov[(h / 2) * w + w - 2] > 200, "right stroke");
        // Ink of every glyph stays inside its quad and the SDF is finite.
        let mut ts = TextSystem::with_default_font().unwrap();
        for c in "AgjÇğİ@%∅".chars() {
            let g = ts.glyph(ts.glyph_index(c)).unwrap();
            assert!(g.uv.is_some() && g.quad[2] > g.quad[0] && g.quad[3] > g.quad[1], "{c}");
        }
    }

    fn text(s: &str) -> Text {
        Text {
            position: Point::new(0.0, 0.0),
            content: s.into(),
            height: 10.0,
            rotation: 0.0,
            halign: HAlign::Left,
            valign: VAlign::Baseline,
        }
    }

    #[test]
    fn turkish_and_symbols_have_glyphs() {
        let ts = TextSystem::with_default_font().unwrap();
        let font = FontRef::new(DEFAULT_FONT).unwrap();
        for c in "çÇğĞıİöÖşŞüÜ°±×∅µ²€ΩπДж".chars() {
            assert!(map_char(&font, c).is_some(), "missing {c}");
            assert_ne!(ts.glyph_index(c), 0, "{c}");
        }
        // Diameter sign falls back to the empty-set glyph.
        assert_eq!(ts.glyph_index('\u{2300}'), ts.glyph_index('\u{2205}'));
    }

    #[test]
    fn layout_metrics_follow_the_contract() {
        let mut ts = TextSystem::with_default_font().unwrap();
        let g = ts.layout(&text("H")).unwrap();
        assert_eq!(g.len(), 1);
        // Cap height of Inter ≈ 0.75 × text height (cap + descender = height).
        let cap_top = g[0].y1 - (SPREAD as f64 / f64::from(RASTER_PX)) * (10.0 / ts.height_per_em);
        assert!((cap_top - 7.5).abs() < 0.3, "cap top {cap_top}");
        // Second line is 1.2 h lower.
        let two = ts.layout(&text("H\nH")).unwrap();
        assert!((two[0].y0 - two[1].y0 - 12.0).abs() < 1e-9);
    }

    #[test]
    fn headless_text_metrics_match_the_font() {
        // dotloom-geometry lays text out with generated tables
        // (crates/render/assets/text-metrics.py) that the renderer also uses for
        // the default font. Check them against the font file itself: every mapped
        // character's advance, the units per em and the vertical scale.
        let mut ts = TextSystem::with_default_font().unwrap();
        let font = FontRef::new(DEFAULT_FONT).unwrap();
        let upm = f32::from(font.head().unwrap().units_per_em());
        assert_eq!(f64::from(upm), Text::FONT_UNITS_PER_EM);
        let hmtx = font.hmtx().unwrap();
        let mut checked = 0;
        for cp in 0..=0xffff_u32 {
            let Some(c) = char::from_u32(cp).filter(|c| !c.is_control()) else { continue };
            let Some(gid) = map_char(&font, c) else { continue };
            let want = f64::from(hmtx.advance(gid).unwrap());
            assert_eq!(Text::line_pens(&c.to_string()).1, want, "advance of U+{cp:04X}");
            checked += 1;
        }
        assert!(checked > 900, "{checked}");
        let cap = outline_bounds(&font, map_char(&font, 'H').unwrap(), upm).unwrap().max.1;
        let descender = -f32::from(font.hhea().unwrap().descender().to_i16());
        assert!((1.0 / Text::em_size(1.0) - f64::from((cap + descender) / upm)).abs() < 1e-12);
        // Missing characters advance like `.notdef`, which is what gets drawn.
        let notdef = f64::from(hmtx.advance(GlyphId::NOTDEF).unwrap());
        assert_eq!(Text::line_pens("\u{e000}").1, notdef);
        assert_eq!(ts.glyph_index('\u{e000}'), 0);
        // The renderer's line widths are the shared ones, kerning included.
        for s in ["Dotloom 0123 ABC xyz", "Ölçü ğüşıİç ÇĞÖŞÜ", "W i\tm", "∅ 40 mm ⌀ ±0,5 €", "Дж Ωπ", "AVATAR"]
        {
            let want = ts.line_width(s, 10.0);
            let got = Text::line_width(s, 10.0);
            assert!((got - want).abs() <= 1e-9 * want.max(1.0), "{s:?}: geometry {got} vs renderer {want}");
        }
        // "AV" is drawn kerned: V sits left of where A's advance alone puts it.
        let em = Text::em_size(10.0);
        let kerned = ts.layout(&text("AV")).unwrap();
        let a_advance = f64::from(ts.glyph(ts.glyph_index('A')).unwrap().advance) * em;
        let v_left = f64::from(ts.glyph(ts.glyph_index('V')).unwrap().quad[0]) * em;
        assert!(kerned[1].x0 < a_advance + v_left - 0.01, "{} vs {}", kerned[1].x0, a_advance + v_left);
        // The layout box encloses every drawn glyph quad (minus the SDF padding).
        let t = Text { content: "Ölçü\nÇĞÖŞÜ gjpq".into(), ..text("") };
        let b = t.layout_box();
        let pad = SPREAD as f64 / f64::from(RASTER_PX) * (t.height / ts.height_per_em);
        for g in ts.layout(&t).unwrap() {
            assert!(g.x0 + pad >= b.min.x - 1e-6 && g.x1 - pad <= b.max.x + 1e-6, "x {g:?} {b:?}");
            assert!(g.y0 + pad >= b.min.y - 1e-6 && g.y1 - pad <= b.max.y + 1e-6, "y {g:?} {b:?}");
        }
    }

    #[test]
    fn alignment() {
        let mut ts = TextSystem::with_default_font().unwrap();
        let mut t = text("İstanbul");
        let w = ts.line_width(&t.content, t.height);
        assert!(w > 20.0 && w < 60.0, "{w}");
        t.halign = HAlign::Right;
        let g = ts.layout(&t).unwrap();
        // Quads include the SDF padding (SPREAD / RASTER_PX em ≈ 1.3 units here).
        let pad = SPREAD as f64 / f64::from(RASTER_PX) * (t.height / ts.height_per_em);
        let right = g.last().unwrap().x1 - pad;
        assert!(right <= 0.1 && right > -2.0, "{right}");
        t.halign = HAlign::Center;
        t.valign = VAlign::Middle;
        let g = ts.layout(&t).unwrap();
        let min_x = g.iter().map(|q| q.x0).fold(f64::INFINITY, f64::min);
        assert!((min_x + w * 0.5).abs() < 1.5);
    }

    #[test]
    fn sdf_is_monotonic_across_an_edge() {
        // A filled square in a 10×10 bitmap.
        let mut cov = vec![0u8; 100];
        for y in 3..7 {
            for x in 3..7 {
                cov[y * 10 + x] = 255;
            }
        }
        let sdf = signed_distance_field(&cov, 10, 10, 4);
        let pw = 18;
        let row = 4 + 5;
        let vals: Vec<u8> = (0..pw).map(|x| sdf[row * pw + x]).collect();
        let center = vals[9];
        assert!(center > 128, "{vals:?}");
        assert!(vals[0] < 64);
        for x in 1..9 {
            assert!(vals[x] >= vals[x - 1], "{vals:?}");
        }
    }

    #[test]
    fn controls_are_skipped_and_empty_text_is_fine() {
        let mut ts = TextSystem::with_default_font().unwrap();
        assert!(ts.layout(&text("")).unwrap().is_empty());
        assert_eq!(ts.layout(&text("a\u{7}b")).unwrap().len(), 2);
        let mut bad = text("x");
        bad.height = f64::NAN;
        assert!(ts.layout(&bad).unwrap().is_empty());
    }
}