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"
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.