GitCorner

Code

ossartcraftphotocraft🌐
856f865cf98d
use super::Map;

/// 1D squared distance transform (Felzenszwalb & Huttenlocher).
fn dt1(f: &[f32], out: &mut [f32], v: &mut [usize], z: &mut [f32], near: &mut [usize]) {
    let n = f.len();
    let mut k = 0usize;
    v[0] = 0;
    z[0] = f32::NEG_INFINITY;
    z[1] = f32::INFINITY;
    for q in 1..n {
        loop {
            let p = v[k];
            let s = ((f[q] + (q * q) as f32) - (f[p] + (p * p) as f32)) / (2.0 * q as f32 - 2.0 * p as f32);
            if s <= z[k] && k > 0 {
                k -= 1;
                continue;
            }
            if s <= z[k] {
                // k == 0 and parabola dominates: replace.
                v[0] = q;
                z[0] = f32::NEG_INFINITY;
                z[1] = f32::INFINITY;
                break;
            }
            k += 1;
            v[k] = q;
            z[k] = s;
            z[k + 1] = f32::INFINITY;
            break;
        }
    }
    k = 0;
    for (q, o) in out.iter_mut().enumerate() {
        while z[k + 1] < q as f32 {
            k += 1;
        }
        let p = v[k];
        let d = q as f32 - p as f32;
        *o = d * d + f[p];
        near[q] = p;
    }
}

/// Exact Euclidean distance from every pixel to the nearest pixel where
/// `inside` is true (0 on those pixels).
#[cfg(test)]
pub(super) fn edt(inside: &[bool], w: usize, h: usize) -> Vec<f32> {
    edt_nearest(inside, w, h).0
}

/// Maps with fewer pixels (or other units of work) than this are not worth spawning threads for.
const PAR_MIN: usize = 1 << 16;

/// Most threads one pass uses (as for the blurs, [`rows_par`]).
const PAR_THREADS: usize = 16;

#[cfg(test)]
thread_local! {
    /// Test hook: the thread count [`par_threads`] gives on this thread, whatever the work.
    pub(super) static THREADS: std::cell::Cell<Option<usize>> = const { std::cell::Cell::new(None) };
}

/// How many threads a pass over `work` pixels (or similar units) uses.
fn par_threads(work: usize) -> usize {
    #[cfg(test)]
    if let Some(n) = THREADS.with(std::cell::Cell::get) {
        return n;
    }
    if cfg!(target_arch = "wasm32") || work < PAR_MIN { 1 } else { std::thread::available_parallelism().map_or(1, |n| n.get()).clamp(1, PAR_THREADS) }
}

/// Runs `f(scratch, u, a_u, b_u)` for every unit `u` of two slices: unit `u` of `a` is
/// `a[u * unit_a..][..unit_a]` (the last may be shorter), the same of `b` with `unit_b`, which is 0
/// when there is no second slice. `work` says how big the whole pass is ([`par_threads`]). Groups of
/// units go to scoped OS threads, each with a scratch value from `init`; not to rayon, as for
/// [`rows_par`]: maps are built from inside rayon tiles, where a waiting worker steals other tiles.
/// A unit is computed from its own arguments alone, so the result does not depend on the threads.
pub(super) fn par_units<S, A: Send, B: Send>(
    work: usize,
    a: &mut [A],
    unit_a: usize,
    b: &mut [B],
    unit_b: usize,
    init: impl Fn() -> S + Sync,
    f: impl Fn(&mut S, usize, &mut [A], &mut [B]) + Sync,
) {
    if unit_a == 0 {
        return;
    }
    let units = a.len().div_ceil(unit_a);
    let threads = par_threads(work).min(units);
    if threads <= 1 {
        run_units(&mut init(), 0, a, unit_a, b, unit_b, &f);
        return;
    }
    // Many more groups than threads, so that a heavy one (an edge-rich stretch) does not hold the rest up.
    let group = units.div_ceil(threads * 8).max(1);
    let mut groups = Vec::new();
    let (mut rest_a, mut rest_b, mut first) = (a, b, 0usize);
    while !rest_a.is_empty() {
        let (ga, na) = rest_a.split_at_mut((group * unit_a).min(rest_a.len()));
        let (gb, nb) = rest_b.split_at_mut((group * unit_b).min(rest_b.len()));
        groups.push((first, ga, gb));
        (rest_a, rest_b, first) = (na, nb, first + group);
    }
    let queue = std::sync::Mutex::new(groups.into_iter());
    let worker = || {
        let mut scratch = init();
        loop {
            let next = queue.lock().unwrap_or_else(std::sync::PoisonError::into_inner).next();
            let Some((first, ga, gb)) = next else { break };
            run_units(&mut scratch, first, ga, unit_a, gb, unit_b, &f);
        }
    };
    std::thread::scope(|sc| {
        // A thread that cannot be spawned leaves its share to the others.
        for _ in 1..threads {
            let _ = std::thread::Builder::new().spawn_scoped(sc, worker);
        }
        worker();
    });
}

fn run_units<S, A, B>(scratch: &mut S, first: usize, a: &mut [A], unit_a: usize, b: &mut [B], unit_b: usize, f: &impl Fn(&mut S, usize, &mut [A], &mut [B])) {
    for (k, ua) in a.chunks_mut(unit_a).enumerate() {
        let ub = b.get_mut(k * unit_b..((k + 1) * unit_b).min(b.len())).unwrap_or(&mut []);
        f(scratch, first + k, ua, ub);
    }
}

/// A `w × h` buffer of `fill`, then filled row by row through `f(y, row)`.
pub(super) fn par_fill<T: Clone + Send>(w: usize, h: usize, fill: T, f: impl Fn(usize, &mut [T]) + Sync) -> Vec<T> {
    let mut out = vec![fill; w.saturating_mul(h)];
    par_units(out.len(), &mut out, w.max(1), &mut [] as &mut [()], 0, || (), |_, y, row, _| f(y, row));
    out
}

/// Working buffers of the 1D distance transform, for lines of up to `n` pixels.
struct Dt1Scratch {
    f: Vec<f32>,
    o: Vec<f32>,
    v: Vec<usize>,
    z: Vec<f32>,
    near: Vec<usize>,
}

impl Dt1Scratch {
    fn new(n: usize) -> Self {
        Dt1Scratch { f: vec![0.0; n], o: vec![0.0; n], v: vec![0; n], z: vec![0.0; n + 1], near: vec![0; n] }
    }
}

/// [`edt`] plus the index of the nearest `inside` pixel (as `u32`: a map past 2³² pixels has no
/// nearest pixel to give, and every distance is then "far").
///
/// Both passes run line by line in parallel: the columns, then the rows. The columns' results are
/// kept column by column (`gc[x * h + y]`) so that each thread writes its own stretch of them.
pub(super) fn edt_nearest(inside: &[bool], w: usize, h: usize) -> (Vec<f32>, Vec<u32>) {
    const INF: f32 = 1e20;
    let total = w.saturating_mul(h);
    // No pixels: nothing to transform, and the scratch below is sized from the larger
    // dimension, which a zero-by-huge plane would still allocate.
    if total != inside.len() || total > u32::MAX as usize || total == 0 {
        return (vec![INF; inside.len()], vec![0; inside.len()]);
    }
    let n = w.max(h);
    let mut gc = vec![0.0f32; total];
    let mut nc = vec![0u32; total];
    par_units(
        total,
        &mut gc,
        h.max(1),
        &mut nc,
        h.max(1),
        || Dt1Scratch::new(n),
        |t, x, g, near| {
            for (y, f) in t.f[..h].iter_mut().enumerate() {
                *f = if inside[y * w + x] { 0.0 } else { INF };
            }
            dt1(&t.f[..h], &mut t.o[..h], &mut t.v, &mut t.z, &mut t.near[..h]);
            g.copy_from_slice(&t.o[..h]);
            for (d, &p) in near.iter_mut().zip(&t.near[..h]) {
                *d = p as u32;
            }
        },
    );
    let mut g = vec![0.0f32; total];
    let mut nearest = vec![0u32; total];
    par_units(
        total,
        &mut g,
        w.max(1),
        &mut nearest,
        w.max(1),
        || Dt1Scratch::new(n),
        |t, y, out, near| {
            for (x, f) in t.f[..w].iter_mut().enumerate() {
                *f = gc[x * h + y];
            }
            dt1(&t.f[..w], &mut t.o[..w], &mut t.v, &mut t.z, &mut t.near[..w]);
            for (x, (d, ne)) in out.iter_mut().zip(near.iter_mut()).enumerate() {
                *d = t.o[x].sqrt();
                let px = t.near[x];
                *ne = (nc[px * h + y] as usize * w + px) as u32;
            }
        },
    );
    (g, nearest)
}

/// Chamfer distance transform with a 5 × 5 mask of exact Euclidean step lengths (1, √2, √5),
/// plus the index of the nearest `inside` pixel (0 on inside pixels). Photoshop's effect
/// distances follow this metric: its stroke corners measure 3.236 = √5 + 1 at offset (1, 3)
/// and 3.650 = √5 + √2 at (2, 3), where the exact distances are 3.162 and 3.606.
#[cfg(test)]
pub(super) fn chamfer_nearest(inside: &[bool], w: usize, h: usize) -> (Vec<f32>, Vec<usize>) {
    chamfer_from(inside.iter().map(|&b| if b { 0.0 } else { CHAMFER_INF }).collect(), w, h)
}

const CHAMFER_INF: f32 = 1e20;

/// [`chamfer_nearest`] from per-pixel start values (`CHAMFER_INF` = not a seed): the result is
/// the minimum over seeds of start value + path length, so partly covered seeds can start at
/// their sub-pixel edge offset.
fn chamfer_from(mut d: Vec<f32>, w: usize, h: usize) -> (Vec<f32>, Vec<usize>) {
    const S2: f32 = std::f32::consts::SQRT_2;
    const S5: f32 = 2.236_068;
    // Forward-pass neighbours (already visited in raster order); the backward pass mirrors them.
    const FWD: [(i64, i64, f32); 8] = [(-1, 0, 1.0), (-1, -1, S2), (0, -1, 1.0), (1, -1, S2), (-1, -2, S5), (1, -2, S5), (-2, -1, S5), (2, -1, S5)];
    let mut near: Vec<usize> = (0..w * h).collect();
    let (wi, hi) = (w as i64, h as i64);
    let relax = |x: i64, y: i64, sign: i64, d: &mut Vec<f32>, near: &mut Vec<usize>| {
        let i = (y * wi + x) as usize;
        let mut best = d[i];
        let mut bn = near[i];
        for &(ox, oy, wt) in &FWD {
            let (nx, ny) = (x + ox * sign, y + oy * sign);
            if nx < 0 || ny < 0 || nx >= wi || ny >= hi {
                continue;
            }
            let j = (ny * wi + nx) as usize;
            let c = d[j] + wt;
            if c < best {
                best = c;
                bn = near[j];
            }
        }
        d[i] = best;
        near[i] = bn;
    };
    for y in 0..hi {
        for x in 0..wi {
            relax(x, y, 1, &mut d, &mut near);
        }
    }
    for y in (0..hi).rev() {
        for x in (0..wi).rev() {
            relax(x, y, -1, &mut d, &mut near);
        }
    }
    (d, near)
}

/// Distance from each pixel centre outside the shape to the shape's edge.
/// Pixels with non-zero alpha are inside; the edge inside the nearest such
/// pixel is placed by its alpha (coverage), as Photoshop does. Inside pixels
/// get ≤ 0.
pub(super) fn dist_outside(s: &Map) -> Vec<f32> {
    dist_outside_by(s, Metric::Euclidean)
}

/// Distance metric for effect distance fields.
#[derive(Clone, Copy, PartialEq)]
pub(super) enum Metric {
    /// Exact Euclidean (effect edges).
    Euclidean,
    /// 5 × 5 chamfer (inside strokes, spread / choke; see [`chamfer_nearest`]).
    Chamfer,
}

/// Outside width from which a stroke's outer edge uses the exact Euclidean transform instead of
/// the fitted 5 × 5 chamfer.
///
/// The chamfer's level sets are octagons: measured against a point source, its distance exceeds
/// the Euclidean radius by up to `0.027 · r` px — 0.48 px at r = 18 (the widest outside stroke any
/// Photoshop oracle matches with the chamfer) and 1.6 px at r = 60, where a wide stroke's boundary
/// visibly facets (#3646). Half a pixel of deviation is reached at r ≈ 19, so strokes narrower
/// than 20 px keep the chamfer, whose sub-pixel edge seeding Photoshop matches at small offsets,
/// and wider ones stay round.
pub const STROKE_CHAMFER_MAX: f32 = 20.0;

/// Whether a stroke whose outside edge is `out_w` px wide uses the exact Euclidean transform (round)
/// rather than the 5 × 5 chamfer's octagon ([`STROKE_CHAMFER_MAX`]). The CPU compositor and the GPU
/// compositor's `program_with` both call this, so a stroke picks the same field in each.
pub fn stroke_outside_exact(out_w: f32) -> bool {
    out_w >= STROKE_CHAMFER_MAX
}

pub(super) fn dist_outside_by(s: &Map, m: Metric) -> Vec<f32> {
    if m == Metric::Chamfer {
        // Seeds start at their sub-pixel edge offset (1 − coverage).
        let start = s.v.iter().map(|&a| if a > INSIDE_EPS { 1.0 - a.min(1.0) } else { CHAMFER_INF }).collect();
        let (d, _) = chamfer_from(start, s.w, s.h);
        return d.iter().zip(&s.v).map(|(d, &a)| if a > INSIDE_EPS { -0.5 } else { d - 0.5 }).collect();
    }
    let inside = covered(s, |a| a > INSIDE_EPS);
    let (d, near) = edt_nearest(&inside, s.w, s.h);
    par_fill(s.w, s.h, 0.0f32, |y, row| {
        for (x, out) in row.iter_mut().enumerate() {
            let i = y * s.w + x;
            *out = if inside[i] { -0.5 } else { d[i] - 0.5 + (1.0 - s.v[near[i] as usize].min(1.0)) };
        }
    })
}

/// Which pixels of `s` satisfy `test`, row by row in parallel.
fn covered(s: &Map, test: impl Fn(f32) -> bool + Sync) -> Vec<bool> {
    par_fill(s.w, s.h, false, |y, row| {
        for (e, &a) in row.iter_mut().zip(s.v.get(y * s.w..).unwrap_or_default()) {
            *e = test(a);
        }
    })
}

/// Distance from each pixel centre inside the shape to the shape's edge
/// (≤ 0 outside).
pub(super) fn dist_inside(s: &Map) -> Vec<f32> {
    dist_inside_by(s, Metric::Euclidean)
}

pub(super) fn dist_inside_by(s: &Map, m: Metric) -> Vec<f32> {
    if m == Metric::Chamfer {
        // Partly covered edge pixels (alpha below their neighbourhood's) are seeds starting at
        // their coverage, mirroring `dist_outside`: a 25 % edge column puts the edge 0.25 px in.
        let cov = local_coverage(s);
        let start =
            s.v.iter()
                .zip(&cov.v)
                .map(|(&a, &c)| {
                    if a <= INSIDE_EPS {
                        0.0
                    } else if c < 1.0 - INSIDE_EPS {
                        c
                    } else {
                        CHAMFER_INF
                    }
                })
                .collect();
        let (d, _) = chamfer_from(start, s.w, s.h);
        return d.iter().zip(&s.v).map(|(d, &a)| if a <= INSIDE_EPS { -0.5 } else { d - 0.5 }).collect();
    }
    let outside = covered(s, |a| a <= INSIDE_EPS);
    let (d, _) = edt_nearest(&outside, s.w, s.h);
    par_fill(s.w, s.h, 0.0f32, |y, row| {
        for (x, out) in row.iter_mut().enumerate() {
            let i = y * s.w + x;
            *out = if outside[i] { -0.5 } else { d[i] - 0.5 };
        }
    })
}

/// Alpha relative to the 3×3 neighbourhood maximum: separates edge coverage
/// from the fill's own opacity on shape layers.
pub(super) fn local_coverage(s: &Map) -> Map {
    let mut out = s.clone();
    for y in 0..s.h as i64 {
        for x in 0..s.w as i64 {
            let a = s.get(x, y);
            if a <= INSIDE_EPS {
                continue;
            }
            let mut mx = a;
            for dy in -1..=1 {
                for dx in -1..=1 {
                    mx = mx.max(s.get(x + dx, y + dy));
                }
            }
            out.v[y as usize * s.w + x as usize] = (a / mx).min(1.0);
        }
    }
    out
}

/// Signed distance from the centre of a pixel of coverage `a` to the straight edge crossing it,
/// positive when the centre is inside the shape. `n` is the edge's unit normal (its signs don't
/// matter).
///
/// A unit pixel cut by a straight edge at distance `r` from its centre (on the side that holds at
/// most half of the pixel) is covered `1/2 - r/u` while the edge crosses two opposite sides, and
/// `((u + v)/2 - r)² / (2uv)` once it only cuts off a corner, with `u ≥ v` the larger and smaller
/// component of the normal. Inverting that places the edge by its coverage at any angle. For an
/// axis-aligned edge (`v = 0`) it is the `a - 1/2` that [`dist_outside`] assumes.
pub(super) fn edge_offset(n: [f32; 2], a: f32) -> f32 {
    if !a.is_finite() {
        return 0.0;
    }
    let (u, v) = (n[0].abs().max(n[1].abs()), n[0].abs().min(n[1].abs()));
    let (c, inside) = if a > 0.5 { (1.0 - a, true) } else { (a, false) };
    let c = c.clamp(0.0, 0.5);
    // The coverage below which the edge only cuts off a corner.
    let corner = if u > 0.0 { v / (2.0 * u) } else { 0.0 };
    let r = if c >= corner { (0.5 - c) * u } else { 0.5 * (u + v) - (2.0 * u * v * c).sqrt() };
    if inside { r } else { -r }
}

/// A sharp, anti-aliased edge pixel: where it puts the straight edge crossing it.
#[derive(Clone, Copy)]
pub(super) struct SharpEdge {
    /// Signed distance from the pixel's centre to the edge, positive inside ([`edge_offset`]).
    pub(super) offset: f32,
    /// The edge's unit normal pointing into the shape (`[0, 0]` when the coverage gives no direction).
    pub(super) normal: [f32; 2],
}

/// Half the spacing of the edge pixels along an edge (at most √2 / 2, along a diagonal): a pixel
/// within it of the foot of the perpendicular sees the edge as a line, one further out as its end.
const EDGE_REACH: f32 = 0.75;

impl SharpEdge {
    /// Distance to the edge from the pixel `(dx, dy)` away from this one, positive on the shape's
    /// side (`inside`) or on the empty side. It is the distance to the edge's line where the
    /// perpendicular lands within [`EDGE_REACH`] of this pixel, and to the end of that stretch
    /// beyond, so the distance to a straight edge is exact and does not follow the pixel staircase.
    /// `None` when the edge has no direction or `(dx, dy)` is on the wrong side of it.
    fn distance(&self, dx: f32, dy: f32, inside: bool) -> Option<f32> {
        let [nx, ny] = self.normal;
        if nx == 0.0 && ny == 0.0 {
            return None;
        }
        let signed = self.offset + dx * nx + dy * ny;
        let across = if inside { signed } else { -signed };
        let along = (dx * -ny + dy * nx).abs();
        (across > 0.0).then(|| across.hypot((along - EDGE_REACH).max(0.0)))
    }
}

/// A sharp edge pixel and where it sits.
#[derive(Clone, Copy)]
pub(super) struct EdgePixel {
    /// Index of the pixel in the map.
    pub(super) at: u32,
    /// The pixel's coverage ([`local_coverage`] of it).
    pub(super) cov: f32,
    pub(super) edge: SharpEdge,
}

/// The sharp edge pixels of a map: a short list, and for every pixel a 4 byte slot (0 = no edge, k =
/// the k-th of the list). Maps are big and edge pixels few, so a per-pixel `Option<SharpEdge>` (16
/// bytes) made every pass over it, and the copies the refinement needs, memory-bound.
pub(super) struct SharpEdges {
    w: usize,
    h: usize,
    pub(super) slot: Vec<u32>,
    pub(super) pixels: Vec<EdgePixel>,
}

impl SharpEdges {
    fn empty(w: usize, h: usize) -> Self {
        SharpEdges { w, h, slot: Vec::new(), pixels: Vec::new() }
    }

    /// The edge of pixel `i`, if it is a sharp edge pixel.
    fn get(&self, i: usize) -> Option<SharpEdge> {
        let k = (*self.slot.get(i)? as usize).checked_sub(1)?;
        self.pixels.get(k).map(|p| p.edge)
    }

    /// The edge of pixel `(x, y)`, if it is a sharp edge pixel (`None` off the map).
    fn at(&self, x: usize, y: usize) -> Option<SharpEdge> {
        if x >= self.w || y >= self.h { None } else { self.get(y * self.w + x) }
    }

    fn has(&self, x: usize, y: usize) -> bool {
        self.at(x, y).is_some()
    }

    pub(super) fn is_empty(&self) -> bool {
        self.pixels.is_empty()
    }

    /// Every sharp edge pixel, as (index in the map, its edge), in pixel order.
    #[cfg(test)]
    pub(super) fn iter(&self) -> impl Iterator<Item = (usize, SharpEdge)> + '_ {
        self.pixels.iter().map(|p| (p.at as usize, p.edge))
    }
}

/// Where the sharp, anti-aliased edge pixels of `s` put the edge ([`edge_offset`], along the normal
/// the coverage gradient gives). Sharp pixels are partly covered and touch both an empty and a full
/// pixel; hard edges and soft ramps have none and keep the `alpha - 1/2` of [`dist_outside`].
///
/// An edge pixel is covered and has an empty neighbour, so a pass over which pixels are covered finds
/// the few candidates without computing [`local_coverage`] of the whole map; the coverage is then
/// worked out where it is needed, by the same formula. Rows are independent and go in parallel.
pub(super) fn sharp_edges(s: &Map) -> SharpEdges {
    let (w, h) = (s.w, s.h);
    if w == 0 || h == 0 || s.v.len() != w * h || s.v.len() >= u32::MAX as usize {
        return SharpEdges::empty(w, h);
    }
    let (wi, hi) = (w as i64, h as i64);
    // `local_coverage` of the pixel at (x, y), on the map.
    let cov_at = |x: i64, y: i64| -> f32 {
        let a = s.v[y as usize * w + x as usize];
        if a <= INSIDE_EPS {
            return a;
        }
        let mut mx = a;
        for dy in -1..=1 {
            for dx in -1..=1 {
                mx = mx.max(s.get(x + dx, y + dy));
            }
        }
        (a / mx).min(1.0)
    };
    // The coverage with the map's border repeated, for the gradient.
    let cov_clamped = |x: i64, y: i64| cov_at(x.max(0).min(wi - 1), y.max(0).min(hi - 1));
    // Whether a pixel is not empty. Off the map counts as covered: only a neighbour on the map can be empty.
    let solid = |x: i64, y: i64| -> bool {
        if x < 0 || y < 0 || x >= wi || y >= hi {
            return true;
        }
        let a = s.v[y as usize * w + x as usize];
        a.is_nan() || a > INSIDE_EPS
    };
    let mut rows: Vec<Vec<EdgePixel>> = vec![Vec::new(); h];
    par_units(
        w * h,
        &mut rows,
        1,
        &mut [] as &mut [()],
        0,
        || (),
        |_, y, row, _| {
            let Some(row) = row.first_mut() else { return };
            let y = y as i64;
            for x in 0..wi {
                if !solid(x, y) || (-1..=1).all(|dy| (-1..=1).all(|dx| solid(x + dx, y + dy))) {
                    continue;
                }
                let i = (y * wi + x) as usize;
                let c = cov_at(x, y);
                if s.v[i] <= INSIDE_EPS || c >= 1.0 - INSIDE_EPS {
                    continue;
                }
                let (mut empty, mut full) = (false, false);
                for (dx, dy) in (-1..=1).flat_map(|dy| (-1..=1).map(move |dx| (dx, dy))) {
                    let (nx, ny) = (x + dx, y + dy);
                    if (dx, dy) == (0, 0) || nx < 0 || ny < 0 || nx >= wi || ny >= hi {
                        continue;
                    }
                    empty |= s.get(nx, ny) <= INSIDE_EPS;
                    full |= cov_at(nx, ny) >= 1.0 - INSIDE_EPS;
                }
                if !(empty && full) {
                    continue;
                }
                let at = &cov_clamped;
                let gx = (at(x + 1, y - 1) + 2.0 * at(x + 1, y) + at(x + 1, y + 1)) - (at(x - 1, y - 1) + 2.0 * at(x - 1, y) + at(x - 1, y + 1));
                let gy = (at(x - 1, y + 1) + 2.0 * at(x, y + 1) + at(x + 1, y + 1)) - (at(x - 1, y - 1) + 2.0 * at(x, y - 1) + at(x + 1, y - 1));
                let len = gx.hypot(gy);
                let (normal, n) = if len.is_finite() && len > 1e-6 { ([gx / len, gy / len], [gx / len, gy / len]) } else { ([0.0, 0.0], [1.0, 0.0]) };
                row.push(EdgePixel { at: i as u32, cov: c, edge: SharpEdge { offset: edge_offset(n, c), normal } });
            }
        },
    );
    let mut pixels: Vec<EdgePixel> = Vec::with_capacity(rows.iter().map(Vec::len).sum());
    for row in rows {
        pixels.extend(row);
    }
    let mut slot = vec![0u32; w * h];
    for (k, p) in pixels.iter().enumerate() {
        if let Some(s) = slot.get_mut(p.at as usize) {
            *s = k as u32 + 1;
        }
    }
    refine_edge_normals(&mut pixels, &slot, w, h);
    SharpEdges { w, h, slot, pixels }
}

/// How far (in pixels) around an edge pixel [`refine_edge_normals`] looks for its neighbours.
const NORMAL_RADIUS: i64 = 3;

/// The 3×3 gradient of the coverage gives an edge's direction to 1-2 degrees, and its error is
/// systematic, so it tilts the distance of every pixel the same way and shows as a faint ripple.
/// The edge points of a straight edge's pixels (each pixel's centre moved to its edge) lie on one
/// line, and the line through the points of the pixels around one gives the direction to a fraction
/// of a degree. Where those points are not on a line (corners, tight curves) the gradient's normal
/// stays.
fn refine_edge_normals(pixels: &mut [EdgePixel], slot: &[u32], w: usize, h: usize) {
    let (wi, hi) = (w as i64, h as i64);
    let points: Vec<[f32; 2]> = pixels
        .iter()
        .map(|p| [(p.at as i64 % wi) as f32 - p.edge.offset * p.edge.normal[0], (p.at as i64 / wi) as f32 - p.edge.offset * p.edge.normal[1]])
        .collect();
    let before: Vec<SharpEdge> = pixels.iter().map(|p| p.edge).collect();
    // Every pixel reads the unrefined edges around it and writes its own, so they go in parallel.
    let work = pixels.len().saturating_mul(32);
    par_units(work, pixels, 1, &mut [] as &mut [()], 0, Vec::<[f32; 2]>::new, |near, k, pixel, _| {
        let (Some(pixel), Some(&e)) = (pixel.first_mut(), before.get(k)) else { return };
        let (x, y) = (pixel.at as i64 % wi, pixel.at as i64 / wi);
        let (mut n, mut sum) = (0.0f32, [0.0f32; 2]);
        near.clear();
        for (dx, dy) in (-NORMAL_RADIUS..=NORMAL_RADIUS).flat_map(|dy| (-NORMAL_RADIUS..=NORMAL_RADIUS).map(move |dx| (dx, dy))) {
            let (nx, ny) = (x + dx, y + dy);
            if dx * dx + dy * dy > NORMAL_RADIUS * NORMAL_RADIUS || nx < 0 || ny < 0 || nx >= wi || ny >= hi {
                continue;
            }
            let Some(j) = slot.get((ny * wi + nx) as usize).and_then(|&s| (s as usize).checked_sub(1)) else { continue };
            let (Some(o), Some(&p)) = (before.get(j), points.get(j)) else { continue };
            if o.normal[0] * e.normal[0] + o.normal[1] * e.normal[1] > 0.9 {
                near.push(p);
                sum = [sum[0] + p[0], sum[1] + p[1]];
                n += 1.0;
            }
        }
        if near.len() < 3 {
            return;
        }
        let mean = [sum[0] / n, sum[1] / n];
        let (mut sxx, mut sxy, mut syy) = (0.0f32, 0.0f32, 0.0f32);
        for p in near.iter() {
            let (dx, dy) = (p[0] - mean[0], p[1] - mean[1]);
            sxx += dx * dx;
            sxy += dx * dy;
            syy += dy * dy;
        }
        // Spread along and across the best line through the points.
        let half = 0.5 * (sxx + syy);
        let root = (0.25 * (sxx - syy) * (sxx - syy) + sxy * sxy).sqrt();
        let (along, across) = (((half + root) / n).max(0.0).sqrt(), ((half - root) / n).max(0.0).sqrt());
        if !(along > EDGE_LINE_MIN_SPREAD && across < EDGE_LINE_MAX_OFF) {
            return;
        }
        let angle = 0.5 * (2.0 * sxy).atan2(sxx - syy);
        let mut normal = [-angle.sin(), angle.cos()];
        if normal[0] * e.normal[0] + normal[1] * e.normal[1] < 0.0 {
            normal = [-normal[0], -normal[1]];
        }
        pixel.edge.normal = normal;
        pixel.edge.offset = edge_offset(normal, pixel.cov);
    });
}

/// The edge points around a pixel must spread at least this far (px, standard deviation) along
/// their line to give it a direction, and stay within [`EDGE_LINE_MAX_OFF`] of it.
const EDGE_LINE_MIN_SPREAD: f32 = 0.7;

const EDGE_LINE_MAX_OFF: f32 = 0.1;

/// How far from the foot of the perpendicular (in pixels) [`edge_distance`] looks for edge pixels.
const FOOT_RADIUS: i64 = 2;

/// The distance from pixel `p` to the sharp edge whose pixel `q` is nearest to it, or `None` when
/// `q` gives no usable distance. The nearest pixel by its centre is not the best one: it can sit a
/// few pixels along the edge from the foot of the perpendicular and deeper than the edge, and the
/// further `p` is from the edge the further, so its distance ripples along the edge. So this takes
/// the smallest distance of the edge pixels around that foot, which is exact for a straight edge.
fn edge_distance(sharp: &SharpEdges, p: [usize; 2], q: [usize; 2], inside: bool) -> Option<f32> {
    let (px, py) = (p[0] as f32, p[1] as f32);
    let e = sharp.at(q[0], q[1])?;
    let mut best = e.distance(px - q[0] as f32, py - q[1] as f32, inside)?;
    // Where p's perpendicular meets q's line.
    let signed = e.offset + (px - q[0] as f32) * e.normal[0] + (py - q[1] as f32) * e.normal[1];
    let (fx, fy) = ((px - signed * e.normal[0]).round() as i64, (py - signed * e.normal[1]).round() as i64);
    for sy in (fy - FOOT_RADIUS).max(0)..=(fy + FOOT_RADIUS).min(sharp.h as i64 - 1) {
        for sx in (fx - FOOT_RADIUS).max(0)..=(fx + FOOT_RADIUS).min(sharp.w as i64 - 1) {
            if let Some(near) = sharp.at(sx as usize, sy as usize)
                && let Some(d) = near.distance(px - sx as f32, py - sy as f32, inside)
            {
                best = best.min(d);
            }
        }
    }
    Some(best)
}

/// [`dist_inside`] for chiselled bevels. A sharp edge pixel puts the edge where its coverage says,
/// at any angle, and the pixels near it measure to that edge ([`edge_distance`]), so the distance
/// ramps stay planar along an oblique edge instead of following the pixel staircase. The plain
/// distance (to the nearest empty pixel, less half a pixel) never falls short of the true one, so
/// it caps the result where an edge lies exactly on a pixel boundary and has no sharp pixel; a mask
/// without sharp pixels gives exactly [`dist_inside`]. Values past `reach` pixels are not refined.
pub(super) fn bevel_dist_inside(s: &Map, sharp: &SharpEdges, reach: f32) -> Vec<f32> {
    let empty = covered(s, |a| a <= INSIDE_EPS);
    let (d, near) = edt_nearest(&empty, s.w, s.h);
    let at = |x: usize, y: usize| -> f32 {
        let i = y * s.w + x;
        if empty[i] {
            return -0.5;
        }
        if let Some(e) = sharp.get(i) {
            return e.offset;
        }
        let plain = d[i] - 0.5;
        if d[i] > reach + EDGE_MARGIN || sharp.is_empty() {
            return plain;
        }
        // The sharp pixel next to the nearest empty one that is nearest to this pixel.
        let (px, py) = (x as i64, y as i64);
        let (ox, oy) = ((near[i] as usize % s.w) as i64, (near[i] as usize / s.w) as i64);
        let q = (-1..=1)
            .flat_map(|dy| (-1..=1).map(move |dx| (ox + dx, oy + dy)))
            .filter(|&(x, y)| x >= 0 && y >= 0 && sharp.has(x as usize, y as usize))
            .min_by_key(|&(x, y)| (x - px) * (x - px) + (y - py) * (y - py));
        match q.and_then(|(x, y)| edge_distance(sharp, [px as usize, py as usize], [x as usize, y as usize], true)) {
            Some(refined) => refined.min(plain),
            None => plain,
        }
    };
    par_fill(s.w, s.h, 0.0f32, |y, row| {
        for (x, out) in row.iter_mut().enumerate() {
            *out = at(x, y);
        }
    })
}

/// [`dist_outside`] for chiselled bevels, with sharp edge pixels placed as in [`bevel_dist_inside`].
pub(super) fn bevel_dist_outside(s: &Map, sharp: &SharpEdges, reach: f32) -> Vec<f32> {
    let inside = covered(s, |a| a > INSIDE_EPS);
    let (d, near) = edt_nearest(&inside, s.w, s.h);
    let at = |x: usize, y: usize| -> f32 {
        let i = y * s.w + x;
        if let Some(e) = sharp.get(i) {
            return -e.offset;
        }
        if inside[i] {
            return -0.5;
        }
        let q = near[i] as usize;
        let Some(e) = sharp.get(q) else { return d[i] - (s.v[q].min(1.0) - 0.5) };
        let (p, qp) = ([x, y], [q % s.w, q / s.w]);
        let measured = if d[i] <= reach + EDGE_MARGIN {
            edge_distance(sharp, p, qp, false)
        } else {
            e.distance(p[0] as f32 - qp[0] as f32, p[1] as f32 - qp[1] as f32, false)
        };
        measured.unwrap_or(d[i] - e.offset)
    };
    par_fill(s.w, s.h, 0.0f32, |y, row| {
        for (x, out) in row.iter_mut().enumerate() {
            *out = at(x, y);
        }
    })
}

/// Pixels past the reach that are still refined, so the value is right where the ramp ends.
const EDGE_MARGIN: f32 = 2.0;

/// Alpha above which a pixel belongs to the layer's shape (half an 8-bit step).
pub(super) const INSIDE_EPS: f32 = 0.5 / 255.0;

/// A distance field of an effect shape, as the map builders above compute it (for the GPU
/// compositor, which builds the rest of the maps itself; keep in sync with `shadow_map`,
/// `glow_map`, `bevel_maps` and `build_maps`).
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum FieldKind {
    /// `dist_outside` of the shape: precise outer glows.
    Outside,
    /// `dist_inside` of the shape: precise inner glows.
    Inside,
    /// `bevel_dist_outside` of the shape: the outside distance of chiselled bevels.
    BevelOutside,
    /// `bevel_dist_inside` of the shape: the inside distance of chiselled bevels.
    BevelInside,
    /// Chamfer distance outside the shape: a narrow raster stroke's outer edge (see
    /// [`stroke_outside_exact`]), and the spread of drop shadows and softer outer glows
    /// ([`dilate`]); their metric is fitted to Photoshop (#224) and keeps the sub-pixel seeding.
    StrokeOutside,
    /// Chamfer distance outside `1 - alpha`: the choke of inner shadows and softer inner glows.
    ChokeInside,
    /// Stroke distance inside the shape.
    StrokeInside,
    /// Exact Euclidean distance outside the shape: a wide raster stroke's outer edge (see
    /// [`stroke_outside_exact`]). The chamfer's level sets are polygons (an ~8-fold octagon), so a
    /// wide stroke's outer boundary facets; the shadow / glow spread above keeps the chamfer (#3646).
    StrokeOutsideExact,
    /// Stroke distance outside a shape layer's outline (from its local coverage), exact Euclidean.
    StrokeOutsideVector,
    /// Chamfer distance outside a shape layer's outline (from its local coverage): a narrow vector
    /// stroke's outer edge, where the chamfer matches Photoshop (see [`STROKE_CHAMFER_MAX`]).
    StrokeOutsideVectorChamfer,
}

/// The `kind` distance field of the shape `alpha` (row-major `w × h`). Values past `reach` pixels
/// from the shape's edge are only meant to be large (the bevel fields skip refining them).
pub fn distance_field(kind: FieldKind, alpha: Vec<f32>, w: usize, h: usize, reach: f32) -> Vec<f32> {
    let s = Map { w, h, v: alpha };
    match kind {
        FieldKind::Outside => dist_outside(&s),
        FieldKind::Inside => dist_inside(&s),
        FieldKind::BevelOutside => bevel_dist_outside(&s, &sharp_edges(&s), reach),
        FieldKind::BevelInside => bevel_dist_inside(&s, &sharp_edges(&s), reach),
        FieldKind::StrokeOutside => dist_outside_by(&s, Metric::Chamfer),
        FieldKind::ChokeInside => dist_outside_by(&s.map(|a| 1.0 - a), Metric::Chamfer),
        FieldKind::StrokeInside => dist_inside_by(&s, Metric::Chamfer),
        FieldKind::StrokeOutsideExact => dist_outside_by(&s, Metric::Euclidean),
        FieldKind::StrokeOutsideVector => dist_outside_by(&local_coverage(&s), Metric::Euclidean),
        FieldKind::StrokeOutsideVectorChamfer => dist_outside_by(&local_coverage(&s), Metric::Chamfer),
    }
}

/// Both chiselled bevel fields of `alpha`, `[BevelInside, BevelOutside]`: each is its
/// [`distance_field`], with the sharp edges they both start from found once.
pub fn bevel_distance_fields(alpha: Vec<f32>, w: usize, h: usize, reach: f32) -> [Vec<f32>; 2] {
    bevel_dists(&Map { w, h, v: alpha }, reach)
}

/// The inside and outside bevel distances of `s`, from one set of sharp edges.
pub(super) fn bevel_dists(s: &Map, reach: f32) -> [Vec<f32>; 2] {
    let sharp = sharp_edges(s);
    [bevel_dist_inside(s, &sharp, reach), bevel_dist_outside(s, &sharp, reach)]
}