Hello, this is going to be a post that I hope drums up a discussion on the various algorithms( and their merits ) for 2d dynamic shadows.

As a preface, I have implemented and expanded on Catalin's sample for 2D Dynamic Shadows which is itself an implementation of this article on GameDev.net.
The reason I am wanting to have this discussion is that I am trying to find a way to do dynamic shadows in a performant way. Not to knock Catalina's sample, but its not exactly efficient. I know that the aim was to teach the idea first and leave the optomizations up to the reader, and I am grateful for the starting point.

With that said, I have included some optimizations of my own in an effort to nail down the culprit of the slowdown. They include:

• Creating an edge list for the convex hull at creation time instead of per frame. This speeds up shadow volume generation.
• Added a really rough circle to AABB check using the Seperating Axis Thereom. It doesn't take into account the veroni regions but in practice should be close enough for an early out. This reduced the shadow generation count: instead of L * N ( L = number of lights, N = number of objects ) it was reduced to: L * number of objects in range of L. This sped up rendering a bit.
• Added movement and rotation for convex hulls. This didn't speed things up but it did allow the addition of a convex hull following the player object around, or moveable objects.
• Added in rotation for lights, so a flashlight could be simulated.

I know some of these changes are not going to increase performance but were necessary to make it a useable system for my game. What initially surprised me was that the framerate only increased by about 30% at this point. Through initial profiling I was under the impression that the bottleneck was probably the shadow generation. Having improved it as well as reducing the number of times it was called ( from 260 down to about 60 ) I had thought to get a better result.

I know believe the problem is in the lightmap generation itself since profiling has revealed that 75% of the draw call is in that particular function, and 52% of the function is spent inside it and not its callees. Here is the algorithm for reference:

1. For each Light, set render state to draw alpha only( disable color buffer )
2. for each shadow caster( with my changes, only shadow casters in range), draw the shadow volume to the lightmap's alpha channel.
3. Set the render state to alpha blending and reenable the color buffer.
4. Blend the light texture with the scene at the correct position, rotation and scale.

As you can see, for every light there are two seperate state changes being made. I am relatively certain this is the culprit, but not completely. I'm hoping someone here has a better idea of what to profile this with( I'm using CLR and a free profiler I think was calle EQi something. I'll edit this when I get home to have the right name. ) as well as a better solution for the lightmap algorithm.

I have been having a brief discussion with Catalina about this( which is linked here ) and he suggested using the stencil buffer instead of the alpha buffer,  and clearing it after every light. I am going to implement that this week, as well as pushing the shadow volume generation onto the vertex shader as per Manders vs Machine. However if that doesn't work, I'm unsure where to turn next.

I had considered rendering a shadow id as a color to a rendertarget, and using it as a lookup for a pixel shader for each light.. but I'm not sure how to handle overlapping shadows in that case.

Anyone interested in this? I'm not looking for someone to hand me source code, just discuss it.

So I experimented with the stencil buffer last night and ended up with disastrous results. I'm sure its mismatched render states and my incomplete understanding of how I'm using it. However, something else occured to me that is bugging me a lot...

I want this to ultimately be an xbox game, so constant mid-frame rendertarget switching is definetly out.( from MSDN it seems the xbox automatically resolves rendertargets when they are switched, since it uses the same memory space for them ) That procludes me drawing the stencil shadows to a seperate render target in order to avoid switching the renderstate to turn off color writing. Plus, I'm not sure switching render targets would be any faster than setting render states... they both require a sync up between the GPU and CPU right?

So I'm at a bit of a loss right now on where to go. Both google and Bing have failed me for finding anything but the gamedev article for 2d dynamic shadows, or web pages of people who have implemented his algorithm.

I know I can speed up the general case of the game by caching static shadows, or using temporal coherence to cache them as often as possible. However, I still wanted upwards of the 8 lights I'm able to currently get at 30 fps on my laptop.

The last time I implemented dynamic shadows in 2D, I ended up using a single screen-size buffer for compositing lights into the scene, instead of doing it on a per-light basis. I also found that I needed to aggressively cache both static shadows *and* static lights wherever possible to improve performance, and that I needed to also aggressively cull the geometry I was feeding into the algorithm.

I suspect that if you stuck to a single display-sized render target for all lights, and used stenciling + a shader to render illumination for each light source to that render target in an additive blending mode, you'd get relatively good performance. However, since I did my lighting in software rendering and OpenGL, not Direct3D, I can't say whether or not it will overcome the performance issues you're having.

My understanding however is that render state changes are considerably cheaper than render target changes, though. Just think about the amount of work you'd have to do if you were writing a video driver to implement a render target change correctly - it's considerably more complex. Whether or not the driver does work to speed one or the other up is another matter - I'm sure both are relatively optimized in modern drivers.

You may find it helpful to read up on modern 3d deferred renderers, if you haven't already - the techniques they use are directly applicable to what you're doing.

It may be easier for me to help you dive into your performance issues if I have a better idea of what you're trying to do. What are the specific things you're trying to add to your game's visuals with dynamic lighting? What are the inputs you're feeding into your lighting algorithm? It sounds like you have convex hulls for objects, plus positioned point light sources.

If you feel like it you can glance at the videos of my old lighting system on vimeo and see if there are any techniques being used there that are applicable to your game. If it's of use to you, I can dig up the source code and explain precisely how I implemented it (rendering passes, optimizations, etc).

Kevin, i know its a fat chance youll read this but i would love to get that source code if you could.

Psykolambchopz:

Kevin, i know its a fat chance youll read this but i would love to get that source code if you could.

I don't have the source code for all the demos anymore, but the code for the lighting engine is up on SourceForge. I must apologize because it's not particularly high quality; I wasn't very familiar with C++ at the time.

http://fury2.svn.sourceforge.net/viewvc/fury2/libraries/SoftFX/module/Fury2.cpp?revision=52&view=markup

The lighting engine starts around line 2272. Hopefully you can make some sense of it - it's very complicated, since it had to handle a lot of edge cases.

However, I'll give a general overview of the technique:

For any given scene there is a corresponding 'lighting environment'. The environment defines light sources, light obstructions, light 'planes', and light 'sprites'.

Light sources emit light in one of three shapes: Sphere, cone, or projected rectangle (the latter projects a bitmap as a light source, essentially).
Light obstructions are line segments that block light and cast shadows. They have no thickness or depth, since my environments are 2D.
Light planes are line segments with a 'height' value: Instead of blocking light, they passively receive incoming light and project it upwards a given amount, to create the appearance of light striking a flat surface like a wall.
Light sprites are stand-ins for normal 2D sprites within the lighting environment. They can optionally both cast shadows and passively receive incoming light. If they receive light, a silhouette of the sprite is drawn with the appropriate color to create the appearance of the sprite being illuminated by the lighting environment. If the sprite has an associated normal map, that normal map will be used to compute per-pixel lighting for the sprite based on its position instead of rendering a silhouette.

The game renders the scene as you normally would, creating a composited 2D backbuffer. After this, it takes the objects from the lighting environment and builds a lightmap for the scene, that corresponds to the backbuffer:

First, the lightmap is cleared with the ambient light color.

Then, for each light source in the scene:

• The light source's illumination is rendered to an empty temporary buffer. This is done using a fast approximation (a gradient triangle for cones, a radial gradient for spheres, a bitmap for projectors).
• A pair of lines is then projected from the light source to the endpoints of each light obstruction. This is used to compute a cast shadow, which is then masked out of the temporary buffer (making that section of the buffer pure black).
• Any sprites set to cast shadows are also masked out of the temporary buffer much like a light obstruction.
• The temporary buffer is copied to the lightmap using additive blending.

Then, for each light plane and sprite in the scene, ordered by Y:

• If the object is a plane:
  
  • Light values are computed for each point along the bottom surface of the plane, via a raycasting technique. These values are stored into a 1-dimensional temporary texture representing the plane's illumination.
  • The 1-dimensional texture containing the plane's light values is rendered to the lightmap as a textured quad, replacing the previous contents of the lightmap in the area occupied by the plane.
• If the object is a sprite:
  • A light value is computed for the bottom centerpoint of the sprite via a raycasting technique.
  • If the sprite is set to receive incoming light, A silhouette of the sprite is rendered to the lightmap, replacing the previous contents of the lightmap. The silhouette is colored using the light value for the sprite, and if a normal map is available it is used to compute per-pixel light values. If the sprite has an alpha channel it is used to mask the silhouette.
  • If the sprite is set to be 'emissive', the optional emissive light map is rendered to the lightmap using additive blending.

Once this is done, you have a complete lightmap for the scene. You can then composite it onto the existing scene (I typically use a 2X multiply blend, but you can use other techniques), and you can also preprocess it, using a blur filter or such, to make it look more interesting.

In practice this is similar to a deferred renderer but has some different advantages/disadvantages. Note that this was designed and implemented before 3D hardware acceleration was prevalent so there are cases where it could be made more efficient and realistic by utilizing D3D9 features - for example, you could drop the temporary buffer for light sources entirely and use stenciling instead. You could also feasibly do per-pixel lighting computations for the entire surface of a plane, instead of just the bottom-most pixels, and get more realistic looking light for those surfaces.

Here are some images to demonstrate how it works. In this test scene, the barrels and boxes have normal maps and the boxes with lights inside them have both a normal map and an emissive map. The boxes also have a small projector attached to them.

Lightmap



Scene (unlit)



Composited Scene



Composited Scene w/ gaussian-blurred lightmap



Lighting environment in level editor


Hope this gives you an idea of how the technique works!