The Pixel-Accurate Collision project

This project demonstrates how to detect collision between a large and a small texture. The textures themselves vary widely in complexity. Both textures contain both transparent and nontransparent areas. A collision occurs only when the nontransparent pixels of one texture overlap those of the other texture. In this project, when a collision occurs, a soccer ball appears at the collision point. You can see an example of this project in Figure 5-1.

The project’s controls are as follows:

• Right thumbstick (arrow-keys) Moves the small texture
• Left thumbstick (WSAD-keys) Moves the large texture

The goals of the project are as follows:

• To demonstrate how to detect nontransparent pixel overlaps
• To understand the pros and cons of using pixel-accurate collision detection

The steps for creating the project are as follows:

1. Extend the textured primitive class to support pixel-accurate collision.
2. Modify the GameState class to use the new collision detection.

Before moving forward, let’s first define the requirements needed for collision between two textured primitives. Foremost is that the texture itself needs to contain an area of transparency, in order for this type of collision detection to provide any increase in accuracy. Without transparency in the texture, you can and should use simple primitive-based collision detection. If one or both of the textures contain transparent areas, then you’ll need to handle two cases of collision. The first case is to check whether the bounds of the two primitives collide. You can see this reflected in Figure 5-2. Notice how the bounds of the primitives overlap, yet none of the nontransparent colored pixels are touching.

The next case is when the colored pixels (nontransparent) of the texture overlap. Take a look at Figure 5-3. The flower texture and the target texture are clearly in contact with one another.

Now that the problem is clearly defined, here’s the logic or pseudocode you need to achieve this type of behavior:

• Given two images, Image-A and Image-B
• If the bounds of the primitive of Image-A and Image-B collide then
  • for each Pixel-A in Image-A
  • pixelCameraSpace = pixel position in camera space
  • Transform pixelCameraSpace to Image-B space
  • Read Pixel-B from Image-B
  • If Pixel-A and Pixel-B are not both completely transparent then
  • A collision has occurred

The per-pixel transformation to Image-B space from pixelCameraSpace is required because collision checking must be carried out within the same coordinate space. Additionally, notice the runtime requirements for this behavior. Each pixel within Image-A must be checked, so the runtime is O(N), where N is equal to the number of pixels in Image-A, or Image-A’s resolution. To mitigate some of this performance hit, you should use the smaller of the two images (the target in this case) as Image-A. However, at this point, you can probably see why the performance of pixel-accurate collision is of concern. Checking for these collisions during every update with many high-resolution textures on screen can quickly bog down performance.

Now let’s take a look at how you can implement pixel-accurate collision for the TexturedPrimitive class.

Extending the TexturedPrimitive class

1. To begin, create a new file in the GraphicsSupport folder and name it TexturedPrimitivePixelCollide.cs. This class will extend the original TexturedPrimitive class. To do this, add the keyword partial to the existing TexturedPrimitive class and name the newly created class TexturedPrimitive so their names match within the code. You can see an example of this following:

   public partial class TexturedPrimitive
   {
       ...
   }

2. Create an array to hold the value of every pixel’s color within the texture. Add a function to initialize the color array with the proper size and data of the image. In addition, add an accessor that returns the color of the specific pixel within the image:

   private Color[] mTextureColor = null;
    
   private void ReadColorData()
   {
       mTextureColor = new Color[mImage.Width * mImage.Height];
       mImage.GetData(mTextureColor);
   }
    
   private Color GetColor(int i, int j)
   {
       return mTextureColor[(j * mImage.Width) + i];
   }

3. You must call the ReadColorData() function from the InitPrimitive() function. Recall that the InitPrimitive() function was defined in the original TexturedPrimitive.cs file, and thus you must perform the modification in that file as well.

   protected void InitPrimitive(String imageName,
       Vector2 position, Vector2 size, String label = null)
   {
       ...
    
       ReadColorData();    // For pixel-level collision support
   }

4. Add a function for transforming indexes into the camera’s coordinate space. You can see this demonstrated in the code that follows, where the index values of i and j are converted into a position in camera space and returned.

   private Vector2 IndexToCameraPosition(int i, int j)
   {
       float x = i * Width / (float)(mImage.Width - 1);
       float y = j * Height / (float)(mImage.Height - 1);
    
       return new Vector2(Position.X + x - (mSize.X * 0.5f),
                           Position.Y - y + (mSize.Y * 0.5f));
   }

5. You also need a function to convert a position in camera space into the corresponding pixel index within the image. An important note for the caller of this function is that, because the camera space is often larger than the images, it is important to first check to see whether the returning position is within the bounds of the image. Take note of how the following code achieves this:

   private Vector2 CameraPositionToIndex(Vector2 p)
   {
       Vector2 delta = p - Position;
       float i = mImage.Width * (delta.X / Width);
       float j = mImage.Height * (delta.Y / Height);
       i += mImage.Width / 2;
       j = (mImage.Height / 2) - j;
       return new Vector2(i, j);
   }

6. With the support functions completed, you can now build the primary function for pixel-accurate collision.
   1. Create a function called PixelTouches() that returns a bool and accepts a TexturedPrimitive and an out Vector2.

      public bool PixelTouches(TexturedPrimitive otherPrim, out Vector2 collidePoint)
      {
          ...
      }

       Note  In C#, the keyword out is used as a parameter modifier to indicate that the argument is being passed by ­reference. This is similar to the argument modifier ref; however, an out argument does not need to be initialized beforehand.

   2. Within the function, first check whether the bounds of the two primitives overlap. If they don’t, you can return false. However, when the bounds of the primitives overlap, then you need to check whether the texture pixels overlap. To do this, create while loops to iterate through every pixel within the image, transforming each to camera space. Then make sure the pixel in question is not transparent, and test whether it collides with the other image. You can see an example of this in the code that follows. Note the check that ensures the returned pixel index is within the bounds of the image.

      bool touches = PrimitivesTouches(otherPrim);
      collidePoint = Position;
       
      if (touches)
      {
          bool pixelTouch = false;
       
          int i=0;
          while ( (!pixelTouch) && (i<mImage.Width) )
          {
              int j = 0;
              while ( (!pixelTouch) && (j<mImage.Height) )
              {
                  collidePoint = IndexToCameraPosition(i, j);
                  Color myColor = GetColor(i, j);
                  if (myColor.A > 0)
                  {
                      Vector2 otherIndex =
                          otherPrim.CameraPositionToIndex(collidePoint);
                      int xMin = (int)otherIndex.X;
                      int yMin = (int)otherIndex.Y;
       
                      if ((xMin >= 0) && (xMin < otherPrim.mImage.Width) &&
                          (yMin >= 0) && (yMin < otherPrim.mImage.Height))
                      {
                          pixelTouch = (otherPrim.GetColor(xMin, yMin).A > 0);
                      }
                  }
                  j++;
              }
              i++;
          }
          touches = pixelTouch;
      }
      return touches;

7. Lastly, you need to update the PrimitivesTouches() function to perform a simple bounds check:

   public bool PrimitivesTouches(TexturedPrimitive otherPrim)
   {
       Vector2 myMin = MinBound;
       Vector2 myMax = MaxBound;
       Vector2 otherMin = otherPrim.MinBound;
       Vector2 otherMax = otherPrim.MaxBound;
       return
           ((myMin.X < otherMax.X) && (myMax.X > otherMin.X) &&
               (myMin.Y < otherMax.Y) && (myMax.Y > otherMin.Y));
   }

Now you just need to modify the GameState class to support the new functionality of the TexturedPrimitive class.

Modifying the GameState class

1. Start by adding the following code to the UpdateGame() function, which is separated into two sections by the comments:
   1. The step 1a portion of the function handles primitive movement via the gamepad by mapping the primitive position to the thumbsticks.
   2. The step 1b portion of the function handles the collision detection. Note that, as prescribed earlier, the mSmallTarget.PixelTouches target is used instead of mLargeFlower.PixelTouches, because the small target contains fewer pixels than the large flower. This means that the runtime is O(100 × 100) instead of O(2413 × 2467).

      public void UpdateGame()
      {
          #region Step 1a.
          mLargeFlower.Position += InputWrapper.ThumbSticks.Left;
          mSmallTarget.Position += InputWrapper.ThumbSticks.Right;
          #endregion
       
          #region Step 1b.
          mPrimitiveCollide = mLargeFlower.PrimitivesTouches(mSmallTarget);
          if (mPrimitiveCollide)
          {
              Vector2 p;
              mPixelCollide = mSmallTarget.PixelTouches(mLargeFlower, out p);
              mCollidePosition.Position = p;
          }
          else
          {
              mPixelCollide = false;
          }
          #endregion
      }

2. Lastly, draw the images via their draw functions and output the results using the FontSupport class:

   public void DrawGame()
   {
       mLargeFlower.Draw();
       mSmallTarget.Draw();
    
       FontSupport.PrintStatus("Primitive Collide=" +
           mPrimitiveCollide + "    PixelCollide=" + mPixelCollide, null);
       FontSupport.PrintStatusAt(mSmallTarget.Position,
           mSmallTarget.Position.ToString(), Color.Red);
    
       if (mPixelCollide)
           mCollidePosition.Draw();
   }

The General Pixel Collision project

This project demonstrates how to detect a collision between two rotated images with pixel-level accuracy. In this project, a user can rotate each image by pressing the appropriate buttons, as detailed following. As before, when the two images collide, a soccer ball appears (as well as a test confirmation). You can see an example of this project running in Figure 5-4.

The project’s controls are as follows:

• Right thumbstick (arrow-keys) Moves the small texture
• Left thumbstick (WSAD-keys) Moves the large texture
• Button A (K-key) Rotates the large flower texture in the clockwise direction
• Button B (L-key) Rotates the large flower texture in the counterclockwise direction
• Button X (J-key) Rotates the small target texture in the clockwise direction
• Button Y (I-key) Rotates the small target texture in the counterclockwise direction

The goal of the project is as follows:

• To generate a pixel-accurate collision test for rotated images

The steps for creating the project are as follows:

1. Review vector decomposition.
2. Modify the TexturedPrimitive class’s pixel-accurate collision to support rotation.
3. Modify the GameState class to support the new rotation behavior.

Modifying the TexturedPrimitive class

1. Start by adjusting the IndexToCameraPosition() function, taking into account the new rotated axes to compute the correct position in camera space. You do this by modifying the return values of vector r with the incoming vectors xDir and yDir. In this case, xDir and yDir are the  and  component vectors. You can see this in the following code:

   private Vector2 IndexToCameraPosition(int i, int j, Vector2 xDir, Vector2 yDir)
   {
       float x = i * Width / (float)(mImage.Width - 1);
       float y = j * Height / (float)(mImage.Height - 1);
    
       Vector2 r = Position + (x - (mSize.X * 0.5f)) * xDir - (y - (mSize.Y * 0.5f)) * yDir;
    
       return r;
   }

2. Similarly, adjust the camera space–to–pixel space function by using the rotated axes. You do this by using the incoming vectors xDir and yDir to calculate the x and y offsets and then applying them to the images’ width and height, as shown in the following code:

   private Vector2 CameraPositionToIndex(Vector2 p, Vector2 xDir, Vector2 yDir)
   {
       Vector2 delta = p - Position;
       float xOffset = Vector2.Dot(delta, xDir);
       float yOffset = Vector2.Dot(delta, yDir);
       float i = mImage.Width * (xOffset / Width);
       float j = mImage.Height * (yOffset / Height);
       i += mImage.Width / 2;
       j = (mImage.Height / 2) - j;
       return new Vector2(i, j);
   }

3. Lastly, the PixelTouches() function needs some modification. Following, in step 3a, because you know the angle of rotation, and you know the initial orthonormal set (the x and y unit vectors), you can compute the rotated orthonormal set (). Then, in step 3b, you can use the newly computed orthonormal set to compute the offset or camera space transformations.

   public bool PixelTouches(TexturedPrimitive otherPrim, out Vector2 collidePoint)
   {
       bool touches = PrimitivesTouches(otherPrim);
       collidePoint = Position;
        
       if (touches)
       {
           bool pixelTouch = false;
    
           #region Step 3a.
           Vector2 myXDir = ShowVector.RotateVectorByAngle(Vector2.UnitX, RotateAngleInRadian);
           Vector2 myYDir = ShowVector.RotateVectorByAngle(Vector2.UnitY, RotateAngleInRadian);
           Vector2 otherXDir = ShowVector.RotateVectorByAngle(
               Vector2.UnitX, otherPrim.RotateAngleInRadian);
           Vector2 otherYDir = ShowVector.RotateVectorByAngle(
               Vector2.UnitY, otherPrim.RotateAngleInRadian);
           #endregion
    
           #region Step 3b.
           int i=0;
           while ( (!pixelTouch) && (i<mImage.Width) )
           {
               int j = 0;
               while ( (!pixelTouch) && (j<mImage.Height) )
               {
                   collidePoint =
                       IndexToCameraPosition(i, j, myXDir, myYDir);
                   Color myColor = GetColor(i, j);
                   if (myColor.A > 0)
                   {
                       Vector2 otherIndex =
                           otherPrim.CameraPositionToIndex(
                               collidePoint,
                               otherXDir,
                               otherYDir);
                       int xMin = (int)otherIndex.X;
                       int yMin = (int)otherIndex.Y;
                       if ((xMin >= 0) && (xMin < otherPrim.mImage.Width) &&
                           (yMin >= 0) && (yMin < otherPrim.mImage.Height))
                       {
                           pixelTouch = (otherPrim.GetColor(xMin, yMin).A > 0);
                       }
                   }
                   j++;
               }
               i++;
           }
           #endregion
           touches = pixelTouch;
       }
       return touches;
   }

public void UpdateGame()
{
    #region Step 1a. Select to work with PA or PB
    ...
     
    if (InputWrapper.Buttons.A == ButtonState.Pressed)
        mLargeFlower.RotateAngleInRadian += MathHelper.ToRadians(1f);
    if (InputWrapper.Buttons.B == ButtonState.Pressed)
        mLargeFlower.RotateAngleInRadian -= MathHelper.ToRadians(1f);
    if (InputWrapper.Buttons.X == ButtonState.Pressed)
        mSmallTarget.RotateAngleInRadian += MathHelper.ToRadians(1f);
    if (InputWrapper.Buttons.Y == ButtonState.Pressed)
        mSmallTarget.RotateAngleInRadian -= MathHelper.ToRadians(1f);
    #endregion
 
    ...
}

The Simple Physics project

This project demonstrates how to simulate a ball falling under gravitational pull, or free fall, while also taking into account both the elasticity and friction associated with the ball when it collides with an object. You can see an example of this project running in Figure 5-9.

The project’s controls are as follows:

• Hold Button A (K-key) Respawns the ball
• Release Button A (K-key) Releases the ball

The goals of the project are as follows:

• To simulate the following simple physical behaviors:
• Rotational velocity
• Gravitational free fall
• Elasticity
• Friction

The steps for creating the project are as follows:

1. Gain an overview of the simple physics being implemented.
2. Review the math required to calculate the arc of a circle.
3. Add a gravity constant variable.
4. Create a RotateObject class for the ball.
5. Create a Platform class to interact with the ball object.
6. Modify the GameState class to include the support for the new objects.

public class GameState
{
    // Global constant for simple world physical properties
    static public float sGravity = 0.01f;
 
    ....
}

Creating the RotateObject class

1. Create a new class called RotateObject that inherits from the GameObject class, and include an accessor for the radius of the object.

   public class RotateObject : GameObject
   {
       public RotateObject(String image, Vector2 center, float radius)
               : base(image, center, new Vector2(radius*2f, radius*2f))
       {
       }
       public float Radius {
               get { return mSize.X / 2f; }
               set { mSize.X = 2f * value; mSize.Y = mSize.X; }
       }
    
       ...
   }

2. Override the Update() function in the new RotateObject class so the object’s behavior can be modified. Remember to call the base update function so that the velocity is applied. Here’s what happens:
   1. The velocity is modified by the gravity constant at each update to simulate a free-falling state.
   2. Then, the object is rotated in accordance with its speed in the x direction, via the implementation of the equation derived earlier.
   3. Lastly, the rotation direction, clockwise or counterclockwise, is applied:

      override public void Update()
      {
          // Moves object by velocity
          base.Update();
           
          #region Step 2a.
          Vector2 v = Velocity;
          v.Y -= GameState.sGravity;
          Velocity = v;
          #endregion
           
          #region Step 2b.
          // Now rotate the object according to the speed in the x direction
          float angularDisplace = (v.X / Radius);
          #endregion
       
          #region Step 2c.
          // This assumes object is rolling "on top of" surfaces
          if (v.X > 0)
              mRotateAngle += angularDisplace;
          else
              mRotateAngle -= angularDisplace;
          #endregion
      }

Now that you have a rotating object or ball, you can create a platform for it to bounce on.

Creating the Platform class

1. Create a new class called Platform that inherits from the TexturedPrimitive class. Have its constructor pass its parameters to the base class. Additionally, define variables and accessors for both friction and elasticity. You can see this in the code that follows:

   public class Platform : TexturedPrimitive
   {
       // Slows down by 2% at each update
       private float mFriction = 0.98f;
       // Retains 70% of velocity at each bounce
       private float mElasticity = 0.7f;
       public Platform(String image, Vector2 center, Vector2 size)
               : base(image, center, size)
       {
       }
    
       public float Friction { get { return mFriction; } set { mFriction = value; } }
       public float Elasticity {  get { return mElasticity; } set { mElasticity = value; } }
    
       ...
   }

2. Now add a BounceObject() function. This function causes an object that collides with the platform to bounce, and applies friction to the object. Make the function virtual so that you can implement subclasses with varying amounts of friction and/or bounce effect. First, check to see if there is any collision, and if collision occurs, then do the following:
   1. Update the object’s velocity by applying the elasticity and friction variables. Remember that friction affects the x velocity and elasticity affects the y velocity.
   2. Make sure the object does not penetrate and get stuck in the platform. Do this by checking whether the object has penetrated the platform, and if it has, push the object out.

      virtual public void BounceObject(GameObject obj)
      {
          Vector2 collidePoint;
          if (obj.PixelTouches(this, out collidePoint))
          {
              #region Step 2a.
              // Limitation: Only collide from top/bottom, not from the sides
              Vector2 v = obj.Velocity;
              v.Y *= -1 * mElasticity;
              v.X *= mFriction;
              obj.Velocity = v;
              #endregion
               
              #region Step 2b.
              // Make sure object is not "stuck" inside the platform
              Vector2 p = obj.Position;
              if (p.Y > Position.Y)
                  p.Y = Position.Y + Size.Y * 0.5f + obj.Size.Y * 0.5f;
              else
                  p.Y = Position.Y - Size.Y * 0.5f - obj.Size.Y * 0.5f;
              obj.Position = p;
              #endregion
          }
      }

Modifying the GameState class

1. Return to the GameState class and add the following variables for the rotation object, platform, and position:

   public class GameState
   {
       ...
    
       private Vector2 kInitBallPosition = new Vector2(3f, 48f);
       // Objects in the world
       Platform mSlowStone, mBrick, mStone;
       RotateObject mBasket;
    
       ...
   }

2. Next, initialize the rotation object (ball) and the three platforms within the constructor. Provide the three platforms with different textures, friction, and elasticity. You can see the default values used in the code that follows:

   public GameState()
   {
       // Create the platforms
       mBrick = new Platform("BrickPlatform", new Vector2(15, 40), new Vector2(30f, 5f));
       // How rapidly object slows down: Retains most speed
       mBrick.Friction = 0.999f;
       // How bouncy is this platform: 90%
       mBrick.Elasticity = 0.85f;
    
       mStone = new Platform("StonePlatform", new Vector2(50, 30), new Vector2(30, 5f));
       // How rapidly object slows down: Retains some speed
       mStone.Friction = 0.99f;
       // How bouncy is this platform: Slightly more than half: 60%
       mStone.Elasticity = 0.5f;
    
       mSlowStone = new Platform("StonePlatform", new Vector2(85, 20), new Vector2(30, 5));
       // How rapidly object slows down: Very rapidly
       mSlowStone.Friction = 0.9f;
       // How bouncy is this platform: Not very
       mSlowStone.Elasticity = 0.2f;
    
       // Both outside of the camera, so neither will be drawn
       mBasket = new RotateObject("BasketBall", new Vector2(-1, -1), 3f);
   }

3. When the user presses the A button, you want the update function to create a ball at its initial position with a random velocity. If the ball is within the camera window, apply its update and bounce check for each platform. Here’s the code:

   public void UpdateGame()
   {
       if (InputWrapper.Buttons.A == ButtonState.Pressed)
       {
           mBasket.Position = kInitBallPosition;
           Vector2 v = new Vector2((float)(0.3f + (Game1.sRan.NextDouble()) * 0.1f), 0f);
           mBasket.Velocity = v;
       }
    
       if (mBasket.ObjectVisibleInCameraWindow())
       {
           mBasket.Update();
           mSlowStone.BounceObject(mBasket);
           mStone.BounceObject(mBasket);
           mBrick.BounceObject(mBasket);
       }
   }

4. Finally, draw the platforms within the DrawGame() function. Only draw the ball if it is within the camera window.

   public void DrawGame()
   {
       mSlowStone.Draw();
       mStone.Draw();
       mBrick.Draw();
    
     if (mBasket.ObjectVisibleInCameraWindow())
           mBasket.Draw();
   }