How to handle pixel-perfect collision detection with rotation?

Does anyone have any ideas how to go about achieving rotational pixel-perfect collision detection with Bitmaps in Android? Or in general for that matter? I have pixel arrays currently but I don't know how to manipulate them based on an arbitrary number of degrees.

I'm not familiar with Android so I don't know what tools you have at your disposal, but I can tell you a way to implement this in general terms. How easy it will be depends on what Android provides for you. You're going to need matrices or at least they'll simplify calculations a lot.

For starters do a bounding box collision check and return immediately if they don't collide in order to avoid further computations. That's logical because if the bounding boxes don't collide it's guaranteed that no pixels will be colliding either.

Afterwards, if a pixel perfect collision check is needed, then the most important point is that you have to perform that check in the same space. This can be done by taking each pixel from sprite A, applying a series of transformations in order to get them into sprite B's local space, and then check if it collides with any pixel in that position on sprite B. A collision happens when both pixels checked are opaque.

So, the first thing you need is to construct a world matrix for each of the sprites. There are probably tutorials online teaching you how to create one, but it should basically be a concatenation of a few simpler matrices in the following order:

Translation(-Origin) * Scale * Rotation * Translation(Position)


The utility of this matrix is that by multiplying a point in local space - and for instance if you get the pixels using a method like bitmap.getPixelAt(10,20) then 10,20 is defined in local space - by the corresponding world matrix will move it into world space:

LocalA * WorldMatrixA -> World
LocalB * WorldMatrixB -> World


And if you invert the matrices you can also go in the opposite direction i.e. transform points from world space into each of the sprite's local spaces depending on which matrix you used:

World * InverseWorldMatrixA -> LocalA
World * InverseWorldMatrixB -> LocalB


So in order to move a point from sprite A's local space into sprite B's local space, you first transform it using sprite A's world matrix, in order to get it into world space, and then using sprite B's inverse world matrix, to get it into sprite B's local space:

LocalA * WorldMatrixA -> World * InverseWorldMatrixB -> LocalB


After the transformation, you check if the new point falls within sprite B's bounds, and if it does, you check the pixel at that location just like you did for sprite A. So the entire process becomes something like this (in pseudocode and untested):

bool PixelCollision(Sprite a, Sprite B)
{
// Go over each pixel in A
for(i=0; i<a.Width; ++i)
{
for(j=0; j<a.Height; ++j)
{
// Check if pixel is solid in sprite A
bool solidA = a.getPixelAt(i,j).Alpha > 0;

// Calculate where that pixel lies within sprite B's bounds
Vector3 positionB = new Vector3(i,j,0) * a.WorldMatrix * b.InverseWorldMatrix;

if(positionB.X<0 || positionB.Y<0 ||
positionB.X>=b.Width || positionB.Y>=b.Height) continue;

// Check if pixel is solid in sprite B
bool solidB = b.getPixelAt(positionB.X, positionB.Y).Alpha > 0;

// If both are solid then report collision
if(solidA && solidB) return true;
}
}
return false;
}

• I like this because it's elegant, but using matrices like this - multiplying a 3x3 matrix per pixel per frame- will introduce some pretty serious performance penalties for any but the smallest bitmaps, especially on most Android devices. – 3Dave Feb 9 '12 at 23:21
• @DavidLively Indeed it will, this an expensive process computationally. And I think even with the matrix calculations being unrolled into regular calculations with trigonometry - possibly leaving out scaling if it's not being used - it would still be pretty much the same. There might be other solutions, but I couldn't think of any. Ultimately the best solution would be to ponder whether pixel perfect collision detection are really necessary at all. And some games that use pixel perfect collisions (like the first Sonic games) abstract the characters into a series of collision points instead. – David Gouveia Feb 9 '12 at 23:35
• good point; I'm wracking my brain trying to come up with an alternate solution that doesn't involve subtracting bitmaps and looking for peaks. There's probably an opportunity for a paper in this somewhere. :) Mantra: optimal vs sufficient... optimal vs sufficient.. – 3Dave Feb 9 '12 at 23:59
• Thanks a lot that is really great explanation. I currently have bounding box collision detection set up and if that occurs then I check pixel overlap between the two bitmaps but only in the overlapping rectangle. This all works great and isn't too processor intensive. The problem occurs when I rotate the image. The pixels themselves are not rotated in the bitmap. I am just drawing a rotated image. So when I continue to check the pixel collision it is still using the old pixels. I like what you said about mapping pixels to world coordinates. This may very well be what I need to do. Thanks!!! – DRiFTy Feb 10 '12 at 2:08
• +1 I've always wondered how the algorith works, Thank you @DavidGouveia – Vishnu Feb 10 '12 at 6:19

While David Gouveia's answer sounds correct, it is not the best solution from a performance point of view. There are several important optimizations you need to do:

1. sort out and avoid unnecessary checks by checking first with a simple circle collision: to get the center and radius of your sprites in any rotation, get the minima and maxima x and y coordinates of all 4 (already rotated) vertices: then you can construct an circle closing in the sprite by:

center = max_x-min_x/2 , max_y-min_y/2