31:T885,{ const ctx = DOM.context2d(w, h, 1); Object.assign(ctx.canvas.style, {width: w * (2 ** zoom) + 'px', imageRendering: 'pixelated'}); ctx.putImageData(initialImgData, 0, 0); if (animate) yield ctx.canvas; // treat pixel colors as 32-bit integers for easier manipulation const imgData = ctx.getImageData(0, 0, w, h); const data = new Uint32Array(imgData.data.buffer); // initialize a grid that keeps track of the closest data point for each pixel const closest = new Uint32Array(w * h).fill(65535); // init data points as closest to themselves for (let i = 0; i < closest.length; i++) if (data[i]) closest[i] = i; let numUpdates = 0; // starting flood step is the half of the grid size's closest power of two const maxStep = 2 ** (Math.ceil(Math.log2(Math.max(w, h))) - 1); if (preflood) yield* pass(1); // an optional 1-step pass that increases precision for (let step = maxStep; step >= 1; step >>= 1) { yield* pass(step); // run passes at e.g. 512, 256, 128, ..., 1 } ctx.putImageData(imgData, 0, 0); yield ctx.canvas; function* pass(step) { for (let y = 0; y < h; y++) { for (let x = 0; x < w; x++) { // propagate the closest point & corresponding color from 8 directions const k = y * w + x; let bestSeed = -1; for (let i = -1, bestDist = Infinity; i <= 1; i++) { for (let j = -1; j <= 1; j++) { const y0 = y + i * step; const x0 = x + j * step; const m = y0 * w + x0; if (!data[m] || x0 < 0 || x0 >= w || y0 < 0 || y0 >= h) continue; // skip empty pixels const seed = closest[m]; const d = (x - seed % w) ** 2 + (y - seed / w | 0) ** 2; if (d < bestDist) { // found a closer point bestDist = d; bestSeed = seed; } } } if (bestSeed === -1) continue; closest[k] = bestSeed; data[k] = data[bestSeed]; const newFrame = animate && ++numUpdates % (viewof iterationsPerFrame).value === 0; if (newFrame) { ctx.putImageData(imgData, 0, 0); yield ctx.canvas; } } } } }32:[] 2f:{"title":"Discrete Voronoi with Jump Flooding","cells":[{"id":0,"value":"# Discrete Voronoi with Jump Flooding\n\n[Jump Flooding](https://en.wikipedia.org/wiki/Jump_flooding_algorithm) (JFA) is a fast algorithm for computing Voronoi diagrams and distance transforms on a grid of data. Because it's highly parallelizable, it's designed to run on the GPU, like in [this awesome notebook by Ricky](https://observablehq.com/@rreusser/gpu-voronoi-diagrams-using-the-jump-flooding-algorithm), or [this one by Claudio](https://observablehq.com/@esperanc/jump-flooding). \n\nHowever, a WebGL-based implementation can be quite involved. So, for learning purposes, I made this very minimal 30-line version that runs on the CPU with a 2D canvas. You can see how passes unfold, and how the results compare between JFA and 1+JFA variants of the algorithm.","pinned":false,"hidden":false,"mode":"md"},{"id":331,"value":"viewof numPoints = Inputs.range([10, 1000], {label: \"Number of points\", step: 10, value: 500})","pinned":false,"hidden":false,"mode":"ojs"},{"id":647,"value":"viewof zoom = Inputs.range([1, 4], {label: \"Zoom\", step: 1, value: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":646,"value":"viewof iterationsPerFrame = {\n const max = ((w * h) / 15) | 0;\n return Inputs.range([1, max], {\n label: \"Iterations per frame\",\n value: max,\n step: 1,\n transform: Math.log2\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":394,"value":"viewof animate = {\n const input = html``;\n const label = html`${input} animate`;\n const button = html``;\n const div = html`${label} ${button}`;\n input.oninput = () => {\n div.value = input.checked;\n button.disabled = !input.checked;\n }\n div.value = input.checked;\n button.onclick = () => div.dispatchEvent(new CustomEvent('input'));\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":261,"value":"viewof preflood = {\n const input = html``;\n const label = html`${input} additional pass (1+JFA — slower but more precise)`;\n input.oninput = () => { label.value = input.checked; };\n label.value = input.checked;\n return label;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":635,"value":"## Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":343,"value":"initialImgData = { // create a canvas with a bunch of points\n const ctx = DOM.context2d(w, h, 1); \n for (let i = 0; i < numPoints; i++) {\n ctx.fillStyle = '#' + (Math.random() * 0xFFFFFF | 0).toString(16); // random color\n ctx.fillRect(Math.random() * w | 0, Math.random() * h | 0, 1, 1); // random position\n }\n return ctx.getImageData(0, 0, w, h);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":348,"value":"w = width >> zoom","pinned":true,"hidden":false,"mode":"ojs"},{"id":643,"value":"h = 400 >> zoom","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}