GPU = require("gpu.js@2.15.2")
gpu = new GPU.GPU({ mode: "gpu" })
createCostsTexture = gpu
.createKernel(function(points) {
const a0 = points[2 * this.thread.x],
a1 = points[2 * this.thread.x + 1],
b0 = points[2 * this.thread.y],
b1 = points[2 * this.thread.y + 1];
const dist2 = (a0 - b0) * (a0 - b0) + (a1 - b1) * (a1 - b1);
if (dist2 < 20) return dist2;
return 1e6; // not to say Infinity
})
.setPipeline(true)
.setOutput([N, N])
kernelSum = gpu
.createKernel(function(v) {
let sum = 0;
for (let j = 0; j < this.constants.N; j++) {
sum += v[0][j];
}
return sum;
})
.setConstants({ N })
.setPipeline(false)
.setOutput([1])
kernel = () =>
gpu
.createKernel(function(v, costs) {
const i = this.thread.x,
line = this.thread.y;
/* let costs = v[0],
predecessors = v[1],
origins = v[2],
front = v[3]; */
let c0 = v[0][i],
predecessor = v[1][i],
origin = v[2][i];
for (let j = 0; j < this.constants.N; j++) {
if (v[3][j] > 0) {
if (v[0][j] < 1000) {
const c = v[0][j] + costs[i][j];
if (c < c0) {
c0 = c;
predecessor = j;
origin = v[2][j];
if (line == 3) return 1; // front
}
}
}
}
if (line == 0) return c0;
if (line == 1) return predecessor;
if (line == 2) return origin;
})
.setConstants({ N })
.setPipeline(true)
//.setImmutable(true)
.setOutput([N, 4])
max_texture_size = {
const gl = DOM.canvas(1, 1).getContext("webgl");
return gl.getParameter(gl.MAX_TEXTURE_SIZE);
}
n = 40 // Math.sqrt(max_texture_size) | 0
N = n ** 2
startNodes = [0, 1, 2]
points = (replay,
Array.from(
{ length: N },
(_, i) => [Math.random() * n, Math.random() * n] || [i % n, (i - (i % n)) / n]
).flat())
function* dijkstra(points) {
const time = performance.now();
const COSTS = createCostsTexture(points);
const t_costs = performance.now() - time;
let current = [
Float32Array.from({ length: N }, (_, i) =>
startNodes.includes(i) ? 0 : 1e9
), // initial costs
Int32Array.from({ length: N }).fill(-1), // initial predecessors
Int32Array.from({ length: N }, (_, i) => i), // initial origins
Int32Array.from({ length: N }, (_, i) => (startNodes.includes(i) ? 1 : 0)) // initial front
],
sum,
sum0 = kernelSum(current)[0];
// The easiest way to setup just two variable that you can alternate,
// is simply create two kernels, even if they are identical.
// They’ll keep their textures straight.
const kernel0 = kernel(),
kernel1 = kernel();
for (var i = 0; i < 100; i++) {
current = kernel1(kernel0(current, COSTS), COSTS);
// current = kernel1(kernel0(current, COSTS), COSTS);
sum = kernelSum(current)[0];
console.warn(i, performance.now() - time, sum);
if (sum >= sum0 - 0.0001) break;
sum0 = sum;
yield { value: current, t: performance.now() - time, t_costs, sum, i };
}
// COSTS.delete();
yield { value: current, t: performance.now() - time, t_costs, sum, i };
}
R = (replay, dijkstra(points))
result = {
const time = performance.now();
if (R.value.toArray) {
R.texture = R.value;
R.value = R.value.toArray();
}
R.t = performance.now() - time;
return R;
}
color = ({
0: d3.scaleSequential(d3.interpolateBlues).domain([0, 50]),
1: d3.scaleSequential(d3.interpolateReds).domain([0, 50]),
2: d3.scaleSequential(d3.interpolateGreens).domain([0, 50])
})
COSTS = createCostsTexture(points)
d3 = require("d3@5")
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.
