Working on shadows…

Those that follow my twitter account have seen this already, but I wanted to let everyone know I’m working on a system for 2D dynamic shadows, again.

However, this one is very different from the last sample I made on the subject. In that one, you had to define the geometry of the shadow casters, and build the shadows based on that. This process also implied lots of computations done each frame on the CPU, which yielded in low peformance. So all in all, even though it looked great, I was never really satisfied with tat technique for shadows.

I spent a lot of time thinking of an alternative way to do dynamic 2D shadows, while not using the CPU too much, and having unlimited complexity for the shadow casters. And two weeks ago, the idea hit me. I’m not going to go into technical details just yet, since I plan to make a nice tutorial about this, but I can say that my idea was based on taking the concept of shadow maps from 3D and somehow use it in 2D.

Here’s two pictures of how it looks so far:

first version

second version

As you can see, the casters can have any shape and complexity, and furthermore, the complexity of the shadow casters has no effect on the framerate.

I’m still working on this, but you’ll know as soon as it’s done.

Categorized: HLSL, XNA
  • Pnikosis

    So with this new method you don’t define the geometry for the shadow casters? Now I’m really curious on how your method works, looks really nice.

  • http://www.catalinzima.com Catalin Zima

    Indeed, you don’t define the shadow caster geometry. It’s all image based.
    So you could have shadows casted by animated sprites, particle systems, deformable terrain.

    There is one drawback as opposed to geometry-driven shadows. Here, the size of the area for which we compute shadows affects performance, as opposed to geometry shadows, where this doesn’t matter. But some tricks can be used for better performance, if needed. I’ll cover them also when I’m done :)

  • Pnikosis

    Amazing! I’m eager to see it. I’ll wait patiently 😛

  • http://fxcritic.blogspot.com Chance

    This is the solution to exactly the same problem I’ve been trying to solve for my 2D shadow engine :) Amazing stuff!

    I’m just dying to see how you pulled it off, so I can compare it to my own solution. Will it spoil the fun too much if I post about the ideas I am exploring so far? It’s all image-based as well and that’s exactly the requirement I wanted to solve most.

    Congratulations in advance for solving this :) I was yet to get my own to work…

  • http://www.catalinzima.com Catalin Zima

    sure, I’d be interested to know how others thought to solve this problem.

  • http://fxcritic.blogspot.com Chance

    Ok, then, I’ll try and summarize a little about what I was thinking for my lighting and shadowing system.

    My current approximation to lighting was texture-based fake lighting, so basically my “lights” were just regular sprites representing light maps rendered into an additive render target which was then modulation blended as a post-process on the regular scene.

    For shadowing I was thinking that maybe I could compute or have pre-baked light “propagation” textures, indicating the propagation vectors for each light sprite (in this case, attenuation intuitively corresponds to an image gradient in these propagation textures).

    Now, my main idea was that for each non-transparent pixel sprite, the light propagation vector at the location of that sprite indicated the offset of shadow “extrusion” for that pixel (basically indicating how much to offset and scale that pixel for the shadow map). Multiple lights could be handled by somehow numerically combining the propagation textures in a number of ways.

    Ultimately I faced a number of problems trying to imagine an implementation for this approach, namely:
    1. It doesn’t appear to be ammenable to shader based implementation.
    2. It doesn’t appear to be that efficient
    3. Numerical combination of “propagation” textures can even be a wrong approach for doing shadowing in the first place.

    That’s it. My two cents on image-based 2D shadowing. I’ve been rummaging on this for the last week, but didn’t get around to grind this into code yet.

    Once again, just dying to see your take on this :)

  • http://www.catalinzima.com Catalin Zima

    The first part is absolutely fine. You have several lightmap, add them together to obtain a single light map, and combine that with the normal scene. There aren’y many alternatives to that. The actual problem is generating the lightmaps.

    I’m not sure I entirely understand your method (maybe I’m too set on mine), but at first look, it seems that it’s quite mathematically heavy, and indeed, doesn’t seem to map to a shader-based implementatio too well.

    And now I realised it’s been a month and a half since I posted this teaser… I really hope I can release the code soon :)

  • http://fxcritic.blogspot.com Chance

    I’m really hoping for the release of this tutorial :) I’m still trying to hint at how you addressed the shadow map generation. Can I ask you a quick question?

    You mentioned how your algorithm retains its complexity regardless of the shadow casters’ complexity. What about the lights? Does the complexity remain the same regardless of the number of lights? Or does shadow computation have to be addressed on a per-light basis using this method?

  • http://www.catalinzima.com Catalin Zima

    Unfortunately you can’t have it all :)

    While the number and shape of casters makes no difference, the algorithm is executed per-light. So the factors that influence performance are the number of lights, and the radius of each light. Obviously, a smaller light will be faster to compute than a large one.

  • http://fxcritic.blogspot.com Chance

    I’m sorry for being curious, but I’m enjoying the reasoning process 😛
    The fact that the method works per-light has made me wonder, mainly of whether it works on a pixel- or sprite-basis, and particularly whether it will work for any particular shape of light.

    Initially, when I heard the suggestion that the method was a sort of translation of shadow maps from 3D to 2D, I found it strange since shadow maps in 3D involve rendering the scene from the light’s point of view (and how can you do that in 2D?).

    But then it struck me that there’s probably a perspective transformation which you can apply to a sprite so that you obtain the extrusion of that particular sprite in relation to the light’s position. So in principle I believe you could indeed render the sprites from the 2D point light’s “point of view”.

    However, you mention that the number of shadow casters makes no difference, so I’m still in doubt whether the method is somehow pixel-based. In this sense you could possibly apply a light of any shape and still come up with fairly realistic shadows. If this was the case, this means that only pixels inside the light radius would be affected, and, in the worst case, it would mean that I could blend all lights into a single “light texture” and treat that as my “light”, and make a single-pass through all image pixels. That wouldn’t be so bad.

    But, alas, I’m still not sure how you could go about the pixel-based version… Sorry for the rambling! Hope I’ve explained myself clearly enough, though. Just can’t wait for this one :)

  • http://fxcritic.blogspot.com Chance

    Today I took a little time to read on the subject and I caught hold of Mander’s technique: http://blogs.msdn.com/manders/archive/2007/03/14/shadows-in-2d.aspx

    Is your method in any way related to this technique? It looks pretty reasonable, although he relates the method to shadow volume rendering and not to shadow maps…

    Well, just another wild guess :)

  • http://www.catalinzima.com Catalin Zima

    No that’s not it :) His method is geometry-based.

  • http://fxcritic.blogspot.com Chance

    Yes, I tried to imagine whether you could generalize his method to work on any sprite form, but it’s not so easy.

    In the meanwhile I found another method by Lukas Heise which is indeed image-based :) Although his example is pretty hard-wired, he uses a heightmap of the rendered scene and samples pixels from this map in order to determine whether a given pixel is in light or shadow.

    You can find it at http://www.lukasheise.com/web_res/progs.html
    It’s the Dynamic 2D Shadows Demo near the end of the page.

    In the end his method is quite similar to ray tracing, where he samples the line from the light to each target pixel and tries to find out whether there is any obstacle in the way.

    He only provides the shader sources, but based on that I managed to port it successfully to XNA 3.1, and it works quite well for his specific example.

    Is this technique closer to the mark? 😉

  • http://www.catalinzima.com Catalin Zima

    Something like that was my initial take on the problem.
    However, the issues is that it is not really GPU-friendly because of the sampling it does along the light ray, and I also am not sure how he deals with thin objects (which the samples might miss).

    So this is somewhat closer, but still not it.

  • http://fxcritic.blogspot.com/ Chance

    You’re right, of course, and Lukas does not seem to deal with any of these issues (in fact, his sample has really large shadow casters probably for this very reason).

    I think I’ll just wait patiently for the tutorial from now on. I’m sorry for being such a pest 😛

    Until then I’ll try to figure out how to reinterpret the shadow mapping idea to 2D as you said. My main difficulty is figuring out what it means in 2D to “render the depth map from the light’s point of view”. This makes complete sense in 3D since the shadow map is essentially an index into the light’s “first occluders”.

    But I can’t for the life of me figure out how to obtain such an index for a 2D setup…

  • http://www.catalinzima.com Catalin Zima

    In all honesty, I wish I could find a way to organize my busy schedule, and start letting out more info about this without waiting till all is written. I even though about splitting the articles into a series of episodes, and releasing them as I write, but this would involve a high risk of something coming up in the middle of the tutorial, and having to leave it incomplete for a longer while.
    I’m still trying to figure out the best way to get this thing out as soon as possible, and in a form that’s convenient for everyone. Sorry you need to wait so long :)

  • http://fxcritic.blogspot.com/ Chance

    Any news on the shadows tutorial? Any new hints you can let out? Unfortunately I’ve had little time (and I admit no inspiration) to think about new solutions to the issue and your claim to the problem is still the strongest of all I’ve found on the web.

    Would be really nice to have an inkling of the approach you used here. Can’t seem to get there without stamping on the methods I’ve enumerated above… Will keep trying, I guess :)

    Again, nice work.

  • http://fxcritic.blogspot.com/ Chance

    Hi again :) Today I’ve been reading some papers about dynamic soft shadows in GPU and this one caught my attention: “Approximate Soft Shadows win an Image-Space Flood-Fill Algorithm”; from the fact that they used recursive flood-filling from umbra regions to compute the penumbra.

    Could it be that your method is somehow based on flood-filling heightmap occluder pixels to cover the light range? That technique had crossed my mind before, but flood-fill seemed terribly expensive to run on GPU because of the multiple passes… although it would work.

    Just another possible method for the record.

  • http://fxcritic.blogspot.com Chance

    I’m very, very sorry for being so active in a comments section, but since I started my search here this has become a very nice compilation of techniques.

    I’ve just found what seems to be a very efficient and interesting way to implement flood-filling in the GPU, requiring log(n) passes to fill a grid with dimensions n x n. It’s called Jump Flooding and the original paper can be found at: http://www.comp.nus.edu.sg/~tants/jfa.html.

    So basically it seems like flood-filling may even be an interesting technique after all :) I’ll analyse it further and if I can derive and implement a 2D shadowing algorithm from it I’ll be sure to post it here.

    Thanks again and sorry for the loudness again…

  • http://www.catalinzima.com Catalin Zima

    Hi Chance,
    I really appreciate your interest in this, and I’m really sorry I can’t be more involved in this discussion.
    Jump Flooding is an interesting technique, but I’m not sure it could be all that useful for shadows. I would have to look at it into more details. Though to be fair, my technique does something similar to flooding.
    Basically, for each “ray” starting from the source of light, I find the position of the closest occluding pixel along that way. Then, whenever I test a pixel for shadows, I see what ray it stands on, and see if the distance from this pixel to the light is larger of shorter then the minimum on that ray. As I said, very similar to how shadow maps work.
    Unfortunately due to time constraints, work, and real life, I haven’t been able to write the promised article.
    I think I will be forced to publish the sample soon, even if I don’t manage to write an article about it, though it would be a shame not to have a proper explanation of the technique.
    You’ll be the first to know when I manage to release something :)

  • http://fxcritic.blogspot.com/ Chance

    Hi Catalin,

    First of all, please don’t worry about being busy. We’re lucky enough you have any time at all to share your knowledge with us for free 😀

    Second, thanks for the insight! I understand the principle behind it now, and will try a few experiments with the concept. You know, this idea kind of hit me, but I think I dismissed it too quickly as being too heavy to compute. However, on a second pass, I think I can come up with a few ways to speed it up :)

    Third, this Jump Flooding algorithm is looking pretty neat. I’m already past the point of verification and moving out to a full-blown implementation. I’m pretty sure it will work for shadows after the first rough experiments I tried, although the principle is much closer to shadow volumes than to shadow mapping.

    Basically the idea is simply to “seed” the shadow map with the pixels from active sprites, since they are all possible occluders. Then what I do is basically jump-flood the shadow from there following the direction of light.

    Besides the log(n) passes (e.g. 9 passes to flood a pixel into an 800×800 pixel grid), the shader runs only on the pixels affected by the light. If you use sprites as light shapes, you can pretty much constrain the number of pixels affected, which will also reduce the number of passes.

    The shader is still a bit heavy from texture sampling (a total of 8-9 samplings corresponding to the k-neighbors sampled around the tested pixel), but I’m yet to reach a profiling phase. For now, just need to put this up and running.

    In closing, I wanted to assure you it’s been fun to learn about all this. While trying to crack your idea, I learned about all sorts of techniques, and even maybe ended up with a different idea of my own to try. So all in all, a great time.

    Will look forward to the sample/tutorial of course 😀 Keep up the excellent work!

  • http://www.catalinzima.com Catalin Zima

    Good luck with your implementation, and I think it will be very interesting to see such an implementation, whatever the outcome.

    Well, if my posts made you want to learn more and experiment with all sorts of stuff, then I am very satisfied :)

  • http://fxcritic.blogspot.com/ Chance

    Hi again,

    Just to let you know that I managed to implement a somewhat working solution for shadows starting from the Jump Flooding idea. However, I have to admit it didn’t quite live up to my expectations from two main factors:

    – although I’m only using log(n) passes, it still hits quite a bit on the render frame rate. Right now on my computer (which granted isn’t all that great) it’s running at just above 30 fps… not so bad for seeing the effect, but terrible if you want to build a game on top of it.

    – I managed to reduce texture samplings down to a maximum of 2, since I finally realized I didn’t need to sample all neighbors like in Jump Flooding, but just the neighbors along the line to the light. What finally hit me was that this was the same as Luke Heise’s method, but with line samplings spread across multiple passes, instead of sampling as much as a single shader pass would allow (he did close to 16 texture samplings).

    Right now I’m thinking of following your hint and implementing a new solution based on tracking first occluders and see how that goes. Anyway, I’m putting my “Jump Trace” solution on my dropbox if you want to take a look. It’s not very big and for an experiment, it’s relatively “clean”. Here it is: http://dl.dropbox.com/u/3907539/Dynamic2DShadows.zip

    Again, thanks for everything :)

  • http://www.catalinzima.com Catalin Zima

    Thanks,
    I’ll try to take a look at it later :)

  • Pnikosis

    Nice sample Chance! I’m totally ignorant about graphics programming, and I’ve been looking for implementing 2D shadows as well, so I’ve been following this thread with big interest.

    And thanks Catalin for sharing with us your knowledge (right now I’m using your old 2d shodows method), and for this interesting discussion.

    I’ll keep following this comment thread with great interest. Cheers!

  • Michael

    Ive been trying to work out the same thing, starting by modifying A*, unsuccesfully of course. But i think i may understand your method. You create a ray map by checking each occluding pixel and setting that pixel edges angles and distance from the light source, if its not completely enclosed in an existing ray. next, you render the shadow map by drawing all pixels not even partially obscured by an occluding pixel’s ray. As an added bonus, you can simulate transluscent materials by adding a falloff multiply value and possibly even a colour value to the ray. I havn’t tried this (i am at work) but it seems to work in my head and on paper.

    Cheers,
    Michael

  • http://hotel-gostey.ru Борис

    А вы сами так пробовали?

  • Brett

    Do you do the occlusion checks for each ray on the CPU or in the shader?

  • http://www.catalinzima.com Catalin Zima

    In the shader

  • Brett

    Thanks a lot I went that direction and it works great. Much much more efficient than ray tracing each pixel. Thanks for the idea, you’re a genius.

    If anybody is interested I’ll share my code after I add add multiple light sources and optimize it a little

  • John Hampson

    Hi Brett,
    Would you mind explaining how you stored the occlusion information? I’ve been trying for a while now and can’t figure out how to store the distance of the occluders along a ray in such a way that the pixel shader can read them later.

    If you wouldn#t mind, it’d be great to see until Catalin has finished his tutorial.
    thanks

  • John Hampson

    Hi Again,

    Or are you actually creating the ray in one shader pass and running a texture lookup all along the ray to find the closest occluder?

    @ Catalin, a little late, but congratulations on getting married!

  • Pingback: XNA Bits « XNA Tidbits

  • http://www.twsfqwygdvwgqd.com Alina Lauri

    Hey foq6 k6, very interesting post, it really got me thinking. Thank you. u11nv