Pixel perfect collision detection using GPU occlusion queries

Pixel perfect collision detection using GPU occlusion queries

  • Comments 9

Ladies and gentlemen, I hereby present my final joke of 2008:

Q: what do you get if you cross a stencil buffer with an occlusion query?

A: pixel perfect collision detection!

Ok, the joke sucks. But I think the technique has merit:

  • Temporarily disable writing to the color buffer
  • Draw a shape into the stencil buffer
  • Set the stencil buffer to only allow writes where this shape was drawn
  • Begin an occlusion query
  • Draw a second shape
  • Count how many pixels passed the query
  • If greater than zero, the two shapes overlap

I made a test app to confirm this works. It can tell me not only that the cat is intersecting the building, but also exactly how many pixels are overlapping:

image

The code first declares some variables:

    OcclusionQuery query;
    bool queryActive;

    int collisionCount;

In my game constructor, I ask for a depth format that includes 8 bits of stencil data:

    graphics.PreferredDepthStencilFormat = DepthFormat.Depth24Stencil8;

In my LoadContent method, I create the query object:

    query = new OcclusionQuery(GraphicsDevice);

At the top of my Draw method, I check whether any previous collision query has completed, and if so, store its result. If no query is active, I then issue a new one:

    if (queryActive && query.IsComplete)
    {
        collisionCount = query.PixelCount;
        queryActive = false;
    }

if (!queryActive)
{
IssueOcclusionQuery();
queryActive = true;
}

After this collision detection code, I proceed to draw the scene as normal.

The IssueOcclusionQuery helper method disables writing to the color buffer, sets the stencil buffer to always replace the current stencil value with 1, and draws the building sprite:

    GraphicsDevice.RenderState.ColorWriteChannels = ColorWriteChannels.None;

    GraphicsDevice.RenderState.StencilEnable = true;
    GraphicsDevice.RenderState.StencilFunction = CompareFunction.Always;
    GraphicsDevice.RenderState.StencilPass = StencilOperation.Replace;
    GraphicsDevice.RenderState.StencilFail = StencilOperation.Keep;
    GraphicsDevice.RenderState.ReferenceStencil = 1;

    spriteBatch.Begin();
    spriteBatch.Draw(building, Vector2.Zero, Color.White);
    spriteBatch.End();

It then changes the stencil buffer to only allow writes where the existing stencil value is 1 (ie. where the new sprite is overlapping with the building), begins the occlusion query, and draws the cat sprite:

    GraphicsDevice.RenderState.StencilFunction = CompareFunction.Equal;
    GraphicsDevice.RenderState.StencilPass = StencilOperation.Keep;
    GraphicsDevice.RenderState.ReferenceStencil = 1;

    query.Begin();

    spriteBatch.Begin();
    spriteBatch.Draw(cat, catPosition, Color.White);
    spriteBatch.End();

    query.End();

Finally, it resets the stencil and color write renderstates, to avoid messing up my normal scene rendering:

    GraphicsDevice.RenderState.StencilEnable = false;
    GraphicsDevice.RenderState.ColorWriteChannels = ColorWriteChannels.All;

Advantages of this technique:

  • Simple
  • Fast
  • Does all the work on the GPU, so the CPU cost is very low
  • Handles arbitrarily complex shapes. It makes no difference whether you are dealing with single sprites, groups of multiple sprites, geometry, combinations of geometry with alpha texture cutouts, etc. (but only works on the 2D screen projection of 3D geometry: this is not full 3D collision detection)
  • Tells you not only whether a collision occurred, but also how many pixels are overlapping

Disadvantages:

  • Reading the query result back to the CPU is delayed by at least one frame, so you will be slightly late in detecting collisions (fine for some games, but unacceptable for others)
  • Because collision detection is tied to rendering, collisions can be missed if the framerate is poor (catchup logic that skips drawing to get the updates back in sync doesn't work in the usual way)
  • Only works on hardware that supports occlusion queries (some lower end graphics cards do not)

If you want to check for more than one collision at a time, you need multiple OcclusionQuery objects. To avoid them interfering with each other, you must either clear the stencil buffer between each query, or (more efficiently) use a different ReferenceStencil value per sprite. With an 8 bit stencil buffer, that gives 255 separate queries before you need to clear the buffer.

For more complex query logic, you can use individual bits of the stencil buffer in conjunction with the StencilMask and StencilWriteMask renderstates. For instance if you set bit 1 for all enemies and bit 2 for all bullets, you could issue one query to ask "has the player collided with any enemy or bullet", then change the mask and issue a single other query that asks "has this particular enemy collided with any bullet (while ignoring other enemies)".

My test app draws the sprites twice: once with color writes disabled for the collision detection, then again for real. In some cases you may be able to optimize this by doing the occlusion query at the same time as your main scene rendering, but that is not always possible.

  • Is there any way to make this work correctly on the 360 by chance?

    Please email kanno41 (at) gmail.com

    Thanks

  • kanno41: I don't understand what you mean? Occlusion queries work fine on Xbox.

  • I am using the AnimatingSprite class from the RPG starter kit on XNA.  When I use this post's method for two of those, it doesn't seem to ignore transparent pixels.  The collision count is the overlap of the entire destination rectangle of the animations.

    Is there something I should be doing different if the sprites are animated?

  • khayman218: this technique relies on alpha testing being used to reject any pixels that are not supposed to be tested. It won't work if you have alpha testing turned off for some reason, or if your sprites just have fractional alpha values rather than true zero alpha.

  • Ok, that makes sense.  Thanks for the help.  Unfortunately, I do have another issue now.  The collision detection is working correctly up until the first collision (i.e. when pixels first overlap).  After the first one, the query never resets to 0 even when the sprites are drawn on opposite ends of the screen.  I suppose my stencil buffer is never being reset entirely, because the pixel collision count is always about the peak number (and subsequent collisions in new areas of the buffer increase the query return value).  I even tried disposing and reallocating the query each time, but the return value was always the cumulative peak.  What is the best way to ensure my buffer is being cleared between collisions test?

  • I also tried removing this line:

    GraphicsDevice.RenderState.ColorWriteChannels = ColorWriteChannels.None;

    so that I could see where I was testing the collision.  When writing to the screen during the collision test it was clear the sprites were not touching, yet the query continued to return the max number of colliding pixels (from when they were visibly touching).

    Just to make things clearer, here is a video of the test app I am using.  The vectors are the screen positions of the sprites.  The red text is the result from the collision detection query.  The detection query is run on every update and displayed when the value returned is not zero.

    http://www.youtube.com/watch?v=6Ye0BAFhhZg

  • I was able to get the desired functionality.  I had to insert the following code to clear the stencil buffer to 0s before drawing the first sprite to it:

               gDevice.RenderState.StencilFunction = CompareFunction.Always;

    gDevice.RenderState.StencilPass = StencilOperation.Replace;

    gDevice.RenderState.StencilFail = StencilOperation.Keep;

               gDevice.RenderState.ReferenceStencil = 0;

    sbatch.Begin();

               sbatch.Draw(TextureManager.Instance.GetTexture("shadow"), new Rectangle(0, 0, gDevice.Viewport.Width, gDevice.Viewport.Height), Color.White);

    sbatch.End();

    After that I continue your code sample to draw the first sprite for detection.  Is this necessary or do I need to read a lot more about the stencil buffer and querying it?  Is there possibly a more graceful way to clear the stencil buffer?

    Thanks.

  • GraphicsDevice.Clear can be used to clear the stencil buffer. Just make sure you specify that it should clear stencil (via the ClearOptions parameter).

  • I was in awe of this technique until I realized that it only works for piercing bullets. Have you ever thought if it is possible to apply this technique to a non-piercing one? The one that only hits the first enemy pixel on its way? Moreover, if you can, how to find out WHICH enemy got hit?

Page 1 of 1 (9 items)
Leave a Comment
  • Please add 5 and 8 and type the answer here:
  • Post