Pixel Perfect Collision Detection in HTML5 Canvas

Question

Hi,

I want to check a collision between two Sprites in HTML5 canvas. So for the sake of the discussion, let's assume that both sprites are IMG objects and a collision means that the alpha channel is not 0. Now both of these sprites can have a rotation around the object's center but no other transformation in case this makes this any easier.

Now the obvious solution I came up with would be this:

• calculate the transformation matrix for both
• figure out a rough estimation of the area where the code should test (like offset of both + calculated extra space for the rotation)
• for all the pixels in the intersecting rectangle, transform the coordinate and test the image at the calculated position (rounded to nearest neighbor) for the alpha channel. Then abort on first hit.

The problem I see with that is that a) there are no matrix classes in JavaScript which means I have to do that in JavaScript which could be quite slow, I have to test for collisions every frame which makes this pretty expensive. Furthermore I have to replicate something I already have to do on drawing (or what canvas does for me, setting up the matrices).

I wonder if I'm missing anything here and if there is an easier solution for collision detection.

Answer 1

I'm not a javascript coder but I'd imagine the same optimisation tricks work just as well for Javascript as they do for C++.

Just rotate the corners of the sprite instead of every pixel. Effectively you would be doing something like software texture mapping. You could work out the x,y position of a given pixel using various gradient information. Look up software texture mapping for more info.

If you quadtree decomposed the sprite into "hit" and "non-hit" areas then you could effectively check to see if a given quad tree decomposition is all "non-hit", "all hit" or "possible hit" (ie contains hits and non-hit pixels. The first 2 are trivial to pass through. In the last case you then go down to the next decomposition level and repeat the test. This way you only check the pixels you need too and for large areas of "non-hit" and "hit" you don't have to do such a complex set of checks.

Anyway thats just a couple of thoughts.

Answer 2

I have to replicate something I already have to do on drawing

Well, you could make a new rendering context, plot one rotated white-background mask to it, set the compositing operation to lighter and plot the other rotated mask on top at the given offset.

Now if there's a non-white pixel left, there's a hit. You'd still have to getImageData and sift through the pixels to find that out. You might be able to reduce that workload a bit by scaling the resultant image downwards (relying on anti-aliasing to keep some pixels non-white), but I'm thinking it's probably still going to be quite slow.

I have to test for collisions every frame which makes this pretty expensive.

Yeah, I think realistically you're going to be using precalculated collision tables. If you've got space for it, you could store one hit/no hit bit for every combination of sprite a, sprite b, relative rotation, relative-x-normalised-to-rotation and relative-y-normalised-to-rotation. Depending on how many sprites you have and how many steps of rotation or movement, this could get rather large.

A compromise would be to store the pre-rotated masks of each sprite in a JavaScript array (of Number, giving you 32 bits/pixels of easily &&-able data, or as a character in a Sring, giving you 16 bits) and && each line of intersecting sprite masks together.

Or, give up on pixels and start looking at eg. paths.