Examine any typical game involving weapons that fire bullets (or some other type of ammunition) and you'll generally find that firing one of these weapons causes a decal (bullet hole) to be drawn on the surface - these are essentially 2D images overlaid onto the surface to give the impression of chipping. Wouldn't it be great to actually see the chip in the wall, though? Well, this fairly simple method enables you to do just that, without splitting up polygons.
The algorithm presented here relies on a stencil buffer of at least 1 bit in size being present - that eliminates cards up to Voodoo 2 (to my knowledge) from being able to draw these 3D decals. However, most gamers will not be using a card as old as that, so it shouldn't be a problem nowadays.
If you're to be able to see a small model (which is what would be used for a 3D decal) behind a large polygon (the wall on which it has been placed) you need to somehow be able to chop a hole in the polygon. This could be done by splitting it up into multiple convex polygons, but that can be very computationally expensive, especially when there are quite a few decals in the scene. A much cheaper method is required.
The stencil buffer, being available in the hardware of nearly all 3D cards nowadays, is perfect for the task - it's already been put to good use in games for the last couple of years via real-time 'sharp' shadows. It enables you to only draw pixels where you want to, and therefore enables you to create a 'hole' in a wall. Here's how the method works in theory (this will be presented in the context of OpenGL, but Direct3D can be used as well).
When drawing a world polygon in a scene, you first check to see if there is a decal on the wall. If there is, then you do the procedure that follows.
Firstly, make sure that stencil buffer testing is enabled (glEnable(GL_STENCIL_TEST)). Then, rendering to the framebuffer is disabled (glColorMask(0, 0, 0, 0)), the stencil function is set as to allow all pixels to pass the test (glStencilFunc(GL_ALWAYS, 1, 1)) and the operation to perform when a pixel passes is set to replace the current value with the new one, in this case a 1 (glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE)). Depth buffer writing must also be disabled (glDepthMask(GL_FALSE)). Now, the 'hole' can be created in the stencil buffer by first orienting the decal model to point in the direction of the polygon's normal, and then projecting the vertices of the decal model onto the plane of the polygon (the oriented, but not projected version of the model can be saved for the actual rendering of the decal) - see figure 1. The resulting 'flattened' version of the model can then be rendered, putting 1s in the stencil buffer where the decal will show through and leaving 0s where the wall should show.
Next, rendering to the framebuffer is re-enabled (glColorMask(1, 1, 1, 1)), depth buffer writing is re-enabled (glDepthMask(GL_TRUE)), and the stencil operation is set to always keep the current stencil buffer value (glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP)). This readies the application to actually render the decal and the wall.
To render the decal, the stencil function is set to allow all pixels to pass the test (glStencilFunc(GL_ALWAYS, 1, 1)), and the decal is drawn in the position you wish it to be in (using the rotated decal, generated earlier, to form the basis of the transformation to the wall itself, saving unnecessary re-computations).
To render the wall (which can be done before or after the decal - it doesn't matter which way around this is done) the stencil buffer function needs to be set to only render the pixel if the stencil buffer is not set to 1 (i.e. it's set to 0) - this is done with glStencilFunc(GL_NOTEQUAL, 1, 1). The wall is then rendered as normal.
Caveats, Extensions and Conclusion
That's all there is to 3D decals - they look miles better than current 2D decals, and can create a much greater sense of realism. However, there are a few caveats to the above method:
There are also some extensions to the algorithm outlined here that can be implemented:
For more information on the stencil buffer, I recommend the OpenGL Programming Guide (often called the 'red book') and NeHe. Any comments on the algorithm (problems or extensions you've done) can be emailed to me at email@example.com - I'd love to hear your comments. (Thanks should go to Ryan "Professional Victim" Desgroseilliers and Tim "Chips" Green for valuable input into this article.)
Francis "DeathWish" Woodhouse