// 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; } } }