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:
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
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:
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:
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):
|show 2 more comments|
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:
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