2D Collision Tutorial 2: Per-Pixel

This article explains how to perform per-pixel collision detection.
Note
This tutorial builds on code you have written during the previous tutorial, 2D Collision Tutorial 1: Rectangle. Follow the steps in the previous tutorial before starting this tutorial.

Introduction

In the previous example, you created a simple object avoidance game using rectangle collision detection. The rectangles used were only an approximation of the blocks and person drawn into the textures. You may have noticed the exclusive use of rectangles resulted in imprecise behavior for nonrectangular objects.

The current behavior is a red background, which indicates that the block is colliding with the person. That is clearly not the case in this image; therefore, this behavior is undesired. The sprite rectangles are overlapping, but the rectangular collision detection is not smart enough to realize that the shapes within these sprites are not in fact touching.

The desired behavior in this instance is a blue background, indicating the block is colliding with the person.

In order to achieve the desired behavior, the code must examine every overlapping pixel to determine if there is a collision. This is called per-pixel collision.

Step 1: Get Texture Data

Per-pixel collision requires examining individual pixels of a given texture. To access the individual pixels, you must call Texture2D.GetData. This method copies the pixels into an array you specify. The default texture processor will have pixel data of type Color.

  1. First, declare a Color array for each texture at the top of your game class.

    // The color data for the images; used for per-pixel collision
    Color[] personTextureData;
    Color[] blockTextureData;			  
  2. Next, use Texture2D.GetData to retrieve a copy of the pixel data from our textures. This must be done after the textures are loaded. Modify the LoadContent method by adding the bold lines.

    // Load textures
    blockTexture = Content.Load<Texture2D>("Block");
    personTexture = Content.Load<Texture2D>("Person");
    
    // Extract collision data
    blockTextureData =
        new Color[blockTexture.Width * blockTexture.Height];
    blockTexture.GetData(blockTextureData);
    personTextureData =
        new Color[personTexture.Width * personTexture.Height];
    personTexture.GetData(personTextureData);			  

    For both textures, you first allocate a color array. The color array is linear, which means that there is only one row of pixels that will contain all of the texture's rows attached end to end. Once the color array is allocated, GetData is called to fill the array with the pixels from the texture.

Step 2: Write Per-Pixel Collision Method

Now that you are equipped with all of the necessary data, you need to write a method to perform the per-pixel collision test. This method will accept a pair of sprite bounding rectangles and their necessary color data.

  1. Add a method with the following signature to your code.

    static bool IntersectPixels(Rectangle rectangleA, Color[] dataA,
                                Rectangle rectangleB, Color[] dataB)			  

    This method will have two key parts. First, it will identify the intersecting region of both rectangles. The intersection will be another rectangle or will not exist. Second, the method will iterate over every pixel in the intersection region and test for collision. If a collision is found, the method will terminate immediately with a return value of true. If after walking through each potentially colliding pixel, no collision is found, the method will return false.

  2. Add the following code to the beginning of the IntersectPixels method.

    // Find the bounds of the rectangle intersection
    int top = Math.Max(rectangleA.Top, rectangleB.Top);
    int bottom = Math.Min(rectangleA.Bottom, rectangleB.Bottom);
    int left = Math.Max(rectangleA.Left, rectangleB.Left);
    int right = Math.Min(rectangleA.Right, rectangleB.Right);			  

    These four variables represent the intersection rectangle of the two input rectangles. If no intersection exists, right minus left or bottom minus top, or both, will be negative. The nested for loops used in the following section automatically account for the non-intersecting bounding rectangles case.

  3. Append the following code to the end of the IntersectPixels method:

    // Check every point within the intersection bounds
    for (int y = top; y < bottom; y++)
    {
    	for (int x = left; x < right; x++)
    	{
    		// Get the color of both pixels at this point
    		Color colorA = dataA[(x - rectangleA.Left) +
    					(y - rectangleA.Top) * rectangleA.Width];
    		Color colorB = dataB[(x - rectangleB.Left) +
    					(y - rectangleB.Top) * rectangleB.Width];
    
    		// If both pixels are not completely transparent,
    		if (colorA.A != 0 && colorB.A != 0)
    		{
    			// then an intersection has been found
    			return true;
    		}
    	}
    }
    
    // No intersection found
    return false;

The for loops iterate over the overlapping rectangle one pixel at a time in reading order (left to right, top to bottom). For each pixel coordinate in global space, the coordinate is converted into each rectangles local space by subtracting the upper-left corner of the rectangle. The local coordinate is made linear by multiplying the y-coordinate by the texture width. The linear coordinate is then indexed into the color data. Given both colors, an intersection occurs when both are not completely transparent (alpha of 0).

Note
Recall from tutorial 1 that the default texture processor performs color keying, which converts the magenta background to be zero alpha.

Step 3: Invoke the Per-pixel Collision Test

Now that you have a method to perform per-pixel collision, you need to invoke it in place of the existing rectangle collision test.

  1. In your game's Update method, modify the block update loop to match the following code. The changed lines are bold.

    // Update each block
    personHit = false;
    for (int i = 0; i < blockPositions.Count; i++)
    {
    	// Animate this block falling
    	blockPositions[i] =
    		new Vector2(blockPositions[i].X,
    					blockPositions[i].Y + BlockFallSpeed);
    
    	// Get the bounding rectangle of this block
    	Rectangle blockRectangle =
    		new Rectangle((int)blockPositions[i].X, (int)blockPositions[i].Y,
    		blockTexture.Width, blockTexture.Height);
    
    	// Check collision with person
    	if (IntersectPixels(personRectangle, personTextureData,
    				blockRectangle,	blockTextureData))
    	{
    		personHit = true;
    	}
    
        // Remove this block if it has fallen off the screen
    	if (blockPositions[i].Y > Window.ClientBounds.Height)
    	{
    		blockPositions.RemoveAt(i);
    
    		// When removing a block, the next block will have the same index
    		// as the current block. Decrement i to prevent skipping a block.
    		i--;
    	}
    }			  
  2. That's it! Compile and run the game.

Congratulations!

You should now have working per-pixel collision detection.

Ideas to Expand

Haven't had enough per-pixel collisions? Try these ideas.

  • Create several shapes and sizes of blocks, and then randomly pick a shape each time a block is spawned
  • Add the ability to activate a round bubble shield
  • Add falling items, which you need to collect to boost your score