android - 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.

Answer

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    {
        for(j=0; 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 it's outside bounds skip to the next pixel
            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;
}