Pixel-Perfect Collision Detection Android

Question

Ok so I am working on a game on Android. I need to implement pixel perfect collision detection. I already have the bounding boxes set up around each of the images, each bounding box is transformed to match the current rotation of the image. That all works great. I also have the pixel data from each bitmap stored in an array. Can someone help me figure out the most efficient way to go about detecting if the pixels overlap? Thanks in advance for any help!

Answer 1

The basic idea is to create a bitmask for each object where you indicate in each pixel if the object is actually there or not. Then you compare each pixel of the bitmasks for the two objects.

You could minimize the number of pixels you need to check by calculating the rectangular area in which the two bounding boxes overlap. The pixels within this area are what you need to check.

Iterate through all of those pixels, and check if the pixel is filled in both objects. If any of them are, then you have a collision.

If your rectangles are aligned with the x/y axis, to find the overlap, find the left, right, top and bottom of the overlap. It would look something like this (I could have screwed up the edge cases, haven't tried this):

int left = max(obj1.left, obj2.left)
int right = min(obj1.right, obj2.right)
int top = min(obj1.top, obj2.top)
int bottom = max(obj1.bottom, obj2.bottom)

for (int x = left; x < right; x++) {
  for (int y = top; y < bottom; y++) {
     if (obj1.isFilled(x,y) && obj2.isFilled(x,y)) {
        return true;
     }
  }
}

Answer 2

I have based my code on Mayra's example and made bitmap pixel collision handling. I hope this will help.

public class CollisionUtil {
    public static boolean isCollisionDetected(Sprite sprite1, Sprite sprite2){
        Rect bounds1 = sprite1.getBounds();
        Rect bounds2 = sprite2.getBounds();

        if( Rect.intersects(bounds1, bounds2) ){
            Rect collisionBounds = getCollisionBounds(bounds1, bounds2);
            for (int i = collisionBounds.left; i < collisionBounds.right; i++) {
                for (int j = collisionBounds.top; j < collisionBounds.bottom; j++) {
                    int sprite1Pixel = getBitmapPixel(sprite1, i, j);
                    int sprite2Pixel = getBitmapPixel(sprite2, i, j); 
                    if( isFilled(sprite1Pixel) && isFilled(sprite2Pixel)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private static int getBitmapPixel(Sprite sprite, int i, int j) {
        return sprite.getBitmap().getPixel(i-(int)sprite.getX(), j-(int)sprite.getY());
    }

    private static Rect getCollisionBounds(Rect rect1, Rect rect2) {
        int left = (int) Math.max(rect1.left, rect2.left);
        int top = (int) Math.max(rect1.top, rect2.top);
        int right = (int) Math.min(rect1.right, rect2.right);
        int bottom = (int) Math.min(rect1.bottom, rect2.bottom);
        return new Rect(left, top, right, bottom);
    }

    private static boolean isFilled(int pixel) {
        return pixel != Color.TRANSPARENT;
    }
}

Answer 3

I changed arcones' code, so the method works with Bitmaps instead of Sprites.

import android.graphics.Bitmap;
import android.graphics.Color;
import android.graphics.Rect;


public class KollisionsErkennung {

/**
 * @param bitmap1 First bitmap
 * @param x1 x-position of bitmap1 on screen.
 * @param y1 y-position of bitmap1 on screen.
 * @param bitmap2 Second bitmap.
 * @param x2 x-position of bitmap2 on screen.
 * @param y2 y-position of bitmap2 on screen.
 */
public static boolean isCollisionDetected(Bitmap bitmap1, int x1, int y1,
        Bitmap bitmap2, int x2, int y2) {

    Rect bounds1 = new Rect(x1, y1, x1+bitmap1.getWidth(), y1+bitmap1.getHeight());
    Rect bounds2 = new Rect(x2, y2, x2+bitmap2.getWidth(), y2+bitmap2.getHeight());

    if (Rect.intersects(bounds1, bounds2)) {
        Rect collisionBounds = getCollisionBounds(bounds1, bounds2);
        for (int i = collisionBounds.left; i < collisionBounds.right; i++) {
            for (int j = collisionBounds.top; j < collisionBounds.bottom; j++) {
                int bitmap1Pixel = bitmap1.getPixel(i-x1, j-y1);
                int bitmap2Pixel = bitmap2.getPixel(i-x2, j-y2);
                if (isFilled(bitmap1Pixel) && isFilled(bitmap2Pixel)) {
                    return true;
                }
            }
        }
    }
    return false;
}

private static Rect getCollisionBounds(Rect rect1, Rect rect2) {
    int left = (int) Math.max(rect1.left, rect2.left);
    int top = (int) Math.max(rect1.top, rect2.top);
    int right = (int) Math.min(rect1.right, rect2.right);
    int bottom = (int) Math.min(rect1.bottom, rect2.bottom);
    return new Rect(left, top, right, bottom);
}

private static boolean isFilled(int pixel) {
    return pixel != Color.TRANSPARENT;
}
}

For my needs it works fast enough.

Answer 4

If anyone of you is interested, I'd like to share the code I wrote:

Important for you to know is that Sprite.getWidth() and Sprite.getHeight() simply return the width/height of the Bitmap that the Sprite holds. You can easily adjust the code for your needs, it should be pretty easy to understand how the code works :)

public static boolean touchesSprite(Sprite s1, Sprite s2) {

    Bitmap b1 = s1.getBmp();
    Bitmap b2 = s2.getBmp();

    int xshift = s2.getX()-s1.getX();
    int yshift = s2.getY()-s1.getY();

    //Test if the Sprites overlap at all
    if((xshift > 0 && xshift > s1.getWidth()) || (xshift < 0 && -xshift > s2.getWidth())) {
        return false;
    }

    if((yshift > 0 && yshift > s1.getHeight()) || (yshift < 0 && -yshift > s2.getHeight())) {
        return false;
    }

    //if they overlap, find out in which regions they do
    int leftx, rightx, topy, bottomy;
    int leftx2, topy2;

    if(xshift >= 0) {
        leftx = xshift;
        leftx2 = 0;

        rightx = Math.min(s1.getWidth(), s2.getWidth()+xshift);
    } else {
        rightx = Math.min(s1.getWidth(), s2.getWidth()+xshift);

        leftx = 0;
        leftx2 = -xshift;
    }

    if(yshift >= 0) {
        topy = yshift;
        topy2 = 0;

        bottomy = Math.min(s1.getHeight(), s2.getHeight()+yshift);
    } else {
        bottomy = Math.min(s1.getHeight(), s2.getHeight()+yshift);

        topy = 0;
        topy2 = -yshift;
    }

    //then compare the overlapping regions,
    //if in any spot both pixels are not transparent, return true

    int ys = bottomy-topy;
    int xs = rightx-leftx;

    for(int x=0; x<xs; x++) {
        for(int y=0; y<ys; y++) {
            int pxl = b1.getPixel(leftx+x, topy+y);
            int pxl2 = b2.getPixel(leftx2+x, topy2+y);

            if(!((pxl & 0xff000000) == 0x0) && !((pxl2 & 0xff000000) == 0x0)) {
                return true;
            }
        }
    }

    return false;
}