NB: Here is a better post about the below algorithm. Includes source code.

The idea

Did you know you can do pixel accurate collision detection using the OpenGL stencil buffer and occlusion queries? I got this idea while working on a 2D/3D game engine (think of a side-scroller but with 3D objects).

The idea is actually very similar to how you do collision checking on most 8-bit computers and consoles: when drawing the sprites on screen, the graphics chip automatically keeps track if it drew a pixel on something that was already there. OpenGL doesn’t do that by default (especially because this is not a 3D method) but we can fake it. This is how I do it:

1. Each model has it’s bounding box which is translated and rotated with the object

2. Each potential collision between two objects is checked:

   1. Project each corner of the bounding box on the screen plane (gluProject()). You can project all the object vertices if you want more accuracy

   2. Get the smallest rectangle that fits around the projected points

   3. Using this rectangle check if the objects are anywhere near each other, i.e. check if the rectangles overlap. If the rectangles do overlap:

      1. Use the first object to draw a stencil shape (i.e. use the same drawing code you use to draw the object on the screen but enable GL_STENCIL_TEST and put the stencil function in the GL_ALWAYS mode). You need to clear the stencil buffer, I do this with the scissor area set so I clear just the needed area.

      2. Use the second object to do an occlusion query using the stencil – draw only if the stencil is set (again, reuse the code for drawing the object in general but enable stencil test and start the occlusion query before drawing).

      3. The objects collide if there are any pixels drawn, i.e. the objects shared some pixels and the query returns a non-zero value

3. Draw the scene, next frame etc.

(Text on yellow is what I’m talking about here)

Discussion and improvements

Now, this isn’t exactly a fast technique and you probably will have good results with normal multiple bounding box/rectangle checking even if that isn’t as accurate as this method. However, this should work with anything you can draw on the screen with OpenGL, including alpha textures (i.e. 2D sprites) and you don’t need to keep track of any extra bounding boxes.

One thing I like is that you automatically get a bit more sophisticated collision checking: even if this method is inherently 2D, you can use the far and near clipping planes to make the objects not collide if an object is actually behind another object. If you use perspective, you can stop the player colliding with a floor that stretches to infinity (which of course when projected in 2D only goes from the bottom of the screen to the middle of the screen) – just draw the part of the floor that is at the same the depth as the player.

You can also optimize this a lot. In my case, I get more speed using the rectangle check above and limiting collisions (e.g. no check between two enemies, checking only player and landscape collisions, testing only the rectangle if it is a static square tile etc.). I also don’t draw the stencil every time I check an object pair and obviously cache rects if the orientation of the object doesn’t change much.

Not much examples here but you should get this working in a few days by just googling for occlusion queries, stencil buffer and OpenGL (assuming you already do know how to draw stuff on screen and realize how the object translation and rotation works etc.). There are a ton of tutorials on the Net about drawing reflections and whatnot using stencil, which is precisely what we do here, only that we don’t show the reflection and only count the pixels.

Links

• Nehe tutorial on stencil reflections