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.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
);
}
// returns the thresholds for split and delete
thresholds(radius) {
const area = Math.PI * radius * radius;
return [
(1.0 + this.threshold / 2.0) * area,
(1.0 - this.threshold / 2.0) * area
];
}
// 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
0, // "hue density" (I hope this works by averaging :/)
0, // "saturation density"
0 // "lightness density"
];
}
return stipples;
}
// Delaunator freaks out if stipples align too perfectly,
// adding a microscopic amount of sub-pixel noise helps
// with that while also avoiding real consequences for
// the rendering result
jitter() {
return (Math.random() - Math.random()) * 0.00000762939453125;
}
// 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
st[10] = 0; // hue density
st[11] = 0; // saturation density
// st[12] = 0; // lightness density (will be set by radius density)
}
// compute the density and the weighted centroid of each cell
{
const { stipples, width } = this,
dValues = this.densityGrid.values,
rValues = this.resolutionGrid.values,
sValues = this.densityGrid.saturation,
hValues = this.densityGrid.hue;
for (let y = 0, found = 0; 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 idx = x + line;
const densityVal = dValues[idx];
const resolutionVal = rValues[idx];
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
st[10] += hValues[idx]; // hue
st[11] += sValues[idx]; // saturation
}
}
}
const { resolutionDensityToRadius, jitter } = 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]); //area ? inkDensityToRadius(st[3] / area) : 0; // radiusDensity
const hue = area ? st[10] / area : 0;
const saturation = area ? st[11] / area : 0;
const lightness = area ? st[3] / area : 0;
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 + jitter();
st[1] = cy + deltaY + jitter();
st[2] = renderRadius;
st[10] = saturation;
st[11] = hue;
// re-use arrays to reduce GC pressure
centroid[0] -= deltaX + jitter();
centroid[1] -= deltaY + jitter();
centroid.push(
renderRadius,
0, // radiusDensity
0, // resolutionDensity
0, // moment10
0, // moment01
0, // moment11
0, // moment20
0, // moment02
saturation,
hue,
lightness
);
newStipples.push(st, centroid);
} else {
// Relax
st[0] = st[5] / density + jitter(); // moment10
st[1] = st[6] / density + jitter(); //moment01
st[2] = renderRadius;
st[10] = hue;
st[11] = saturation;
st[12] = lightness;
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
st[10] = 0; // hue
st[11] = 0; //saturation
// st[12] = 0; // lightness
}
// compute the density and the weighted centroid of each cell
{
const { stipples, width } = this,
dValues = this.densityGrid.values,
rValues = this.resolutionGrid.values,
sValues = this.densityGrid.saturation,
hValues = this.densityGrid.hue;
for (let y = 0, found = 0; 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 idx = x + line;
const densityVal = dValues[idx];
const resolutionVal = rValues[idx];
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[10] += hValues[idx]; // hue
st[11] += sValues[idx]; // saturation
}
}
}
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 area = abs(d3.polygonArea(polygon));
const renderRadius = sqrt(st[3]); // radiusDensity
const hue = area ? st[10] / area : 0;
const saturation = area ? st[11] / area : 0;
const lightness = area ? st[3] / area : 0;
// Relax
const density = st[4];
st[0] = st[5] / density; // moment10
st[1] = st[6] / density; // moment01
st[3] = renderRadius;
st[10] = hue;
st[11] = saturation;
st[12] = lightness;
}
}
}
// https://stackoverflow.com/questions/2353211/hsl-to-rgb-color-conversion
/**
* Converts an RGB color value to HSL. Conversion formula
* adapted from http://en.wikipedia.org/wiki/HSL_color_space.
* Assumes r, g, and b are contained in the set [0, 255] and
* returns h, s, and l in the set [0, 1].
*
* @param {number} r The red color value
* @param {number} g The green color value
* @param {number} b The blue color value
* @return {Array} The HSL representation
*/
function rgbToHsl(r, g, b){
r /= 255, g /= 255, b /= 255;
var max = Math.max(r, g, b), min = Math.min(r, g, b);
var h, s, l = (max + min) / 2;
if(max == min){
h = s = 0; // achromatic
}else{
var d = max - min;
s = l > 0.5 ? d / (2 - max - min) : d / (max + min);
switch(max){
case r: h = (g - b) / d + (g < b ? 6 : 0); break;
case g: h = (b - r) / d + 2; break;
case b: h = (r - g) / d + 4; break;
}
h /= 6;
}
return [h, s, l];
}
/**
* Converts an HSL color value to RGB. Conversion formula
* adapted from http://en.wikipedia.org/wiki/HSL_color_space.
* Assumes h, s, and l are contained in the set [0, 1] and
* returns r, g, and b in the set [0, 255].
*
* @param {number} h The hue
* @param {number} s The saturation
* @param {number} l The lightness
* @param {number} a The opacity
* @return {"rgba(RR,GG,BB,AA)" | "#RRGGBB"} The RGB representation (picks hex string if a == 1)
*/
function hslToRgb(h, s, l, a = 1) {
h = (h + 1) % 1;
s = clamp(0, 1, s);
l = clamp(0, 1, l);
var r, g, b;
if (s == 0) {
r = g = b = Math.round(l * 255); // achromatic
} else {
var hue2rgb = function hue2rgb(p, q, t) {
if (t < 0) t += 1;
if (t > 1) t -= 1;
if (t < 1 / 6) return p + (q - p) * 6 * t;
if (t < 1 / 2) return q;
if (t < 2 / 3) return p + (q - p) * (2 / 3 - t) * 6;
return p;
};
var q = l < 0.5 ? l * (1 + s) : l + s - l * s;
var p = 2 * l - q;
r = clamp(0, 255, Math.round(hue2rgb(p, q, h + 1 / 3) * 255));
g = clamp(0, 255, Math.round(hue2rgb(p, q, h) * 255));
b = clamp(0, 255, Math.round(hue2rgb(p, q, h - 1 / 3) * 255));
}
if (a < 1) {
return `rgba(${r}, ${g}, ${b}, ${a})`;
}
const RR = r
.toString(16)
.padStart(2, "0")
.toUpperCase();
const GG = g
.toString(16)
.padStart(2, "0")
.toUpperCase();
const BB = b
.toString(16)
.padStart(2, "0")
.toUpperCase();
return `#${RR}${GG}${BB}`;
}
function initGrids(sobelFactor, data, w, h) {
const grid = {
width: w,
height: h,
values: new Float64Array(w*h), // lightness
saturation: new Float64Array(w*h),
hue: new Float64Array(w*h),
};
for(let i = 0; i < w*h; i++) {
const [h, s, l] = rgbToHsl(data[i*4], data[i*4 + 1], data[i*4 + 2]);
grid.hue[i] = h
grid.values[i] = l;
grid.saturation[i] = s;
}
const gridSobel = {
width: w,
height: h,
values: toSobel(w, h, sobelFactor, data, grid.values),
}
return [grid, gridSobel];
}
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
}
} = event;
w = width;
h = height;
[grid, gridSobel] = initGrids(sobelFactor, imgData, width, height);
postMessage({ grid, gridSobel });
stippling = new Stippling(grid, gridSobel, minRadius, maxRadius);
const stippleSorter = ([x1, y1], [x2, y2]) => {
if (y1 < y2) return -1;
else if (y1 > y2) return 1;
else if (x1 < x2) return -1;
else if (x1 > x2) return 1;
else return 0;
};
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 % 5 === 0 || i == maxIterations) {
const points = new Float64Array(stippling.stipples.length * 6);
const { stipples } = stippling;
stipples.sort(stippleSorter);
for (let j = 0; j < stipples.length; j++) {
const st = stipples[j];
const idx = j * 6;
points[idx] = st[0];
points[idx + 1] = st[1];
points[idx + 2] = st[2]; // radius
points[idx + 3] = st[10]; // hue
points[idx + 4] = st[11]; // saturation
points[idx + 5] = st[12]; // lightness
}
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 % 20 === 0 || i == totalRelaxations) {
const points = new Float64Array(stippling.stipples.length * 6);
const { stipples } = stippling;
stipples.sort(stippleSorter);
for (let j = 0; j < stipples.length; j++) {
const st = stipples[j];
const idx = j * 6;
points[idx] = st[0];
points[idx + 1] = st[1];
points[idx + 2] = st[2]; // radius
points[idx + 3] = st[10]; // hue
points[idx + 4] = st[11]; // saturation
points[idx + 5] = st[12]; // lightness
}
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 * 6);
const { stipples } = stippling;
stipples.sort(stippleSorter);
for (let j = 0; j < stipples.length; j++) {
const st = stipples[j];
const idx = j * 6;
points[idx] = st[0];
points[idx + 1] = st[1];
points[idx + 2] = st[2]; // radius
points[idx + 3] = st[10]; // hue
points[idx + 4] = st[11]; // saturation
points[idx + 5] = st[12]; // lightness
}
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()}
${rgbToHsl.toString()}
${hslToRgb.toString()}
${colorDelta.toString()}
${toSobel.toString()}
${initGrids.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";
};
}
{
await imgData;
return startWorker(
Object.assign({}, options, {
imgData: imgData.data,
width: imgData.width,
height: imgData.height
})
);
}
defaultSettings = {
return {
showProgress: true,
channel: "0",
minRadius: 2,
maxRadius: 3,
sobelFactor: 0.05,
inkDensity: 0.8,
maxIterations: 20,
totalRelaxations: 20,
stippleOpacity: 1
};
}
mutable iterationMessage = "Awaiting first iteration"
d3 = require("d3@6")
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;
const im = fileImg;
for (let i = 0; i < points.length; i += 6) {
svgPoints.push([
points[i],
points[i + 1],
points[i + 2],
points[i + 3],
points[i + 4],
points[i + 5]
]);
}
const w = im.naturalWidth || im.width;
const h = im.naturalHeight || im.height;
const svg = d3.select(DOM.svg(w, h));
svg
.append("g")
.append("rect")
.attr("x", 0)
.attr("y", 0)
.attr("width", w)
.attr("height", h)
.attr("fill", "black");
// let's limit the subpixel precision to two digits, and
// strip trailing zeroes to reduce the size of the SVG a bit
const limitDigits = v => {
let output = v.toFixed(2);
if (output.endsWith(".00")) return output.slice(0, output.length - 3);
if (output.endsWith("0")) return output.slice(0, output.length - 1);
else return output;
};
const distanceFn = makeDistanceFn(w, h, lensEffectMode, lensEffectSettings);
const fallOff = (lensEffectSettings.light * 2 || 0) + 1;
const opacityFn = d => opacity / distanceFn(d[0], d[1]) ** fallOff;
svg
.append("g")
.selectAll("circle")
.data(svgPoints)
.join("circle")
.attr("r", d =>
limitDigits(d[2] * inkDensity.inkDensity * distanceFn(d[0], d[1]))
)
.attr("cx", d => limitDigits(d[0]))
.attr("cy", d => limitDigits(d[1]))
.attr("fill", d => hslToRgb(d[3], d[4], d[5], 1))
.attr("fill-opacity", opacityFn);
// 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" });
}
opacity = clamp(0, 1, stippleOpacity.stippleOpacity)
function makeDistanceFn(w, h, lensEffectMode, lensEffectSettings) {
let distanceFn;
// We divide by the edgeFactor, so the smaller it is,
// the bigger the vignetting effect at the edges
const edgeFactor =
(w * w + h * h) / (1 + 127 * (lensEffectSettings.blur || 0));
const cx = w * lensEffectSettings.x;
const cy = h * (1 - lensEffectSettings.y);
if (lensEffectMode === "vignette") {
distanceFn = (x, y) => {
const dx = x - cx;
const dy = y - cy;
return 1 + (dx * dx + dy * dy) / edgeFactor;
};
} else if (lensEffectMode === "tiltShift") {
let slope = lensEffectSettings.slope || 0;
if (slope >= -1 && slope <= 1) {
distanceFn = (x, y) => {
const dy = y - cy + (x - cx) * slope;
return 1 + (dy * dy) / edgeFactor;
};
} else {
slope += slope < 0 ? 2 : -2;
distanceFn = (x, y) => {
const dx = x - cx + (y - cy) * -slope;
return 1 + (dx * dx) / edgeFactor;
};
}
} else {
// "Off"
distanceFn = (x, y) => 1;
}
return distanceFn;
}
function clamp(a, b, v) {
return v < a ? a : v > b ? b : v;
}
import { imageInput } from "@mbostock/file-input"
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.