There are two components to rendering decals that you'll need to deal with. The first is actually constructing the decal mesh itself. I've written an article about this that can be found in the following two places:

"Applying Decals to Arbitrary Surfaces", Game Programming Gems 2, Section 4.8, Charles River Media, 2001.

Mathematics for 3D Game Programming and Computer Graphics, 2nd ed., Section 9.2, Charles River Media, 2004.

The second thing is implementing some kind of polygon offset. OpenGL has the glPolygonOffset() function and DirectX has the D3DRS_DEPTHBIAS render state, but using either of these causes hardware-based hierarchical z-buffering to be disabled, reducing performance. I developed an alternative back in 2000 that modifies the projection matrix to achieve the same effect without any performance impact. You can find this article in the following two places:

"Tweaking a Vertex's Projected Depth Value", Game Programming Gems, Section 4.1, Charles River Media, 2000.

Mathematics for 3D Game Programming and Computer Graphics, 2nd ed., Section 9.1, Charles River Media, 2004.

-- Eric Lengyel

I use it very liberally in my engine, and the performance is fine. Since creating a decal is not something you do every frame (unless lots of characters are continuously spraying bullets all over the place), it doesn't have a significant performance cost. And I've found that clipping a mesh to a decal boundary goes very quickly (that is, there is no detectable delay, even with good instrumentation, that appears during frames in which you do create new decals).

You can download a demo of my engine at the link below. All of the scorch marks that you see when you shoot stuff use the exact techniques described in the above articles. Go ahead and go crazy with the plasma gun (the green gun that you can find in the warehouse-like room -- hit 4 to use) and see how well it works. You can toggle wireframe to see the decal meshes by typing "wire" in the command console.

http://www.terathon.com/c4engine/download.html

-- Eric Lengyel

Edit: Made link clickable

Thanks. The standard shadow technique used by the engine is stencil. The shadows for the trees are actually stored in a precomputed orthographic shadow map (depth along the light direction).