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.

13.6 KB
Raw Blame
//! Resampling under any affine map: each output pixel's center is mapped
//! back into the source and sampled there (nearest, bilinear, or bicubic
//! with Keys' `a = -0.5`) from premultiplied values, then unpremultiplied.
//!
//! Where the map shrinks the source by more than half (an output pixel
//! spans over two source pixels along either of its sides), each output
//! pixel instead averages a grid of bilinear samples spread over its
//! footprint, so downscales do not alias. Nearest neighbor never averages:
//! it keeps hard pixels hard.
//!
//! The output is processed a tile at a time, each reading only the source
//! area it maps back to (split smaller while that area is large, and read
//! pixel by pixel when even a small block maps back to too much).

use super::Interpolation;
use crate::edit::filters::premul::{add_scaled, load, store};
use crate::raster::{IRect, Raster};

/// Farthest the output reaches from the canvas origin, in pixels.
const MAX_COORD: f64 = (1 << 21) as f64;
/// Most samples along each side of an output pixel when averaging.
const MAX_SUBSAMPLES: usize = 16;
/// Most source pixels a block reads before it is split.
const MAX_SOURCE: i64 = 1 << 20;
/// Smallest block side worth splitting.
const MIN_BLOCK: i32 = 16;
/// The most output pixels a resampling makes (a billion: more than any
/// layer the engine can hold); a map that would make more leaves nothing.
const MAX_OUTPUT: i64 = 1 << 30;

/// The raster's pixels mapped through `m`, resampled.
pub(super) fn resample(src: &Raster, m: [f64; 6], interpolation: Interpolation) -> Raster {
    match src.channels() {
        4 => run::<4>(src, m, interpolation),
        1 => run::<1>(src, m, interpolation),
        c => Raster::new(c),
    }
}

fn run<const C: usize>(src: &Raster, m: [f64; 6], interpolation: Interpolation) -> Raster {
    let mut out = Raster::new(C as u8);
    let Some(content) = src.content_bounds() else {
        return out;
    };
    let [a, b, c, d, e, f] = m;
    let det = a * d - b * c;
    if !det.is_finite() || det.abs() < 1e-12 {
        return out;
    }
    let inv = [
        d / det,
        -b / det,
        -c / det,
        a / det,
        (c * f - d * e) / det,
        (b * e - a * f) / det,
    ];
    // The content's corners mapped give the output's bounds.
    let (l, t) = (f64::from(content.x), f64::from(content.y));
    let (r, btm) = (f64::from(content.right()), f64::from(content.bottom()));
    let corners =
        [(l, t), (r, t), (l, btm), (r, btm)].map(|(x, y)| (a * x + c * y + e, b * x + d * y + f));
    let snap = |v: f64| {
        let n = v.round();
        if (v - n).abs() < 1e-6 { n } else { v }
    };
    let xs = corners.map(|p| snap(p.0));
    let ys = corners.map(|p| snap(p.1));
    let lo = |v: [f64; 4]| v.iter().copied().fold(f64::INFINITY, f64::min).floor();
    let hi = |v: [f64; 4]| v.iter().copied().fold(f64::NEG_INFINITY, f64::max).ceil();
    let clamp = |v: f64| v.clamp(-MAX_COORD, MAX_COORD) as i32;
    let rect = IRect::from_ltrb(clamp(lo(xs)), clamp(lo(ys)), clamp(hi(xs)), clamp(hi(ys)));
    if rect.is_empty() || rect.area() > MAX_OUTPUT {
        return out;
    }
    out.set_origin((rect.x, rect.y));
    // How many samples to average along each side of an output pixel.
    let average = |dx: f64, dy: f64| {
        let span = dx.hypot(dy);
        if interpolation != Interpolation::Nearest && span > 2.0 {
            (span.ceil() as usize).min(MAX_SUBSAMPLES)
        } else {
            1
        }
    };
    let sampler = Sampler {
        src,
        content,
        inv,
        interpolation,
        sub: (average(inv[0], inv[1]), average(inv[2], inv[3])),
        margin: match interpolation {
            Interpolation::Nearest => 1,
            Interpolation::Bilinear => 2,
            Interpolation::Bicubic => 3,
        },
    };
    for (tx, ty) in IRect::new(0, 0, rect.w, rect.h).tiles() {
        let block = IRect::tile(tx, ty)
            .translate(rect.x, rect.y)
            .intersect(&rect);
        sampler.block::<C>(&mut out, block);
    }
    out
}

/// Samples the source for blocks of output.
struct Sampler<'a> {
    src: &'a Raster,
    content: IRect,
    /// The inverse map: output canvas to source canvas.
    inv: [f64; 6],
    interpolation: Interpolation,
    /// Samples averaged across and down each output pixel.
    sub: (usize, usize),
    /// Source pixels read around what a block maps back to.
    margin: i32,
}

impl Sampler<'_> {
    /// Where an output canvas point comes from in the source.
    fn back(&self, x: f64, y: f64) -> (f64, f64) {
        let m = &self.inv;
        (m[0] * x + m[2] * y + m[4], m[1] * x + m[3] * y + m[5])
    }

    /// Fills one block of the output.
    fn block<const C: usize>(&self, out: &mut Raster, block: IRect) {
        let corners = [
            (block.x, block.y),
            (block.right(), block.y),
            (block.x, block.bottom()),
            (block.right(), block.bottom()),
        ]
        .map(|(x, y)| self.back(f64::from(x), f64::from(y)));
        let lo = |v: [f64; 4]| v.iter().copied().fold(f64::INFINITY, f64::min);
        let hi = |v: [f64; 4]| v.iter().copied().fold(f64::NEG_INFINITY, f64::max);
        let (us, vs) = (corners.map(|p| p.0), corners.map(|p| p.1));
        let whole = |v: f64| v.clamp(-MAX_COORD, MAX_COORD) as i32;
        let need = IRect::from_ltrb(
            whole(lo(us).floor()) - self.margin,
            whole(lo(vs).floor()) - self.margin,
            whole(hi(us).ceil()) + self.margin,
            whole(hi(vs).ceil()) + self.margin,
        )
        .intersect(&self.content.outset(self.margin));
        if need.is_empty() {
            return;
        }
        let sparse = need.area() > MAX_SOURCE;
        if sparse && block.w >= 2 * MIN_BLOCK && block.h >= 2 * MIN_BLOCK {
            let (hw, hh) = (block.w / 2, block.h / 2);
            for part in [
                IRect::new(block.x, block.y, hw, hh),
                IRect::new(block.x + hw, block.y, block.w - hw, hh),
                IRect::new(block.x, block.y + hh, hw, block.h - hh),
                IRect::new(block.x + hw, block.y + hh, block.w - hw, block.h - hh),
            ] {
                self.block::<C>(out, part);
            }
            return;
        }
        let grid = if sparse {
            // Shrinking so far that even a small block maps back to more
            // than is worth reading whole: read only what is sampled.
            Grid {
                px: Vec::new(),
                raw: Vec::new(),
                rect: need,
                sparse: Some(self.src),
            }
        } else {
            let raw = self.src.read_vec(need);
            if raw.iter().all(|&v| v == 0) {
                return;
            }
            Grid {
                px: if self.interpolation == Interpolation::Nearest {
                    Vec::new()
                } else {
                    raw.chunks_exact(C).map(load::<C>).collect()
                },
                raw,
                rect: need,
                sparse: None,
            }
        };
        let mut data = vec![0u8; block.area() as usize * C];
        let (n0, n1) = self.sub;
        for (row, line) in data.chunks_exact_mut(block.w as usize * C).enumerate() {
            let y = f64::from(block.y + row as i32) + 0.5;
            let Some((x0, x1)) = self.span(y, block) else {
                continue;
            };
            for x in x0..x1 {
                let px = &mut line[((x - block.x) as usize) * C..][..C];
                let cx = f64::from(x) + 0.5;
                if self.interpolation == Interpolation::Nearest {
                    let (u, v) = self.back(cx, y);
                    grid.nearest(u, v, px);
                    continue;
                }
                let value = if n0 * n1 > 1 {
                    let mut sum = [0.0f32; C];
                    for j in 0..n1 {
                        let sy = y - 0.5 + (j as f64 + 0.5) / n1 as f64;
                        for i in 0..n0 {
                            let sx = cx - 0.5 + (i as f64 + 0.5) / n0 as f64;
                            let (u, v) = self.back(sx, sy);
                            add_scaled(&mut sum, &grid.bilinear(u, v), 1.0);
                        }
                    }
                    let k = 1.0 / (n0 * n1) as f32;
                    sum.map(|s| s * k)
                } else {
                    let (u, v) = self.back(cx, y);
                    match self.interpolation {
                        Interpolation::Bicubic => grid.bicubic(u, v),
                        _ => grid.bilinear(u, v),
                    }
                };
                store(value, px);
            }
        }
        out.write(block, &data);
    }

    /// The output pixels of row `y` (at pixel centers) within `block` that
    /// map back near the content.
    fn span(&self, y: f64, block: IRect) -> Option<(i32, i32)> {
        let reach = self.content.outset(self.margin + 1);
        let m = &self.inv;
        let (mut lo, mut hi) = (f64::from(block.x), f64::from(block.right()));
        for (base, slope, min, max) in [
            (m[2] * y + m[4], m[0], reach.x, reach.right()),
            (m[3] * y + m[5], m[1], reach.y, reach.bottom()),
        ] {
            let (min, max) = (f64::from(min), f64::from(max));
            if slope.abs() < 1e-12 {
                if base < min || base > max {
                    return None;
                }
                continue;
            }
            // base + slope · (x + 0.5) within min..max.
            let (a, b) = ((min - base) / slope - 0.5, (max - base) / slope - 0.5);
            lo = lo.max(a.min(b).floor() - 1.0);
            hi = hi.min(a.max(b).ceil() + 1.0);
        }
        (lo < hi).then_some((lo as i32, hi as i32))
    }
}

/// Source pixels around what a block maps back to.
struct Grid<'a, const C: usize> {
    /// Premultiplied values (not for nearest neighbor, nor when sparse).
    px: Vec<[f32; C]>,
    /// The samples as read (not when sparse).
    raw: Vec<u8>,
    rect: IRect,
    /// The source, when it is read a pixel at a time instead.
    sparse: Option<&'a Raster>,
}

impl<const C: usize> Grid<'_, C> {
    /// The samples of grid pixel `(i, j)` (inside the grid).
    fn samples(&self, i: i64, j: i64) -> [u8; 4] {
        match self.sparse {
            Some(src) => src.get(self.rect.x + i as i32, self.rect.y + j as i32),
            None => {
                let at = (j as usize * self.rect.w as usize + i as usize) * C;
                let mut px = [0u8; 4];
                px[..C].copy_from_slice(&self.raw[at..at + C]);
                px
            }
        }
    }

    /// The value of grid pixel `(i, j)`, zero outside.
    fn at(&self, i: i64, j: i64) -> [f32; C] {
        if i < 0 || j < 0 || i >= i64::from(self.rect.w) || j >= i64::from(self.rect.h) {
            return [0.0; C];
        }
        if self.px.is_empty() {
            return load::<C>(&self.samples(i, j));
        }
        self.px[j as usize * self.rect.w as usize + i as usize]
    }

    /// The source pixel containing canvas point `(u, v)`, copied as is.
    fn nearest(&self, u: f64, v: f64, out: &mut [u8]) {
        let (i, j) = (
            u.floor() - f64::from(self.rect.x),
            v.floor() - f64::from(self.rect.y),
        );
        if i < 0.0 || j < 0.0 || i >= f64::from(self.rect.w) || j >= f64::from(self.rect.h) {
            return;
        }
        out.copy_from_slice(&self.samples(i as i64, j as i64)[..C]);
    }

    /// Bilinear value at canvas point `(u, v)`.
    fn bilinear(&self, u: f64, v: f64) -> [f32; C] {
        let (fx, fy) = (
            u - 0.5 - f64::from(self.rect.x),
            v - 0.5 - f64::from(self.rect.y),
        );
        let (x0, y0) = (fx.floor(), fy.floor());
        let (tx, ty) = ((fx - x0) as f32, (fy - y0) as f32);
        let (i, j) = (x0 as i64, y0 as i64);
        let mut out = [0.0f32; C];
        add_scaled(&mut out, &self.at(i, j), (1.0 - tx) * (1.0 - ty));
        add_scaled(&mut out, &self.at(i + 1, j), tx * (1.0 - ty));
        add_scaled(&mut out, &self.at(i, j + 1), (1.0 - tx) * ty);
        add_scaled(&mut out, &self.at(i + 1, j + 1), tx * ty);
        out
    }

    /// Bicubic value at canvas point `(u, v)`.
    fn bicubic(&self, u: f64, v: f64) -> [f32; C] {
        let (fx, fy) = (
            u - 0.5 - f64::from(self.rect.x),
            v - 0.5 - f64::from(self.rect.y),
        );
        let (x0, y0) = (fx.floor(), fy.floor());
        let (wx, wy) = (keys((fx - x0) as f32), keys((fy - y0) as f32));
        let (i, j) = (x0 as i64 - 1, y0 as i64 - 1);
        let (w, h) = (i64::from(self.rect.w), i64::from(self.rect.h));
        let mut out = [0.0f32; C];
        if !self.px.is_empty() && i >= 0 && j >= 0 && i + 4 <= w && j + 4 <= h {
            let stride = w as usize;
            for (dy, &ky) in wy.iter().enumerate() {
                let row = &self.px[(j as usize + dy) * stride + i as usize..][..4];
                let mut acc = [0.0f32; C];
                for (v, &kx) in row.iter().zip(&wx) {
                    add_scaled(&mut acc, v, kx);
                }
                add_scaled(&mut out, &acc, ky);
            }
        } else {
            for (dy, &ky) in wy.iter().enumerate() {
                for (dx, &kx) in wx.iter().enumerate() {
                    add_scaled(&mut out, &self.at(i + dx as i64, j + dy as i64), kx * ky);
                }
            }
        }
        out
    }
}

/// Keys' cubic convolution weights (`a = -0.5`) for the four pixels around
/// a point `t` (`0..1`) past the second.
fn keys(t: f32) -> [f32; 4] {
    let (t2, t3) = (t * t, t * t * t);
    [
        -0.5 * t3 + t2 - 0.5 * t,
        1.5 * t3 - 2.5 * t2 + 1.0,
        -1.5 * t3 + 2.0 * t2 + 0.5 * t,
        0.5 * t3 - 0.5 * t2,
    ]
}