Tinkering with code and algorithms for fun
// decouple resolution (stipples per area) from ink density (stipple radius)
class Stippling {
constructor(densityGrid, resolutionGrid, minRadius, maxRadius) {
this.densityGrid = densityGrid;
this.resolutionGrid = resolutionGrid;
// assumes widh and height are the same for both grids
this.width = resolutionGrid.width;
this.height = resolutionGrid.height;
this.densityGridExtent = d3.extent(densityGrid.values);
this.resolutionGridExtent = d3.extent(resolutionGrid.values);
this.radiusExtent = [minRadius, maxRadius];
this.resolutionDensityToRadius = d3
.scaleLinear()
.domain(this.resolutionGridExtent)
.range([minRadius, maxRadius]);
this.threshold = 0.4;
this.delta_threshold = 0.01;
// we initialize the algorithm with random stipples - 1 per 25x25 pixels
this.stipples = this.random_stipples(this.width*this.height / 625 | 0);
}
// generates `num` random stipples on top of the grid.
random_stipples(num) {
const stipples = []
const xran = d3.randomUniform(0, this.width);
const yran = d3.randomUniform(0, this.height);
for (var i = 0; i < num; ++i) {
stipples[i] = [
xran(), // x
yran(), // y
// d3.Delaunay only cares about the first two
// values as coordinates and ignores the rest,
// so we can safely store all other data in the
// array. This is slightly faster than adding
// properties dynamically.
this.radiusExtent[0], // radius
0, // radiusDensity
0, // resolutionDensity
0, // moment10
0, // moment01d
0, // moment11
0, // moment20
0, // moment02
];
}
return stipples;
}
// performs one iteration of the LBG stippling algorithm
iterate() {
const delaunay = d3.Delaunay.from(this.stipples),
voronoi = delaunay.voronoi([0, 0, this.width, this.height]);
// initialize densities
for(let i = 0; i < this.stipples.length; i++) {
const st = this.stipples[i];
st[3] = 0; // radiusDensity
st[4] = 0; // resolutionDensity aka moment00
st[5] = 0; // moment10
st[6] = 0; // moment01
st[7] = 0; // moment11
st[8] = 0; // moment20
st[9] = 0; // moment02
}
// compute the density and the weighted centroid of each cell
var found = 0;
for(let y = 0, {stipples, width} = this, dValues = this.densityGrid.values, rValues = this.resolutionGrid.values; y < this.height; y++) {
const line = y * width;
for(let x = 0; x < width; x++) {
found = delaunay.find(x, y, found);
const st = stipples[found];
const densityVal = dValues[x + line];
const resolutionVal = rValues[x + line];
const xval = x*resolutionVal;
const yval = y*resolutionVal;
st[3] += densityVal; // radiusDensity
st[4] += resolutionVal; // resolutionDensity aka moment00
st[5] += xval; // moment10
st[6] += yval; // moment01
st[7] += x * yval; // moment11
st[8] += x * xval; // moment20
st[9] += y * yval; // moment02
}
}
const {
resolutionDensityToRadius,
} = this;
const resolutionGridMax = this.resolutionGridExtent[1];
let deleted = 0;
let splitted = 0
const newStipples = [];
const {abs, atan2, cos, min, sin, sqrt, PI } = Math;
for (let i = 0; i < this.stipples.length; i++) {
const polygon = voronoi.cellPolygon(i);
if (!polygon) continue;
const st = this.stipples[i];
const density = st[4]; // resolutionDensity aka moment00
// determine point size based on average intensity
const area = abs(d3.polygonArea(polygon));
const avgDensity = area ? density / area : 0;
const resolutionRadius = resolutionDensityToRadius(avgDensity);
const resolutionArea = PI * resolutionRadius * resolutionRadius * resolutionGridMax;
const splitThreshold = (1.0 + this.threshold / 2.0) * resolutionArea;
const deleteThreshold = (1.0 - this.threshold / 2.0) * resolutionArea;
const renderRadius = sqrt(st[3]) / 16; // radiusDensity
if (density < deleteThreshold) {
deleted++;
} else if (density > splitThreshold) {
// Split
splitted++;
const centroid = d3.polygonCentroid(polygon);
const cx = centroid[0];
const cy = centroid[1];
const dist = sqrt(area / PI) / 2.0;
const x = st[8] / density - cx * cx; // moment20
const y = 2 * (st[7] / density - cx * cy); // moment11
const z = st[9] / density - cy * cy; // moment02
var orientation = atan2(y, x - z) / 2.0;
var deltaX = dist * cos(orientation);
var deltaY = dist * sin(orientation);
st[0] = cx + deltaX;
st[1] = cy + deltaY;
st[2] = renderRadius;
// re-use arrays to reduce GC pressure
centroid[0] -= deltaX;
centroid[1] -= deltaY;
centroid.push(
renderRadius,
0, // radiusDensity
0, // resolutionDensity
0, // moment10
0, // moment01
0, // moment11
0, // moment20
0, // moment02
);
newStipples.push(st, centroid);
} else {
// Relax
st[0] = st[5] / density; // moment10
st[1] = st[6] / density; //moment01
st[2] = renderRadius;
newStipples.push(st);
}
}
// we increase the threshold with each iteration for faster convergence
this.threshold = min(1, this.threshold + this.delta_threshold);
this.stipples = newStipples;
// is done?
return splitted + deleted === 0;
}
// Performs plain Voronoi relaxation (can be used to "clean up" LBG stippling that doesn't converge)
relax() {
const delaunay = d3.Delaunay.from(this.stipples),
voronoi = delaunay.voronoi([0, 0, this.width, this.height]);
// initialize densities
for(let i = 0; i < this.stipples.length; i++) {
const st = this.stipples[i];
st[3] = 0; // radiusDensity
st[4] = 0; // resolutionDensity aka moment00
st[5] = 0; // moment10
st[6] = 0; // moment01
}
// compute the density and the weighted centroid of each cell
var found = 0;
for(let y = 0, {stipples, width} = this, dValues = this.densityGrid.values, rValues = this.resolutionGrid.values; y < this.height; y++) {
const line = y * width;
for(let x = 0; x < width; x++) {
found = delaunay.find(x, y, found);
const st = stipples[found];
const densityVal = dValues[x + line];
const resolutionVal = rValues[x + line];
const xval = x*resolutionVal;
const yval = y*resolutionVal;
st[3] += densityVal; // radiusDensity
st[4] += resolutionVal; // resolutionDensity aka moment00
st[5] += xval; // moment10
st[6] += yval; // moment01
}
}
const {abs, sqrt} = Math;
for (let i = 0; i < this.stipples.length; i++) {
const polygon = voronoi.cellPolygon(i);
if (!polygon) continue;
const st = this.stipples[i];
// determine point size based on average intensity
const renderRadius = sqrt(st[3]) / 16; // radiusDensity
// Relax
const density = st[4]
st[0] = st[5] / density; // moment10
st[1] = st[6] / density; // moment01
st[3] = renderRadius;
}
}
}
initGrids(options.sobelFactor, options.blurRadius, +options.channel, options.invert, imgData.data, imgData.width, imgData.height)
messageHandler = {
// stub, just for workerscript
let grid, gridSobel, w, h, stippling;
function postMessage(foo){}
return function onmessage(event) {
const {
data: {
imgData,
width,
height,
minRadius,
maxRadius,
sobelFactor,
maxIterations,
totalRelaxations,
channel,
showProgress,
invert,
blurRadius,
}
} = event;
w = width;
h = height;
[grid, gridSobel] = initGrids(sobelFactor, blurRadius, channel, invert, imgData, width, height);
postMessage({grid, gridSobel});
stippling = new Stippling(grid, gridSobel, minRadius, maxRadius)
for(let i = 1, done = false; i <= maxIterations; i++) {
if (!done) {
done = stippling.iterate();
} else {
stippling.relax();
}
let message = i < maxIterations || totalRelaxations > 0 ?
`Rendering - iteration ${i}/${maxIterations},` : "Done!";
message += ` ${stippling.stipples.length} points`
if (showProgress || i%10 === 0 || i == maxIterations) {
const points = new Float64Array(stippling.stipples.length * 3);
for(let j = 0, {stipples} = stippling; j < stipples.length; j++) {
const st = stipples[j];
const idx = j*3;
points[idx] = st[0];
points[idx+1] = st[1];
points[idx+2] = st[2]; // radius
}
postMessage({message, points}, [points.buffer]);
} else {
postMessage({message});
}
}
for(let i = 1; i <= totalRelaxations; i++) {
stippling.relax();
let message = !showProgress || i < totalRelaxations ?
`Rendering - relaxation ${i}/${totalRelaxations},` : "Done!";
message += ` ${stippling.stipples.length} points`
if (showProgress || i%40 === 0 || i == totalRelaxations) {
const points = new Float64Array(stippling.stipples.length * 3);
for(let j = 0, {stipples} = stippling; j < stipples.length; j++) {
const st = stipples[j];
const idx = j*3;
points[idx] = st[0];
points[idx+1] = st[1];
points[idx+2] = st[2]; // radius
}
postMessage({message, points}, [points.buffer]);
} else {
postMessage({message});
}
}
// Pass final result if we didn't pass the previous renders
if (!showProgress) {
const points = new Float64Array(stippling.stipples.length * 3);
for(let j = 0, {stipples} = stippling; j < stipples.length; j++) {
const st = stipples[j];
const idx = j*3;
points[idx] = st[0];
points[idx+1] = st[1];
points[idx+2] = st[2]; // radius
}
postMessage({message: `Done! ${stippling.stipples.length} points`, points}, [points.buffer]);
}
};
}
workerScript = {
const script = `
importScripts("${await require.resolve("d3@5")}", "${await require.resolve("d3-delaunay@5")}");
${Stippling.toString()}
${initGrids.toString()}
${toSobel.toString()}
${gaussianBlurTwoPass.toString()}
${bellcurvish1D.toString()}
let grid, gridSobel, w, h, stippling;
onmessage = ${messageHandler.toString()}
`;
const blob = new Blob([script], {type: 'text/javascript'});
const url = URL.createObjectURL(blob);
invalidation.then(() => {
URL.revokeObjectURL(url);
});
return url;
}
startWorker = {
let worker;
invalidation.then(() => {
if (worker) worker.terminate();
})
return (settings) => {
// end previous worker session
if (worker) worker.terminate();
worker = new Worker(workerScript);
const messaged = (e) => {
if (e.data.points) {
mutable points = e.data.points;
}
mutable iterationMessage = e.data.message;
};
worker.onmessage = messaged;
// Initial render
worker.postMessage(settings);
return "worker initiated"
};
}
startWorker(defaultSettings)
defaultSettings = {
await obamaData;
return {
imgData: obamaData.data,
width: obamaData.width,
height: obamaData.height,
showProgress: true,
invert: false,
channel: "0",
minRadius: 0.25,
maxRadius: 2,
sobelFactor: 0,
blurRadius: 0,
inkDensity: 0.6,
maxIterations: 30,
totalRelaxations: 50
};
}
mutable iterationMessage = "Awaiting first iteration"
d3 = require("d3@5", "d3-delaunay@5");
obama = {
const obama = await FileAttachment("obama.png").image();
return obama;
}
obamaData = {
const width = obama.naturalWidth || obama.width;
const height = obama.naturalHeight || obama.height
const context = DOM.context2d(width, height, 1);
context.drawImage(obama, 0, 0, width, height);
return context.getImageData(0, 0, width, height);
}
im = {
if (fileImg.length) {
let img = new Image();
img.src = await Files.url(fileImg[0]);
return img;
} else return obama;
}
import {file} from "@jashkenas/inputs"
serialize = {
const xmlns = "http://www.w3.org/2000/xmlns/";
const xlinkns = "http://www.w3.org/1999/xlink";
const svgns = "http://www.w3.org/2000/svg";
return function serialize(svg) {
svg = svg.cloneNode(true);
const fragment = window.location.href + "#";
const walker = document.createTreeWalker(svg, NodeFilter.SHOW_ELEMENT, null, false);
while (walker.nextNode()) {
for (const attr of walker.currentNode.attributes) {
if (attr.value.includes(fragment)) {
attr.value = attr.value.replace(fragment, "#");
}
}
}
svg.setAttributeNS(xmlns, "xmlns", svgns);
svg.setAttributeNS(xmlns, "xmlns:xlink", xlinkns);
const serializer = new window.XMLSerializer;
const string = serializer.serializeToString(svg);
return new Blob([string], {type: "image/svg+xml"});
};
}
function svgOutput(points) {
const svgPoints = [];
const {round} = Math;
for(let i = 0; i < points.length; i += 3) {
// let's limit the subpixel precision, yeah?
const x = round(points[i] * 100) / 100;
const y = round(points[i+1] * 100) / 100;
const radius = round(points[i+2] * 100) / 100;
svgPoints.push([x, y, radius]);
}
const svg = d3.select(DOM.svg(im.naturalWidth || im.width, im.naturalHeight || im.height));
svg.append("g")
.append("rect")
.attr("x", 0)
.attr("y", 0)
.attr("width", im.naturalWidth || im.width)
.attr("height", im.naturalHeight || im.height)
.attr("fill", optionsInvert.invert ? "black" : "white");
svg.append("g")
.attr("fill", optionsInvert.invert ? "white" : "black")
.selectAll("circle")
.data(svgPoints)
.join("circle")
.attr("r", d => d[2] * inkDensity.inkDensity)
.attr("cx", d => d[0])
.attr("cy", d => d[1])
// convert to serialized SVG
const xmlns = "http://www.w3.org/2000/xmlns/";
const xlinkns = "http://www.w3.org/1999/xlink";
const svgns = "http://www.w3.org/2000/svg";
const fragment = window.location.href + "#";
const svgNode = svg.node();
const walker = document.createTreeWalker(svgNode, NodeFilter.SHOW_ELEMENT, null, false);
while (walker.nextNode()) {
for (const attr of walker.currentNode.attributes) {
if (attr.value.includes(fragment)) {
attr.value = attr.value.replace(fragment, "#");
}
}
}
svgNode.setAttributeNS(xmlns, "xmlns", svgns);
svgNode.setAttributeNS(xmlns, "xmlns:xlink", xlinkns);
const serializer = new window.XMLSerializer;
const string = serializer.serializeToString(svgNode);
return new Blob([string], {type: "image/svg+xml"});
}
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.
