Introduction
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).


The Method
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.


Figure 1 - Projecting the decal's vertices onto the surface's plane

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:

• Vertices in the decal model must not extend further outwards than the leading edge of the model (the one that will be 'on' the wall) - if the models feature this, then you'll get holes in the wall beside it due to the method of generating the hole in the wall via flattening the vertices. This can be countered by finding the edge of the decal and flattening that instead. (A way to do this would be to use all edges that only have one triangle on them, as opposed to 2.)
• Decals can't extend across more than one surface. This would be extremely complex to do across, say, 3 surfaces (in a corner of a room or something similar) but across 2 surfaces shouldn't be too difficult - it would require a weighted rotation of the vertices about the edge between the first surface and the second (where a 'weighted rotation' is where vertices that are further from the edge are rotated more than those located nearer the edge).
• Large decals will stretch through to other surfaces if the other surface is near enough the decaled wall. It's possible to avoid this by capping the decal at the other wall, preventing it from being rendered once past it - this can be done automatically via OpenGL's clip planes, or it can be computed manually. There are also some extensions to the algorithm outlined here that can be implemented:
  
  
  • Texture of a wall extends across the decal. If you shoot brick across the line of mortar, you'd expect to still see the mortar with brick on either side of it in the chipped-out hole left by the bullet, rather than a flat-colored hole. The vertices of the decal can be projected onto the plane of the wall (or other surface) and then the texture coordinates can be calculated relative to the vertices of the wall.
  • Lighting the decal. This may seem fairly obvious, but the decal needs to be lit - if there's a bright decal standing out in the middle of a fairly dark wall, it'll look totally out of place. Simple per-vertex lighting can be used to make it look more in-place.
  • Scaling the decal. If you have one or two decals of the same size, you're going to want an RPG impact to create a larger decal than a revolver bullet (although significant extensions to the algorithm would be required to do very large scalings without artifacts cropping up). The decal can be scaled up or down to reflect the size of the impact, thus giving some variation in your decals.
  • What to do if decals overlap. If you have two decals overlapping and you just render them both as normal, then you'll get butt-ugly artifacts - you'll be able to clearly see the models overlapping, which doesn't look good at all. What is needed is to clip the decals before rendering them if you detect an overlap (just project the bounding boxes of the decals onto the surface and check for a 2D box collision - see figure 2) and render some 'bridging' polygons between the two clipped edges (as is done in some terrain rendering LOD implementations) to close any gap that may have appeared (see figure 3).
    Figure 2 - The bounding boxes of the overlapping decals projected onto the plane with the ideal clipping line marked in red. The dotted lines represent the parts of the decals to clip away.
    
    
    Figure 3 - A 2D analogy (side-on) of rendering 'bridging' polygons. The red line represents a 'bridging' polygon, with the clipped decals either side.
    
    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="deathwish@valve-erc.com"]deathwish@valve-erc.com[/email] - 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
    http://www.dwish.net