Pixel perfect collision detection using GPU occlusion queries

Originally posted to Shawn Hargreaves Blog on MSDN, Wednesday, December 31, 2008

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:

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.