Tinkering with code and algorithms for fun
Pseudo-Blue Noise
// This is a *very* inefficient approach,
// but it makes it easier to follow the steps (I hope)
function makeBayerIndex(recursionSteps) {
function split(stride, indices) {
if (stride === 1) return indices;
let topLeft = [],
topRight = [],
bottomLeft = [],
bottomRight = [];
// Divide indices across four sections in Bayer-order
for (let i = 0; i < indices.length; i++) {
const idx = indices[i];
switch (i % 4) {
case 0:
topLeft.push(idx);
continue;
case 1:
bottomRight.push(idx);
continue;
case 2:
topRight.push(idx);
continue;
case 3:
bottomLeft.push(idx);
continue;
}
}
// Recursively subdivide indices in each quadrant
const stride2 = stride / 2;
topLeft = split(stride2, topLeft);
topRight = split(stride2, topRight);
bottomLeft = split(stride2, bottomLeft);
bottomRight = split(stride2, bottomRight);
// Merge back indices. We merge each quadrant row by row
const output = [];
// First the top two quadrants
for (let y = 0; y < stride2; y++) {
const line = y * stride2;
for (let x = 0; x < stride2; x++) {
output.push(topLeft[x + line]);
}
for (let x = 0; x < stride2; x++) {
output.push(topRight[x + line]);
}
}
// Then the bottom quadrants
for (let y = 0; y < stride2; y++) {
const line = y * stride2;
for (let x = 0; x < stride2; x++) {
output.push(bottomLeft[x + line]);
}
for (let x = 0; x < stride2; x++) {
output.push(bottomRight[x + line]);
}
}
return output;
}
const length = 4 ** recursionSteps;
const rootIndices = [];
for (let i = 0; i < length; i++) rootIndices[i] = i;
return split(2 ** recursionSteps, rootIndices);
}
function split1D(length) {
const rootIndices = [];
function splitHalf(indices) {
// split in half
const left = Math.floor(indices.length / 2);
const right = indices.length - left;
let leftIndices = [],
rightIndices = [];
// We use Bresenham line algorithm-style error accumulators
// (in other words: fractions) to decide when to divide an
// index to the left half and when to the right half.
let lNumerator = 0,
rNumerator = 0;
// We make the denominator the *smallest* of the two halves.
// See below for an explanation why
const denominator = right < left ? right : left;
let i = 0;
for (let i = 0; i < indices.length; ) {
// grow our fractions. Because the denominator is the
// smallest of the two, this is effectively ensuring
// that the smaller fraction is equal to "one" every
// loop, and the larger one... well, whatever the
// proportion of large half : small half is
lNumerator += left;
rNumerator += right;
// Now for both fractions we pass on indices to their
// respective half for as long as they are "bigger than one",
// which is guaranteed to be true at least once due to
// using the smallest of the numerators as the denominator).
do {
lNumerator -= denominator;
leftIndices.push(indices[i++]);
} while (lNumerator >= denominator);
do {
rNumerator -= denominator;
rightIndices.push(indices[i++]);
} while (rNumerator >= denominator);
}
// And of course we repeat this proces recursively on both indices
if (leftIndices.length > 2) leftIndices = splitHalf(leftIndices);
if (rightIndices.length > 2) rightIndices = splitHalf(rightIndices);
// copy divided indices back from buffer
return [...leftIndices, ...rightIndices];
}
for (let i = 0; i < length; i++) rootIndices[i] = i;
return splitHalf(rootIndices);
}
function split2D(width, height) {
const { random } = Math;
const flip = () => random() < 0.5;
// Instead of creating new arrays all the time I ping-pong
// between two arrays of large enough size, and use a length
// plus offset to divide indices into smaller parts
function splitHalf(w, h, source, target, offset) {
const left = w >> 1;
const right = w - left;
let lNumerator = 0,
rNumerator = 0;
const denominator = right < left ? right : left;
let i = offset,
j = offset + left * h,
k = offset;
const end = offset + w * h;
while (k < end) {
lNumerator += left;
rNumerator += right;
while (lNumerator >= denominator) {
target[i++] = source[k++];
lNumerator -= denominator;
}
while (rNumerator >= denominator) {
target[j++] = source[k++];
rNumerator -= denominator;
}
}
return left;
}
function divide(x, y, w, h, source, target, offset) {
if (w === 1 && h === 1) {
indices[x + y * width] = source[offset];
} else if (w > h) {
const left = splitHalf(w, h, source, target, offset);
const right = w - left;
// note that we swap the target and source in the recursive call
divide(x, y, left, h, target, source, offset);
divide(x + left, y, right, h, target, source, offset + left * h);
} else {
const top = splitHalf(h, w, source, target, offset);
const bottom = h - top;
divide(x, y, w, top, target, source, offset);
divide(x, y + top, w, bottom, target, source, offset + top * w);
}
}
const indices = new Int32Array(width * height);
// Use a single arraybuffer for better cache locality
// (probably premature optimization, but also harmless)
// See also: https://devdocs.io/javascript/global_objects/typedarray/subarray
const buffer = new Int32Array(width * height * 2);
const source0 = buffer.subarray(0, width * height);
const target0 = buffer.subarray(width * height, width * height * 2);
for (let i = 0; i < width * height; i++) source0[i] = i;
divide(0, 0, width, height, source0, target0, 0);
return indices;
}
function interleavedGradientNoise(x, y) {
// http://www.iryoku.com/next-generation-post-processing-in-call-of-duty-advanced-warfare
// https://bartwronski.com/2016/10/30/dithering-part-three-real-world-2d-quantization-dithering/
const v = 52.9829189 * (0.06711056 * x + 0.00583715 * y);
return v - Math.floor(v);
}
function interleavedGradientNoiseX(x, y) {
const v = 52.9829189 * 0.06711056 * x;
return v - Math.floor(v);
}
function interleavedGradientNoiseY(x, y) {
const v = 52.9829189 * 0.00583715 * y;
return v - Math.floor(v);
}
function interleavedGradientNoiseSmallX(x, y) {
const v = 0.06711056 * x;
return v - Math.floor(v);
}
function interleavedGradientNoiseSmall(x, y) {
const v = 0.06711056 * x + 0.00583715 * y;
return v - Math.floor(v);
}
function interleavedGradientNoiseCustom(x, y) {
const v = constantC * (constantX * x + constantY * y);
return v - Math.floor(v);
}
noise = split2D_v3
noiseMap1D = split1DNoise(width * 100)
function split1DNoise(length) {
const rootIndices = [];
const { random } = Math;
const flip = () => random() < 0.5;
function splitHalf(indices) {
// split in half
let left = Math.floor(indices.length / 2);
let right = indices.length - left;
// randomize which side we round to
if (flip()) [left, right] = [right, left];
let leftIndices = [],
rightIndices = [];
let lNumerator = 0,
rNumerator = 0;
const denominator = right < left ? left : right;
let i = 0;
for (let i = 0; i < indices.length; ) {
lNumerator += left;
rNumerator += right;
if (flip()) {
if (lNumerator >= denominator) {
lNumerator -= denominator;
leftIndices.push(indices[i++]);
}
if (rNumerator >= denominator) {
rNumerator -= denominator;
rightIndices.push(indices[i++]);
}
} else {
if (rNumerator >= denominator) {
rNumerator -= denominator;
rightIndices.push(indices[i++]);
}
if (lNumerator >= denominator) {
lNumerator -= denominator;
leftIndices.push(indices[i++]);
}
}
}
// And of course we repeat this proces recursively on both indices
if (leftIndices.length > 2) leftIndices = splitHalf(leftIndices);
if (rightIndices.length > 2) rightIndices = splitHalf(rightIndices);
// copy divided indices back from buffer
return [...leftIndices, ...rightIndices];
}
for (let i = 0; i < length; i++) rootIndices[i] = i;
return splitHalf(rootIndices);
}
import {render, label, getCtx, toU32Color, toU32Gray} from "@jobleonard/canvas-tools"
import {diff} from "@jobleonard/diff-tool"
showDiff = (left, right, summary, open, opts) =>
summary
? html`<details ${open ? "open" : ""}><summary>${summary}</summary>${diff(
left,
right
)}</details>`
: diff(left, right, opts)
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.