This PR introduces worker-based spatial indexing and exposes the index for reuse.
Description
What was changed in this pull request?
Updated KDBush to v4
Expose the KDBush's spatial index via scatterplot.get('spatialIndex')
Export helper function to create the spatial index upfront via createSpatialIndex(points)
Accept a precomputed spatial index when drawing new points via scatterplot.draw(newPoints, { spatialIndex })
Update pubSubEs to v3 for better types
Why is it necessary?
Fixes #174
tl/dr: Exposing and (re)using spatial indices is useful when performance is key as it allows to drastically reduce the draw time by skipping the expensive spatial indexing. For instance, imagine you only want to change the z/w coordinates that are used for defining the point color, opacity, or size. Previously, every time you called scatterplot.draw(points) would trigger a re-indexing of the x/y point coordinates even though the did not change. Similarly, one could now precompute the spatial index and load it upfront. In both cases, scatterplot.draw(points, { spatialIndex }) can be dramatically as the spatial indexing is skipped.
Caution: Please be advised that when you pass a spatial index to the draw call, regl-scatterplot assumes the index conforms with the point data. Regl-scatterplot does not actual verify that the two conform! So only use this feature if you know what you're doing!
Example
In the example below you can see how one can reuse the initial spatial index to save redrawing time upon follow up draw calls where only the z/w coordinates change.
const x = (length) => Array.from({ length }, () => -1 + Math.random() * 2);
const y = (length) => Array.from({ length }, () => -1 + Math.random() * 2);
const z = (length) => Array.from({ length }, () => Math.round(Math.random()));
const w = (length) => Array.from({ length }, () => Math.random());
const numPoints = 1000000;
const points = {
x: x(numPoints),
y: y(numPoints),
z: z(numPoints),
w: w(numPoints),
};
const scatterplot = createScatterplot({ ... });
scatterplot.draw(initialPoints).then(() => {
// After the initial draw, we retrieve and save the KDBush spatial index.
const spatialIndex = scatterplot.get('spatialIndex');
setInterval(() => {
// Update Z and W values
points.z = z(numPoints);
points.w = w(numPoints);
// We redraw the scatter plot with the updates points. Importantly, since
// the x/y coordinates remain unchanged we pass in the saved spatial index
// to avoid having to re-index the points.
scatterplot.draw(points, { spatialIndex });
}, 2000);
})
In the video you can see that this leads to a roughly 6x performance increase in Firefox when rendering one million points.
This PR introduces worker-based spatial indexing and exposes the index for reuse.
Description
scatterplot.get('spatialIndex')createSpatialIndex(points)scatterplot.draw(newPoints, { spatialIndex })Fixes #174
tl/dr: Exposing and (re)using spatial indices is useful when performance is key as it allows to drastically reduce the draw time by skipping the expensive spatial indexing. For instance, imagine you only want to change the z/w coordinates that are used for defining the point color, opacity, or size. Previously, every time you called
scatterplot.draw(points)would trigger a re-indexing of the x/y point coordinates even though the did not change. Similarly, one could now precompute the spatial index and load it upfront. In both cases,scatterplot.draw(points, { spatialIndex })can be dramatically as the spatial indexing is skipped.Caution: Please be advised that when you pass a spatial index to the draw call, regl-scatterplot assumes the index conforms with the point data. Regl-scatterplot does not actual verify that the two conform! So only use this feature if you know what you're doing!
Example
In the example below you can see how one can reuse the initial spatial index to save redrawing time upon follow up draw calls where only the z/w coordinates change.
In the video you can see that this leads to a roughly 6x performance increase in Firefox when rendering one million points.
https://github.com/flekschas/regl-scatterplot/assets/932103/d7200b11-97cc-4346-bcf7-d68c3755b0d6
Checklist
CHANGELOG.mdupdatedREADME.mdadded or updated