Tinkering with code and algorithms for fun
function createWNframe(width, height, imageScale, scale, sourceData, d) {
const targetData = new ImageData(d.data.slice(), width);
for (let i = 0, n = sourceData.data.length; i < n; i += 4) {
const pixel = sourceData.data[i] < Math.random() * 256 ? 0 : 255;
targetData.data[i] = pixel;
targetData.data[i + 1] = pixel;
targetData.data[i + 2] = pixel;
targetData.data[i + 3] = 255;
}
return targetData;
}
mutable framesPQT = {
width;
return [];
}
function createPQTframe(
pqt,
width,
height,
imageScale,
scale,
totalPixels,
sourceData,
d
) {
const targetData = new ImageData(d.data.slice(), width);
for (let i = 0; i < totalPixels; i++) {
const val = (i * 256) / totalPixels;
const [x, y] = pqt.insert(val);
const j = (x + y * width) << 2;
const pixel = sourceData.data[j] < val ? 0 : 255;
targetData.data[j] = pixel;
targetData.data[j + 1] = pixel;
targetData.data[j + 2] = pixel;
targetData.data[j + 3] = 255;
}
return targetData;
}
PachinkoQuadTree = {
class PachinkoQuadTree {
constructor(depth, seed) {
this.depth = depth;
let size = 1;
this.offsets = [0];
for (let i = 1; i <= depth; i++) {
this.offsets[i] = size;
size += 4 ** i;
}
// What a node needs to store:
// - 4 bits to keep track of which direction previous
// insertions have fallen towards
// what a leaf needs to store:
// - 32 bits for index (supports a depth of 16, or
// textures up to 65535 × 65535)
// Easiest solution: two separate arrays.
// Note that we could try to be clever and pack two
// 4-bit values in a Uint8Array byte, but this code
// is probably tricky enough to follow as is.
this.pachinkoBitNodes = new Uint8Array(size);
this.valueLeaves = new Uint32Array(4 ** depth);
}
clear() {
this.pachinkoBitNodes.fill(0);
this.valueLeaves.fill(0);
}
idx(x, y, depth) {
return this.offsets[depth] + x + y * 2 ** depth;
}
getBits(x, y, depth) {
return this.pachinkoBitNodes[this.idx(x, y, depth)];
}
setBits(x, y, depth, bits) {
this.pachinkoBitNodes[this.idx(x, y, depth)] = bits;
}
pickChild(x, y, depth) {
const bits = this.getBits(x, y, depth);
// Note that we *branchlessly* pick a random child
const r = ((Math.random() * 12) | 0) * 2;
const picks = this.picks[bits];
const randomPick = (picks >> r) & 0b11;
// Convert the random pick to x and y offsets
const xn = randomPick & 1;
const yn = randomPick >> 1;
x = (x << 1) + xn;
y = (y << 1) + yn;
return [x, y];
}
// Note: does not update the tree! (because we want to
// be able to implement best-candidate approaches)
randomWalk() {
let xy = [0, 0];
let depth = 0;
for (let i = 0; i < this.depth; i++) {
xy = this.pickChild(xy[0], xy[1], depth++);
}
return xy;
}
// Once we have picked our final x,y coordinate, update
// the tree. We need to:
// - update our pachinko array so that every branch that
// was picked has its bitflag set
// - bubble up our x,y coordinate to the top unsaturated
// layer of our coordinateArray (for the sake of finding
// nearest neighbors faster in best-candidate search)
applyPick(x, y, index) {
this.valueLeaves[x + y * 2 ** this.depth] = index;
for (let i = 0; i < this.depth; i++) {
const xi = x >> (this.depth - i);
const yi = y >> (this.depth - i);
const idx = this.idx(xi, yi, i);
// x,y coordinates of picked child of the current node
const xn = x >> (this.depth - 1 - i);
const yn = y >> (this.depth - 1 - i);
// Set the appropriate bitflag in our pachinko array
const pick = 0b1000 >> ((xn & 1) + ((yn & 1) << 1));
const bits = this.pachinkoBitNodes[idx];
const updatedBits = bits | pick;
// if our pachinoArray is full we reset it,
// otherwise write back the updated flags
this.pachinkoBitNodes[idx] = updatedBits === 0b1111 ? 0 : updatedBits;
}
}
insert(val) {
const xy = this.randomWalk();
this.applyPick(xy[0], xy[1], val);
return xy;
}
}
// TODO: change the following to static propertites
// once Observable parser is updated to support it.
const TOP = 0,
BOTTOM = 2,
LEFT = 0,
RIGHT = 1,
TL = TOP + LEFT,
TR = TOP + RIGHT,
BL = BOTTOM + LEFT,
BR = BOTTOM + RIGHT;
// Twelve two-bit (x, y) picks packed into 16 bits in total.
// This way we can always have an unbiased pick of the
// remaining openings.
const packPicks = (...picks) => {
let out = 0;
for (const pick of picks) {
out = (out << 2) + pick;
}
console.log({ picks, out });
return out;
};
const picks = Uint32Array.from([
// outputs , // input flags (i.e. which branches were already picked?)
packPicks(TL, TL, TL, TR, TR, TR, BL, BL, BL, BR, BR, BR), // 0b0000 - none set
packPicks(TL, TL, TL, TL, TR, TR, TR, TR, BL, BL, BL, BL), // 0b0001 - bottom-right
packPicks(TL, TL, TL, TL, TR, TR, TR, TR, BR, BR, BR, BR), // 0b0010 - bottom-left
packPicks(TL, TL, TL, TL, TL, TL, TR, TR, TR, TR, TR, TR), // 0b0011 - bottom
packPicks(TL, TL, TL, TL, BL, BL, BL, BL, BR, BR, BR, BR), // 0b0100 - top-right
packPicks(TL, TL, TL, TL, TL, TL, BL, BL, BL, BL, BL, BL), // 0b0101 - right
packPicks(TL, TL, TL, TL, TL, TL, BR, BR, BR, BR, BR, BR), // 0b0110 - top-right, bottom-left
packPicks(TL, TL, TL, TL, TL, TL, TL, TL, TL, TL, TL, TL), // 0b0111 - everything except top-left
packPicks(TR, TR, TR, TR, BL, BL, BL, BL, BR, BR, BR, BR), // 0b1000 - top-left
packPicks(TR, TR, TR, TR, TR, TR, BL, BL, BL, BL, BL, BL), // 0b1001 - top-left, bottom-right
packPicks(TR, TR, TR, TR, TR, TR, BR, BR, BR, BR, BR, BR), // 0b1010 - left
packPicks(TR, TR, TR, TR, TR, TR, TR, TR, TR, TR, TR, TR), // 0b1011 - everything except top-right
packPicks(BL, BL, BL, BR, BR, BR, BL, BL, BL, BR, BR, BR), // 0b1100 - top
packPicks(BL, BL, BL, BL, BL, BL, BL, BL, BL, BL, BL, BL), // 0b1101 - everything except bottom-left
packPicks(BR, BR, BR, BR, BR, BR, BR, BR, BR, BR, BR, BR) // 0b1110 - everything except bottom-right
]);
Object.assign(PachinkoQuadTree.prototype, {
TOP,
BOTTOM,
LEFT,
RIGHT,
TL,
TR,
BL,
BR,
picks
});
return PachinkoQuadTree;
}
image = FileAttachment("ricardo-gomez-angel-9AdeEdYB2yk-unsplash.jpg").image({width: 64})
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
