Skip to content

armgit / macro

Public Imported from GitHub
0

Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.

5.7 KB
Raw Blame
//! Growing and shrinking selections by a distance: an exact Euclidean
//! distance transform (Felzenszwalb and Huttenlocher's lower envelope of
//! parabolas) from the selected pixels, or from the unselected ones, so the
//! cost does not depend on the distance and round shapes stay round.
//!
//! Only distances up to the growth matter, so the work goes in tiles, each
//! measured over a halo that wide around it: memory stays bounded however
//! large the selection.

use crate::raster::{IRect, Raster, Selection};

/// Pixels at or above this coverage count as selected.
const SELECTED: u8 = 128;
/// The most a selection grows or shrinks (Photoshop's).
pub(super) const MAX_DISTANCE: i32 = 500;
/// Side of the tiles worked on (more for long distances).
const SIDE: i32 = 512;

/// Grows (positive) or shrinks (negative) a selection by `pixels`, with
/// antialiased edges where the new edge is not straight.
pub(super) fn expand(selection: &Selection, pixels: i32) -> Selection {
    let pixels = pixels.clamp(-MAX_DISTANCE, MAX_DISTANCE);
    let Some(bounds) = selection.mask.content_bounds() else {
        return Selection::none();
    };
    if pixels == 0 {
        return selection.clone();
    }
    let grow = pixels > 0;
    let r = f64::from(pixels.unsigned_abs());
    // Growing needs room for the growth; shrinking, a ring of unselected
    // pixels around the selection to measure from.
    let area = bounds.outset(if grow { pixels + 1 } else { 1 });
    // Distance to the nearest feature: selected pixels when growing,
    // unselected ones when shrinking. Past `far` is far enough.
    let far = pixels.unsigned_abs() as u16 + 2;
    let halo = i32::from(far);
    let side = SIDE.max(4 * halo);
    let feature = |v: u8| (v >= SELECTED) == grow;
    let cap = f64::from(far) * f64::from(far);
    let mut mask = Raster::gray();
    let mut cover = Vec::new();
    let mut out = Vec::new();
    for y in (area.y..area.bottom()).step_by(side as usize) {
        for x in (area.x..area.right()).step_by(side as usize) {
            let part = IRect::new(x, y, side, side).intersect(&area);
            // Pixels past the area are unselected, and past its edge ring
            // never nearer than the ring itself.
            let ctx = part.outset(halo).intersect(&area);
            let (w, h) = (ctx.w as usize, ctx.h as usize);
            cover.clear();
            cover.resize(w * h, 0);
            selection.mask.read(ctx, &mut cover);
            let columns = column_distances(&cover, w, h, far, feature);
            let mut f = vec![0.0; w];
            let mut d2 = vec![0.0; w];
            let mut v = vec![0usize; w];
            let mut z = vec![0.0; w + 1];
            out.clear();
            for row in (part.y - ctx.y) as usize..(part.bottom() - ctx.y) as usize {
                let line = row * w..(row + 1) * w;
                for (f, &c) in f.iter_mut().zip(&columns[line.clone()]) {
                    *f = f64::from(c) * f64::from(c);
                }
                envelope(&f, &mut d2, &mut v, &mut z);
                let cols = (part.x - ctx.x) as usize..(part.right() - ctx.x) as usize;
                for (&px, &d2) in cover[line][cols.clone()].iter().zip(&d2[cols]) {
                    let d = d2.min(cap).sqrt();
                    let edge = if grow {
                        (r + 1.0 - d).clamp(0.0, 1.0)
                    } else {
                        (d - r).clamp(0.0, 1.0)
                    };
                    let edge = (edge * 255.0 + 0.5) as u8;
                    out.push(if grow { px.max(edge) } else { px.min(edge) });
                }
            }
            mask.write(part, &out);
        }
    }
    Selection { mask }
}

/// For each pixel of a `w × h` grid, the distance up or down its column to
/// the nearest pixel where `feature` holds (`far` when none is nearer).
fn column_distances(
    cover: &[u8],
    w: usize,
    h: usize,
    far: u16,
    feature: impl Fn(u8) -> bool,
) -> Vec<u16> {
    let mut d = vec![far; w * h];
    let mut last = vec![None::<usize>; w];
    for y in 0..h {
        for (x, last) in last.iter_mut().enumerate() {
            if feature(cover[y * w + x]) {
                *last = Some(y);
            }
            if let Some(f) = *last {
                d[y * w + x] = (y - f).min(usize::from(far)) as u16;
            }
        }
    }
    last.fill(None);
    for y in (0..h).rev() {
        for (x, last) in last.iter_mut().enumerate() {
            if feature(cover[y * w + x]) {
                *last = Some(y);
            }
            if let Some(f) = *last {
                let i = y * w + x;
                d[i] = d[i].min((f - y).min(usize::from(far)) as u16);
            }
        }
    }
    d
}

/// One row of the distance transform: `out[q]` is the least
/// `f[p] + (q - p)²` over `p`, the lower envelope of parabolas rooted at
/// each `p` (`v` and `z` are scratch: `f.len()` and one more).
fn envelope(f: &[f64], out: &mut [f64], v: &mut [usize], z: &mut [f64]) {
    let n = f.len();
    if n == 0 {
        return;
    }
    let mut k = 0;
    v[0] = 0;
    z[0] = f64::NEG_INFINITY;
    z[1] = f64::INFINITY;
    for q in 1..n {
        let fq = f[q] + (q * q) as f64;
        let meet = |p: usize| (fq - (f[p] + (p * p) as f64)) / (2.0 * (q - p) as f64);
        let mut s = meet(v[k]);
        // z[0] is -inf, so this stops at the first parabola.
        while s <= z[k] {
            k -= 1;
            s = meet(v[k]);
        }
        k += 1;
        v[k] = q;
        z[k] = s;
        z[k + 1] = f64::INFINITY;
    }
    k = 0;
    for (q, o) in out.iter_mut().enumerate() {
        while z[k + 1] < q as f64 {
            k += 1;
        }
        let dq = q as f64 - v[k] as f64;
        *o = dq * dq + f[v[k]];
    }
}