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 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;
}
``````
-
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. – David Lively 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.. – David Lively 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

radius = max(max_x-min_x, max_y-min_y)

2. now you should have not too many candidates to check by rasterizing the already transformed (rotated) images basically by using a simple affine texturemapping algorithm. Basically you keep track of 4 lines per rasterized sprite: 2 lines going from vertex a to the next vertices of your rotated box (b and c) 2 lines going in "bitmap space" from vertex u1/v1 to the next vertices u2/v2 and u3/v3: Note: I googled this image and it shows a triangle, your boxes are just two triangles. It is vital for this algorithm to draw horizontal lines (that's why it is called "rasterizer") to avoid "holes" inside the bitmap due to round off errors. By calculating the lines with a bresenham algorithm, you need for each pixel only 4 additions and 4 compares (and sometimes two additional adds, depending on the slope) What you do is you write your own polygon texturemapper, however without the costly(and difficult to optimize) 3d correction.

3. you can easily reduce the resolution of the collision bitmaps (for example by factor 2) and save even more time. a collision check on half of the resolution shouild be unnoticeable.

4. If you are using graphics accelleration it could be possible to use some kind of HW-accelerated Buffer check(stencil?) to avoid coding the rasterizer by yourself..

The main problem is: Java is not very fast on accessing bitmap data stored in an 2D-array. I would recommend to store the data in a 1-dimensional array to avoid at least 1 indexOutOfBounds check for each access. Also use power-of-2 dimensions(like 64x64, 128x128, etc. By this you can calculate the offset via bitshifting and not multiplication). You can also optimize the second texture access to perform it only if first one has value != 0 (transparent)

All these problems were solved in software rendering engines, it could be useful to look into sourcecode

-