Pixel Level Collision Detection

quark

There have been a number of questions recently about collision detection between images that ignore transparent pixels. So I decided it might to useful to create a simple function that does the job.

This sketch shows this method in action.

Below is the code for the pixel level collision detection.

The method requires six parameters, for each image - the image object and the screen position for the top-left corner of the image.

// A pixel width an alpha level below this value is
// considered transparent.
final int ALPHALEVEL = 20;

boolean pp_collision(PImage imgA, float aix, float aiy, PImage imgB, float bix, float biy) {
  int topA, botA, leftA, rightA;
  int topB, botB, leftB, rightB;
  int topO, botO, leftO, rightO;
  int ax, ay;
  int bx, by;
  int APx, APy, ASx, ASy;
  int BPx, BPy; //, BSx, BSy;

  topA   = (int) aiy;
  botA   = (int) aiy + imgA.height;
  leftA  = (int) aix;
  rightA = (int) aix + imgA.width;
  topB   = (int) biy;
  botB   = (int) biy + imgB.height;
  leftB  = (int) bix;
  rightB = (int) bix + imgB.width;

  if (botA <= topB  || botB <= topA || rightA <= leftB || rightB <= leftA)
    return false;

  // If we get here, we know that there is an overlap
  // So we work out where the sides of the overlap are
  leftO = (leftA < leftB) ? leftB : leftA;
  rightO = (rightA > rightB) ? rightB : rightA;
  botO = (botA > botB) ? botB : botA;
  topO = (topA < topB) ? topB : topA;

  // P is the top-left, S is the bottom-right of the overlap
  APx = leftO-leftA;   
  APy = topO-topA;
  ASx = rightO-leftA;  
  ASy = botO-topA-1;
  BPx = leftO-leftB;   
  BPy = topO-topB;

  int widthO = rightO - leftO;
  boolean foundCollision = false;

  // Images to test
  imgA.loadPixels();
  imgB.loadPixels();

  boolean pixelAtransparent, pixelBtransparent = true;

  // Get start pixel positions
  int pA = (APy * imgA.width) + APx;
  int pB = (BPy * imgB.width) + BPx;

  ax = APx; 
  ay = APy;
  bx = BPx; 
  by = BPy;
  for (ay = APy; ay < ASy; ay++) {
    bx = BPx;
    for (ax = APx; ax < ASx; ax++) {
      pixelAtransparent = alpha(imgA.pixels[pA]) < ALPHALEVEL;
      pixelBtransparent = alpha(imgB.pixels[pB]) < ALPHALEVEL;

      if (!pixelAtransparent && !pixelBtransparent) {
        foundCollision = true;
        break;
      }
      pA ++;
      pB ++;
      bx++;
    }
    if (foundCollision) break;
    pA = pA + imgA.width - widthO;
    pB = pB + imgB.width - widthO;
    by++;
  }
  return foundCollision;
}

redraw

it's pretty fast quarks! I wonder if it would response the same way in more complex games/things thanks for sharing!

redraw

I hope that. Now I see pixel detection starts only if images overlap each other, that's fine

quark

Now I see pixel detection starts only if images overlap each other, that's fine

It also only tests the pixels in the overlap area and stops as soon as it detects a collision. So it is quite fast provided the image is cropped to remove 'transparent borders'.

Berkmann18

@quark do you know a good method/function for geometric forms collision detection ?

quark

geometric forms?

See this post

and this webpage