Efficient dynamic character shadows [SW Rasterizer]

Question

I am working on a SW rasterizer for a quarter-century old console (think sub-100 MHz RISC CPU, no dedicated 3D HW, couple megs of RAM) and am approaching a stage where I will be adding dynamic character shadows. It's a next-gen engine for the platform, so there are no known or proven approaches. Basically, render stuff as fast as possible - e.g. in least amount of instructions (and least amount of RAM access).

The biggest performance bottleneck of the platform is memory read / write(e.g. fillrate). The RISC can do almost all instructions in 1-3 cycles (except division), but anything requiring access to main RAM is 10x slower (than from small cache).

I am not looking for some generic shadowing solution (I wrote few for PC/XBOX-using Shadow Volume and Shadow Mapping, so I have an idea how shadowing works). I am alright with writing multiple codepaths for multiple scenarios (e.g. one for characters, another for static objects).

Known limitations:

1. No Z-Buffer
2. No Stencil Buffer
3. Target resolution : 320x200
4. Shadows can be black (no need for transparent shadows)
5. A fallback shadowing solution is having pre-rendered shadows from each animation frame into texture and just drawing the texture below character (but it looks too lame). It's possibly the fastest solution, though (rotate shadow bitmap and just blit the texels)

Considering the above limitations, I have chosen the technique of transforming the character mesh (a low-poly version of the original mesh) onto the floor plane (from the position of the light) and drawing the shadow mesh on the floor (with black color). This should result in the desired sharp shadows without any pixelation effects (unlike shadowing methods based on projecting a shadow texture). But it will provide an effect of shadow being very large initially, and as character walks around, the shadow shrinks (until he is right below the light source) and then the shadow grows again.

Advantage:

1. Generic : If need be, I can apply it also on the walls, not just the floor
2. Fast : Transforms are fast on the RISC

Disadvantage:

1. Overdraw : I expect a major portion of the floor to be covered by the shadow (lightpos will be tweaked accordingly, for the sake of the effect). Since shadow is black, all the expensive lighting calculations on the floor are wasted, since they are [mostly] overwritten by the shadow.

The floor (basically one large rectangle) is internally divided into multiple square tiles (anywhere between 10-100 tiles per room). I think I can easily find out which floor tiles will be affected by shadow (I will calculate them during projection of the mesh onto the floor).

Question - how can I easily merge the floor texturing routine with the shadowing ? Ideally, each texel would be written just once. There are just two choices - either it is a floor texel or black (the shadow).

Anything - that merges the two approaches into one which will be faster than rasterizing a floor and then overdrawing majority of it with black shadow- is a win. Ideas ?

The most amount, I could theoretically spare, from the tiny cache (10x faster access than from main RAM) is about 1-2 KB for a temp buffer. Obviously, it is not enough to cover all shadow texels at given resolution, but it could perhaps prove useful for some other algorithm.

As of right now, I can only think of span buffers as the best solution for the overdraw. The spans would be short (e.g. easily fit into 1-2 KB), I just would have to rewrite the floor texturing algorithm - but if it was a faster solution, I could do that.

Any other ideas ?

Answer 1

If you eventually end up going with the pre-rendered shadow approach, or any other texture based solution...

To save some memory, and maybe also to be able to soften up the edges of the shadow (maybe even contact hardening shadows), have you considered using distance field textures?

They are useful for monochromatic textures (decals, fonts and shadows!), and each pixel encodes a signed distance to the shape. Positive = outside, negative = inside. You basically treat 0 to 255 as -1 to 1.

The benefit here is that you can use a much smaller texture for really nice results. With knowledge of the distance in texture space, you can also do things like stroke and anti aliasing, or making the texture have a softer edge under certain conditions (;

The best part is that the logic to render it is essentially an alpha test that could be performed by FFP, so should be very efficient in your usage case.

As an example, this 1280x720 mustache decal image was generated using a 64x32 single channel source image with alpha test logic.

And here it is using smoothstep (y = 3*x^2 – 2*x^3) to give a little softness and AA to the edges.

My blog post on more details is here: http://blog.demofox.org/2014/06/30/distance-field-textures/

Valve's paper on it is here: http://www.valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf