1
\$\begingroup\$

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 ?

\$\endgroup\$
1
\$\begingroup\$

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. enter image description here

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ I am a fan of the distance fields for procedural generation of content. Haven't heard of using it for shadows, though! Interesting ! Thanks for the links, I am going to give it a proper read, first. \$\endgroup\$ – 3D Coder Jul 28 '15 at 21:00
  • 1
    \$\begingroup\$ So, I read through the paper and it is shader-only solution that also relies heavily on bilinear filtering in HW. None of which are available for a SW rasterizer. I am grateful for the link since it broadened my horizons about usage of distance fields, but implementing this technique on RISC would be easily an order of magnitude slower than the next fastest thing. However, this paper primed my brain into finishing another idea that I had last few weeks, but it just unfolded upon reading first page of the paper. So, you basically nudged me in a good direction ;) \$\endgroup\$ – 3D Coder Jul 29 '15 at 19:39
  • 1
    \$\begingroup\$ Oh, it worked out way too good,as while reading your paper,even though it is mostly unrelated, I was imagining the projected shadow texture and when the paper mentioned vectors, that's when I realized I could greatly simplify the storage and computational overhead of the 'not-the-solution-yet', that I was pondering last few days. If I wasn't reading your paper, the solution might have eluded me altogether ! It's like when they were trying to prove the NGC0XXXX galaxy has supermassive black-hole by comparing it with Andromeda (that didn't have one),but by doing it, they found one unexpectedly. \$\endgroup\$ – 3D Coder Jul 30 '15 at 12:56
  • 1
    \$\begingroup\$ ad Bilinear: I was hoping for some neat trick that would reduce the super-expensive 4 memory reads, but it looks like the article covers just basic stuff.While experimenting,I came up with a semi-bilinear filtering (horiz./vert.) that doesn't have any additional memory-read costs, by simple early pre-fetch, and at the cost of 2 RISC instructions - so basically free - but looks much better than no filtering.It's of course possible to do a bilinear for ~free too(no 4 reads), if you break down texturing routine,so it works in blocks of 2x2,at the cost of more instructions that handle the blocks. \$\endgroup\$ – 3D Coder Jul 30 '15 at 13:19
  • 1
    \$\begingroup\$ On topic of filtering - do you have anything on more expensive filters ? Personally, at load-time (the additional wait is minor, but end result well worth it), I am using various kernel sizes (2x3, 3x3, 5x5) and various shapes (quad, cross, diamond) of filters, as each texture looks best only after a certain combination of kernel shape&size is applied to it. I was wondering if it's merely 'artistic' or there is some science to the low/high-frequency distribution of the texels and the best combination if filters to enhance its look. \$\endgroup\$ – 3D Coder Jul 30 '15 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.