per pixel based collision detection

Question

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); 

}

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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!