Chris Taylor

My foray into XNA : Basic Pixel Perfect Collision Detection

So I decided to give XNA a quick spin. Now I am not a game developer, not even an aspiring game developer, but I generally take anything new for a drive just to familiarize myself with it.

I was pleasantly surprised, in about 10 minutes I have objects flying around the screen in all directions and that was written entirely from scratch using only the initially wizard. The 2D stuff is really easy to get started with, I have not ventured into the 3D side yet.

Anyway, once I had all these object flying around I decided to do some basic collision detection to test when they collide. I wanted to go further than just bounding box checks; I wanted pixel perfect collision detection, the kind that reports collisions on when the pixels of one image collide with the pixels of another.

To optimize the collision detection the detection is performed in two stages.

1. Check for potential collisions using the bounding box

2. If test 1 revealed a potential collision perform a pixel level comparison of the overlapping areas of the two textures.

Before I get started I first want to define some simplified terminology that I will be using.

Texture – Represents the graphical information required to render a Sprite.

Texture co-ordinate space – Rectangle defining the size of the texture. A texture that is 32x32 will have texture co-ordinate space (0, 0, 32, 32).

Sprite – A graphical object painted with a texture at a location defined by the sprite co-ordinates.

Sprite co-ordinates – Rectangle representing the space occupied by the sprite in the game.

Now back to the tests, test 1 is to check for the potential collision by checking for a overlap between the is easily accomplished using the following function which compares to rectangles and returns true if they overlap.

public static bool Intersect(Rectangle rectangle1, Rectangle rectangle2)
{
  if (((rectangle1.X < (rectangle2.X + rectangle2.Width))
    && (rectangle2.X < (rectangle1.X + rectangle1.Width)))
    && (rectangle1.Y < (rectangle2.Y + rectangle2.Height)))
  {
    return (rectangle2.Y < (rectangle1.Y + rectangle1.Height));
  }
  return false;
}

To determine if two sprites have overlapped the Intersect function is called with sprite co-ordinates of the two sprites you are interested in. If this function returns true we need to move on to Test 2.

Test 2 requires that we determine if any of the corresponding pixels in the overlap between the two sprites are visible i.e. not transparent. If both sprites contain corresponding visible pixels at the same location this represents a collision, if on the other hand none of the visible pixels overlap with visible pixels of the other texture then there is no collision. The following images depict the two situations graphically.

The first image shows two sprites which there bounding rectangles overlapping however none of the visible pixels overlap and therefore this is not a true collision. The second image shows that there is an overlap of visible pixels between the two sprites in the intersection and therefore represents a collision.

To do the pixel level tests we first need to determine the intersection rectangle, the rectangle highlighted in black in the above images. The following function can be used to achieve this.

public static Rectangle Intersection(Rectangle rectangle1, Rectangle rectangle2)
{
  int x1 = Math.Max(rectangle1.Left, rectangle2.Left);
  int y1 = Math.Max(rectangle1.Top, rectangle2.Top);
  int x2 = Math.Min(rectangle1.Right, rectangle2.Right);
  int y2 = Math.Min(rectangle1.Bottom, rectangle2.Bottom);

  if ((x2 >= x1) && (y2 >= y1))
  {
    return new Rectangle(x1, y1, x2 - x1, y2 - y1);
  }
  return Rectangle.Empty;
}

The two rectangles passed to the function will be the sprite rectangles; the result is a new rectangle which represents the intersection of the two rectangles.

Armed with the intersection rectangle we need to convert the co-ordinate of the intersection rectangle to the texture co-ordinates of the two textures. In other words, we need to determine the rectangles within the textures that overlapped. Viewing each texture individually this would look like the following.

The following function will translate the co-ordinates one rectangle to the co-ordinate space of the reference rectangle.

public static Rectangle Normalize(Rectangle reference, Rectangle rectangle)
{
  return new Rectangle(
    rectangle.X - reference.X,
    rectangle.Y - reference.Y,
    rectangle.Width,
    rectangle.Height);
}

The function is called passing the sprite co-ordinate rectangle as the reference and the intersection rectangle as the second rectangle argument. Call this function once for each of the sprites, resulting in two rectangles, representing the rectangle within each of the textures that we are interested in.

Now we need to extract the pixel data for the two rectangles and compare them pixel for pixel. The following function will perform this task in a reasonably efficient manner, but my focus was readability.

public static bool TestCollision(
  Texture2D texture1, Rectangle texture1Intersection,
  Texture2D texture2, Rectangle texture2Intersection)
{
  int pixelCount = texture1Intersection.Width * texture1Intersection.Height;
  uint[] texture1Pixels = new uint[pixelCount];
  uint[] texture2Pixels = new uint[pixelCount];

  texture1.GetData(0, texture1Intersection, texture1Pixels, 0, pixelCount);
  texture2.GetData(0, texture2Intersection, texture2Pixels, 0, pixelCount);
  for (int i = 0; i < pixelCount; ++i)
  {
    if (((texture1Pixels[i] & 0xff000000) > 0)
      && ((texture2Pixels[i] & 0xff000000) > 0))
    {
      return true;
    }
  }
  return false;
}

The key to performance in this function is to extract only the pixel data we are interested in, because the area of intersection within both texture is the same size we can extract the data and run through it one element at a time. Each element index represents the corresponding pixel data in each of the textures. In the loop we mask out the Alpha channel bits by performing a bitwise and, if the alpha channel of both pixels (texture1 and texture2) is not 0 we have a visible pixel overlap which is considered a collision and we can break out of the loop.

Some notes:

1. As has already been mentioned the above does not address scaled or rotated sprites.

2. Additional performance can be achieved by compiling with the unsafe switch and using pointer arithmetic to iterate the pixel data. From my tests I get roughly 4 frames per second extra when using pointers, which is with 100 sprites bouncing around.

3. If the original textures are not powers of 2 in size XNA automatically scales the textures, this is for performance reasons. However the problem with that for this version of the algorithm is that the scaling introduces noise (anti-aliasing) into the image which improves the visual quality of the scaled image. While the artifacts from this process are not individually visible to the eye the algorithm does detect them as visible pixels and potentially results in a false positive, at least as far as the eye can see.