Skip to content

Open source CapCut alternative.

TypeScript
22.5 KB
Raw Blame
/** Measurements of a source's own pixels at source seconds — the numbers a
 * replica is built from: every hard cut to its frame, the colour of a region,
 * and the box an element fills frame by frame with the ease of each move.
 * Frames come through the same base-rendering sink the watch and the colour
 * reads use, so a log or HDR source measures as the preview shows it. */

import { baseFrameSink, colorReadAt } from "../baseFrame";
import { openMedia, UnreadableMediaError, videoTrackOf, type FrameSize } from "../mediaRead";
import { createRasterCanvas, decodeRasterImageUrl } from "../raster";
import type { WrappedCanvas } from "mediabunny";
import { CAMERA_LONG_SIDE, cameraPath, grayOf, holdsStill, type CameraPose, type Gray } from "./camera";
import { hexOf, regionColor, regionStripes, parseHex, type PixelRect, type Pixels, type Rgb, type Stripes } from "./color";
import { frameStep, gridsOf, pickShotEdges, type FrameGrids, type FrameStep, type PictureFade, type ShotChange } from "./cuts";
import { fitMoves, type Move } from "./easeFit";
import { FULL_FRAME, areaOf, findPictureBox, intoArea, type PictureFind } from "./picture";
import { inkBox, shapeBox } from "./track";
import { readLetters, type LetterFrame, type LetterRead } from "./letters";

/** A box as the editor places one: centre and size, frame fractions. */
export interface FrameBox {
  x: number;
  y: number;
  w: number;
  h: number;
}

/** Every frame of a cut scan is this small: 128² holds the 32-grid a word
 * appearing is read on at four pixels a cell, and the 16-grid a cut is. */
const SCAN_SIZE: FrameSize = { width: 128, height: 128, fit: "fill" };
/** Long side colours are read at: a 1080p source's own pixels. */
const COLOR_LONG_SIDE = 1920;
/** Long side elements are tracked at: a pixel is 0.14% of the frame. */
const TRACK_LONG_SIDE = 720;
/** Reads a pass back off by this much so the frame on `from` is scored. */
const LEAD_S = 0.001;
/** A time handed back to the millisecond sits up to half of one either side
 * of the frame start it names, so a frame ending that close past `from` is
 * the one before it. */
const HALF_MS = 0.0005;
/** Long side the picture box is found at: a pixel is 0.16% of the frame. */
const PICTURE_LONG_SIDE = 640;
/** Frames sampled across a source to find its picture. */
const PICTURE_SAMPLES = 48;

/** An open video source: its display size, first timestamp and frame reads. */
interface SourceVideo {
  width: number;
  height: number;
  first: number;
  frames(from: number, to: number, size: FrameSize): AsyncGenerator<SourceFrame>;
  framesAt(times: number[], size: FrameSize): AsyncGenerator<SourceFrame | null>;
}

interface SourceFrame extends Pixels {
  t: number;
  duration: number;
}

function pixelsOf(w: WrappedCanvas): SourceFrame {
  const canvas = w.canvas;
  const ctx = canvas.getContext("2d") as CanvasRenderingContext2D | null;
  if (!ctx) throw new Error("Could not read the frame's pixels.");
  const image = ctx.getImageData(0, 0, canvas.width, canvas.height);
  return { data: image.data, width: image.width, height: image.height, t: w.timestamp, duration: w.duration };
}

/** Open `url`'s video track for the length of `fn`, closing it after. */
async function withSourceVideo<T>(url: string, fn: (v: SourceVideo) => Promise<T>): Promise<T> {
  const input = openMedia(url);
  try {
    const track = await videoTrackOf(input);
    if (!track) throw new UnreadableMediaError("This file has no readable video.");
    const reading = colorReadAt(url);
    const width = await track.getDisplayWidth();
    const height = await track.getDisplayHeight();
    const first = await track.getFirstTimestamp().catch(() => 0);
    return await fn({
      width,
      height,
      first,
      frames: async function* (from, to, size) {
        // A small pool: each frame is read and dropped before the next.
        for await (const w of baseFrameSink(track, size, reading, { poolSize: 2 }).canvases(from, to)) yield pixelsOf(w);
      },
      framesAt: async function* (times, size) {
        for await (const w of baseFrameSink(track, size, reading).canvasesAtTimestamps(times)) yield w ? pixelsOf(w) : null;
      },
    });
  } finally {
    input.dispose();
  }
}

/** A picture's pixels at `longSide`, for a still asset. */
async function imagePixels(url: string, longSide: number): Promise<Pixels> {
  const img = await decodeRasterImageUrl(url);
  if (!img || !img.width || !img.height) throw new Error("Could not read the image.");
  const k = Math.min(1, longSide / Math.max(img.width, img.height));
  const w = Math.max(1, Math.round(img.width * k));
  const h = Math.max(1, Math.round(img.height * k));
  const canvas = createRasterCanvas(w, h);
  const ctx = canvas.getContext("2d") as CanvasRenderingContext2D | null;
  if (!ctx) throw new Error("Could not read the image.");
  ctx.drawImage(img.source, 0, 0, w, h);
  const image = ctx.getImageData(0, 0, w, h);
  return { data: image.data, width: w, height: h };
}

/** The read size for a source whose `area` is `longSide` on its long side,
 * never past its own pixels. */
function sizeAt(width: number, height: number, longSide: number, area: FrameBox = FULL_FRAME): FrameSize {
  const k = Math.min(1, longSide / Math.max(width * area.w, height * area.h, 1));
  return { width: Math.max(1, Math.round(width * k)), height: Math.max(1, Math.round(height * k)), fit: "fill" };
}

/** The pixels of `px` inside `r`, as a picture of their own. */
function cropPixels(px: Pixels, r: PixelRect): Pixels {
  const x0 = Math.max(0, Math.min(px.width - 1, Math.round(r.x)));
  const y0 = Math.max(0, Math.min(px.height - 1, Math.round(r.y)));
  const w = Math.max(1, Math.min(px.width - x0, Math.round(r.w)));
  const h = Math.max(1, Math.min(px.height - y0, Math.round(r.h)));
  const data = new Uint8ClampedArray(w * h * 4);
  for (let y = 0; y < h; y++) {
    const from = ((y0 + y) * px.width + x0) * 4;
    data.set(px.data.subarray(from, from + w * 4), y * w * 4);
  }
  return { data, width: w, height: h };
}

/** A centre-and-size box in frame fractions, as pixels of `px`. */
const toPixels = (px: Pixels, b: FrameBox): PixelRect => ({
  x: (b.x - b.w / 2) * px.width,
  y: (b.y - b.h / 2) * px.height,
  w: Math.max(1, b.w * px.width),
  h: Math.max(1, b.h * px.height),
});

/** A pixel box as centre-and-size frame fractions. */
const toFrame = (px: { width: number; height: number }, r: PixelRect): FrameBox => ({
  x: (r.x + r.w / 2) / px.width,
  y: (r.y + r.h / 2) / px.height,
  w: r.w / px.width,
  h: r.h / px.height,
});

/** The frame rate a run of decoded frames plays at: the median frame
 * duration, or the median gap between timestamps when durations are absent. */
function rateOf(times: number[], durations: number[]): number {
  const steps = durations.filter((d) => d > 0);
  const gaps = steps.length > 0 ? steps : times.slice(1).map((t, i) => t - times[i]).filter((d) => d > 0);
  if (gaps.length === 0) return 0;
  gaps.sort((a, b) => a - b);
  return 1 / gaps[Math.floor(gaps.length / 2)];
}

export interface CutScan {
  fps: number;
  frames: number;
  cuts: { t: number; frame: number; change: number }[];
  /** Changes inside the shots: a word or a shape coming, going or swapping
   * style over a picture that stays. */
  changes: (Omit<ShotChange, "frame"> & { t: number; frame: number })[];
  /** The whole picture fading into black or white or out of it: from `t`
   * for `seconds` along `ease`. */
  fades: (Omit<PictureFade, "frame" | "frames"> & { t: number; frame: number; seconds: number })[];
  coveredTo: number;
  truncated: boolean;
}

/** Every hard cut in [from, to) of a video, found by scoring every frame
 * against the one before it. A pass stops at `maxCuts` or at the time
 * budget, and `coveredTo` says where the next pass picks up. */
export async function scanCuts(
  url: string,
  opts: { from: number; to: number; maxCuts: number; maxChanges: number; budgetMs: number; area?: FrameBox }
): Promise<CutScan> {
  return withSourceVideo(url, async (v) => {
    // Inside a picture box, the frame is read big enough that the box alone
    // is the scan's size: a change that fills the picture fills the grid.
    const area = opts.area ?? FULL_FRAME;
    const size: FrameSize = {
      width: Math.min(v.width, Math.round(SCAN_SIZE.width! / area.w)),
      height: Math.min(v.height, Math.round(SCAN_SIZE.height! / area.h)),
      fit: "fill",
    };
    const deadline = Date.now() + opts.budgetMs;
    const times: number[] = [];
    const durations: number[] = [];
    const steps: FrameStep[] = [];
    // Each frame's fine grid, rounded to bytes, for the changes too gradual
    // for one frame to show.
    const fines: Uint8Array[] = [];
    let prev: FrameGrids | null = null;
    let outOfTime = false;
    for await (const f of v.frames(Math.max(0, opts.from - LEAD_S), opts.to, size)) {
      if (Date.now() > deadline) {
        outOfTime = true;
        break;
      }
      const grid = gridsOf(opts.area ? cropPixels(f, toPixels(f, area)) : f);
      steps.push(prev ? frameStep(prev, grid) : { pct: NaN, faint: NaN, fine: NaN, box: null });
      fines.push(Uint8Array.from(grid.fine, Math.round));
      times.push(f.t);
      durations.push(f.duration);
      prev = grid;
    }
    if (times.length === 0) throw new Error("Could not read any frames in that span.");

    const fps = rateOf(times, durations);
    const { cuts: picked, changes: found, fades } = pickShotEdges(steps, fines);

    // A capped pass ends on the frame before the first cut or change it
    // leaves out, so the next pass scores that one against it.
    const firstLeftOut = Math.min(
      picked.length > opts.maxCuts ? picked[opts.maxCuts] : Infinity,
      found.length > opts.maxChanges ? found[opts.maxChanges].frame : Infinity
    );
    const capped = Number.isFinite(firstLeftOut);
    const coveredTo = capped ? times[firstLeftOut - 1] : outOfTime ? times[times.length - 1] : opts.to;
    const frameOf = (i: number) => (fps > 0 ? Math.round((times[i] - v.first) * fps) : i);
    return {
      fps,
      frames: times.length,
      cuts: picked
        .filter((i) => i < firstLeftOut)
        .map((i) => ({
          t: times[i],
          frame: frameOf(i),
          change: Math.round(steps[i].pct),
        })),
      changes: found
        .filter((c) => c.frame < firstLeftOut)
        .map((c) => ({ ...c, t: times[c.frame], frame: frameOf(c.frame), change: Math.round(c.change * 10) / 10 })),
      // A fade starts between frames: its time runs on from the frame before.
      fades: fades
        .filter((f) => f.frame < firstLeftOut)
        .map(({ frame, frames, ...f }) => {
          const i = Math.max(0, Math.min(times.length - 1, Math.floor(frame)));
          const step = fps > 0 ? 1 / fps : 0;
          return { ...f, t: times[i] + (frame - i) * step, frame: frameOf(i), seconds: frames * step };
        }),
      coveredTo,
      truncated: capped || outOfTime,
    };
  });
}

/** A source's picture at second `t`: the frame inside `area`, read at about
 * `longSide` on that area's long side, as the preview shows it — what a grade
 * is matched to. */
export async function sourcePictureAt(url: string, t: number, area: FrameBox = FULL_FRAME, longSide = 192): Promise<Pixels> {
  return withSourceVideo(url, async (v) => {
    const size = sizeAt(v.width, v.height, longSide, area);
    for await (const f of v.framesAt([t], size)) {
      if (f) return cropPixels(f, toPixels(f, area));
    }
    throw new Error(`Could not read the frame at ${t}s.`);
  });
}

export interface ColorSample {
  t: number;
  box: FrameBox;
}

export type ColorRead = ReturnType<typeof regionColor> & { stripes?: Stripes };

/** The colour of each sample's region at its moment, read in one ordered
 * pass over the source. `k` ≥ 2 adds the k colours each region is made of;
 * a region laid in parallel lines adds its `stripes`, in px at 1080 of the
 * area's short side. */
export async function sampleColors(
  url: string,
  kind: "video" | "image",
  samples: ColorSample[],
  k: number,
  area: FrameBox = FULL_FRAME
): Promise<ColorRead[]> {
  // Each sample's box is in the area's fractions; the reads are the frame's.
  samples = samples.map((s) => ({ ...s, box: intoArea(area, s.box) }));
  const read = (px: Pixels, box: FrameBox): ColorRead => {
    const rect = toPixels(px, box);
    const stripes = regionStripes(px, rect, 1080 / Math.min(area.w * px.width, area.h * px.height));
    return { ...regionColor(px, rect, k), ...(stripes ? { stripes } : {}) };
  };
  if (kind === "image") {
    const px = await imagePixels(url, COLOR_LONG_SIDE);
    return samples.map((s) => read(px, s.box));
  }
  const times = [...new Set(samples.map((s) => s.t))].sort((a, b) => a - b);
  return withSourceVideo(url, async (v) => {
    const size = sizeAt(v.width, v.height, COLOR_LONG_SIDE, area);
    const out = new Array<ColorRead>(samples.length);
    let at = 0;
    for await (const f of v.framesAt(times, size)) {
      const t = times[at++];
      if (!f) throw new Error(`Could not read the frame at ${t}s.`);
      samples.forEach((s, i) => {
        if (s.t === t) out[i] = read(f, s.box);
      });
    }
    return out;
  });
}

export type TrackMatch = "shape" | "ink";

export interface TrackRun {
  color: string;
  fps: number;
  /** Per frame read: its time and the element's box, or null where absent. */
  boxes: { t: number; box: FrameBox | null }[];
  moves: (Move & { prop: keyof FrameBox })[];
  coveredTo: number;
  truncated: boolean;
}

/** The box an element fills in every frame of [from, to) — one frame at
 * `from` when `to` is absent — and the moves of its centre and size, each
 * fitted with an ease. The element is the piece of `color` the seed points
 * at ("shape"), or every pixel of it inside the seed ("ink"); with no colour
 * the seed's own median colour on the first frame is the element's. */
export async function trackElement(
  url: string,
  kind: "video" | "image",
  opts: {
    from: number;
    to?: number;
    seed: FrameBox;
    within?: FrameBox;
    color?: string;
    tolerance: number;
    match: TrackMatch;
    maxFrames: number;
    /** The picture box the seed, within and every box out are fractions of. */
    area?: FrameBox;
  }
): Promise<TrackRun> {
  const area = opts.area ?? FULL_FRAME;
  let truncated = false;
  let coveredTo = opts.to ?? opts.from;

  // The element's box in each frame, carried forward as the next one's seed.
  let target: Rgb | null = opts.color ? parseHex(opts.color) : null;
  let near: PixelRect | null = null;
  const boxes: TrackRun["boxes"] = [];
  const read = (t: number, px: Pixels) => {
    const seed = toPixels(px, intoArea(area, opts.seed));
    if (!target) target = parseHex(regionColor(px, seed).hex)!;
    const look = opts.within ? toPixels(px, intoArea(area, opts.within)) : opts.match === "ink" ? seed : toPixels(px, area);
    const found =
      opts.match === "ink"
        ? inkBox(px, target, opts.tolerance, look)
        : (shapeBox(px, target, opts.tolerance, look, near ?? seed) ??
          (near ? shapeBox(px, target, opts.tolerance, look, seed) : null));
    if (found) near = found;
    boxes.push({ t, box: found ? areaOf(area, toFrame(px, found)) : null });
  };

  let size = { width: 1, height: 1 };
  const times: number[] = [];
  const durations: number[] = [];
  if (kind === "image") {
    const px = await imagePixels(url, TRACK_LONG_SIDE);
    size = px;
    read(0, px);
  } else {
    await withSourceVideo(url, async (v) => {
      const at = sizeAt(v.width, v.height, TRACK_LONG_SIDE, area);
      size = { width: at.width!, height: at.height! };
      if (opts.to === undefined || opts.to <= opts.from) {
        for await (const f of v.framesAt([opts.from], at)) {
          if (!f) throw new Error(`Could not read the frame at ${opts.from}s.`);
          read(opts.from, f);
        }
        return;
      }
      for await (const f of v.frames(opts.from, opts.to, at)) {
        if (times.length >= opts.maxFrames) {
          truncated = true;
          coveredTo = times[times.length - 1];
          break;
        }
        times.push(f.t);
        durations.push(f.duration);
        read(f.t, f);
      }
    });
  }

  // Each of the four numbers fitted on its own: a grow moves w and h, a
  // slide moves x or y, and one fit per number keys each the way it moved.
  const moves: TrackRun["moves"] = [];
  if (boxes.length > 2) {
    const ts = boxes.map((b) => b.t);
    for (const prop of ["x", "y", "w", "h"] as const) {
      const step = 1 / (prop === "x" || prop === "w" ? size.width * area.w : size.height * area.h);
      for (const m of fitMoves(ts, boxes.map((b) => (b.box ? b.box[prop] : null)), step)) moves.push({ ...m, prop });
    }
    moves.sort((a, b) => a.from - b.from);
  }
  const rgb = target as Rgb | null;
  return {
    color: rgb ? hexOf(...rgb) : "",
    fps: rateOf(times, durations),
    boxes,
    moves,
    coveredTo,
    truncated,
  };
}

export interface LetterRun extends Omit<LetterRead, "passes"> {
  color: string;
  fps: number;
  framesRead: number;
  /** Other ink the letters cross on their way in, its box in the area's fractions. */
  passes: (Omit<LetterRead["passes"][number], "box" | "color"> & { color: string; box: FrameBox })[];
  truncated: boolean;
}

/** How the letters of `text` come in over [from, to]: the line sits inside
 * `seed` at `to`, every letter landed. The letters are the seed's dominant
 * colour other than its ground, or `color`. */
export async function trackLetters(
  url: string,
  opts: { from: number; to: number; seed: FrameBox; text: string; color?: string; maxFrames: number; area?: FrameBox }
): Promise<LetterRun> {
  const area = opts.area ?? FULL_FRAME;
  return withSourceVideo(url, async (v) => {
    const at = sizeAt(v.width, v.height, TRACK_LONG_SIDE, area);
    const frames: LetterFrame[] = [];
    const durations: number[] = [];
    let truncated = false;
    const crop = (f: SourceFrame) => cropPixels(f, toPixels(f, area));
    for await (const f of v.frames(opts.from, opts.to, at)) {
      if (frames.length >= opts.maxFrames - 1) {
        truncated = true;
        break;
      }
      frames.push({ ...crop(f), t: f.t });
      durations.push(f.duration);
    }
    // The landed line is read on the frame at `to` itself.
    for await (const f of v.framesAt([opts.to], at)) if (f && (!frames.length || f.t > frames[frames.length - 1].t)) frames.push({ ...crop(f), t: f.t });
    if (frames.length < 3) throw new Error(`Only ${frames.length} frames between ${opts.from}s and ${opts.to}s — give the whole entrance.`);
    const last = frames[frames.length - 1];
    const region = toPixels(last, opts.seed);
    let ink = opts.color ? parseHex(opts.color) : null;
    if (!ink) {
      // The line's colour: the seed's biggest colour other than the picture's ground.
      const ground = regionColor(last, { x: 0, y: 0, w: last.width, h: last.height }).hex;
      const g = parseHex(ground)!;
      const parts = (regionColor(last, region, 3).dominant ?? []).map((d) => ({ ...d, rgb: parseHex(d.hex)! }));
      const far = parts.filter((d) => Math.hypot(d.rgb[0] - g[0], d.rgb[1] - g[1], d.rgb[2] - g[2]) > 60);
      ink = (far.sort((a, b) => b.share - a.share)[0] ?? parts[0])?.rgb ?? null;
    }
    if (!ink) throw new Error("Could not tell the letters' colour — pass color.");
    const read = readLetters(frames, { text: opts.text, region, ink, unit: 1080 / Math.min(last.width, last.height), earliest: 0 });
    return {
      ...read,
      color: hexOf(...ink),
      fps: rateOf(
        frames.map((f) => f.t),
        durations
      ),
      framesRead: frames.length,
      passes: read.passes.map((p) => ({ ...p, color: hexOf(...p.color), box: toFrame(last, p.box) })),
      truncated,
    };
  });
}

export interface CameraRun {
  fps: number;
  /** Per frame read: its time and how the picture sits against the first. */
  path: ({ t: number } & CameraPose)[];
  moves: (Move & { prop: "scale" | "dx" | "dy" | "rotation" })[];
  /** Whether one picture holds under the whole move — a freeze frame — or
   * null when the camera never comes back to a pose to tell by. */
  still: boolean | null;
  coveredTo: number;
  truncated: boolean;
}

/** How the camera moves over [from, to) of a video, inside its picture box:
 * each frame's zoom, shift and turn against the frame on `from`, and the
 * moves of each fitted with an ease. */
export async function trackCamera(
  url: string,
  opts: { from: number; to: number; maxFrames: number; area?: FrameBox }
): Promise<CameraRun> {
  const area = opts.area ?? FULL_FRAME;
  let truncated = false;
  let coveredTo = opts.to;
  const times: number[] = [];
  const durations: number[] = [];
  const frames: Gray[] = [];
  await withSourceVideo(url, async (v) => {
    const at = sizeAt(v.width, v.height, CAMERA_LONG_SIDE, area);
    for await (const f of v.frames(Math.max(0, opts.from - LEAD_S), opts.to, at)) {
      // The shot before a cut would anchor every pose to the wrong picture.
      if (f.t + f.duration <= opts.from + HALF_MS) continue;
      if (frames.length >= opts.maxFrames) {
        truncated = true;
        coveredTo = times[times.length - 1];
        break;
      }
      times.push(f.t);
      durations.push(f.duration);
      frames.push(grayOf(cropPixels(f, toPixels(f, area))));
    }
  });
  const poses = cameraPath(frames);
  const path = poses.map((p, i) => ({ t: times[i], ...p }));
  // A measurement step per number: a fifth of a read pixel, or the zoom or
  // turn that moves the frame's edge that far.
  const moves: CameraRun["moves"] = [];
  if (path.length > 2) {
    const w = frames[0].width;
    const h = frames[0].height;
    const steps = { scale: 0.4 / Math.max(w, h), dx: 0.2 / w, dy: 0.2 / h, rotation: 0.2 };
    for (const prop of ["scale", "dx", "dy", "rotation"] as const) {
      for (const m of fitMoves(times, path.map((p) => p[prop]), steps[prop])) moves.push({ ...m, prop });
    }
    moves.sort((a, b) => a.from - b.from);
  }
  return {
    fps: rateOf(times, durations),
    path,
    moves,
    still: holdsStill(frames, poses),
    coveredTo,
    truncated,
  };
}

/** The box a video's picture fills inside its frame, found from frames
 * sampled evenly over [from, to): the part that changes, apart from bars and
 * an app's chrome around it. Null when too little moves to tell. */
export async function findPicture(url: string, opts: { from: number; to: number }): Promise<PictureFind | null> {
  return withSourceVideo(url, async (v) => {
    const span = Math.max(0, opts.to - opts.from);
    const times = Array.from({ length: PICTURE_SAMPLES }, (_, i) => opts.from + ((i + 0.5) * span) / PICTURE_SAMPLES);
    const frames: Pixels[] = [];
    for await (const f of v.framesAt(times, sizeAt(v.width, v.height, PICTURE_LONG_SIDE))) {
      if (f) frames.push(f);
    }
    return findPictureBox(frames);
  });
}