How do modern game engines handle many shadow casting lights?

Question

This is a very general question, and not aimed at any particular language or graphics API; I am more interested in the theories & algorithms behind the solutions.

I'm reasonably familiar with the basic idea behind shadow mapping:

Each spotlight and directional light requires a rendering pass to generate it's shadow map, and each point light requires 6 such passes, prior to any lighting calculations.

Such a potentially large number of rendering passes could quite easily have a substantial negative impact on performance and texture bandwidth, so how do modern game engines deal with this problem, especially in the case with deferred rendering systems, where many lights are involved?

Consider the following scenario:

A scene contains a reasonable amount of geometry, spread out over a "level". That level has a certain number (let's say 20, for brevity) stationary point lights dotted around the level. The player can place lights around the level too, and carries a torch (spotlight).

The rendering system uses the deferred shading model, given the potentially high number of lights in the scene.

How does the renderer decide which lights to render shadowmaps for? Of those lights, during the "light pass", how is that variable number of shadow maps handled dynamically, bearing in mind that they could be 2d textures (spots and directional), or cube maps (points)?

Do graphics API's have the capability to support shaders with arrays of maps/lights, or would the shadow maps require a single discrete lighting pass for each individual light?

Answer 1

I don't really see the intent of the question, but I will give a stab at it anyway. For a start, there is no silver bullet, if you want shadows, you need to some form of shadow test. Commonly in current hardware this is achieved with shadow maps. But there are a few "hacks" that can be used to speed up the entire process.

Deferred Rendering

Speeds up the rendering of large amount of light sources. Normally with forward rendering you have to render each geometry (G) for each light (L), resulting in cubic complexity. O(G*L) Deferred rendering allows you to render the geometry once and each light separately, resulting in linear complexity. O(G+L) The only downside here is that you need to have some special handling for transparency. But if you want to do that properly, you need to do it separately anyway.

Baked Light & Shadow Maps

One trick that the Unreal Engine uses a lot, is pre-computing or baking the lighting information for everything static. The engine separates the geometry and lights into static and dynamic items. Static lights on static geometry are backed into a light map with lightmass. This uses a high quality global illumination solution and results in nice looking shadows. They are "free" since they are just blended onto the geometry in the standard render pass. Everything dynamic computes a shadow map on the fly. The renderer then decides based on the dynamic / static light and geometry if to apply shadows or not. But since the number of dynamic objects tend to be few, this works quite well.

If you can live with dynamic objects not casting shadows, you can pre-compute the shadow map from all static lights.

Answer 2

I can't answer to the question "how do they do it" but i can tell you how did I. In fact, I wrote a 3D Rasterizer / Renderer with dynamic interpolated directional lighting and had some performance problems while dealing with several spot lights or light sources.

As long as I worked on it, I discovered there are some tricks that one can implement in order to reduce the iterations and shadow map complexity:

1. dark by default

My models where rendered as rgb-50,50,50, my textures colors were several points lower than the final color I wanted to achieve (related to points bellow)

2. don't aplly shadows but lights

I realized that casting light is lot easier than computing shadows, get a spot light, get the angle between the poligon normal and the light vector and interpole the result in a "brightness" scale, by doing this, you can just ignore all those polygons that are not in a given angle relative to the light source, speeding up the process. If the scene has many of these light points, just repeat the process.

3. baked shadows

In fact, I decide to use ambient oclusion as standard, since it can be easily baked into the 3D object at load time, just decide your "incidence angle" (i used the camera initial position) and apply the color mutation. after the dynamic lighting explained above, the result is real enough to look as if it were all dynamic.

4. Blending

I'm not sure if this is a good point or if it just works for my pet project, but i used to blend the SSAO into each texture so it were just calculated once.

5. Cache

Same as point 4, i used to do it but not sure if it's done like that in the industry, i made a cache for each drawable entity to store the "main" poligons affected in each angle, so the engine had to iterate every objects polygons just once in each position, after that, the cache knew exactly which indexes were affected in each angle for each object so just one array of indexes had to be calculated, and, if the angle was between two cached angles, then both index arrays were used, it got pretty fast after doing this

Hope it helps :)

Answer 3

Here is how I do it in my engine:

The scene can hold an arbitrary amount of lights, of which arbitrary amount can be tagged as shadow caster.
There is a shadow budget which is the number of the maximum amount of shadow maps allowed to be rendered in a frame. Usually, the closest lights are prioritized, but screen space area occupancy could also be taken into account. If there are more lights tagged as shadow casters than the budget, then the shadow rendering ends, and remaining lights will have no shadows. This kind of simple logic can however result in popping, so it could be beneficial to smooth the transition of a shadowed light from "rendering shadow in this frame" to "unable to render shadow in this frame so bypass shadow".
You mentioned that point lights need 6 shadow passes, but it can be easily achieved in a single rendering pass with a recent graphics API eg. DirectX 11.
For deferred rendering, you could render the shadow map just before rendering the light so you can have a single shadow map for each light if they have the same resolution requested. But in case of a Tiled Forward (or Forward+) renderer, you are looping through each light in the mesh object shader, so you have to provide all shadow maps up front. You have to render shadows into multiple textures in this case, I recommend storing them inside a texture array or texture atlas.

For performance reasons it is very important to avoid rendering objects into the shadow map which are not inside the range of the light. The trivial way to do this is just to check for each object if it is intersecting with the light bounds (AABB, sphere or frustum).
There are further optimizations possible with this.

• You could use a space partitioning accelerator structure like an octree so you could query the intersecting objects faster.
• For point lights, only render objects to the minimal amount of cubemap faces it intersects. It complicates things when you want to render in one pass, but doable none the less with instancing.

An advanced optimization is to only re-render objects to the shadow maps which are changed from the previous frame (or all if the light position has changed). For this you have to keep the static parts of the shadow maps in a separate texture, and the dynamic parts in an other (or different parts of a texture atlas). I haven't implemented this, but the new Doom game has this working as I've heard.

There are other techniques used for shadow rendering apart from shadow mapping though:

• Shadow volumes. It was widely used after Doom 3 came out, but once shadow mapping got efficient to do on GPUs, it got overlooked because of high CPU requirements. It could still be relevant if GPU is overcommitted I think. Oh and I reckon something about patenting issues for this technique.
• Ray traced shadows. Trivial to implement in a ray traced renderer, but for game engines, it could be implemented in screen space in the form of ray marching.
• Voxel based shadows. There are some engines capable of voxel based global illumination (like mine :P), and for a voxelized scene there can also be shadowing information retrieved from ray marching ("cone tracing") the scene.

There are also light maps or some form of baked lighting which is calculated offline and needs only a single texture sample when rendering. This is obviously the fastest, many engines support it by default, but it can be hard to sync it with real time lighting while still getting accurate results.