JavaScript Per-Pixel HTML5 Canvas Image Collision Detection

Posted: by Joe under Under the Hood

Recently Play My Code gained per-pixel image collision detection. Here is a small demo of it in action:

Like the previous blog post about our image tinting implementation, here’s some behind the scenes information on how we added pixel-perfect collision detection to Play My Code- using a different approach to the usual algorithm.

Before We Begin

First I want to clarify that this is not an image to image collision detection, but between two ‘ImageData’ objects. The ImageData objects represents the pixels behind an image.

You can convert an image to imageData by drawing it to a canvas, and then calling ‘getImageData’ on the canvas object to retrieve its pixels. The code to do that can be found online.

The Initial Code

Some setup code is needed first inside the collision function; we need to round the locations to ensure they are integers, and get the dimensions of our image data.

Developers tend to work with a location referring either to the top left of the image or its centre, and the last ‘isCentred’ parameter is to specify which mode we are in. If we are centred, then we need to move the locations to the top left corner. Otherwise we can just leave them.

/**
 * @param first An ImageData object from the first image we are colliding with.
 * @param x The x location of 'first'.
 * @param y The y location of 'first'.
 * @param other An ImageData object from the second image involved in the collision check.
 * @param x2 The x location of 'other'.
 * @param y2 The y location of 'other'.
 * @param isCentred True if the locations refer to the centre of 'first' and 'other', false to specify the top left corner.
 */
function isPixelCollision( first, x, y, other, x2, y2, isCentred )
{
    // we need to avoid using floats, as were doing array lookups
    x  = Math.round( x );
    y  = Math.round( y );
    x2 = Math.round( x2 );
    y2 = Math.round( y2 );

    var w  = first.width,
        h  = first.height,
        w2 = other.width,
        h2 = other.height ;

    // deal with the image being centred
    if ( isCentred ) {
        // fast rounding, but positive only
        x  -= ( w/2 + 0.5) << 0
        y  -= ( h/2 + 0.5) << 0
        x2 -= (w2/2 + 0.5) << 0
        y2 -= (h2/2 + 0.5) << 0
    }

Next we need to work out the area within the two images that overlaps. To do this we work out the top-left corner, held in xMin and yMin, and the bottom right corner, held in xMax and yMax. If xMin is greater then xMax, or yMin is greater then yMax, then there is not an overlapping area and no collision has occurred. This means we can leave the function early.

// find the top left and bottom right corners of overlapping area
var xMin = Math.max( x, x2 ),
    yMin = Math.max( y, y2 ),
    xMax = Math.min( x+w, x2+w2 ),
    yMax = Math.min( y+h, y2+h2 );

// Sanity collision check, we ensure that the top-left corner is both
// above and to the left of the bottom-right corner.
if ( xMin >= xMax || yMin >= yMax ) {
    return false;
}

At this stage we can prepare for the actual per-pixel collision checks. We work out the size of this overlapping area, which is a simple matter of subtracting the larger value from the smaller one, and get the pixel data out from the ImageData objects.

var xDiff = xMax - xMin,
    yDiff = yMax - yMin;

// get the pixels out from the images
var pixels  = first.data,
    pixels2 = other.data;

The Linear Scan

Now for the actual per-pixel collision check, which for the sake of the article I am referring to as a ‘linear scan’. We simply iterate across all pixels in order, across the area that overlaps…

for ( var pixelX = xMin; pixelX < xMax; pixelX++ ) {
    for ( var pixelY = yMin; pixelY < yMax; pixelY++ ) {
        // do the pixel check here
    }
}

We need to retrieve the pixel from pixels and pixels2 at each location in the for-loop. To do this, the location must be translated in three ways.

First, we need to move from pixelX/Y to the location in the image. Second, pixels is a 1-dimensional array of pixels, so we need to change from an x/y value to a position in the flat array. Third, the pixels array holds each pixel as 4 separate components; red, green, blue and alpha. So for example the 10th pixel starts at the 40th element, with 40 being the red, 41 being the green, 42 for blue and 43 for alpha (and 44 being red for the next pixel that follows).

Translating this location is:

var pixel1 = ((pixelX-x ) + (pixelY-y )*w )*4 + 3 ;
var pixel2 = ((pixelX-x2) + (pixelY-y2)*w2)*4 + 3 ;

Next we lookup the component and check if it is not zero, in both sets of pixels. If it is then there is a collision:

if ( pixels[pixel1] !== 0 && pixels2[pixel2] !== 0 ) {
    return true;
}

This can also be inlined directly to:

if (
        ( pixels [ ((pixelX-x ) + (pixelY-y )*w )*4 + 3 ] !== 0 ) &&
        ( pixels2[ ((pixelX-x2) + (pixelY-y2)*w2)*4 + 3 ] !== 0 )
) {
    return true;
}

Resulting in…

for ( var pixelX = xMin; pixelX < xMax; pixelX++ ) {
    for ( var pixelY = yMin; pixelY < yMax; pixelY++ ) {
        if (
                (pixels [ ((pixelX-x ) + (pixelY-y )*w )*4 + 3 ] !== 0) &&
                (pixels2[ ((pixelX-x2) + (pixelY-y2)*w2)*4 + 3 ] !== 0)
        ) {
            return true;
        }
    }
}

return false;

That’s it, the whole scan, with an added return false. If the algorithm reaches that then there is definitely no collision.

Could It Be Faster?

The linear scan searches all pixels in the top of the image collision area first, before searching all pixels in the middle, and then all of the remaining pixels at the bottom. This is because it just checks all pixels in the order they are stored.

In the worst case scenario it will search the whole area, but if the collision is at the bottom then this will be almost as expensive. A collision in the middle only cuts this cost in half.

Ideally a collision in the middle, edges or the bottom should not be much more expensive then a collision at the top. So to improve the algorithm I am going to make a presumption about how most collisions occur. If one occurs I would predict that multiple pixels have collided, especially if the collision area is very large.

This presumption implies that I don’t have to care about being too precise when scanning across the colliding area, and that a full scan should only be made if my presumption is wrong.

To implement this, instead of moving across the overlapping area by just 1 pixel at a time, I will move by much larger increments. For lack of a better name, I am going to refer to this as the ‘incremental scan’.

For the size of the increment, I have picked a third or just greater (achieved through the fast ceiling code below). A third is picked so that we check one side, then the middle and then the other side in turn (and top, then middle and then the bottom along the y-axis). The ceiling code is to prevent us splitting the area into 4 sections; 3 large sections and 1 thin strip of pixels down the right or bottom edge.

A base offset is also used as a starting point, which allows us to simply repeat the same search multiple times, increasing the offset on each search.

// Work out the increments,
// it's a third, but ensure we don't get a tiny slither of an area for the last iteration
var incX = xDiff / 3.0;
var incY = yDiff / 3.0;

// fast ceil
incX = (~~incX === incX) ? incX : (incX+1 | 0 );
incY = (~~incY === incY) ? incY : (incY+1 | 0 );

for ( var offsetY = 0; offsetY < incY; offsetY++ ) {
    for ( var offsetX = 0; offsetX < incX; offsetX++ ) {
        for ( var pixelY = yMin+offsetY; pixelY < yMax; pixelY += incY ) {
            for (var pixelX = xMin+offsetX; pixelX < xMax; pixelX += incX){
                if (
                    (pixels [((pixelX-x ) + (pixelY-y )*w )*4+3] !== 0) &&
                    (pixels2[((pixelX-x2) + (pixelY-y2)*w2)*4+3] !== 0)
                ) {
                    return true;
                }
            }
        }
    }
}

The algorithm above is written so that incX and incY can be changed to any increment, and the algorithm deals with it. So for example you could experiment with a quarter, fifth, or a fixed value.

If incX and inxY were always going to be a third, then you could remove the two inner for-loops and expand them into 9 direct pixel lookups (with some code to ensure some of those locations are legal).

The downside is that the worst case scenario, having to check all pixels for a collision, is now more expensive. But collisions on the bottom, the sides and in the middle are now much faster. This is because the amount of iteration required to find a collision, is on average, dramatically reduced.

Summary, and Further Optimisations

I have built some crude benchmarks where I counted how many iterations are performed, shows this reducing the number of iterations by as much as a factor of 350. However in the majority of cases it is iterating around 20 to 100 times less.

In short, we are talking about checking 10s of pixels instead of 100s or 1000s! So I’m very pleased with this approach.

I am in no doubt that there will be more ways to make this more efficient. You could do this through simplifying my code, so it performs less calculations, but also if you devise a more intelligent route for searching the image. For example you could search around the edge of the image working inwards, or search from the middle outwards. On both of those you could also add in an ‘increment’, so it searches a larger area in less time.

It would also be interesting to experiment with other ways to scan across the overlapping area, such as in a cross or x shape, and then just perform a liner scan if that search fails.

Finally the best optimization is to not perform the check at all, such as using a more precise bounding box first (such as a circle or ellipse). This would allow you to detect that there was no collision earlier in the process, or you could use that instead of a per-pixel check.

All Code

Finally here is all the code combined together. It uses the linear scan on very small areas, and the more complex skipping approach on larger ones.

/**
 * @author Joseph Lenton - PlayMyCode.com
 *
 * @param first An ImageData object from the first image we are colliding with.
 * @param x The x location of 'first'.
 * @param y The y location of 'first'.
 * @param other An ImageData object from the second image involved in the collision check.
 * @param x2 The x location of 'other'.
 * @param y2 The y location of 'other'.
 * @param isCentred True if the locations refer to the centre of 'first' and 'other', false to specify the top left corner.
 */
function isPixelCollision( first, x, y, other, x2, y2, isCentred )
{
    // we need to avoid using floats, as were doing array lookups
    x  = Math.round( x );
    y  = Math.round( y );
    x2 = Math.round( x2 );
    y2 = Math.round( y2 );

    var w  = first.width,
        h  = first.height,
        w2 = other.width,
        h2 = other.height ;

    // deal with the image being centred
    if ( isCentred ) {
        // fast rounding, but positive only
        x  -= ( w/2 + 0.5) << 0
        y  -= ( h/2 + 0.5) << 0
        x2 -= (w2/2 + 0.5) << 0
        y2 -= (h2/2 + 0.5) << 0
    }

    // find the top left and bottom right corners of overlapping area
    var xMin = Math.max( x, x2 ),
        yMin = Math.max( y, y2 ),
        xMax = Math.min( x+w, x2+w2 ),
        yMax = Math.min( y+h, y2+h2 );

    // Sanity collision check, we ensure that the top-left corner is both
    // above and to the left of the bottom-right corner.
    if ( xMin >= xMax || yMin >= yMax ) {
        return false;
    }

    var xDiff = xMax - xMin,
        yDiff = yMax - yMin;

    // get the pixels out from the images
    var pixels  = first.data,
        pixels2 = other.data;

    // if the area is really small,
    // then just perform a normal image collision check
    if ( xDiff < 4 && yDiff < 4 ) {
        for ( var pixelX = xMin; pixelX < xMax; pixelX++ ) {
            for ( var pixelY = yMin; pixelY < yMax; pixelY++ ) {
                if (
                        ( pixels [ ((pixelX-x ) + (pixelY-y )*w )*4 + 3 ] !== 0 ) &&
                        ( pixels2[ ((pixelX-x2) + (pixelY-y2)*w2)*4 + 3 ] !== 0 )
                ) {
                    return true;
                }
            }
        }
    } else {
        /* What is this doing?
         * It is iterating over the overlapping area,
         * across the x then y the,
         * checking if the pixels are on top of this.
         *
         * What is special is that it increments by incX or incY,
         * allowing it to quickly jump across the image in large increments
         * rather then slowly going pixel by pixel.
         *
         * This makes it more likely to find a colliding pixel early.
         */

        // Work out the increments,
        // it's a third, but ensure we don't get a tiny
        // slither of an area for the last iteration (using fast ceil).
        var incX = xDiff / 3.0,
            incY = yDiff / 3.0;
        incX = (~~incX === incX) ? incX : (incX+1 | 0);
        incY = (~~incY === incY) ? incY : (incY+1 | 0);

        for ( var offsetY = 0; offsetY < incY; offsetY++ ) {
            for ( var offsetX = 0; offsetX < incX; offsetX++ ) {
                for ( var pixelY = yMin+offsetY; pixelY < yMax; pixelY += incY ) {
                    for ( var pixelX = xMin+offsetX; pixelX < xMax; pixelX += incX ) {
                        if (
                                ( pixels [ ((pixelX-x ) + (pixelY-y )*w )*4 + 3 ] !== 0 ) &&
                                ( pixels2[ ((pixelX-x2) + (pixelY-y2)*w2)*4 + 3 ] !== 0 )
                        ) {
                            return true;
                        }
                    }
                }
            }
        }
    }

    return false;
}

2 Responses to JavaScript Per-Pixel HTML5 Canvas Image Collision Detection

Steven Wittens

It would be much less confusing if you included a diagram of your scanning order. The code is quite hard to picture without comments. Ultimately, your scattered scan is a particular optimization for shapes that stick out at those critical points. But it still results in an O(n) algorithm where n = overlapping pixels, and you can easily make shapes that defy any scanning pattern. Instead, you could try integral images (aka summed area tables), You can use them to integrate across any rectangular area just by looking up the 4 corners and adding up the values with appropriate signs. If you make an integral image of an opacity map, you can determine if an image has any solid pixels in any rectangular area. You would start with the whole area of overlap, check if both shapes are solid in it, and do an early exit if not. You could then recursively subdivide to iteratively narrow down the overlapping areas, stopping at arbitrary granularity. This would still have pathological cases, but should work pretty well for most cases.

Joe

Although it is still O(n), when a collision does occur, on average the time complexity is dramatically reduced. But your idea is brilliant, so I might implement it in a follow up post. Thanks!

Leave a Response

Your email address will not be published. Required fields are marked *