HTML5 canvas: Advanced image picking

Let’s take a look at some more advanced ways to do picking with HTML5 canvas for game development. In this article, we’ll cover two techniques to address problems with pixel-perfect picking; using convex hulls, and using grid binning.

Advanced data structures can accelerate our picking code, while in some cases, sacrificing resolution perfection.

Using convex hulls for picking

As discussed in the last article, Pixel-Perfect picking can increase the memory footprint, and potential performance burden for slower devices. For example, if we had a 1024x1024 image, that may only be 64k in PNG form, but once we fetch it to main memory, it’s now 4MB. There’s really no (good) way around this, since the getImageData function on canvas returns RGBA data uncompressed, even if we pass in a grayscale image, we’d get the full pixel footprint.

Ideally, it would be great to get a lower-memory representation of the image, without having to store the whole thing in memory. And to that degree, we’re going to introduce the concept of using Convex Hulls for picking.

Effectively, a convex hull is a minimum representation of the shape of our sprite; Once the mouse is pressed, we’ll test the mouse-point against the convex hull of sprite instances to determine if it’s inside, or outside of a target object.
We will lose some resolution on this process; that is, our results won’t be pixel-perfect any longer, but there’s a whole separate discussion about how precise your picking code needs to be, especially on mobile, where pixels are (generally) smaller than peoples’ fingers.

Generating the convex hull

Generating a convex hull is should be done offline, ahead of time, so that we can reduce the loading time for our HTML5 game. As such, I threw together a simple C++ app that loads a sprite, calculates its convex hull, and outputs JSON data that we include in the HTML file. Your mileage may vary.

I’ll spare you walking through the C++ details here, as the code itself is simple. It opens an image and calculates, for each scan-line what the min/max pixels are that represent alpha boundaries. From there, we use a modified QHull algorithm to determine what the maximum convex hull is for the set of spatial points.

The hull points are dumped to individual files, which for simplicity, I've manually added the hull data to the HTML file :

var cHullData=[
{"name":"0.png", "hull":[{"x":0,"y":16}, {"x":1,"y":15}, {"x":31,"y":0}, {"x":34,"y":0}, {"x":64,"y":15}, {"x":65,"y":16}, {"x":65,"y":25}, {"x":64,"y":26}, {"x":34,"y":41}, {"x":31,"y":41}, {"x":1,"y":26}, {"x":0,"y":25}, {"x":0,"y":16}]},
//etc. etc.

Hull generation process. Per-scan-line we find the min-max pixels for that row, and toss those at a convex hull generator.

Doing picking against the convex hull

To transition from per-pixel picking to hull picking, we need to make a few small changes. Firstly, a sprite prototype needs to load the hull data, rather than fetching the image pixel data. This is an easy task, as the C++ app will spit out the image name for a hull, so that when an image loads, we can look up with the proper hull is for the image.

SpriteProto = Class.extend({
//...

load : function(filename,w,h)
{
//...

var img = new Image();
img.onload = function(){

 targetSpriteProto.imgHandle = img;
 for(var u =0; u < cHullData.length; u++)
 {
  var thull = cHullData[u];
  if(thull.name == filename)
  {
   targetSpriteProto.hullData = cHullData[u].hull;
   break;
  }
 } 
}
img.src = filename;

To determine if a mouse click (ie point) is inside of our new convex polygon hull, we utilizing a method of point in polygon testing known as ray casting which performs it’s test by casting a line through the 2D polygon, through the point in question. For each line that our ray intersects, we toggle a boolean value to determine if we’re in or out of the polygon. The simplistic algorithm I used in the source code came from here.

SpriteProto = Class.extend({
//...
//--------------
isPixelContained:function(lclx,lcly)
{
 var inPoly = false;
 var numPoints = this.hullData.length;
 var j = numPoints-2;
 var latLng={x:lclx,y:lcly};
  
 for(var i=0; i < numPoints; i++)
 {
  
  var vertex1 = this.hullData[i];
  var vertex2 = this.hullData[j];

  if ((vertex1.x < latLng.x && vertex2.x >= latLng.x) || (vertex2.x < latLng.x && vertex1.x >= latLng.x) )
  {
   if (vertex1.y + (latLng.x - vertex1.x) / (vertex2.x - vertex1.x) * (vertex2.y - vertex1.y) < latLng.y)
   {
    inPoly = !inPoly;
   }
  }
  j=i;
 }
 return inPoly;
 
}

An example of ray casting to determine if a point is in a polygon. The line through the polygon an even number of times, signaling that the point is not inside the polygon boundaries.

Caveats

As mentioned, this method will reduce the overall memory footprint for your data significantly, and on some platforms can have the added benefit of faster execution for a given pick operation.

One down side is that this process doesn't fit well into a pipeline for atlases; You’ll need to calculate the convex hulls of your loose sprites before placing them into your atlas. Of course the lower memory performance comes at the cost of less resolution, something that you should consider before adopting this technique.

Faster picking via bucketing

Let’s say you’re complex app, and have 4096 images in flight when a user clicks. Obviously, you’d want to reduce the number you did a pixel or convex-hull test on, and although a simple bounding-box test will be the quickest to implement, you still end up touching a lot of items that aren't even remotely near the point in question.

The solution to this is to introduce a  spatial acceleration structure to our canvas; A process which organizes / separates our sprites spatially, such that we speed up spatial tests by only referencing items which are reasonably co-located. There’s lots of variants for SAS which have pros, cons, and lots of trade-offs, and for our purposes, we will use a very simplistic 2D binning algorithm, which will divide our canvas into a grid of cells; each cell will contain a list of objects which touch that cell, allowing a sprite to be listed in multiple cells.

Our bucket Grid class will effectively create a 2D array, of arrays, such that when a sprite is spawned, we calculate what grid cells it overlaps, and add a pointer to this instance to each of those cell’s lists.

BucketGrid = Class.extend({
 tileSize:16,
 numXTiles:0,
 numYTiles:0,
 tileData:null,
 
 init:function()
 {
  this.tileData = new Array();
  //16pixels is an arbitrary number from testing.
  this.tileSize = 16;
  this.numXTiles= 512 / this.tileSize; //512 = canvas size
  this.numYTiles= 512 / this.tileSize;
  
  this.tileData.length = this.numXTiles * this.numYTiles;
  for(var k =0; k < this.tileData.length;k++)
   this.tileData[k] = new Array();
 },

Marking a sprite instance on the grid is pretty simple, we simply run some math on the corners of the sprite to calculate the min/max boundaries of it, and what tiles those boundaries fall into; and for each grid cell, we add the sprite to the containing list.

//--------------
 markInstanceInAccelGrid:function(sp)
 {
  var gridminX = Math.floor(sp.pos.x / this.tileSize);
  var gridmaxX = Math.floor((sp.pos.x + sp.size.w) / this.tileSize);
  var gridminY = Math.floor(sp.pos.y / this.tileSize);
  var gridmaxY = Math.floor((sp.pos.y + sp.size.h) / this.tileSize);
 
  //we cheat here, knowing that our rand() placement doesn’t allow neg numbers
  if(gridmaxX >= this.numXTiles) gridmaxX = this.numXTiles-1;
  if(gridmaxY >= this.numYTiles) gridmaxY = this.numYTiles-1;
  
  for(var y = gridminY; y <=gridmaxY; y++)
  {
   var idx = y*this.numXTiles;
   for(var x = gridminX; x <=gridmaxX; x++)
   {
    this.tileData[idx+x].push(sp);
   }
  }
 },

This makes finding entities extremely quick, because we've already pre-sorted the environment. When a mouse-click comes in, we simply find the bucket it resides in, and return the list of entities that we've already calculated.

//--------------
 getEntsForPoint:function(x,y)
 {
  var gridminX = Math.floor(x / this.tileSize);
  var gridminY = Math.floor(y / this.tileSize);
  var idx = gridminX + gridminY*this.numXTiles;
  var ents = this.tileData[idx];
  return ents;
 }
});

Which makes modification to our existing code very nice and tidy

//--------------
function findClickedSprite(x,y)
{
 
 var alphaThreshold = 50;
 var pickedSprite = null;
 var tgtents = acclGrid.getEntsForPoint(x,y);

The acceleration grid reduces performance overhead by reducing the number of times the inner loop is called, regardless of how many sprites we have universally, this bucketing will only care about what sprites reside in a grid cell. An easy trade-off in bang-for-the-buck; We didn't have to derail ourselves by worrying how JavaScript is handling the math for convex hulls, or the array-access times for pixel-perfect picking. It’s a simple technique that can be used for static and dynamic environments.

Closing thoughts

Hopefully, you've got enough information from these past two articles to implement a very fast, efficient picking system in HTML5 canvas. note that there’s lots of other improvements you could continue on with; For example, having a separate Spatial Grid for dynamic vs. static objects; Compressing the Hull data for faster load times; and even caching click results for grid cells. Go forth and pick stuff!

Source Code

You can find the source code to this article on my github. It’s fairly simple, and shows how to use the polygon system, alongside bucketing.

~Main

You can find Colt McAnlis here: