Needles, Haystacks, and the Canvas API

Rendering and animating a lot of objects while maintaining the interactivity we want to deliver is one challenge we sometimes face as creators of data visualizations. Dominikus Baur explores the axis of performance vs. developer pain in his OpenVis 2015 talk. In summary, higher level APIs such as the DOM and SVG offer a rich API for interaction but have a lower performance ceiling when compared to rendering APIs such as Canvas or WebGL. However, when we use the more performant rendering technologies, all the burden of handling interaction falls on the creators’ shoulders.

A recent conversation around this trade-off with another developer brought to mind a technique for implementing mouse interaction when using HTML5 Canvas. In this post, I will demonstrate this technique and provide some code snippets you can adapt to your visualizations if you are in a similar situation where you want to render lots of points in a visualization without sacrificing performance.

First, let’s demonstrate the issue. Here, representing our visualization in this post, is a small sketch of some translucent boxes bouncing around in a container. It is implemented using SVG and d3.

SVG Based Rendering

Source code

When you click on a box, its color will change to yellow. Drag the count slider up to render more boxes, and watch what happens to the frames per second graph on the right as well as the performance of the animating boxes.

By the time we are up to 2000 boxes, our frames per second has dropped to 12, at 5000 boxes we are down to about 3 frames per second. This also slows down the website or application that contains it.

Note that this sluggishness is not a bottleneck in d3, but comes from our use of SVG. You can’t have much more than a thousand or so SVG elements moving around on the screen before it becomes sluggish. However, programming our click interaction is relatively straightforward due to the DOM API. It boils down to the following code (and in particular the last 3 lines):

nodes.enter()
  .append('rect')
  .attr('class', 'node')
  .on('click', function(d){
    // Here we set the render color associated with this data to orange.
    d.renderCol = 'Orange';
  });

Fantastic! And using d3’s wonderful data binding, we can easily access data associated with this node.

But I have lot of data!

But what if we are in a position where we need to render a lot of discrete objects, on the order of thousands, and still support mouse interaction with them? What can we do?

One of the things we can do is switch rendering technologies. HTML5 Canvas is a 2D immediate mode rendering API that is much more low level, but more performant than SVG.

Note: There are other important differences that are discussed in the video linked above.

Importantly for this discussion: there are no interaction handlers built into Canvas for the geometry you draw. So how can we add our own?

First, a demonstration of the technique, and then we will discuss it below:

Canvas Based Rendering

Source code

In this sketch, which is functionally equivalent to the first, you will notice that when you click on the nodes they also change color. You can also drag the count slider all the way to about 6000 boxes and maintain a frame rate greater than 30. At 20,000 nodes, we get a framerate of about 12, i.e. we have an order of magnitude more boxes for the same frame rate as our previous sketch which only rendered 2000 boxes at the same frame rate.

You will also notice a few extra controls. If you click on the showHiddenCanvas check button, you will see another very similar looking configuration of boxes, except they are very colorful. What is going on here?

‘Picking’ using an offscreen color buffer

The basic problem of trying to figure out what we’ve clicked on is known as ‘picking’ in computer graphics circles, and here we are using an invisible offscreen canvas to help us do this. The technique is to redraw all the geometry we want to interact with into an invisible layer. At the same time, we render each discrete element in a unique color and store that mapping. When a user clicks on the original canvas, we can just look up the color in the hidden canvas and map that to a node on the original canvas. This may seem expensive, but as the example above demonstrates, it works out!

The full source code is in the link above, but let’s break out some of the key parts for closer inspection.

First, we make our two canvases:

var mainCanvas = document.createElement("canvas");
var hiddenCanvas = document.createElement("canvas");
mainCanvas.setAttribute('width',  width);
mainCanvas.setAttribute('height', height);
hiddenCanvas.setAttribute('width', width);
hiddenCanvas.setAttribute('height', height);
hiddenCanvas.style.display = 'none'; //hide the second one.

// We also make a map/dictionary to keep track of colors associated
// with node.
var colToNode = {};

And here is our render function. In the full source code, it is called in a loop using requestAnimationFrame:

function draw(data, canvas, hidden) {
  var ctx = canvas.getContext('2d');
  ctx.clearRect(0, 0, width, height);

  //
  // Loop through our data
  //
  var numElements = data.length;
  for(var i = 0; i < numElements; i++) {
    var node = data[i];

    if(node.renderCol) {
      // Render clicked nodes in the color of their corresponding node
      // on the hidden canvas.
      ctx.fillStyle = node.renderCol;
    } else {
      ctx.fillStyle = 'RGBA(105, 105, 105, 0.8)';
    }

    //
    //  If we are rendering to the hidden canvas each element
    // should get its own color.
    //
    if(hidden) {
      if(node.__pickColor === undefined) {
        // If we have never drawn the node to the hidden canvas get a new
        // color for it and put it in the dictionary. genColor returns a new color
        // every time it is called.
        node.__pickColor = genColor();
        colToNode[node.__pickColor] = node;
      }
      // On the hidden canvas each rectangle gets a unique color.
      ctx.fillStyle = node.__pickColor;
    }

    // Draw the actual shape
    drawMark(ctx, node);
  }
}

// drawMark in this instance is simply the following
function drawMark(ctx, node) {
  // Draw the actual rectangle
  ctx.fillRect(node.x, node.y, node.width, node.height);
}

And here is how we implement the mouse interaction:


// Listen for clicks on the main canvas mainCanvas.addEventListener("click", function(e){ // We actually only need to draw the hidden canvas when // there is an interaction. This sketch can draw it on // each loop, but that is only for demonstration. draw(data, hiddenCanvas, true); //Figure out where the mouse click occurred. var mouseX = e.layerX; var mouseY = e.layerY; // Get the corresponding pixel color on the hidden canvas // and look up the node in our map. var ctx = hiddenCanvas.getContext("2d"); // This will return that pixel's color var col = ctx.getImageData(mouseX, mouseY, 1, 1).data; //Our map uses these rgb strings as keys to nodes. var colString = "rgb(" + col[0] + "," + col[1] + ","+ col[2] + ")"; var node = colToNode[colString]; if(node) { // We clicked on something, lets set the color of the node // we also have access to the data associated with it, which in // this case is just its original index in the data array. node.renderCol = node.__pickColor; //Update the display with some data controls.lastClickedIndex = node.index; lastClicked.updateDisplay(); animateHidden.updateDisplay(); console.log("Clicked on node with index:", node.index, node); } });

But wait—there’s more!

This is not the only way to figure out what you have clicked on in a canvas. For example, you could calculate whether the mouse coordinates intersect with your drawn geometry, and this can be highly performant, depending on the geometry and how you organize your data.

While other options do exist, I do appreciate how this technique is agnostic to geometry: you don’t have to know how to calculate whether a point intersects with your shape, which can be advantageous if your elements are complex shapes.

This is why the code above splits out the drawMark function. It can be pretty much anything (and can be easily adapted if your elements have multiple colors), and the rest of the code won’t care.

This ‘color picking’ technique also extends to 3D rendering, which was the original context where I learned this technique.

Final thoughts

In many situations where you have a lot of data, some form of aggregation or filtering to reduce the data will be a better approach than trying to render it all as discrete elements. However, if you find yourself needing to do the latter, I hope this technique can help you achieve your rendering and data viz goals! Again, here is the full source of the canvas based solution. Feel free to share if this is useful for you!

Comments

Contact Us

We'd love to hear from you. Get in touch!

Phone

+1 617-283-2807

Mail

P.O. Box 961436
Boston, MA 02196