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 🙂

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…

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 🙂

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?

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 🙂

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

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.

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 🙂

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.

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 🙂

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 🙂

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

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

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

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

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!