Many points on canvas in phyllotaxis layout

Sometimes in life, you’ve just gotta move thousands of points around on the screen. For hundreds of points, this can be accomplished with D3 through d3-transition on SVG nodes, but this typically becomes too slow when you need to animate more than a thousand points. So how do you do it?

Enter canvas. Each point is rendered as pixels on the canvas, which is much faster than moving DOM elements around. Unfortunately, it comes at the cost of increased complexity. Instead of just doing the standard d3.selectAll('rect').transition() and having the points move around, we have to do the animation manually.

In this post, I’ll demonstrate a simple approach of solving this problem using the basic canvas API and a few helper functions from D3.

Create the points to move around

We’re going to have 7,000 points move through a handful of different layouts in a loop. We can use d3.range as a simple helper to create our array of points and d3-scale to assign a color to each point.

const numPoints = 7000;
const colorScale = d3.scaleSequential(d3.interpolateViridis)
  .domain([numPoints - 1, 0]);

// generate the array of points with a unique ID and color
const points = d3.range(numPoints).map(index => ({
  id: index,
  color: colorScale(index),
}));

Layout the points

Next, we’ll need to define a couple of functions for laying out the points. For positioning the points in a grid layout, we can use the following:

/**
 * Given a set of points, lay them out in a grid.
 * Mutates the `points` passed in by updating the x and y values.
 *
 * @param {Object[]} points The array of points to update.
 *   Will get `x` and `y` set.
 * @param {Number} pointWidth The size in pixels of the point's
 *   width. Should also include margin.
 * @param {Number} gridWidth The width of the grid of points
 *
 * @return {Object[]} points with modified x and y
 */
function gridLayout(points, pointWidth, gridWidth) {
  const pointHeight = pointWidth;
  const pointsPerRow = Math.floor(gridWidth / pointWidth);
  const numRows = points.length / pointsPerRow;

  points.forEach((point, i) => {
    point.x = pointWidth * (i % pointsPerRow);
    point.y = pointHeight * Math.floor(i / pointsPerRow);
  });

  return points;
}

As is the case for all of our layout functions, x and y attributes are added to each point in the points array. The other three layouts used in this example are a phyllotaxis layout, a spiral layout, and a sine wave layout, shown below.

Layouts used in example: grid, phylllotaxis, spiral, sine

The code for each of these layouts is available here.

Note that all these layouts follow the same pattern: they are functions that take an array of points and modify the x and y properties of the points. That’s it!

Drawing the points

To draw the points on the canvas, we use the same draw function regardless of layout. It reads the x and y positions of the points and draw them accordingly.

// draw the points based on their current layout
function draw() {
  const ctx = canvas.node().getContext('2d');
  ctx.save();

  // erase what is on the canvas currently
  ctx.clearRect(0, 0, width, height);

  // draw each point as a rectangle
  for (let i = 0; i < points.length; ++i) {
    const point = points[i];
    ctx.fillStyle = point.color;
    ctx.fillRect(point.x, point.y, pointWidth, pointWidth);
  }

  ctx.restore();
}

We can test out our layout and drawing functions by calling them in succession and seeing what shows up on screen.

const pointWidth = 4;
const pointMargin = 3;
const width = 600;
gridLayout(points, pointWidth + pointMargin, width);
draw();

Points in grid layout

Since we assigned color based on the position of the points in the array, they show up in a smooth gradient on screen.

Animating the points

At this point, we’re ready to begin animating the points with d3-timer and d3-ease. Here’s a general procedure for tackling this problem:

Step 1. Store the source position. We’ll store the source position using properties directly on the object called sx and sy. These values represent the position they’re currently at on screen, which is where the animation will begin interpolating from.

// store the source position
points.forEach(point => {
  point.sx = point.x;
  point.sy = point.y;
});

Step 2. Update the positions of the points to use the next layout. This will update the x and y attributes on each object.

gridLayout(points, pointWidth + pointMargin, width);

Step 3. Store the target position. We could have set tx and ty directly in step 2, but our layout algorithms set x and y, which is common behavior in other third party D3 layouts, so we copy the values over now.

// store the destination position
points.forEach(point => {
  point.tx = point.x;
  point.ty = point.y;
});

Step 4. Set up a timer to interpolate between source and target positions. Now that we have both the source and target positions stored separately from the current position, we can easily interpolate between them.

By applying our d3-ease function to the t variable, we can get things like cubic easing despite doing linear interpolation between source and target positions.

const duration = 1500;
const ease = d3.easeCubic;

timer = d3.timer((elapsed) => {
  // compute how far through the animation we are (0 to 1)
  const t = Math.min(1, ease(elapsed / duration));

  // update point positions (interpolate between source and target)
  points.forEach(point => {
    point.x = point.sx * (1 - t) + point.tx * t;
    point.y = point.sy * (1 - t) + point.ty * t;
  });

  // update what is drawn on screen
  draw();

  // if this animation is over
  if (t === 1) {
    // stop this timer since we are done animating.
    timer.stop();
  }
});

Demo

A full working example looping through the different layouts is shown below:

The code for this example is available here as a block.

What if I want to animate more than 10,000 points?

Using this approach with canvas can only get us so far. As you exceed 5,000 points and approach closer to 10,000 it is common to see degradation in performance. If you really need to animate that many points flying around, your best bet is to turn to WebGL and have shaders do the work for you. The regl library provides a nice interface to working with shaders and can be used effectively for this purpose, but that’s a topic for another day!

UPDATE: That blog post has now been written. Check out how to animate 100,000 points in regl for details.

If you want to learn more about regl, Mikola Lysenko, the creator of the library, is speaking at OpenVis Conf this year!

Conclusion

There are a lot of clever ways to refactor this and make it easier to use, but this covers a basic approach to getting animation working in canvas. The core ideas are:

  • a draw function that draws points at their current position
  • layout functions that set target x and y positions
  • storing source and target positions and interpolating between them in a d3-timer

I hope this was helpful! If you have any questions, feel free to leave a comment or contact me on twitter @pbesh.