2d:["$","title",null,{"children":"Walk on Spheres — draw me! | Fil | Observable"}] 32:T7af,viewof features = { const svg = d3 .create("svg") .attr("width", width) .attr("viewBox", [0, 0, width, height]); const features = features0; svg.node().value = { type: "FeatureCollection", features }; const path = d3.geoPath(); function clear() { features.splice(0, features.length); draw(); } function draw() { svg .attr("fill", "none") .attr("stroke-width", 2) .selectAll("path") .data(features) .join("path") .attr("fill-opacity", 0.1) .attr("fill", (d) => d.properties.color) .attr("stroke", (d) => d.properties.color) .attr("d", path); svg.node().value.drawing = true; svg.node().dispatchEvent(new CustomEvent("input")); } svg .on("touchmove", (e) => e.preventDefault()) // prevent scrolling .on("pointerenter", () => (svg.dbltap = svg.dbltap || trackDbltap())) .on("pointerup", (e) => { svg.node().value.drawing = false; svg.selectAll("path").remove(); svg.node().dispatchEvent(new CustomEvent("input")); }) .on("pointerdown", (e) => { if (svg.dbltap(e)) return clear(); trackPointer(e, { start: (p) => { const r = (Math.random() * 3) | 0; features.push({ type: "Feature", properties: { color: "white", //d3.hsl(360 * Math.random(), 0.9, 0.7).hex(), left: r / 2, right: ((r + 1) % 3) / 2 }, geometry: { type: "LineString", coordinates: (p.line = []) } }); }, move: (p) => { // save the pressure to the third dimension of the point // though unfortunately geoPath doesn't know how to render variable width lines (yet) // see https://github.com/d3/d3-geo/issues/200 const z = 2 * p.sourceEvent.pressure || 1; p.line.push([...p.point, z]); draw(); } }); }); return svg.node(); }33:T714,dmap = { const distances = Float32Array.from({ length: height * width }).fill( Infinity ), values = Float32Array.from({ length: height * width }).fill(0); yield { distances, values }; if (!segments.length) return; if (features.drawing) return; // Delaunay optimisation: instead of going though all the segments for each pixel, // we start by sampling the segments pixel by pixel, and build a delaunay of these sample points. // Then, to look up the (distance, value) of a pixel, we quickly find the segment with the delaunay. const pts = [], seg = [], sampleSize = 1; // sample every x pixels; for (let n = 0; n < segments.length; n++) { const [[ax, ay], [bx, by]] = segments[n]; const l = Math.hypot(ax - bx, ay - by) / sampleSize, m = Math.ceil(l); for (let i = 0; i <= m; i++) { pts.push([ax + (i / m) * (bx - ax), ay + (i / m) * (by - ay)]); seg.push(n); } } const delaunay = d3.Delaunay.from(pts); let stop = false; invalidation.then(() => (stop = true)); let c = 0; for (let i = 0; i < values.length; i++) { const x = i % width, y = Math.floor(i / width); c = delaunay.find(x, y, c); const n = seg[c]; const s = segments[n]; const d = distanceToSegment(x, y, s[0][0], s[0][1], s[1][0], s[1][1]); values[i] = d > 0 ? s[3] : s[2]; distances[i] = Math.abs(d); if (stop) break; } /* // code without Delaunay optimisation for (let i = 0; i < values.length; i++) { const x = i % width, y = Math.floor(i / width); for (const s of segments) { const d = distanceToSegment(x, y, s[0][0], s[0][1], s[1][0], s[1][1]); if (Math.abs(d) < distances[i]) { values[i] = d > 0 ? s[3] : s[2]; distances[i] = Math.abs(d); } } } */ }34:T493,{ await visibility(); const { floor, ceil } = Math; const context = DOM.context2d(width, height, 2), density = context.canvas.width / width; const data = context.createImageData(width * density, height * density), pixels = data.data; const colors = d3.range(256).map(x => d3.rgb(color(x / 255))); for (let x = 0; x <= width - 1; x += 1 / density) { for (let y = 0; y <= height - 1; y += 1 / density) { const c = colors[ Math.round( (255 * (values[floor(x) + width * floor(y)] + values[ceil(x) + width * ceil(y)])) / 2 ) ]; const i = density * x + density * width * (density * y); pixels[4 * i] = c.r; pixels[4 * i + 1] = c.g; pixels[4 * i + 2] = c.b; pixels[4 * i + 3] = 255; } } context.putImageData(data, 0, 0); yield context.canvas; // cheat to remove aliasing context.lineWidth = 1; for (const s of segments) { context.beginPath(); context.moveTo(...s[0]); context.lineTo(...s[1]); context.strokeStyle = colors[Math.round(255 * Math.max(s[2], s[3]))]; context.stroke(); } }35:[] 30:{"id":"f2ea3d94e6a933be","slug":"walk-on-spheres-draw-me","title":"Walk on Spheres — draw me!","thumbnail":"a60aa975420cde3a5e137315b1f1419afce22bdf07279a30de56752488426b19","access_level":"unlisted","create_time":"$D2020-09-01T06:44:19.145Z","update_time":"$D2026-05-24T01:36:00.254Z","view_time":null,"first_public_time":null,"has_unpublished_edits":null,"fork":{"id":"0ffd70554d6247cb","slug":"wos-segments","title":"Walk on Spheres — segments edition","owner":{"id":"da2a32154638c457","login":"fil","name":"Fil"}},"stars":2,"starred":false,"owner":{"type":"team","id":"da2a32154638c457","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":"starter_2024"},"version":764,"publish_version":764,"role":null,"authored":false,"authors":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}],"members":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Walk on Spheres — draw me!","cells":[{"id":756,"value":"# Walk on Spheres — draw me!\n\nDraw on the rectangle below. Double-click to reset.\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":646,"value":"drawspace = html`

${viewof features}

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":760,"value":"viewof reset = Inputs.button(\"Reset\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"_this version uses [@fil/needle-in-a-haystack](/@fil/needle-in-a-haystack) to find the closest line_\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":743,"value":"import { findOne } with { lines } from \"@fil/needle-in-a-haystack\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":737,"value":"md`\n\n\n_this is quite slow—but it works!_\n\nTo do:\n- UI: add two value selectors (one for left, one for right)\n- UI: add color interpolator selector\n- UI: undo/redo\n- optimize (ex: use workers or GPU to draw)\n- nicer paths (less control points, nice curve)\n- reuse initial state rather than restart?\n- allow any color instead of values from [0,1]\n\n_send suggestions!_\n\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":712,"value":"context = {\n const context = DOM.context2d(width, height, 1);\n d3.select(drawspace)\n .select(\".bgcanvas\")\n .html(\"\")\n .node()\n .appendChild(context.canvas);\n\n return context;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"canvas = {\n if (features.drawing) return;\n\n const data = context.createImageData(width, height),\n pixels = data.data;\n\n const colors = d3.range(256).map(x => d3.rgb(color(x / 255)));\n\n for (let x = 0; x < width; x++) {\n for (let y = 0; y < height; y++) {\n const c = colors[Math.round(255 * values[x + width * y])];\n const i = x + width * y;\n pixels[4 * i] = c.r;\n pixels[4 * i + 1] = c.g;\n pixels[4 * i + 2] = c.b;\n pixels[4 * i + 3] = 255;\n }\n }\n context.putImageData(data, 0, 0);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":665,"value":"features","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":618,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":620,"value":"import { trackPointer, trackDbltap } from \"@fil/pointer-events-svg\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"color = d3.scaleSequential(d3.interpolateInferno).domain([0, 1])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":350,"value":"segments = Array.from(features.features, f => {\n return d3\n .pairs(f.geometry.coordinates)\n .map(([a, b]) => [a, b, f.properties.left, f.properties.right]);\n}).flat(1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":352,"value":"function distanceToSegment(x, y, ax, ay, bx, by) {\n const dx = bx - ax,\n dy = by - ay,\n cross = (x - ax) * dy - (y - ay) * dx,\n dot = (x - ax) * dx + (y - ay) * dy;\n return dot < 0\n ? Math.hypot(x - ax, y - ay)\n : dot > dx * dx + dy * dy\n ? Math.hypot(x - bx, y - by)\n : cross / Math.hypot(dx, dy);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":254,"value":"runs = 10","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":222,"value":"// calls WalkOnSpheres n times for each pixel and returns the average value\nvalues = {\n const values = new Float32Array(width * height);\n if (features.drawing) return yield values;\n\n let stop = false;\n invalidation.then(() => (stop = true));\n\n for (let run = 1; run <= runs; run++) {\n for (let k = 0; k < values.length; k++) {\n values[k] +=\n (walkOnSpheres(k % width, Math.floor(k / width)) - values[k]) / run;\n if (stop) break;\n }\n yield values;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":207,"value":"md`The dmap below is a distance raster: for each pixel, the nearest node and the corresponding distance. Here we use delaunay.find to compute it, so maybe we don't absolutely need to cache its results in a raster—but it could any other algorithm. Having a raster map can also allow us to compute the WoS in the GPU.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":178,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":211,"value":"md`The WoS algorithm applied to a pixel: look up the distance map, jump to a point at that distance in a random direction—return the node information of the last point.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"function walkOnSpheres(x, y, cell) {\n let x0, y0;\n for (let n = 25; n > 0; ) {\n const dist = dmap.distances[x + width * y] * 0.9; // in theory Math.SQRT1_2;\n if (dist < 2) break;\n do {\n const u = random_unit_vector(dist);\n x0 = Math.round(x + u[0]);\n y0 = Math.round(y + u[1]);\n } while (n-- > 0 && !(x0 >= 0 && x0 < width && y0 >= 0 && y0 < height));\n x = x0;\n y = y0;\n }\n return dmap.values[x + width * y] || 0;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"N = 1500","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"height = 400","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":723,"value":"width = 700","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":295,"value":"md`---\nFinally, here’s a higher resolution rendering of the same values:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":293,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":696,"value":"features0 = (reset,\n[\n {\n type: \"Feature\",\n properties: { color: \"white\", left: 1, right: 0 },\n geometry: {\n type: \"LineString\",\n coordinates: [\n [172, 104, 1],\n [276, 131, 1],\n [254, 226, 1],\n [291, 273, 1]\n ]\n }\n }\n])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":745,"value":"// https://observablehq.com/d/12bcf9c57bb17f4d by @jrus\nfunction random_unit_vector(r = 1) {\n const a = 2 * Math.random() - 1,\n b = 1 - a * a,\n t = a * (-0.0187108 * b + 0.31583526 + 1.27365776 / b),\n // slightly more expensive variant with better uniformity:\n // t = a * (((-0.000221184 * b + 0.0024971104) * b - 0.02301937096) * b\n // + 0.3182994604 + 1.2732402998 / b),\n q = r / (1 + t * t);\n return [2 * t * q, (1 - t * t) * q];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 31:"$30:body" 2c:E{"digest":"NEXT_REDIRECT;replace;/@fil/walk-on-spheres-draw-me;307;"}