Pixel-perfect collision detection

How do geeks spend sunny days?
Exactly! They stay inside and code whatever their wiked mind is up to. And that’s how I started a little experiment on a way to determine 2D sprite-collisions on a pixel-perfect basis. And the best thing about my approach is: it doesn’t rely on the GPU doing super-expensive pixel-loops within each colliding sprite but leaves the whole cake to the GPU, which of course needs the pixel-data anyway.
Let me go into a little bit more detail at this point:
The rendering-pipeline utilizes different buffers to process it’s data within the rasterizer-stage at which’s end is the Frame- or Backbuffer displaying the actual picture on the screen. Before the pixel-data reaches the backbuffer though, it has to pass two other very important buffers: the stencil buffer and the depth buffer. The latter – as the name may suggest – tests each incoming pixel against the depth-value stored in the buffer and passes or rejects the pixel. This buffer is the reason you don’t have to worry about any draw-order when rendering 3D vertices, since the depth-buffer, if enabled, tests each vertex for it’s depth “automatically”.
The first buffer a pixel data has to pass on it’s way to the screen is the stencil buffer. Actually the stencil buffer is packed within the depth buffer’s memory. A few bits of the buffer are then reserved to stencil-purposes ( usually 1 or 8 bits ). Usually the stencil buffer is used to “mark” certain areas of the screen and prohibit drawing to the unmarked or marked areas (the name “stencil” is again very self-exlpanatory for this buffer).

In our case, we’ll utilize this very buffer to mark all pixels the first of our two colliding sprites is drawed to. When the second sprite is drawn, the GPU should check if the target-pixels are already “marked” inside the stencil buffer. Finally we’ll performe a device-query, the “occlusion query” to be exact, to determine how many pixels where actually modifed and passed the stencil buffer in the last rendering-pass. If no pixels where modified, there is no collision, otherwise the two sprites did indeed collide with each other.

Let’s examine how to set up the stencil buffer to achive the desired effects.
We can modify the functionality of the stencil buffer at at least three points: the stencilFunc, the stencilOp and the stencilRef. We also could set a stencilMask, used to mask off certain parts of the stencil data, but we’ll leave that out for now.

The stencilFunc describes how to compare existing stencil-buffer entries at the incoming pixel-position with a stencilRef, which is a simple integer reference value to compare to. The success of this comparision determines whether our incoming pixel passes or fails.
We can choose from different  comparision functions. The general layout of this comparision is:

stencilRef <stencilFunc> stencilValue

Just like described above. The symbol “<stencilFunc>” can now be replaced by a set of pre-defined behaviors:

• EQUAL             –> stencilRef == stencilValue
• ALWAYS         –> always true
• NOT_EQUAL –> stencilRef != stencilValue
• LESS
• GREATER
• NEVER
• …I think you got the point ;-)

Then we can set different behaviours if this comparision failed or suceeded. This is the stencilOp. In Fact we can set different setncilOps for failure and success. These operations include:

• KEEP                 –> No change in the stencil buffer
• REPLACE        –> Replace the entry in the buffer with the stencilRef-value
• INCREMENT –> Increment the entry in the buffer (with clamp to 0 if the maximum bit-range of the buffer is exeeded )
• DECREMENT
• INVERT
• …

Now we got all knowledge we need to write our collision-detector.

The theory looks like this:

• Turn off all color-rendering, so no actual picture is generated. Drawing only happens to the stencil and depth buffer
• Draw the first sprite with stencilFunc “ALWAYS”, stencilPassedOp “REPLACE”, stencilFailedOp “KEEP” and stencilRef = 1 to mark all pixels the sprite is drawn to in the stencil-buffer and leave every other pixel at “0″.
• Start the occlusion-query
• Draw the second sprite with stencilFunc “EQUAL” and stencilRef = 1. The stencilPassedOp in fact doesn’t really matter at this point, since we will build the stencil buffer new in the next frame. We only needed the information that this pixel passed the test, which is the case, when the second sprite intersects with the first ( “EQUAL” ). I suggest to set the stencilPassedOp to “KEEP”
• End the occlusion-query
• Do some stuff to let the occlusion-query finish it’s work
• Retrieve the “PixelCount” from the query, which gives us the number of pixels that passed the stencil buffer ( == the number of intersecting pixels )
• Turn color-rendering back on, disable stencil-testing
• Draw the two sprites again normally

and there we have our pixel-perfect collision detection ;-)

Now I’ll leave you with a little demo. I wrote it in XNA because it just has the lowest setup-times. But since buffer-manipulations and queries are as much low-level as it can get you won’t have any problems porting the functionality to OpenGL or unwrapped DirectX.

protected override void Draw( GameTime gameTime )
{
OcclusionQuery query = new OcclusionQuery( GraphicsDevice );
GraphicsDevice.DepthStencilBuffer = collisionDSBuffer;
GraphicsDevice.Clear( ClearOptions.Stencil | ClearOptions.Target, Color.White, 0.0f, 0 );

base.Draw( gameTime );
}