Scale meme effect

// Seam carving — the algorithm behind Photoshop's Content-Aware Scale. Given an image, it resizes
// WITHOUT uniformly stretching: it removes (to shrink) or duplicates (to enlarge) connected
// low-energy "seams" of pixels, so flat regions (sky, walls) absorb the change while detailed
// regions (faces, text) are left alone — until you push far enough that even they distort, which
// is where the meme lives.
//
// Pure and framework-free: operates on flat RGBA Uint8ClampedArrays (ImageData.data). No DOM, no
// canvas — so the exact same code runs on the main thread AND inside an inlined worker.
//
// References: dual-gradient energy + DP seam finding, the classic Sedgewick/Photoshop approach.

export type RGBA = Uint8ClampedArray;

export interface Frame {
  data: RGBA; // length = w*h*4
  w: number;
  h: number;
}

// How hard resizing biases toward the SUBJECT vs the background. Both shrink and enlarge pick which
// columns to remove/duplicate by mapping k∈[0,count) through pow(t, BIAS) across the ranked list
// (subject at the top). BIAS < 1 clusters picks toward the subject → the subject is carved THROUGH
// (crushed/smeared) while the background still gives a little. BIAS = 1 would be a flat spread;
// smaller = more subject distortion. This is the "smart, funny" knob.
const RESIZE_BIAS = 0.35;
const SHRINK_BIAS = RESIZE_BIAS;
const ENLARGE_BIAS = RESIZE_BIAS;

// ── energy ──────────────────────────────────────────────────────────────────────────────────
// Dual-gradient energy: for each pixel, the squared colour difference to its horizontal and
// vertical neighbours summed. High where detail/edges are, low on flat areas. Border pixels wrap
// so every pixel has neighbours. Returns a Float32Array of length w*h.
export function energyMap(f: Frame): Float32Array {
  const { data, w, h } = f;
  const e = new Float32Array(w * h);
  const at = (x: number, y: number) => (y * w + x) * 4;
  const grad = (a: number, b: number) => {
    const dr = data[a] - data[b];
    const dg = data[a + 1] - data[b + 1];
    const db = data[a + 2] - data[b + 2];
    return dr * dr + dg * dg + db * db;
  };
  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      const xl = x === 0 ? w - 1 : x - 1;
      const xr = x === w - 1 ? 0 : x + 1;
      const yu = y === 0 ? h - 1 : y - 1;
      const yd = y === h - 1 ? 0 : y + 1;
      e[y * w + x] = grad(at(xl, y), at(xr, y)) + grad(at(x, yu), at(x, yd));
    }
  }
  return e;
}

// ── vertical seam (top → bottom) ──────────────────────────────────────────────────────────────
// DP: cumulative minimum energy from the top row down; then backtrack the connected column path of
// least total energy. Returns, for each row y, the x it passes through (length h). Only vertical
// seams are implemented; horizontal carving is done by transposing the frame (see transpose()).
export function findVerticalSeam(e: Float32Array, w: number, h: number): Int32Array {
  const cost = new Float32Array(w * h);
  const from = new Int8Array(w * h); // -1, 0, +1: which parent column we came from
  for (let x = 0; x < w; x++) cost[x] = e[x];
  for (let y = 1; y < h; y++) {
    const row = y * w;
    const prev = row - w;
    for (let x = 0; x < w; x++) {
      let best = cost[prev + x];
      let dir = 0;
      if (x > 0 && cost[prev + x - 1] < best) {
        best = cost[prev + x - 1];
        dir = -1;
      }
      if (x < w - 1 && cost[prev + x + 1] < best) {
        best = cost[prev + x + 1];
        dir = 1;
      }
      cost[row + x] = e[row + x] + best;
      from[row + x] = dir;
    }
  }
  // find the min in the bottom row, then walk back up
  const seam = new Int32Array(h);
  let bx = 0;
  let bcost = Infinity;
  const last = (h - 1) * w;
  for (let x = 0; x < w; x++) {
    if (cost[last + x] < bcost) {
      bcost = cost[last + x];
      bx = x;
    }
  }
  seam[h - 1] = bx;
  for (let y = h - 1; y > 0; y--) {
    bx += from[y * w + bx];
    if (bx < 0) bx = 0;
    else if (bx >= w) bx = w - 1;
    seam[y - 1] = bx;
  }
  return seam;
}

// Remove one vertical seam → a frame one column narrower.
export function removeVerticalSeam(f: Frame, seam: Int32Array): Frame {
  const { data, w, h } = f;
  const nw = w - 1;
  const out = new Uint8ClampedArray(nw * h * 4);
  for (let y = 0; y < h; y++) {
    const sx = seam[y];
    let d = y * nw * 4;
    const srow = y * w * 4;
    for (let x = 0; x < w; x++) {
      if (x === sx) continue;
      const s = srow + x * 4;
      out[d] = data[s];
      out[d + 1] = data[s + 1];
      out[d + 2] = data[s + 2];
      out[d + 3] = data[s + 3];
      d += 4;
    }
  }
  return { data: out, w: nw, h };
}

// Transpose a frame (swap rows/cols), so horizontal seam carving reuses the vertical code.
export function transpose(f: Frame): Frame {
  const { data, w, h } = f;
  const out = new Uint8ClampedArray(w * h * 4);
  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      const s = (y * w + x) * 4;
      const d = (x * h + y) * 4;
      out[d] = data[s];
      out[d + 1] = data[s + 1];
      out[d + 2] = data[s + 2];
      out[d + 3] = data[s + 3];
    }
  }
  return { data: out, w: h, h: w };
}

// NOTE: earlier this file also had a direct carve() (repeated remove/insert per resize). The bench
// no longer uses it — pixel-accurate per-frame carving was far too slow (150-450ms). Everything now
// goes through the precomputed removal-ORDER map below, so that path was deleted. removeVerticalSeam
// / findVerticalSeam / energyMap remain because buildWidthOrder uses them.

// ── removal-order map (the real-time trick) ───────────────────────────────────────────────────
// Pixel-accurate seam carving is far too slow to run per drag frame (each carve re-finds and
// re-scores every seam). Instead we precompute ONCE, on load: carve the image all the way down and
// record, for every ORIGINAL pixel, the STEP at which its seam was removed. Rendering any target
// size then becomes a single linear scan — "keep this pixel iff it survives to that size" — which
// is ~0.5ms per frame instead of hundreds.
//
// Returns a Int32Array of length w*h: order[y*w + x] = the removal step of original column x in row
// y (0 = removed first), or -1 if the pixel survives all the way down to minW. To render target
// width W', drop every pixel whose order is in [0, w - W').
export interface OrderMap {
  order: Int32Array;
  w: number;
  h: number;
  minW: number; // the smallest width we carved down to (how far you can squish)
  // ENLARGE priority, PRECOMPUTED once. For each row y, ranked[y] is the column indices ordered by
  // duplication priority (highest-detail / most-protected subject FIRST). Sorting this per frame was
  // the enlarge lag; it never changes for a given image, so we build it here and the render just
  // reads it. Flat Int32Array of length w*h, row-major: ranked[y*w + k] = the k-th column to grow.
  ranked: Int32Array;
}

export function buildWidthOrder(frame: Frame, minW: number): OrderMap {
  const { w, h } = frame;
  const order = new Int32Array(w * h).fill(-1);
  // survivors[y] = original column indices still present, in current order
  const survivors: Int32Array[] = [];
  for (let y = 0; y < h; y++) {
    const r = new Int32Array(w);
    for (let x = 0; x < w; x++) r[x] = x;
    survivors.push(r);
  }
  let f: Frame = { data: frame.data.slice(), w, h };
  let step = 0;
  const target = Math.max(2, minW);
  while (f.w > target) {
    const e = energyMap(f);
    const seam = findVerticalSeam(e, f.w, f.h);
    for (let y = 0; y < h; y++) {
      const cur = seam[y];
      const ox = survivors[y][cur];
      order[y * w + ox] = step;
      const row = survivors[y];
      const nr = new Int32Array(row.length - 1);
      for (let x = 0, d = 0; x < row.length; x++) if (x !== cur) nr[d++] = row[x];
      survivors[y] = nr;
    }
    f = removeVerticalSeam(f, seam);
    step++;
  }

  // Precompute the enlarge ranking, once. rank: -1 (survives = subject) is top, then descending
  // order value. One sort per row here instead of per row PER FRAME.
  const ranked = new Int32Array(w * h);
  const rankOf = (o: number) => (o === -1 ? Number.MAX_SAFE_INTEGER : o);
  const cols: number[] = new Array(w);
  for (let y = 0; y < h; y++) {
    const base = y * w;
    for (let x = 0; x < w; x++) cols[x] = x;
    cols.sort((a, b) => rankOf(order[base + b]) - rankOf(order[base + a]));
    for (let k = 0; k < w; k++) ranked[base + k] = cols[k];
  }

  return { order, w, h, minW: f.w, ranked };
}

// Render a source frame at a target WIDTH using a precomputed OrderMap. SUBJECT-FIRST in BOTH
// directions — the funny meme behaviour, not classic Photoshop behaviour:
//   - < w  : SHRINK  — remove the SUBJECT's seams first (crush the cat), not the background.
//   - > w  : ENLARGE — duplicate the SUBJECT's seams first (smear the cat), not the background.
// Both use the precomputed `ranked` (highest-detail/most-protected column FIRST per row). Fast:
// one linear scan, no per-frame seam finding.
export function renderWidth(src: Frame, om: OrderMap, targetW: number): Frame {
  const { data, w, h } = src;
  if (targetW === w) return { data: data.slice(), w, h };

  if (targetW < w) {
    const remove = w - targetW;
    const out = new Uint8ClampedArray(targetW * h * 4);
    // Choose `remove` columns to drop, SUBJECT-biased. Walk the ranked list (subject-first) ONCE
    // and drop a column whenever a running accumulator crosses an integer boundary. `keepEvery`
    // controls the rate; because SHRINK_BIAS warps the ranked index we favour the subject end.
    // This is a single bounded O(w) pass and always drops exactly `remove` distinct columns — no
    // probing, no wrap, no chance of an unbounded loop (the previous version could spin forever).
    const drop = new Uint8Array(w);
    for (let y = 0; y < h; y++) {
      const base = y * w;
      drop.fill(0);
      // Distribute `remove` drops across the w ranked positions with a bias curve. For each ranked
      // position k (0 = most subject), cumulative target = round(pow((k+1)/w, SHRINK_BIAS)*remove);
      // drop as many as the target stepped up by. Monotonic and bounded → exactly `remove` drops,
      // subject-clustered (BIAS<1 front-loads them). A tiny top-up guarantees the exact count.
      let prevTarget = 0;
      let dropped = 0;
      for (let k = 0; k < w && dropped < remove; k++) {
        const cumTarget = Math.min(remove, Math.round(Math.pow((k + 1) / w, SHRINK_BIAS) * remove));
        while (dropped < cumTarget && k < w) {
          if (!drop[om.ranked[base + k]]) {
            drop[om.ranked[base + k]] = 1;
            dropped++;
          }
          break; // one column per ranked position k
        }
        prevTarget = cumTarget;
      }
      // exact top-up: if rounding left us short, drop the next subject-ranked columns (bounded).
      for (let k = 0; k < w && dropped < remove; k++) {
        const col = om.ranked[base + k];
        if (!drop[col]) {
          drop[col] = 1;
          dropped++;
        }
      }
      void prevTarget;
      let d = y * targetW * 4;
      for (let x = 0; x < w; x++) {
        if (drop[x]) continue; // carved away
        const s = (base + x) * 4;
        out[d] = data[s];
        out[d + 1] = data[s + 1];
        out[d + 2] = data[s + 2];
        out[d + 3] = data[s + 3];
        d += 4;
      }
    }
    return { data: out, w: targetW, h };
  }

  // ENLARGE — the MEME direction. Classic content-aware enlarge duplicates the FLATTEST seams, so on
  // a subject-on-white photo it just pads white (boring). We do the opposite AND spread it: pick the
  // columns to duplicate across the ranked list via the same power-curve bias as shrink, so the
  // SUBJECT smears/warps proportionally (funny) instead of one strip blowing up.
  const add = targetW - w;
  const out = new Uint8ClampedArray(targetW * h * 4);
  const dupCount = new Int32Array(w);
  for (let y = 0; y < h; y++) {
    const base = y * w;
    dupCount.fill(0);
    // spread `add` duplications across the ranked columns, biased toward the subject (top).
    for (let k = 0; k < add; k++) {
      const t = add > 1 ? k / (add - 1) : 0;
      const idx = Math.min(w - 1, Math.floor(Math.pow(t, ENLARGE_BIAS) * w));
      dupCount[om.ranked[base + idx]]++;
    }

    let d = y * targetW * 4;
    for (let x = 0; x < w; x++) {
      const s = (base + x) * 4;
      out[d] = data[s];
      out[d + 1] = data[s + 1];
      out[d + 2] = data[s + 2];
      out[d + 3] = data[s + 3];
      d += 4;
      const r = (base + Math.min(w - 1, x + 1)) * 4;
      for (let c = 0; c < dupCount[x]; c++) {
        // duplicated subject pixel(s), averaged with the neighbour so the smear stays smooth
        out[d] = (data[s] + data[r]) >> 1;
        out[d + 1] = (data[s + 1] + data[r + 1]) >> 1;
        out[d + 2] = (data[s + 2] + data[r + 2]) >> 1;
        out[d + 3] = (data[s + 3] + data[r + 3]) >> 1;
        d += 4;
      }
    }
  }
  return { data: out, w: targetW, h };
}