Skip to content

Instantly share code, notes, and snippets.

@veltman
Last active January 2, 2021 17:38
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save veltman/017a2093623e1bf3ae041dd3380578cb to your computer and use it in GitHub Desktop.
Save veltman/017a2093623e1bf3ae041dd3380578cb to your computer and use it in GitHub Desktop.
Stippling #2

Another attempt at stippling with a more basic relaxation approach but using multiple dot sizes to add texture.

  1. Position starting points with rejection sampling, using the grayscale image as the density function.
  2. Use Lloyd's algorithm to get a relaxed Voronoi diagram from the starting points.
  3. Size the dots based on the darkness of the pixel at their position, then shrink them as much as necessary to avoid collisions - this could be done all at once but it seems to produce some splotchy artifacts, so instead they're shrunk a little bit at a time.

The heavy computation is done in a web worker to avoid locking up the page, and takes about 15-20 seconds to complete.

See also: Voronoi relaxation, Stippling, Philippe Rivière's CCPD Snowden

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<style>
canvas {
display: block;
width: 800px;
height: 500px;
margin: 0 auto;
}
</style>
</head>
<body>
<canvas width="1600" height="1000"></canvas>
<script src="https://d3js.org/d3.v5.min.js"></script>
<script src="stackblur.min.js"></script>
<script>
const canvas = document.querySelector("canvas"),
context = canvas.getContext("2d"),
img = new Image(),
width = 800,
height = 1000,
threshold = 0.9,
worker = new Worker("worker.js");
context.fillStyle = "#444";
img.onload = function() {
// Draw image
context.drawImage(img, 0, 0, width, height);
// Blur image to smooth it out
StackBlur.canvasRGBA(canvas, 0, 0, width, height, 5);
const density = getDensityFunction(context);
context.drawImage(img, 0, 0, width, height);
// Get initial points
const points = generatePoints(density, 10000);
worker.onmessage = event => draw(event.data);
// Compute in worker
worker.postMessage({ density, points, width, height, threshold });
};
img.src = "obama.png";
// Draw the points
function draw(points) {
context.clearRect(width, 0, width, height);
points.forEach(function(point) {
context.beginPath();
if (point.r) {
context.arc(width + point[0], point[1], point.r, 0, 2 * Math.PI);
context.fill();
}
});
}
function generatePoints(density, numPoints) {
// Generate starting points with rejection sampling against pixel brightness
return d3.range(numPoints).map(function() {
let x, y, d;
while (true) {
x = Math.random() * width;
y = Math.random() * height;
d = density[width * Math.floor(y) + Math.floor(x)];
if (Math.random() > d) {
return [x, y, d];
}
}
});
}
// Convert imageData into an array of brightness values from 0-1
function getDensityFunction(context) {
const data = context.getImageData(0, 0, width, height).data;
return d3.range(0, data.length, 4).map(i => data[i] / 255);
}
</script>
!function(a){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=a();else if("function"==typeof define&&define.amd)define([],a);else{var b;b="undefined"!=typeof window?window:"undefined"!=typeof global?global:"undefined"!=typeof self?self:this,b.StackBlur=a()}}(function(){return function a(b,c,d){function e(g,h){if(!c[g]){if(!b[g]){var i="function"==typeof require&&require;if(!h&&i)return i(g,!0);if(f)return f(g,!0);var j=new Error("Cannot find module '"+g+"'");throw j.code="MODULE_NOT_FOUND",j}var k=c[g]={exports:{}};b[g][0].call(k.exports,function(a){var c=b[g][1][a];return e(c?c:a)},k,k.exports,a,b,c,d)}return c[g].exports}for(var f="function"==typeof require&&require,g=0;g<d.length;g++)e(d[g]);return e}({1:[function(a,b,c){function d(a,b,c,d){if("string"==typeof a)var a=document.getElementById(a);else if("undefined"!=typeof HTMLImageElement&&!a instanceof HTMLImageElement)return;var e=a.naturalWidth,g=a.naturalHeight;if("string"==typeof b)var b=document.getElementById(b);else if("undefined"!=typeof HTMLCanvasElement&&!b instanceof HTMLCanvasElement)return;b.style.width=e+"px",b.style.height=g+"px",b.width=e,b.height=g;var i=b.getContext("2d");i.clearRect(0,0,e,g),i.drawImage(a,0,0),isNaN(c)||c<1||(d?f(b,0,0,e,g,c):h(b,0,0,e,g,c))}function e(a,b,c,d,e){if("string"==typeof a)var a=document.getElementById(a);else if("undefined"!=typeof HTMLCanvasElement&&!a instanceof HTMLCanvasElement)return;var f,g=a.getContext("2d");try{try{f=g.getImageData(b,c,d,e)}catch(h){throw new Error("unable to access local image data: "+h)}}catch(h){throw new Error("unable to access image data: "+h)}return f}function f(a,b,c,d,f,h){if(!(isNaN(h)||h<1)){h|=0;var i=e(a,b,c,d,f);i=g(i,b,c,d,f,h),a.getContext("2d").putImageData(i,b,c)}}function g(a,b,c,d,e,f){var g,h,i,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H=a.data,I=f+f+1,J=d-1,K=e-1,L=f+1,M=L*(L+1)/2,N=new j,O=N;for(i=1;i<I;i++)if(O=O.next=new j,i==L)var P=O;O.next=N;var Q=null,R=null;p=o=0;var S=k[f],T=l[f];for(h=0;h<e;h++){for(y=z=A=B=q=r=s=t=0,u=L*(C=H[o]),v=L*(D=H[o+1]),w=L*(E=H[o+2]),x=L*(F=H[o+3]),q+=M*C,r+=M*D,s+=M*E,t+=M*F,O=N,i=0;i<L;i++)O.r=C,O.g=D,O.b=E,O.a=F,O=O.next;for(i=1;i<L;i++)m=o+((J<i?J:i)<<2),q+=(O.r=C=H[m])*(G=L-i),r+=(O.g=D=H[m+1])*G,s+=(O.b=E=H[m+2])*G,t+=(O.a=F=H[m+3])*G,y+=C,z+=D,A+=E,B+=F,O=O.next;for(Q=N,R=P,g=0;g<d;g++)H[o+3]=F=t*S>>T,0!=F?(F=255/F,H[o]=(q*S>>T)*F,H[o+1]=(r*S>>T)*F,H[o+2]=(s*S>>T)*F):H[o]=H[o+1]=H[o+2]=0,q-=u,r-=v,s-=w,t-=x,u-=Q.r,v-=Q.g,w-=Q.b,x-=Q.a,m=p+((m=g+f+1)<J?m:J)<<2,y+=Q.r=H[m],z+=Q.g=H[m+1],A+=Q.b=H[m+2],B+=Q.a=H[m+3],q+=y,r+=z,s+=A,t+=B,Q=Q.next,u+=C=R.r,v+=D=R.g,w+=E=R.b,x+=F=R.a,y-=C,z-=D,A-=E,B-=F,R=R.next,o+=4;p+=d}for(g=0;g<d;g++){for(z=A=B=y=r=s=t=q=0,o=g<<2,u=L*(C=H[o]),v=L*(D=H[o+1]),w=L*(E=H[o+2]),x=L*(F=H[o+3]),q+=M*C,r+=M*D,s+=M*E,t+=M*F,O=N,i=0;i<L;i++)O.r=C,O.g=D,O.b=E,O.a=F,O=O.next;for(n=d,i=1;i<=f;i++)o=n+g<<2,q+=(O.r=C=H[o])*(G=L-i),r+=(O.g=D=H[o+1])*G,s+=(O.b=E=H[o+2])*G,t+=(O.a=F=H[o+3])*G,y+=C,z+=D,A+=E,B+=F,O=O.next,i<K&&(n+=d);for(o=g,Q=N,R=P,h=0;h<e;h++)m=o<<2,H[m+3]=F=t*S>>T,F>0?(F=255/F,H[m]=(q*S>>T)*F,H[m+1]=(r*S>>T)*F,H[m+2]=(s*S>>T)*F):H[m]=H[m+1]=H[m+2]=0,q-=u,r-=v,s-=w,t-=x,u-=Q.r,v-=Q.g,w-=Q.b,x-=Q.a,m=g+((m=h+L)<K?m:K)*d<<2,q+=y+=Q.r=H[m],r+=z+=Q.g=H[m+1],s+=A+=Q.b=H[m+2],t+=B+=Q.a=H[m+3],Q=Q.next,u+=C=R.r,v+=D=R.g,w+=E=R.b,x+=F=R.a,y-=C,z-=D,A-=E,B-=F,R=R.next,o+=d}return a}function h(a,b,c,d,f,g){if(!(isNaN(g)||g<1)){g|=0;var h=e(a,b,c,d,f);h=i(h,b,c,d,f,g),a.getContext("2d").putImageData(h,b,c)}}function i(a,b,c,d,e,f){var g,h,i,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=a.data,E=f+f+1,F=d-1,G=e-1,H=f+1,I=H*(H+1)/2,J=new j,K=J;for(i=1;i<E;i++)if(K=K.next=new j,i==H)var L=K;K.next=J;var M=null,N=null;p=o=0;var O=k[f],P=l[f];for(h=0;h<e;h++){for(w=x=y=q=r=s=0,t=H*(z=D[o]),u=H*(A=D[o+1]),v=H*(B=D[o+2]),q+=I*z,r+=I*A,s+=I*B,K=J,i=0;i<H;i++)K.r=z,K.g=A,K.b=B,K=K.next;for(i=1;i<H;i++)m=o+((F<i?F:i)<<2),q+=(K.r=z=D[m])*(C=H-i),r+=(K.g=A=D[m+1])*C,s+=(K.b=B=D[m+2])*C,w+=z,x+=A,y+=B,K=K.next;for(M=J,N=L,g=0;g<d;g++)D[o]=q*O>>P,D[o+1]=r*O>>P,D[o+2]=s*O>>P,q-=t,r-=u,s-=v,t-=M.r,u-=M.g,v-=M.b,m=p+((m=g+f+1)<F?m:F)<<2,w+=M.r=D[m],x+=M.g=D[m+1],y+=M.b=D[m+2],q+=w,r+=x,s+=y,M=M.next,t+=z=N.r,u+=A=N.g,v+=B=N.b,w-=z,x-=A,y-=B,N=N.next,o+=4;p+=d}for(g=0;g<d;g++){for(x=y=w=r=s=q=0,o=g<<2,t=H*(z=D[o]),u=H*(A=D[o+1]),v=H*(B=D[o+2]),q+=I*z,r+=I*A,s+=I*B,K=J,i=0;i<H;i++)K.r=z,K.g=A,K.b=B,K=K.next;for(n=d,i=1;i<=f;i++)o=n+g<<2,q+=(K.r=z=D[o])*(C=H-i),r+=(K.g=A=D[o+1])*C,s+=(K.b=B=D[o+2])*C,w+=z,x+=A,y+=B,K=K.next,i<G&&(n+=d);for(o=g,M=J,N=L,h=0;h<e;h++)m=o<<2,D[m]=q*O>>P,D[m+1]=r*O>>P,D[m+2]=s*O>>P,q-=t,r-=u,s-=v,t-=M.r,u-=M.g,v-=M.b,m=g+((m=h+H)<G?m:G)*d<<2,q+=w+=M.r=D[m],r+=x+=M.g=D[m+1],s+=y+=M.b=D[m+2],M=M.next,t+=z=N.r,u+=A=N.g,v+=B=N.b,w-=z,x-=A,y-=B,N=N.next,o+=d}return a}function j(){this.r=0,this.g=0,this.b=0,this.a=0,this.next=null}var k=[512,512,456,512,328,456,335,512,405,328,271,456,388,335,292,512,454,405,364,328,298,271,496,456,420,388,360,335,312,292,273,512,482,454,428,405,383,364,345,328,312,298,284,271,259,496,475,456,437,420,404,388,374,360,347,335,323,312,302,292,282,273,265,512,497,482,468,454,441,428,417,405,394,383,373,364,354,345,337,328,320,312,305,298,291,284,278,271,265,259,507,496,485,475,465,456,446,437,428,420,412,404,396,388,381,374,367,360,354,347,341,335,329,323,318,312,307,302,297,292,287,282,278,273,269,265,261,512,505,497,489,482,475,468,461,454,447,441,435,428,422,417,411,405,399,394,389,383,378,373,368,364,359,354,350,345,341,337,332,328,324,320,316,312,309,305,301,298,294,291,287,284,281,278,274,271,268,265,262,259,257,507,501,496,491,485,480,475,470,465,460,456,451,446,442,437,433,428,424,420,416,412,408,404,400,396,392,388,385,381,377,374,370,367,363,360,357,354,350,347,344,341,338,335,332,329,326,323,320,318,315,312,310,307,304,302,299,297,294,292,289,287,285,282,280,278,275,273,271,269,267,265,263,261,259],l=[9,11,12,13,13,14,14,15,15,15,15,16,16,16,16,17,17,17,17,17,17,17,18,18,18,18,18,18,18,18,18,19,19,19,19,19,19,19,19,19,19,19,19,19,19,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24];b.exports={image:d,canvasRGBA:f,canvasRGB:h,imageDataRGBA:g,imageDataRGB:i}},{}]},{},[1])(1)});
importScripts("https://d3js.org/d3.v5.min.js");
const voronoi = d3.voronoi();
const minRadius = 0.5,
maxRadius = 3.5;
// Linear seems to get better results than sqrt
const radius = d3
.scaleLinear()
.range([maxRadius, minRadius])
.clamp(true);
let iterations = 0;
const quadtree = d3.quadtree();
// Begin compute loop
onmessage = function(event) {
const { points, width, height, density, threshold } = event.data;
voronoi.extent([[0, 0], [width, height]]);
radius.domain([0, threshold]);
compute();
function compute() {
// Relax the voronoi with Lloyd's algorithm the first 12 times
if (iterations < 12) {
voronoi(points)
.polygons()
.map(d3.polygonCentroid)
.forEach(function(centroid, i) {
points[i] = [
...centroid,
density[width * Math.floor(centroid[1]) + Math.floor(centroid[0])]
];
points[i].r = points[i][2] > threshold ? 0 : radius(points[i][2]);
});
// Then shrink the points until there are no collisions
} else if (!shrink(points)) {
return;
}
iterations++;
postMessage(points);
setTimeout(compute, 0);
}
};
// Look for point-point collisions, and shrink both radii
function shrink(points) {
if (!quadtree.size()) {
quadtree.addAll(points);
}
// For each point, shrink points that collide with it
points.forEach(function(point) {
point.shrink = false;
quadtree.visit(function(node, x0, y0, x1, y1) {
if (
point.shrink ||
(!node.data &&
(node.x0 > point[0] + point.r ||
node.x1 < point[0] - point.r ||
(node.y0 > point[1] + point.r || node.y1 < point[1] - point.r)))
) {
return true;
}
if (node.data && node.data !== point) {
const diff = collides(node.data, point);
if (diff > 0) {
[point, node.data].forEach(function(p) {
p.shrink = true;
});
}
}
});
});
let collision = false;
// Smoother than trying to shrink each pair as they're found
points.forEach(function(point) {
if (point.shrink && point.r > minRadius) {
point.r = Math.max(minRadius, point.r * 0.9);
collision = true;
}
});
return collision;
}
function collides(a, b) {
const dx = a[0] - b[0],
dy = a[1] - b[1],
dr = a.r + b.r;
return dr - Math.sqrt(dx * dx + dy * dy);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment