# per pixel based collision detection

I was wondering if anyone had any ideas on how to get per pixel collision detection for the android. I saw that the andEngine has great collision detection on rotation as well but couldn't see where the actual detection happened per pixel. Also noticed a couple solutions for java, could these be replicated for use with the Android SDK?

Maybe someone here has a clean piece of code I could look at to help understand what is going on with per pixel detection and also why when rotating it is a different process.

EDIT: Here is something I am working with right now.

public void getBitmapData(Bitmap bitmap1, Bitmap bitmap2){
int[] bitmap1Pixels;
int[] bitmap2Pixels;

    int bitmap1Height = bitmap1.getHeight();
int bitmap1Width = bitmap1.getWidth();
int bitmap2Height = bitmap2.getHeight();
int bitmap2Width = bitmap2.getWidth();
bitmap1Pixels = new int[bitmap1Height * bitmap1Width];
bitmap2Pixels = new int[bitmap2Height * bitmap2Width];

bitmap1.getPixels(bitmap1Pixels, 0, bitmap1Width, 1, 1, bitmap1Width - 1, bitmap1Height - 1);
bitmap2.getPixels(bitmap2Pixels, 0, bitmap2Width, 1, 1, bitmap2Width - 1, bitmap2Height - 1);


}

• First thing to ask yourself is whether you really, really need pixel level collisions. They can be done, but they're not really as needed as you might think, and implementing efficiently requires bit masks and all sorts of fun. – Jari Komppa Mar 19 '11 at 11:19
• Thanks Jari, I wanted to implement some per pixel collision into my game for when the enemy hits the hero sprite because right now the bitmap has some transparent points in front of the hero. I was just hoping someone could explain the steps involved for achieving this. I am already checking if bounding boxes are intersecting and then was going to implement per pixel collision. – pengume Mar 19 '11 at 23:11
• Also really I am just confused on how to check if it is a pixel by pixel collision rather than bounding boxes. Like if you get the non alpha pixels of the enemy and hero but how do you check if those overlap as well. – pengume Mar 19 '11 at 23:13

From what I know, pixel perfect collision detection is done this way :

• Convert two checked objects coordinate into world coordinate
• Get their bounding box, check for intersection
• if intersection occurs, check every pixel from both objects inside the intersection
• if both objects have non-alpha pixels in the same location inside the intersection, then collision is confirmed.

Sorry, I have no code to share, since I haven't write one in java.

But most of the time my game objects doesn't need pixel perfect collision detection. If it is complex enough, I use multiple bounding boxes (circles, usually) to represent the object.

• yeah thinking about it more and more I wouldn't mind per pixel detection but if I can get it to work without the use of it then I'll just implement that way. maybe I'll draw a circle instead of a box for right now and check to see if the enemy hits that. My hero is pretty much circular anyways. Thanks for your answer. – pengume Mar 20 '11 at 4:08

In addition to the other answer, you could speed up the per pixel solution using an octree to have a hierachical approach to being able to quickly reject completely transparent pixels (or regions). It would work best if there were large areas of non-collidable regions of pixels which could be quickly ignored.

You could also have a hierachy of collision primitives, a basic encompassing circle around the whole object, which if colliding you could then drop down to the next level of primitives which could be a number of more accurately placed circles, etc, which more accurately follows the outline of the object. You could in theory allow this to recurse as much as possible, the hierarchy allowing for early outs if a collision isn't detected at a higher level.

• Hey Roger thanks for your answer. Do you have any examples or anything I could take a look at. I am getting stuck at the point where I evaluate the intersecting points to check for a collision of non alpha values. I'll edit my post with some code h=that I have now. Thanks! – pengume Mar 21 '11 at 1:40
• Quadtree, not octree. Octree is for 3D. I don't think you really need a bounding circle for this, as the first level of the quadtree will discard the whole thing if they don't overlap at all. – ggambett Jul 30 '13 at 5:53

The "classic" per pixel collision system assumes that you're not rotating anything, or the rotations of your sprites are fixed.

Next, make bit masks of your sprites. If your sprites are 32x32 pixels, this is pretty simple, as one sprite consts of 32 32-bit words. If the sprites are wider, things get a bit more complicated.

...xx...    ...++...
..xxxx..    ...++...
.xxxxxx.    ++++++++
xxx..xxx    ...++...
.x....x.    ...++...


To check the collision, first do a aabb collision check, and if the boxes overlap, calculate y difference to know which scanlines to compare, and x difference to calculate the shifts required to make the bitmaps overlap.

The actual check is just an AND operation.

...xx...
..xxxx..
.xxxxxx..++...
xxx..xxx.++...
.x....*+++++++
...++...
...++...


If the sprite(s) are bigger than 32x32 pixels, the easiest (but not the most performant) way to solve the collision check is to handle them as groups of 32x32 pixel sprites.

If you're using OpenGL to rotate your sprites, this technique is naturally out. Rasterizing the rotated sprite(s) and doing pixel-by-pixel checking is probably (but not necessarily) prohibitively slow. If you're going that route, no need to hassle with bits, as you'll have to wade through so much data in any case.

You can obviously avoid unnecessary computation by doing rectangle-intersection first.

Say you really want per-pixel intersection, however.

You could create a 1-bit 'hit' mask for all sprites and do an bitwise & op on the overlap. However, for large overlap this can be very expensive.

An approach that worked very well back in the platform game era - and which would work equally well on phones today - is to run-length-encode (RLE) your hit masks. This may also reduce storage.

If your hit mask is a list of RLE-encoded scan-lines you can cheaply do intersection by walking these encoded lines.

I've seen DOS games that go so far as to special-case right-sided intersections and walk those scan-lines backwards!

• +1 On the RLE stuff. Let me see if I get this: instead of walking each pixel in the overlap region to check for collision, instead you are looking at the two individual sprites' RLE-scanline-by-RLE-scanline, and using simple arithmetic to check whether there is an overlap? Is that the approach? (if so, sounds efficient indeed) – Engineer Jul 14 '11 at 23:13