Skip to content

Open source CapCut alternative.

TypeScript
18.4 KB
Raw Blame
/**
 * Which face a piece of type on a reference frame is set in.
 *
 * The reference's ink is lifted off its ground, cut to its bounding box and
 * laid on a small grid; each candidate face sets the same words, its tracking
 * solved so its ink runs as wide for its height as the reference's does, and
 * goes on a grid the same size. The score is how much of the two grids' ink
 * overlaps (soft IoU) times how close their widths come once the tracking is
 * spent, so a condensed face that cannot stretch to a wide line scores low.
 * Every face draws through the raster seam, so the page and a headless job
 * rank alike.
 */

import { baselineDrop, ensureFontLoaded, LETTER_SPACING_MAX, LETTER_SPACING_MIN, LINE_HEIGHT, TEXT_WEIGHTS, type TextWeight } from "@donkeycut/effects-kit";
import { GOOGLE_FONTS } from "./fontCatalog";
import { faceEmAscent } from "./fontEm";
import { createRasterCanvas, type RasterSurface } from "./raster";
import { allFonts, FONTS, hasFont } from "./types";

/** A face a title can be set in. */
export interface TitleFace {
  font: string;
  weight: TextWeight;
  italic?: boolean;
}

/** A face as it ranks against the reference. */
export interface FaceMatch extends TitleFace {
  /** 0..1: ink overlap times width agreement. */
  score: number;
  /** The letter spacing, em, that runs the face as wide as the reference. */
  tracking: number;
  /** The type size, in the reference's px, that sets its first line's ink
   * as tall as the reference's. */
  typePx: number;
}

/** Pixels in a box. */
export interface InkBox {
  x: number;
  y: number;
  w: number;
  h: number;
}

/** A crop's ink: 1 where type is, 0 where its ground is, and the box the ink
 * fills. `core` marks the strongest of it, the middles of the strokes, which
 * stay apart where soft edges run lines of small type together. */
export interface InkMask {
  w: number;
  h: number;
  ink: Uint8Array;
  core?: Uint8Array;
  box: InkBox | null;
}

/** Type size every candidate is set at, px. */
const PROBE_PX = 64;
/** Grid rows both inks are laid on. */
const GRID_ROWS = 40;
/** A row or column whose ink is under this share of the fullest one is a
 * speck, outside the box. */
const SPECK = 0.02;
/** How little core ink a row between two lines may hold, against the
 * typical row of the lines it parts, to split them. */
const VALLEY = 0.25;
/** The upright weights of the system set, which every host draws. */
const BASE_WEIGHTS: Record<string, TextWeight[]> = { impact: [400] };
const BASE_DEFAULT_WEIGHTS: TextWeight[] = [400, 700];

/** Every face this process can draw a title in: the bundled families at their
 * bundled weights (a lighter cut answers to 400, as a title asks for it), the
 * system set, and the account's own fonts. */
export function bundledFaces(): TitleFace[] {
  const asTitle = (w: number) => TEXT_WEIGHTS.find((t) => t >= w) ?? 900;
  const faces: TitleFace[] = [];
  for (const f of FONTS) {
    for (const weight of BASE_WEIGHTS[f.id] ?? BASE_DEFAULT_WEIGHTS) faces.push({ font: f.id, weight });
  }
  for (const f of GOOGLE_FONTS) {
    if (!hasFont(f.id)) {
      continue;
    }
    for (const w of new Set(f.weights.map(asTitle))) faces.push({ font: f.id, weight: w });
    for (const w of new Set((f.italics ?? []).map(asTitle))) faces.push({ font: f.id, weight: w, italic: true });
  }

  // Fonts the account brought: one face each, drawn as the file sets it.
  const known = new Set([...FONTS.map((f) => f.id), ...GOOGLE_FONTS.map((f) => f.id)]);
  for (const f of allFonts()) {
    if (!known.has(f.id)) faces.push({ font: f.id, weight: 400 });
  }
  return faces;
}

/** The ink in an RGBA crop. The ground is the colour its border mostly
 * holds; ink is whatever sits far from it, split at the Otsu threshold of
 * that distance, so light type on dark, dark on light and coloured type all
 * read the same. */
export function inkMaskOf(data: Uint8ClampedArray, w: number, h: number): InkMask {
  const n = w * h;
  const ground = borderMedian(data, w, h);

  // Distance from the ground, 0..255, and its histogram.
  const dist = new Uint8Array(n);
  const hist = new Float64Array(256);
  for (let i = 0; i < n; i++) {
    const d = Math.max(
      Math.abs(data[i * 4] - ground[0]),
      Math.abs(data[i * 4 + 1] - ground[1]),
      Math.abs(data[i * 4 + 2] - ground[2])
    );
    dist[i] = d;
    hist[d]++;
  }
  const cut = Math.max(24, otsu(hist, n));
  const ink = new Uint8Array(n);
  let peak = 0;
  for (let i = 0; i < n; i++) {
    ink[i] = dist[i] > cut ? 1 : 0;
    peak = Math.max(peak, dist[i]);
  }
  const strong = (cut + peak) / 2;
  const core = new Uint8Array(n);
  for (let i = 0; i < n; i++) core[i] = dist[i] > strong ? 1 : 0;
  return { w, h, ink, core, box: inkBoxOf(ink, w, h, { x: 0, y: 0, w, h }) };
}

/** Rank `faces` by how closely each sets `text` the way the reference's ink
 * shows it, best first. A text with line breaks is scored line by line
 * against the reference's rows of ink, which have to number the same. */
export async function rankFaces(
  ref: InkMask,
  text: string,
  faces: TitleFace[],
  fontStack: (font: string) => string
): Promise<FaceMatch[]> {
  if (!ref.box) throw new Error("No type stands out from its ground in that region.");
  const lines = text.split("\n").map((l) => l.trim()).filter(Boolean);
  if (lines.length === 0) throw new Error("Pass the words the region shows.");
  const bands = bandsOf(ref, ref.box, lines.length);
  if (bands.length !== lines.length)
    throw new Error(
      `The region holds ${lines_(bands.length)} of ink and the text has ${lines_(lines.length)}. Pass the text with a line break where the type breaks, or a region around one line.`
    );

  // The reference lines on their grids, once.
  const refs = bands.map((b) => {
    const cols = gridCols(b);
    return { box: b, cols, grid: soften(gridOf(ref.ink, ref.w, b, cols), cols) };
  });
  const widest = Math.max(...bands.map((b) => b.w));

  const inkWidth = bands.reduce((sum, b) => sum + b.w, 0);

  // Each face sets every line; a line counts by how wide its ink runs.
  const probe = new Probe();
  const ranked: FaceMatch[] = [];
  try {
    for (const face of faces) {
      const css = `${face.italic ? "italic " : ""}${face.weight} ${PROBE_PX}px ${fontStack(face.font)}`;
      await ensureFontLoaded(css, lines.join(" "));
      let score = 0;
      let tracking = 0;
      let typePx = 0;
      for (let i = 0; i < lines.length; i++) {
        const m = fitLine(probe, css, lines[i], refs[i]);
        score += (m.score * refs[i].box.w) / inkWidth;
        if (refs[i].box.w === widest) tracking = m.tracking;
        if (i === 0 && m.inkPerPx > 0) typePx = refs[0].box.h / m.inkPerPx;
      }
      ranked.push({ ...face, score: Math.round(score * 1000) / 1000, tracking: Math.round(tracking * 1000) / 1000, typePx });
    }
  } finally {
    probe.close();
  }
  return ranked.sort((a, b) => b.score - a.score);
}

/** How far a title's ink centre sits from the point it is set at, px, the
 * type upright: each line centred on x and stacked about y, its baseline
 * under the line's middle by the face's em box, as the kit draws it. Caps
 * stand above that baseline, and a browser counts tracking after the last
 * letter, so the ink is off the point; a title set at the reference ink's
 * centre less this lands on it. */
export async function inkOffset(
  face: TitleFace,
  px: number,
  tracking: number,
  text: string,
  fontStack: (font: string) => string
): Promise<{ dx: number; dy: number } | null> {
  const lines = text.split("\n");
  const css = `${face.italic ? "italic " : ""}${face.weight} ${px}px ${fontStack(face.font)}`;
  await ensureFontLoaded(css, text);
  const lineH = px * LINE_HEIGHT;
  const w = Math.ceil(px * (Math.max(...lines.map((l) => [...l].length)) * (1.4 + Math.max(0, tracking)) + 2));
  const h = Math.ceil(lineH * lines.length + px * 2);
  const canvas = createRasterCanvas(w, h);
  try {
    const ctx = canvas.getContext("2d") as CanvasRenderingContext2D | null;
    if (!ctx) return null;
    ctx.font = css;
    if ("letterSpacing" in ctx) ctx.letterSpacing = `${tracking * px}px`;
    ctx.fillStyle = "#ffffff";
    ctx.textAlign = "center";
    ctx.textBaseline = "alphabetic";
    const drop = baselineDrop(ctx, px, faceEmAscent(css));
    lines.forEach((line, i) => ctx.fillText(line, w / 2, h / 2 - (lineH * lines.length) / 2 + lineH * (i + 0.5) + drop));
    const data = ctx.getImageData(0, 0, w, h).data;
    const ink = new Uint8Array(w * h);
    for (let i = 0; i < ink.length; i++) ink[i] = data[i * 4 + 3] > 127 ? 1 : 0;
    const box = inkBoxOf(ink, w, h, { x: 0, y: 0, w, h });
    return box ? { dx: box.x + box.w / 2 - w / 2, dy: box.y + box.h / 2 - h / 2 } : null;
  } finally {
    canvas.width = 0;
  }
}

/** One line set in one face against one reference line: tracking solved
 * from the width its ink runs at tracking 0. */
function fitLine(
  probe: Probe,
  css: string,
  line: string,
  ref: { box: InkBox; cols: number; grid: Float32Array }
): { score: number; tracking: number; inkPerPx: number } {
  const flat = probe.set(css, line, 0);
  if (!flat) return { score: 0, tracking: 0, inkPerPx: 0 };

  // Letter spacing adds a step between each pair of characters.
  // Example: ink 600 wide and 60 tall against a reference 12:1 wants
  // 720, so 11 gaps at 64px take 120/704 ≈ 0.17em.
  const gaps = [...line].length - 1;
  const aspect = ref.box.w / ref.box.h;
  const wanted = gaps > 0 && probe.tracks ? (aspect * flat.box.h - flat.box.w) / (gaps * PROBE_PX) : 0;
  const tracking = Math.max(LETTER_SPACING_MIN, Math.min(LETTER_SPACING_MAX, wanted));
  const set = Math.abs(tracking) > 0.005 ? (probe.set(css, line, tracking) ?? flat) : flat;

  const grid = gridOf(set.ink, set.w, set.box, ref.cols);
  const own = set.box.w / set.box.h;
  const widthAgree = Math.min(own, aspect) / Math.max(own, aspect);
  return { score: softIou(ref.grid, soften(grid, ref.cols)) * widthAgree, tracking: set === flat ? 0 : tracking, inkPerPx: flat.box.h / PROBE_PX };
}

/** "1 line", "2 lines". */
const lines_ = (n: number) => `${n} line${n === 1 ? "" : "s"}`;

/** The canvas candidates are set on, grown to the widest line asked for and
 * released when the ranking ends. */
class Probe {
  private canvas: RasterSurface | null = null;
  private ctx: CanvasRenderingContext2D | null = null;
  /** Whether this surface spaces letters; without it every face sets at 0. */
  tracks = false;

  set(css: string, line: string, tracking: number): (InkMask & { box: InkBox }) | null {
    const w = Math.ceil(PROBE_PX * ([...line].length * (1.4 + Math.max(0, tracking)) + 2));
    const h = PROBE_PX * 2;
    if (!this.canvas || this.canvas.width < w) {
      this.canvas = createRasterCanvas(w, h);
      this.ctx = this.canvas.getContext("2d") as CanvasRenderingContext2D | null;
      this.tracks = Boolean(this.ctx && "letterSpacing" in this.ctx);
    }
    const ctx = this.ctx;
    if (!ctx) throw new Error("No 2D context to set type on.");
    const cw = this.canvas.width;
    ctx.clearRect(0, 0, cw, h);
    ctx.font = css;
    if (this.tracks) ctx.letterSpacing = `${tracking * PROBE_PX}px`;
    ctx.fillStyle = "#ffffff";
    ctx.textBaseline = "middle";
    ctx.textAlign = "left";
    ctx.fillText(line, PROBE_PX / 2, h / 2);

    const data = ctx.getImageData(0, 0, cw, h).data;
    const ink = new Uint8Array(cw * h);
    for (let i = 0; i < ink.length; i++) ink[i] = data[i * 4 + 3] > 127 ? 1 : 0;
    const box = inkBoxOf(ink, cw, h, { x: 0, y: 0, w: cw, h });
    return box ? { w: cw, h, ink, box } : null;
  }

  close(): void {
    if (this.canvas) {
      this.canvas.width = 0;
      this.canvas.height = 0;
    }
    this.canvas = null;
    this.ctx = null;
  }
}

/** The median colour of a crop's outermost pixels. */
function borderMedian(data: Uint8ClampedArray, w: number, h: number): [number, number, number] {
  const r: number[] = [];
  const g: number[] = [];
  const b: number[] = [];
  const take = (x: number, y: number) => {
    const i = (y * w + x) * 4;
    r.push(data[i]);
    g.push(data[i + 1]);
    b.push(data[i + 2]);
  };
  for (let x = 0; x < w; x++) {
    take(x, 0);
    take(x, h - 1);
  }
  for (let y = 1; y < h - 1; y++) {
    take(0, y);
    take(w - 1, y);
  }
  const mid = (v: number[]) => v.sort((p, q) => p - q)[v.length >> 1];
  return [mid(r), mid(g), mid(b)];
}

/** The threshold that best splits a 256-bin histogram in two (Otsu). */
function otsu(hist: Float64Array, total: number): number {
  let sum = 0;
  for (let i = 0; i < 256; i++) sum += i * hist[i];
  let sumB = 0;
  let wB = 0;
  let best = 0;
  let cut = 0;
  for (let t = 0; t < 256; t++) {
    wB += hist[t];
    if (wB === 0) continue;
    const wF = total - wB;
    if (wF === 0) break;
    sumB += t * hist[t];
    const between = wB * wF * (sumB / wB - (sum - sumB) / wF) ** 2;
    if (between > best) {
      best = between;
      cut = t;
    }
  }
  return cut;
}

/** The box the ink inside `within` fills, specks left out. */
function inkBoxOf(ink: Uint8Array, w: number, h: number, within: InkBox): InkBox | null {
  const rows = new Float64Array(within.h);
  const cols = new Float64Array(within.w);
  for (let y = 0; y < within.h; y++) {
    const off = (within.y + y) * w + within.x;
    for (let x = 0; x < within.w; x++) {
      if (ink[off + x]) {
        rows[y]++;
        cols[x]++;
      }
    }
  }
  const span = (v: Float64Array) => {
    const floor = Math.max(1, Math.max(...v) * SPECK);
    let a = 0;
    while (a < v.length && v[a] < floor) a++;
    let b = v.length - 1;
    while (b > a && v[b] < floor) b--;
    return a < v.length ? [a, b] : null;
  };
  const ys = span(rows);
  const xs = span(cols);
  if (!ys || !xs) return null;
  return { x: within.x + xs[0], y: within.y + ys[0], w: xs[1] - xs[0] + 1, h: ys[1] - ys[0] + 1 };
}

/** The rows of ink inside a box, split where a run of empty rows parts them.
 * Short of the `lines` the text has, the tallest band is split again where
 * its stroke cores part: small type set tight, softened by a video, runs its
 * lines together with no clear row between them. */
function bandsOf(ref: InkMask, box: InkBox, lines: number): InkBox[] {
  const bands = rowBands(ref, box);
  while (bands.length < lines) {
    const tallest = bands.reduce((a, b) => (b.h > a.h ? b : a));
    const parts = splitAtCores(ref, tallest, lines - bands.length + 1);
    if (parts.length < 2) break;
    bands.splice(bands.indexOf(tallest), 1, ...parts);
  }
  return bands;
}

/** A band cut into `parts` lines at the rows its stroke cores leave nearly
 * empty, one near each even split; whole when a split finds no such row. */
function splitAtCores(ref: InkMask, band: InkBox, parts: number): InkBox[] {
  if (!ref.core) return [band];
  const rows: number[] = [];
  for (let y = 0; y < band.h; y++) {
    let n = 0;
    const off = (band.y + y) * ref.w + band.x;
    for (let x = 0; x < band.w; x++) n += ref.core[off + x];
    rows.push(n);
  }
  const typical = [...rows].sort((a, b) => a - b)[Math.floor(rows.length * 0.75)];
  const reach = band.h / (2 * parts);
  const cuts: number[] = [];
  for (let i = 1; i < parts; i++) {
    const mid = (band.h * i) / parts;
    let best = -1;
    for (let y = Math.max(1, Math.ceil(mid - reach)); y < Math.min(band.h - 1, mid + reach); y++) {
      if (best < 0 || rows[y] < rows[best]) best = y;
    }
    if (best < 0 || rows[best] > typical * VALLEY) return [band];
    cuts.push(best);
  }
  const edges = [0, ...cuts, band.h];
  const out: InkBox[] = [];
  for (let i = 0; i + 1 < edges.length; i++) {
    const piece = inkBoxOf(ref.ink, ref.w, ref.h, { x: band.x, y: band.y + edges[i], w: band.w, h: edges[i + 1] - edges[i] });
    if (piece) out.push(piece);
  }
  return out.length === parts ? out : [band];
}

/** The rows of ink inside a box where a run of empty rows parts them. */
function rowBands(ref: InkMask, box: InkBox): InkBox[] {
  const rows: number[] = [];
  for (let y = 0; y < box.h; y++) {
    let n = 0;
    const off = (box.y + y) * ref.w + box.x;
    for (let x = 0; x < box.w; x++) n += ref.ink[off + x];
    rows.push(n);
  }
  const floor = Math.max(1, Math.max(...rows) * SPECK);
  const bands: InkBox[] = [];
  let start = -1;
  for (let y = 0; y <= rows.length; y++) {
    const on = y < rows.length && rows[y] >= floor;
    if (on && start < 0) start = y;
    if (!on && start >= 0) {
      const band = inkBoxOf(ref.ink, ref.w, ref.h, { x: box.x, y: box.y + start, w: box.w, h: y - start });
      if (band) bands.push(band);
      start = -1;
    }
  }
  // A sliver of a band is a descender or an accent that broke loose.
  const tallest = Math.max(...bands.map((b) => b.h));
  return bands.filter((b) => b.h >= tallest * 0.25);
}

/** Grid columns for a box: its shape at GRID_ROWS rows. */
const gridCols = (b: InkBox) => Math.max(4, Math.min(640, Math.round((GRID_ROWS * b.w) / b.h)));

/** A box of ink averaged onto a GRID_ROWS × cols grid, each cell the share
 * of ink in the stretch of the box it covers. */
function gridOf(ink: Uint8Array, w: number, box: InkBox, cols: number): Float32Array {
  const grid = new Float32Array(GRID_ROWS * cols);
  const edge = (i: number, n: number, of: number) => Math.floor((i * of) / n);
  for (let gy = 0; gy < GRID_ROWS; gy++) {
    const y0 = edge(gy, GRID_ROWS, box.h);
    const y1 = Math.max(y0 + 1, edge(gy + 1, GRID_ROWS, box.h));
    for (let gx = 0; gx < cols; gx++) {
      const x0 = edge(gx, cols, box.w);
      const x1 = Math.max(x0 + 1, edge(gx + 1, cols, box.w));
      let sum = 0;
      for (let y = y0; y < y1; y++) {
        const off = (box.y + y) * w + box.x;
        for (let x = x0; x < x1; x++) sum += ink[off + x];
      }
      grid[gy * cols + gx] = sum / ((y1 - y0) * (x1 - x0));
    }
  }
  return grid;
}

/** A grid with each cell averaged with its neighbours, so ink a cell off
 * still overlaps. */
function soften(grid: Float32Array, cols: number): Float32Array {
  const out = new Float32Array(grid.length);
  for (let y = 0; y < GRID_ROWS; y++) {
    for (let x = 0; x < cols; x++) {
      let sum = 0;
      let n = 0;
      for (let dy = -1; dy <= 1; dy++) {
        for (let dx = -1; dx <= 1; dx++) {
          const yy = y + dy;
          const xx = x + dx;
          if (yy < 0 || yy >= GRID_ROWS || xx < 0 || xx >= cols) continue;
          sum += grid[yy * cols + xx];
          n++;
        }
      }
      out[y * cols + x] = sum / n;
    }
  }
  return out;
}

/** Overlap of two soft masks: Σmin / Σmax. */
function softIou(a: Float32Array, b: Float32Array): number {
  let lo = 0;
  let hi = 0;
  for (let i = 0; i < a.length; i++) {
    lo += Math.min(a[i], b[i]);
    hi += Math.max(a[i], b[i]);
  }
  return hi > 0 ? lo / hi : 0;
}