// 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 // ); this.stipples = this.random_stipples( ((this.width * this.height) / (Math.PI * (minRadius*minRadius + maxRadius*maxRadius)*2)) | 0 ); this.relaxStipples = null; } // 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, // moment01 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 static jitter = (() => { // const {random} = Math; // return () => (random() - random()) * 0.00000762939453125; // return () => (random() + random() - random() - random()) * 0.000244140625; return () => 0; })(); // performs one iteration of the LBG stippling algorithm iterate() { const { stipples, width, height } = this; const delaunay = d3.Delaunay.from(stipples), voronoi = delaunay.voronoi([0, 0, width, height]); // initialize densities for (let i = 0; i < stipples.length; i++) { const st = 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 dValues = this.densityGrid.values, rValues = this.resolutionGrid.values, sValues = this.densityGrid.saturation, hValues = this.densityGrid.hue; for (let y = 0, found = 0; y < height; y++) { const line = y * width; let x = 0 while(x < width) { found = delaunay.find(x, y, found); const st = stipples[found]; let idx = x + line; let densityVal = dValues[idx]; let resolutionVal = rValues[idx]; let rValSum = resolutionVal; let xval = x * resolutionVal; let yval = y * resolutionVal; let hue = hValues[idx]; let saturation = sValues[idx] let xi = x + 1; let foundi = delaunay.find(xi, y, found); while(xi < width && foundi === found) { idx = xi + line; densityVal += dValues[idx]; resolutionVal = rValues[idx]; rValSum += resolutionVal; xval += xi * resolutionVal; yval += y * resolutionVal; hue += hValues[idx]; saturation += sValues[idx]; foundi = delaunay.find(++xi, y, found); } x = xi; st[3] += densityVal; // radiusDensity st[4] += rValSum; // resolutionDensity aka moment00 st[5] += xval; // moment10 st[6] += yval; // moment01 st[10] += hue; st[11] += saturation; } } } const { resolutionDensityToRadius } = this; const resolutionGridMax = this.resolutionGridExtent[1]; let deleted = 0; let splitted = 0; const newStipples = []; const { abs, atan2, cos, min, random, sin, sqrt, PI } = Math; const { jitter } = Stippling; 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); let cx = centroid[0]; let 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 * sin(orientation); var deltaY = dist * cos(orientation); // jitter, and make sure the centroid is // constrained to the image dimensions cx += deltaX + jitter(); cy += deltaY + jitter(); if (cx < 0) cx = -cx; else if (cx > width) cx = 2 * width - cx; if (cy < 0) cy = -cy; else if (cy > height) cy = 2 * height - cy; st[0] = cx; st[1] = cy; st[2] = renderRadius; st[10] = hue; st[11] = saturation; // re-use arrays to reduce GC pressure cx -= 2 * deltaX; cy -= 2 * deltaY; if (cx < 0) cx = -cx; else if (cx > width) cx = 2 * width - cx; if (cy < 0) cy = -cy; else if (cy > height) cy = 2 * height - cy; centroid[0] = cx; centroid[1] = cy; 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 let moment10 = st[5] / density; // moment10 let moment01 = st[6] / density; // moment01 if (moment10 <= 0.5) moment10 = 0.5; else if (moment10 >= width - 0.5) moment10 = width - 0.5; if (moment01 <= 0.5) moment01 = 0.5; else if (moment01 >= height - 0.5) moment01 = height - 0.5; st[0] = moment10; st[1] = 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 { stipples, width, height } = this, {jitter} = Stippling, delaunay = d3.Delaunay.from(stipples), voronoi = delaunay.voronoi([0, 0, width, height]); for (let i = 0; i < stipples.length; i++) { const st = 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 dValues = this.densityGrid.values, rValues = this.resolutionGrid.values, sValues = this.densityGrid.saturation, hValues = this.densityGrid.hue; for (let y = 0, found = 0; y < 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 < stipples.length; i++) { const polygon = voronoi.cellPolygon(i); if (!polygon) continue; const st = 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]; let moment10 = st[5] / density; // moment10 let moment01 = st[6] / density; // moment01 if (moment10 <= 0.5) moment10 = 0.5; else if (moment10 >= width - 0.5) moment10 = width - 0.5; if (moment01 <= 0.5) moment01 = 0.5; else if (moment01 >= height - 0.5) moment01 = height - 0.5; if ( !Number.isNaN(moment10) && !Number.isNaN(moment01) // Number.isFinite(renderRadius) && // Number.isFinite(hue) && // Number.isFinite(saturation) && // Number.isFinite(lightness) ) { st[0] = moment10; st[1] = moment01; st[3] = renderRadius; st[10] = hue; st[11] = saturation; st[12] = lightness; } } } }