"use client";
/*
* What colours a page is actually made of, taken from a picture of it.
*
* Reading a stylesheet would answer a different question. A site declares
* dozens of colours and paints with a handful; a screenshot is the handful,
* weighted by how much of the screen each one covers, which is what anyone
* looking at the page actually experiences.
*
* Median cut is the quantiser, because it is the one whose failure mode is
* honest. K-means would give prettier centroids and would also invent them:
* an average of two colours that both appear is a third colour that does not.
* Median cut only ever splits the set of colours that are really there, so
* every swatch below is a real pixel's neighbourhood rather than a compromise
* between two.
*/
export type Swatch = {
r: number;
g: number;
b: number;
hex: string;
/** Oklch, which is the space worth arguing in • see below. */
l: number;
c: number;
h: number;
/** How much of the screen this box covered, 0 to 1. */
share: number;
};
const channel = (value: number) => value.toString(16).padStart(2, "0");
export function hex(r: number, g: number, b: number) {
return `#${channel(r)}${channel(g)}${channel(b)}`;
}
/** sRGB's transfer function, undone. Everything below wants light, not bytes. */
function linear(value: number) {
const v = value / 255;
return v <= 0.04045 ? v / 12.92 : ((v + 0.055) / 1.055) ** 2.4;
}
/*
* Oklch, and not HSL.
*
* HSL's lightness is a number about the encoding rather than about the colour:
* a saturated yellow and a saturated blue at L=50% are nowhere near as bright
* as each other, so a palette sorted by HSL lightness is sorted by nothing.
* Oklab was fitted to perceived lightness, so its L can be compared across
* hues, and the polar form gives a chroma that says how colourful something is
* without also saying how light it is.
*
* The matrices are the standard ones: sRGB to LMS, a cube root, and LMS to Lab.
*/
export function toOklch(r: number, g: number, b: number) {
const lr = linear(r);
const lg = linear(g);
const lb = linear(b);
const l = 0.4122214708 * lr + 0.5363325363 * lg + 0.0514459929 * lb;
const m = 0.2119034982 * lr + 0.6806995451 * lg + 0.1073969566 * lb;
const s = 0.0883024619 * lr + 0.2817188376 * lg + 0.6299787005 * lb;
const l_ = Math.cbrt(l);
const m_ = Math.cbrt(m);
const s_ = Math.cbrt(s);
const L = 0.2104542553 * l_ + 0.793617785 * m_ - 0.0040720468 * s_;
const A = 1.9779984951 * l_ - 2.428592205 * m_ + 0.4505937099 * s_;
const B = 0.0259040371 * l_ + 0.7827717662 * m_ - 0.808675766 * s_;
const C = Math.sqrt(A * A + B * B);
let H = (Math.atan2(B, A) * 180) / Math.PI;
if (H < 0) H += 360;
return { l: L, c: C, h: H };
}
export function formatOklch({ l, c, h }: { l: number; c: number; h: number }) {
return `oklch(${(l * 100).toFixed(1)}% ${c.toFixed(3)} ${h.toFixed(1)})`;
}
/** Relative luminance, the WCAG definition • linear light, weighted by the eye. */
export function luminance(r: number, g: number, b: number) {
return 0.2126 * linear(r) + 0.7152 * linear(g) + 0.0722 * linear(b);
}
/** The ratio the guidelines are written in: 21 at most, 1 for a colour on itself. */
export function contrast(a: Swatch, b: Swatch) {
const one = luminance(a.r, a.g, a.b);
const two = luminance(b.r, b.g, b.b);
const light = Math.max(one, two);
const dark = Math.min(one, two);
return (light + 0.05) / (dark + 0.05);
}
/*
* Every pixel, as three numbers, from a canvas that has already been drawn.
*
* Fully transparent pixels are dropped rather than counted as black • a
* screenshot has none, but a dropped PNG might be mostly nothing, and a palette
* whose largest swatch is the colour of "no colour at all" is a bug that looks
* like a result.
*/
export function samples(image: ImageData, stride = 1) {
const out: number[] = [];
const step = Math.max(1, Math.round(stride)) * 4;
for (let i = 0; i < image.data.length; i += step) {
if (image.data[i + 3] < 250) continue;
out.push(image.data[i], image.data[i + 1], image.data[i + 2]);
}
return out;
}
type Box = { from: number; to: number };
/** The widest axis of a box, in the only three dimensions a pixel has. */
function widest(pixels: number[], box: Box) {
const low = [255, 255, 255];
const high = [0, 0, 0];
for (let i = box.from; i < box.to; i += 3) {
for (let axis = 0; axis < 3; axis++) {
const value = pixels[i + axis];
if (value < low[axis]) low[axis] = value;
if (value > high[axis]) high[axis] = value;
}
}
const spread = [high[0] - low[0], high[1] - low[1], high[2] - low[2]];
let axis = 0;
if (spread[1] > spread[axis]) axis = 1;
if (spread[2] > spread[axis]) axis = 2;
return { axis, spread: spread[axis] };
}
/**
* Median cut.
*
* Put every pixel in one box. Repeatedly take the box with the widest spread in
* any one channel, sort it along that channel, and split it at its median • so
* each half holds the same *number* of pixels rather than the same volume of
* colour space. That is the whole idea, and it is why the result follows what a
* picture is mostly made of rather than what corner of the cube it strays into:
* an accent used on one button never gets a box of its own until the boxes for
* everything else have been split to death.
*/
export function palette(pixels: number[], count: number): Swatch[] {
if (pixels.length === 0) return [];
const total = pixels.length / 3;
const boxes: Box[] = [{ from: 0, to: pixels.length }];
while (boxes.length < count) {
let chosen = -1;
let best = 0;
for (let i = 0; i < boxes.length; i++) {
// A box of one pixel cannot be split, whatever its spread says.
if (boxes[i].to - boxes[i].from <= 3) continue;
const { spread } = widest(pixels, boxes[i]);
if (spread > best) {
best = spread;
chosen = i;
}
}
// Every remaining box is a single colour. Asking for more swatches than the
// picture contains is not an error, it just stops here.
if (chosen < 0 || best === 0) break;
const box = boxes[chosen];
const { axis } = widest(pixels, box);
/* Sorting three-number records held flat in one array: pull them out, sort,
write them back. The alternative is an array of small arrays, which at a
hundred thousand pixels is a hundred thousand allocations. */
const run: number[][] = [];
for (let i = box.from; i < box.to; i += 3) {
run.push([pixels[i], pixels[i + 1], pixels[i + 2]]);
}
run.sort((a, b) => a[axis] - b[axis]);
for (let i = 0; i < run.length; i++) {
pixels[box.from + i * 3] = run[i][0];
pixels[box.from + i * 3 + 1] = run[i][1];
pixels[box.from + i * 3 + 2] = run[i][2];
}
const middle = box.from + Math.floor(run.length / 2) * 3;
boxes.splice(
chosen,
1,
{ from: box.from, to: middle },
{ from: middle, to: box.to },
);
}
return boxes
.map((box) => {
let r = 0;
let g = 0;
let b = 0;
const size = (box.to - box.from) / 3;
for (let i = box.from; i < box.to; i += 3) {
r += pixels[i];
g += pixels[i + 1];
b += pixels[i + 2];
}
r = Math.round(r / size);
g = Math.round(g / size);
b = Math.round(b / size);
return {
r,
g,
b,
hex: hex(r, g, b),
...toOklch(r, g, b),
share: size / total,
};
})
.sort((a, b) => b.share - a.share);
}
/*
* How many of these are the same colour wearing a different hat.
*
* Two swatches a couple of units apart in Oklab are a difference nobody can
* see, and a page that ships six of them has six greys where it meant to have
* two. The threshold is in Oklab distance rather than in hex digits, because
* hex distance is not a measure of anything: #101010 and #1a1a1a are further
* apart in the file than #ff0000 and #ff2200 are, and the eye disagrees.
*/
export function nearDuplicates(swatches: Swatch[], limit = 0.045) {
const pairs: { a: Swatch; b: Swatch; distance: number }[] = [];
for (let i = 0; i < swatches.length; i++) {
for (let j = i + 1; j < swatches.length; j++) {
const one = swatches[i];
const two = swatches[j];
// In Lab, not LCh: the polar form's hue is meaningless at low chroma, so
// two near-greys would read as far apart for turning slightly.
const dl = one.l - two.l;
const da =
one.c * Math.cos((one.h * Math.PI) / 180) -
two.c * Math.cos((two.h * Math.PI) / 180);
const db =
one.c * Math.sin((one.h * Math.PI) / 180) -
two.c * Math.sin((two.h * Math.PI) / 180);
const distance = Math.sqrt(dl * dl + da * da + db * db);
if (distance < limit) pairs.push({ a: one, b: two, distance });
}
}
return pairs.sort((one, two) => one.distance - two.distance);
}