31:T5ec,canvasWN = { const canvas = document.createElement("canvas"); const scale = 1; // window.devicePixelRatio; const w = 2 ** Math.floor(Math.log2(width)) * scale; const h = w; const imageScale = Math.min(image.naturalWidth / w, image.naturalHeight / h); canvas.width = w; canvas.height = h; canvas.style = `background: white; max-width: 100%; width: ${ w / scale }px; height: auto; image-rendering: pixelated;`; yield canvas; await visibility(); const context = canvas.getContext("2d"); context.drawImage(image, 0, 0, w * imageScale, h * imageScale, 0, 0, w, h); const sourceData = context.getImageData(0, 0, w, h); const targetData = context.createImageData(w, h); const maxFrames = 40; const frameIndices = []; let frameIdx = 0; for (let i = 0; i < mutable framesWN.length; i++) frameIndices[i] = i; do { if (mutable framesWN.length < maxFrames) { frameIndices.push(mutable framesWN.length); mutable framesWN.push( createWNframe(w, h, imageScale, scale, sourceData, targetData) ); mutable framesWN = mutable framesWN; } const idx = frameIndices[frameIdx]; // Fisher-Yates but spread out over the loop const i = (Math.random() * frameIdx) | 0; const t = frameIndices[i]; frameIndices[i] = idx; frameIndices[frameIdx] = t; frameIdx = (frameIdx + 1) % frameIndices.length; context.putImageData(mutable framesWN[idx], 0, 0); yield context.canvas; await visibility(); } while (animateWN); }32:T6b4,canvasPQT = { const canvas = document.createElement("canvas"); const scale = 1; // window.devicePixelRatio; const w = 2 ** Math.floor(Math.log2(width)) * scale; const h = w; const imageScale = Math.min(image.naturalWidth / w, image.naturalHeight / h); canvas.width = w; canvas.height = h; canvas.style = `background: white; max-width: 100%; width: ${ w / scale }px; height: auto; image-rendering: pixelated;`; const context = canvas.getContext("2d"); // Yield early so the notebook height doesn't jump around while scroling yield canvas; await visibility(); context.drawImage(image, 0, 0, w * imageScale, h * imageScale, 0, 0, w, h); const sourceData = context.getImageData(0, 0, w, h); const targetData = context.createImageData(w, h); const pqt = new PachinkoQuadTree(Math.log2(w)); const totalPixels = w * h; const maxFrames = 40; const frameIndices = []; let frameIdx = 0; for (let i = 0; i < mutable framesPQT.length; i++) frameIndices[i] = i; do { if (mutable framesPQT.length < maxFrames) { frameIndices.push(mutable framesPQT.length); mutable framesPQT.push( createPQTframe( pqt, w, h, imageScale, scale, totalPixels, sourceData, targetData ) ); mutable framesPQT = mutable framesPQT; } const idx = frameIndices[frameIdx]; const i = (Math.random() * frameIdx) | 0; const t = frameIndices[i]; frameIndices[i] = idx; frameIndices[frameIdx] = t; frameIdx = (frameIdx + 1) % frameIndices.length; context.putImageData(mutable framesPQT[idx], 0, 0); yield context.canvas; } while (animateQT); }33:T15d4,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; }34:[{"id":"304856f48b47766b7ca03faa6463ecb354a6e6c255714c1aacf683b30eb9022a995e56a73d981eeea1dbb79db3d49f9fabaadebd5731b1b8a4281c71d0f33792","href":"https://static.observableusercontent.com/files/304856f48b47766b7ca03faa6463ecb354a6e6c255714c1aacf683b30eb9022a995e56a73d981eeea1dbb79db3d49f9fabaadebd5731b1b8a4281c71d0f33792","name":"ricardo-gomez-angel-9AdeEdYB2yk-unsplash.jpg","type":"image/jpeg","lastModified":1641217074467.777,"size":2506481}] 2f:{"title":"White Noise vs Pachinko Tree Dithering","cells":[{"id":0,"value":"# White Noise vs Pachinko Tree Dithering\n\nA quick remix of Mike Bostock's *[Genuary 2022 / 2](https://observablehq.com/@mbostock/genuary-2022-2)* entry to demonstrate the differences in dithering quality when using white noise vs the noise distribution of a pachinko quadtree. Sadly the latter is too slow to animate (at least as implemented in JavaScript)\n\n*Addendum:* With some helpful suggestions from Fabian a limited form of animation is now supported: we render forty frames, then reuse them (shuffling the order every forty frames). So if you turn on the animations below it may start out choppy, but after the initial frames have rendered the animations should be smooth.\n\n\nPhoto by Ricardo Gomez Angel / Unsplash.","pinned":false,"hidden":false,"mode":"md"},{"id":239,"value":"

\n\n## White Noise","pinned":false,"hidden":false,"mode":"md"},{"id":297,"value":"viewof animateWN = Inputs.toggle({\n label: \"Animate white noise dithering\",\n value: false\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":197,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":249,"value":"

\n\n## Pachinko QuadTree (2D)","pinned":false,"hidden":false,"mode":"md"},{"id":304,"value":"viewof animateQT = Inputs.toggle({\n label: \"Animate PQT dithering\",\n value: false\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":225,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":386,"value":"mutable framesWN = {\n width;\n return [];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":391,"value":"function createWNframe(width, height, imageScale, scale, sourceData, d) {\n const targetData = new ImageData(d.data.slice(), width);\n for (let i = 0, n = sourceData.data.length; i < n; i += 4) {\n const pixel = sourceData.data[i] < Math.random() * 256 ? 0 : 255;\n targetData.data[i] = pixel;\n targetData.data[i + 1] = pixel;\n targetData.data[i + 2] = pixel;\n targetData.data[i + 3] = 255;\n }\n return targetData;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":347,"value":"mutable framesPQT = {\n width;\n return [];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":350,"value":"function createPQTframe(\n pqt,\n width,\n height,\n imageScale,\n scale,\n totalPixels,\n sourceData,\n d\n) {\n const targetData = new ImageData(d.data.slice(), width);\n for (let i = 0; i < totalPixels; i++) {\n const val = (i * 256) / totalPixels;\n const [x, y] = pqt.insert(val);\n const j = (x + y * width) << 2;\n const pixel = sourceData.data[j] < val ? 0 : 255;\n targetData.data[j] = pixel;\n targetData.data[j + 1] = pixel;\n targetData.data[j + 2] = pixel;\n targetData.data[j + 3] = 255;\n }\n return targetData;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":212,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":6,"value":"image = FileAttachment(\"ricardo-gomez-angel-9AdeEdYB2yk-unsplash.jpg\").image({width: 64})","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}