Shadow Map Allocation

Originally posted on 15/08/2011

When I first implemented shadow mapping I began by allocating a shadow map texture to each shadow casting light. As the number of shadow casting lights grew, however, I realized that this wasn't an adequate solution. Allocating a single shadow map per-light is a bad idea for three main reasons:

1. Shadow maps have a definite memory cost, so in order to keep the texture memory requirement constant as more shadow casting lights are added, shadow map size would need to be reduced proportionally. This has an ultimate negative impact on shadow quality.
2. Rendering a shadow map can be skipped if the associated light volume doesn't intersect the view frustum, therefore any texture memory allocated for the shadow maps which aren't rendered is wasted.
3. Shadow lights whose influence on the final image is small (i.e. lights covering a smaller area or lights which are far away) require fewer shadow map texels to produce the same quality of shadow; rendering a fixed-size shadow map can therefore be both a waste of texture space and rendering time.

Issue #1 can simply be solved by allocating a fixed number of shadow maps up front, and using these as a shadow map 'pool', or by allocating a single shadow map texture and rendering to/reading from portions of it as if they were separate textures.

Issues #2 and #3 are related in that they affect the amount of shadow map space that's actually required on a per-frame basis. Shadow maps which don't need to be rendered don't require any space (obviously), shadow maps which do need to be rendered require different amounts of shadow map space, depending on how they influence the final image.

This all points the way to a solution in which the available shadow map space can be allocated from a shadow map 'pool' per-frame and per-light, based on a couple of criteria:

1. how much space is actually available
2. how much space each light requires to get good (or good enough) quality results

The first criteria is simple enough; I divide a single shadow texture up into a number of fixed-size subsections, like this:

So for a 2048² texture this gives me 2x1024², 6x512² and 8x256² individual shadow maps, for a maximum of 16 shadow casting lights. These are indexed in order according to their relative size, as shown in the diagram. Even though there is a hard limit on the number of shadow maps, the simplicity of this scheme makes it attractive.

The second criteria is a little more complex; for each light there needs to be a way of judging its 'importance' relative to the other shadow casting lights so that an appropriate shadow map can be assigned from the pool. This 'importance' metric needs to incorporate the radius and distance of a given light volume: angular diameter is perfect for this. The actual calculation of angular diameter is done using trig:

In practice the actual angular diameter isn't needed, since all we want to know is whether or not the angular diameter of one light's volume is bigger or smaller than another, so we can use a cheaper trig-less formula:

Once every frame, we calculate this 'importance' value for each visible light, then they are sorted into importance order and assigned a shadow map from the pool. The most important lights get the biggest, the least important get the smallest. Here's the whole process in action:

This technique works best if the lights are spread apart, otherwise the discrepancies in shadow quality become more obvious and 'popping' (as individual lights skip between shadow map resolutions) becomes more noticeable. The worst case is to have lots of nearby lights of similar size being allocated different shadow map resolutions; it can be very easy to spot which light is getting assigned the bigger shadow map.

Another drawback is when rendering from multiple POVs (e.g. for split-screen multiplayer). Since the importance metric is POV-dependant, the shadow maps may be valid for one view and not for another. You could use a separate shadow map pool per-view, or re-render all of the shadow maps prior to rendering each view.

On the plus side this technique makes it very easy to add lots of shadow casting lights to a scene without too badly denting the available texture resources. It also helps to maximize performance, since rendering time and texture space get spent in the places they're needed most. By using portions of a single shadow map, scaling the quality becomes as simple using a larger or smaller texture.

An additional idea would be to dynamically tessellate the main shadow map at runtime, based on the number of shadow lights and their importance. This may result in more popping, however, as the frequency of resolution changes for each light could be as high as once per frame.

The importance metric can also be used to determine how to filter a shadow map more efficiently (e.g. whether to spend time doing a multisampled/stochastic lookups).

Update (26/06/2012)

I've been asked a couple of times about how to go about using a single shadow texture in the way I've indicated here, so I thought I'd patch this blog post with the requested info. It's pretty simple and can be used any time you want to render to/render from a texture sub-region.

1. The first step is writing to the texture; bind it to the framebuffer and set the viewport to render into the texture sub-region.
2. When accessing the sub-region, scale/bias the texture coordinates as follows: scale = region size / texture size, bias = region offset / texture size.

The downside is that hardware texture filtering can cause texels to 'bleed' into the sub-regions if you're not careful. Edge-handling (wrap, repeat, etc.) needs to be performed manually in the shader. This isn't too much of a problem with shadow maps.

I recently had another idea (which I've not played around with yet - let me know if you try this out) to spread the cost of shadow map rendering across multiple frames. This could be achieved by incorporating each shadow map's age (or frames since rendered) into the metric, such that importance = radius / distance * (age + 1). Age gets incremented every frame until the shadow map gets rendered, in which case it gets reset to 0 (or to 1, in which case you can remove the '+1' from the importance calculation).

In theory this will work because, as the shadow map gets older, it gets more 'important' that rendering occurs. Whether the linear combination above will work well enough in practice is something to be tested; it may be that age needs to become the dominant term more quickly.

Integrating this temporal method with the above spatial method is made tricky by the fact that, in the temporal approach, shadow maps need to persist. Even if a shadow map wasn't updated in this frame we still need it for rendering (if the light is visible), so we can't allow it to be overwritten with another shadow map. Allowing a shadow map to be 'locked' may appear to solve this issue, however the circumstances under which a shadow map can be 'unlocked' aren't really clear: you can safely overwrite a shadow map if it isn't needed this frame. But what if it's needed next frame?