Tinkering with code and algorithms for fun
Published
Edited
Aug 11, 2020
3 stars
function walkOnSpheres(x, y) {
// Sometimes inlining Math.<something> can be faster
// if the function is called in tight loops, because
// it avoids prototypical chain lookups. It seemed to
// make things slightly snappier on my machine when
// I tried it here, probably because walkOnSpheres
// is called up to ten times per pixel.
const {random, SQRT2} = Math;
const {distance, color} = nearest;
const STEPS = 20
let steps = STEPS,
dist = distance[(x|0) + (y|0) * width];
// we can sum up the colors along each step to get more
// averaged out values quicker
let colorSum = 0;
// turns out that box-shaped random walking works
// just as well as circle-shaped random walking
// but to avoid overshooting we must take into
// account that we can step a full pixel in each
while (steps--) {
const dx = x + dist * (random() - 0.5);
const dy = y + dist * (random() - 0.5);
// // More bell-curve-like shaped walk, I think
// // it gives slightly nicer edges in fewer steps,
// // but it doesn't scatter as far and technically
// // it is a bit slower of course
// const dx = x + dist * (random() + random() - random() - random()) * 0.25;
// const dy = y + dist * (random() + random() - random() - random()) * 0.25;
const ddist = distance[(dx|0) + (dy|0) * width];
if (dx >= 0 && dx < width && dy >= 0 && dy < height && ddist > SQRT2) {
x = dx;
y = dy;
dist = ddist;
}
colorSum += color[(x|0) + (y|0) * width]
}
return colorSum / STEPS;
}
nearest = {
const nDistance = new Float32Array(width * height);
// just some value guaranteed to be bigger than any cirle distance
nDistance.fill(width*height);
const nColor = new Float32Array(width * height);
for (let y = 0; y < height; y++) {
for (let x = 0; x < width ; x++) {
// for any given (x, y) coordinate we cache the distance
// to the nearest circle and it's associated color
const idx = x + y * width;
for (const c of circles) {
const [dist, color] = c.closestCirclePoint(x, y);
if (dist < nDistance[idx]) {
nDistance[idx] = dist;
nColor[idx] = color;
}
}
}
}
return { distance: nDistance, color: nColor };
}
values = {
const RUNS = 4;
const values = new Float32Array(width * height);
mutable startSmoothing = false;
for (let c = 0; c < RUNS; c++) {
const oneOverC = 1 / (c + 1);
for (let i = 0; i < width; i++) {
for (let j = 0; j < height; j++) {
const k = i + width * j;
values[k] = (c * values[k] + walkOnSpheres(i, j)) * oneOverC;
}
if (i % 60 === 0) {
yield values;
}
}
yield values;
}
mutable startSmoothing = true;
}
mutable startSmoothing = false;
smoothedValues = new Float32Array(values.length)
function circleBlur(x, y, r, width, values) {
const {sqrt, ceil, floor} = Math;
const r2 = r*r, rj = floor(r);
let v = 0, div = 0;
for (let j = -rj; j <= rj; j++) {
if (y + j < 0 || y + j >= height) continue;
const ri = floor(sqrt(r2 - j*j))
for (let i = -ri; i <= ri; i++) {
if (x + i < 0 || x + i >= width) continue;
div++;
v += values[(x + i) + (y + j) * width];
}
}
return div ? v / div : values[x + y * width];
}
color = d3.scaleSequential(d3[`interpolate${colorInterpolator}`])
colorsU32 = {
const colors = d3.range(0, 1, 1 / 256).map(v => d3.rgb(color(v)));
const colorsU8 = new Uint8ClampedArray(colors.length*4);
for(let i = 0; i < colors.length; i++) {
const c = colors[i];
colorsU8[i*4] = c.r;
colorsU8[i*4 + 1] = c.g;
colorsU8[i*4 + 2] = c.b;
colorsU8[i*4 + 3] = 255
}
return new Uint32Array(colorsU8.buffer);
}
height = 500
circles = {
replay;
// Currently the only way to guarantee an array in JS without holes is to use .push().
// (arrays with holes are slower to iterate over - unlikely to be important here but still)
const circles = [];
// Fun fact: calling .push() once with multiple values is faster than repeated calls
// Not really relevant with an array that's initiated once and which only has 10 entries,
// but nice to know, right?
circles.push(
new Circle(), new Circle(), new Circle(), new Circle(), new Circle(),
new Circle(), new Circle(), new Circle(), new Circle(), new Circle(),
new Circle(), new Circle(), new Circle(), new Circle(), new Circle(),
new Circle(), new Circle(), new Circle(), new Circle(), new Circle()
);
return circles;
}
// Prototypical objects play nicer with the JS JIT.
// Also the only way to get inlined optimizations
// for methods and to avoid de-opts in certain cases
// https://mrale.ph/blog/2015/01/11/whats-up-with-monomorphism.html
class Circle {
constructor() {
const {random} = Math;
this.x = random() * width;
this.y = random() * height;
this.r = random() * width * 0.25;
this.inside = random() * 0.5;
this.outside = (1 + random()) * 0.5;
}
closestCirclePoint(x, y) {
const r = Math.hypot(x - this.x, y - this.y);
let dist = this.r - r;
if (dist < 0) dist = -dist;
return [
dist,
r < this.r ? this.inside : this.outside
];
}
}
d3 = require("d3@6.0.0-rc.3")
import { select } from "@jashkenas/inputs"
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.
