Happycake Development Notes:
Shadows
25 August 2004

Note: From looking at the web logs, I see that a lot of people arrive at this page from links in message boards, etc.  The shadow results on this page are surpassed by superior results in part 12 of the development log, so check out that link first.

This week I started getting serious about shadows.  First I tried some nonlinear projection algorithms, but the artifacts due to the nonlinearity were just way too ugly.  (But there seem to be some very interesting algorithms there, which will be usable sometime when hardware can render arbitrary curved surfaces!)

So I went back and started filling out the rest of the algorithm that I'd been expecting to do all along anyway, which is to use a series of standard, non-projective shadow maps of increasing sizes centered around the player.  After about a day and a half of work, I am pretty happy with the results so far:

In the following picture you can see shrunken-down versions of the shadow maps lining the bottom of the screen:
 

These four white squares are essentially images of the scene drawn from the point of view of the light source (without color).  The left-most one shows the shadows cast in the area immediately around the player; the next one shows shadows cast by things somewhat further out; and so on.  In the rightmost shadow map, the city so far is a tiny blur (though it actually has more resolution in game than is shown there, because the shadow maps are currently 512x512 but they are being drawn in that picture as only 128x128).  Staying with only 4 shadow maps, we could draw visible shadows for a scene much, much bigger than the current little city piece, as much as we could cram into that square.  And if we need a 5th map, or we want to insert more maps to give increased resolution, we can do that pretty easily.

Here's a demonstration of the shadows as visible from far away:
 

I had originally implemented a low-effort version of this for Galstaff (a personal project I had been working on), and when Happycake started up, it just inherited the Galstaff shadows.  Galstaff used only two shadow maps, which isn't enough to get shadows out to an appreciable distance.  Mainly I stopped there because it seemed too slow to do more than that.  But actually, rendering shadow maps is really fast!  After cleaning up the game's Direct3D state management a little bit, we can render these shadows very quickly on my lowly laptop.  And there is much more state management cleanup to be done!  And also the shadow maps themselves are less efficient than they could be.  (I am using 32-bit floating point textures for the depth information, which is overkill; and each shadow map also has a separate depth buffer, which I am using in the hope that it helps with fast-z-culling, but I really don't know the effect of that.)  Now that I am seeing how nicely this runs, I am very happy about it.

It's funny, because I used to consider this algorithm somewhat lame, at least deep down subconsciously.  I had spent a lot of time wrestling with things like Perspective Shadow Maps and getting very disappointing results.  This multiple-shadow-map thing is just a way of getting perspective without having all the singularity problems, resolution warping, etc that you suffer with PSM.  So one reason I hadn't done this work sooner is because deep in the back of my mind I was kind of bummed about this algorithm and that it was the best I could do, after all that work.  Then I was watching John Carmack's QuakeCon 2004 keynote, where he was describing the technology for his next engine, and he described exactly the same algorithm.  And hey, if Carmack's doing it, it can't be that bad.  (Uhh... clipping lines against the frustum in polar coordinates notwithstanding).  So then I felt better about the algorithm.  Which is kind of ridiculous, because I shouldn't require that kind of external validation to appreciate the technical merits of something, but it seems I'm not perfect.

The nicest thing about this algorithm is that the resolution is rock-solid stable -- doesn't matter what objects are in the scene, your shadows will work.  This is in stark contrast with various PSM algorithms that try to play lots of fiddly games about focusing the active shadow area on small subsets of the screen so that they can get acceptable resolution.  (I hate PSM.)

However, in Happycake with the current settings, you can see that the shadow resolution is a little bit lower than I'd like by default, and it's blocky too:
 

The blockiness is just happening because the shadows are point-sampled right now.  This can be solved by taking multiple samples from the shadow map per pixel.  Unfortunately, I seem to be banging against the pixel shader 64-instruction limit for ps2.0 and prior.  Now that DirectX9c is out, we can exceed the 64-instruction limit by specifying a more advanced pixel shader model, but it would only run on a Radeon X800XT or GeForce 6800 right now, and I don't want to buy either of those yet in the hopes that ATI releases a ps3.0 card before this project is over.  (If they don't, we will be switching to Nvidia).  I have a lot of uses for things like vFace, and I need to be able to alpha-blend into deep frame buffers, neither of which I can do on the current ATI card. 

John Carmack mentioned in his lecture that he had some really great idea for randomized shadow map sampling.  I don't quite have a clear picture of how this takes place in a shader (maybe they use dependent texture reads to get the sample coordinates).  For the level of visual quality we are targeting for this game, that might not be necessary; I can probably get by with 4 or 5 samples per pixel laid out in some regular pattern.  I'll be trying that sometime later when we have more pixel shader instructions, and/or figure out a more clever way to do the shadow map filtering.  (ATI has a demo on their developer site that they claim is performing percentage-closer filtering, but it actually is not, the results are much inferior.  Shame on you guys!  Real percentage-closer filtering seems to require significantly more instructions, but then again, I haven't yet sat down to give it a good hard thinking-about.)

The low resolution for things up-close is actually a side effect of a different issue.  My original settings actually had the resolution much finer, but I ran into a problem.  Due to the way objects are rendered, we need to set up 2 shadow maps for each entity, of consecutive resolutions, so that the shadow resolution can transition smoothly across objects.  Since shadow maps are associated with various distances from the camera, then given a particular object, the furthest point on that object from the camera determines the lowest-res shadow map that it needs, and the highest-res shadow that can be painted on it is then one resolution higher than that.  My problem was that the individual blocks of the terrain mesh are pretty big right now (a little over 50 meters), and that was so big that it wouldn't fit within shadow maps 1 and 2.  It had to fall back to maps 2 and 3, which meant that anything casting a shadow on the terrain close to the camera would cast a crappy resolution-2 shadow.

One way to fix this would be to shrink the terrain blocks, but that would involve messing with some saved data, and it would also affect the batch size for terrain rendering (smaller batches = slower rendering!)  But then again, there probably aren't very many terrain blocks, due to the hierarchical combination, so a smaller batch size may not be so bad.  Since I didn't want to mess with the saved data right now, though, I just lowered the shadow resolution until terrain blocks would always fit into resolutions 1 and 2.  I figure there's no use sweating too hard about the shadow resolutions right now, because it'll be hard to determine what the "acceptable resolution" is until the shadow antialiasing is in there. 

There are some other solutions we could do, such as rendering using 3 shadow maps at a time for large objects near the camera (eww -- I don't want to have to maintain more shaders), and raising the resolution of shadow maps 1 and 2 to be higher than the others so that they can stretch out further without penalty.  (Considering how well this runs on my laptop, I am taking for granted that some kind of increase in shadow map size or quantity or both will happen for the target platform.)

Here's another example of a resolution problem, slightly further away (see the jaggy shadow cast by the railing onto the walkway):
 

... but I think this is all solved pretty easily on the target platform.

There's one more class of things that often happens with shadow map algorithms, the surface acne / Peter Panning problem.  But I think that given vFace (also available on the target platform), these problems can be solved pretty effectively.

[Back to Happycake development log]