Open source CapCut alternative.
TypeScript
/** 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);
});
}