[edited by - Drilian on September 11, 2003 4:06:56 PM]
Shadow mapping in large environments
Started by Drilian, Sep 11 2003 09:02 AM
83 replies to this topic
#1 Members - Reputation: 996
Posted 11 September 2003 - 09:02 AM
I apologize in advance for the potential rambling nature of this post.
Okay, so I'm trying to decide if I can do shadow mapping in large (mostly outdoor) environments. Initially, I would like to do this supporting just the sun (Good ol' directional light sources), but eventually I'd like to maybe have a few point lights as well (at the very least, spotlights).
Anyway, working initially with directional lights (lets not mess with cube-shadow-mapped sources just yet), obviously I'd want to use an orthographic projection for the shadow map. Easy enough, and has the added bonus that objects don't really lose resolution as they get far from the light source (lack of projection shrinking and all that).
Obviously, second-depth mapping would be a good idea (I can't believe I'd never heard of that before, since it seems so obvious when you think about it). But would projected (projective?) shadow mapping be something that I'd want to do, or is there a better way to ensure that I get decent resolution shadows across the whole scene?
I thought about using multiple shadow maps for the sun, but I'd rather not have to use 2 shadow maps on one object (a character, say, that's straddling the boundary between the near shadow map and a far shadow map). Plus I can't figure out a good way to make the jumps in shadow quality from far to near unnoticeable).
Basically, I'm hesitant to use projective shadow maps because I've read (somewhere on this forum if I recall correctly) that there are issues when looking directly at the light source (shadows melting away or the like...Actually now that I think about it I'm pretty sure it was Yann that mentioned this). Was there a way around this?
Anyone have any advice (things that I'm wrong about, things that I might want to think about, etc)?
Edit: Of course, not 2 seconds after posting this, I noted a few similar threads, with some good info. Anyway, I guess my major question after having read a few other threads is whether there's a way around the shadows getting all weird when looking towards the light source in Projective shadow mapping? If not, then what are my alternatives? (Of course, any other general ideas as to how to go about solving my interesting (to me) problem are more than welcome)
[edited by - Drilian on September 11, 2003 4:06:56 PM]
[edited by - Drilian on September 11, 2003 4:06:56 PM]
Sponsor:
#2 Moderators - Reputation: 1754
Posted 11 September 2003 - 10:22 AM
The problem of projection mismatch between the eye perspective and the light perspective when looking in the direction of the light source (the so called ''duelling frusta'' problem) only appears with perspective lightsources (spots and pointlights). You don''t have this problem with orthographic lights such as the sun, since the resolution distribution of orthographic lightmaps is distance and direction independent.
I would definitely recommend the use of PSMs (perspective shadow maps) for outdoor lighting. It typically gives you a significant quality boost on near geometry shadowing, and is pretty easy to implement on orthographic lights (as opposed to pointlights, where PSMs are a real pain in the ass to get right). The increased resolution near the eye comes with some drawbacks, as usual. First, the shadowmap becomes view dependent and needs to be recomputed every frame (assuming the camera has moved). In a fully dynamic environment however, this isn''t really an issue since the maps need to be regenerated anyway.
Other drawback is, that your orthographic sunlight will now include a perspective projection. This will make it prone to the duelling frusta problem described above. But it''s not that bad either. The worst case scenario (looking directly into the sun) will essentially cancel out the PSM effect - the quality will revert back to standard orthographic shadowmaps without PSM. And this quality isn''t necessarilly bad, although much more resolution dependent than PSMs.
On the other hand, I would also suggest using multiple view dependent shadowmaps for large scale outdoor environments. Each map will cover a part of the view frustum (with small overlaps to avoid cracks). That way, you can get very good shadow quality near the camera, without requiring huge resolution PSMs. Drawback is, as you mentioned above, potentially multiple shadowmaps per face. You engine should be able to handle that. If you choose your frustum ranges and shadowmap resolutions wisely (ie. compute them beforehand), there won''t be any visible shadow-resolution seams between the maps.
All in all, my experiences with large scale SMs have been very positive, especially on complex geometry. They have some drawbacks, obviously, but much less than eg. stencil volumes. The later ones will simply saturate the hardware from a certain level of complexity on. Both by multiplying the number of faces per frame (especially when using multiple light sources) and by burning invisible fillrate like mad. I personally believe that shadowmaps are the best option for realtime shadowing available to date, assuming a complex environment. That is, until ASMs (adaptive shadowmaps) or realtime GI will be possible
I would definitely recommend the use of PSMs (perspective shadow maps) for outdoor lighting. It typically gives you a significant quality boost on near geometry shadowing, and is pretty easy to implement on orthographic lights (as opposed to pointlights, where PSMs are a real pain in the ass to get right). The increased resolution near the eye comes with some drawbacks, as usual. First, the shadowmap becomes view dependent and needs to be recomputed every frame (assuming the camera has moved). In a fully dynamic environment however, this isn''t really an issue since the maps need to be regenerated anyway.
Other drawback is, that your orthographic sunlight will now include a perspective projection. This will make it prone to the duelling frusta problem described above. But it''s not that bad either. The worst case scenario (looking directly into the sun) will essentially cancel out the PSM effect - the quality will revert back to standard orthographic shadowmaps without PSM. And this quality isn''t necessarilly bad, although much more resolution dependent than PSMs.
On the other hand, I would also suggest using multiple view dependent shadowmaps for large scale outdoor environments. Each map will cover a part of the view frustum (with small overlaps to avoid cracks). That way, you can get very good shadow quality near the camera, without requiring huge resolution PSMs. Drawback is, as you mentioned above, potentially multiple shadowmaps per face. You engine should be able to handle that. If you choose your frustum ranges and shadowmap resolutions wisely (ie. compute them beforehand), there won''t be any visible shadow-resolution seams between the maps.
All in all, my experiences with large scale SMs have been very positive, especially on complex geometry. They have some drawbacks, obviously, but much less than eg. stencil volumes. The later ones will simply saturate the hardware from a certain level of complexity on. Both by multiplying the number of faces per frame (especially when using multiple light sources) and by burning invisible fillrate like mad. I personally believe that shadowmaps are the best option for realtime shadowing available to date, assuming a complex environment. That is, until ASMs (adaptive shadowmaps) or realtime GI will be possible
#3 Members - Reputation: 996
Posted 11 September 2003 - 11:06 AM
Luckily, none of the point lights that I''m going to have will have a range large enough to warrant perspective maps, so I''m off the hook in that regard...Plus I''m assuming a fully dynamic world so the recalculation thing was pretty much a given.
The main reason why I want to keep the number of shadow maps in check is because I''m aiming for ps1.1 minimum support, and alot of my effects use up three texture units, which gives me one unit extra that I was hoping to use for shadow mapping. If I used four (as an example) shadow textures, I''d need to be able to handle up to four shadow textures at a time (since there''s a chance that an object would be at the intersection of all of them, at least the way I''m envisioning it). Now, with PS2.0 I could do it (and the "engine" does support that), but with ps1.1 I''d have to multipass it. Unless I''m missing something. I suppose it''s not THAT bad. Doom3''s going to be multi-pass out the wazoo and it''s turned out fine. I''d still need a pass per light at this rate (though that''s optimizable, especially when only one of the lights is a large-scale sun, and the rest are going to be small-range point/spotlights). I suppose I''d be able to single-pass the objects that AREN''T on a seam, so that would be significantly less calculation. Hmm...
I guess my next question is how best to divide up the frustum into shadow maps? And how many should I use? And what size?
After having read some older posts, I think you (Yann) said you use four maps. How do you pick what portion of the frustum they cover?
I''m imagining this little project is going to be super cool when I''m done, but it''s definitely feeling difficult right now (lucky, this is the good kind of fun difficult, not the maddening "I just want it to be over so I can stop banging my head into various wall-like substances" difficult).
And thanks for all the help, you''ve probably taken a few weeks out of my "thinking process" at least!
The main reason why I want to keep the number of shadow maps in check is because I''m aiming for ps1.1 minimum support, and alot of my effects use up three texture units, which gives me one unit extra that I was hoping to use for shadow mapping. If I used four (as an example) shadow textures, I''d need to be able to handle up to four shadow textures at a time (since there''s a chance that an object would be at the intersection of all of them, at least the way I''m envisioning it). Now, with PS2.0 I could do it (and the "engine" does support that), but with ps1.1 I''d have to multipass it. Unless I''m missing something. I suppose it''s not THAT bad. Doom3''s going to be multi-pass out the wazoo and it''s turned out fine. I''d still need a pass per light at this rate (though that''s optimizable, especially when only one of the lights is a large-scale sun, and the rest are going to be small-range point/spotlights). I suppose I''d be able to single-pass the objects that AREN''T on a seam, so that would be significantly less calculation. Hmm...
I guess my next question is how best to divide up the frustum into shadow maps? And how many should I use? And what size?
After having read some older posts, I think you (Yann) said you use four maps. How do you pick what portion of the frustum they cover?
I''m imagining this little project is going to be super cool when I''m done, but it''s definitely feeling difficult right now (lucky, this is the good kind of fun difficult, not the maddening "I just want it to be over so I can stop banging my head into various wall-like substances" difficult).
And thanks for all the help, you''ve probably taken a few weeks out of my "thinking process" at least!
#4 Members - Reputation: 122
Posted 11 September 2003 - 05:17 PM
PSM is good, but may have clip problem with huge object.
I solve this by using LOD in PSM.
For normal shadowmap light,
you may have an editor to set the frustum of light.
And calculate the light
frustrum intersection with view frustrum to select those
shadowlights you may see.
and foreach shadow light, simply render the lightview
and shadowmap one by one.
#5 Members - Reputation: 182
Posted 11 September 2003 - 07:31 PM
Hi,
I have PSM from directional lights work, and going to implement point lights. I have heard many times that shadow mapping with floating point lights is a big problem (whether using PSM or not). Can someone describe more about how it is typically implemented in a real game (using current hardware)?
Say, do you actually render from the point light 6 times to form 6 shadow cube maps? And as I remember, ps1.3 only have 4 texture registers, so when you render the real scene, how do you decide which shadow map is used in the pixel shader? Or do you render the scene multiple times? (just some random thoughts from me)
I am going to implement it in my school project, so any hints are much appreciated.
I have PSM from directional lights work, and going to implement point lights. I have heard many times that shadow mapping with floating point lights is a big problem (whether using PSM or not). Can someone describe more about how it is typically implemented in a real game (using current hardware)?
Say, do you actually render from the point light 6 times to form 6 shadow cube maps? And as I remember, ps1.3 only have 4 texture registers, so when you render the real scene, how do you decide which shadow map is used in the pixel shader? Or do you render the scene multiple times? (just some random thoughts from me)
I am going to implement it in my school project, so any hints are much appreciated.
#7 Anonymous Poster_Anonymous Poster_* Guests - Reputation:
Posted 14 September 2003 - 10:57 AM
Ive heard of perspective shadow maps thrown around. Does anyone have an implementation of such?
-ddn
-ddn
#8 Members - Reputation: 996
Posted 14 September 2003 - 05:44 PM
I''m working up one now. I''m actually having trouble working on projecting the directional light into camera space. When the direction of the light has z=0, then the projection of the light direction has w=0, which puts the light at infinity (which it is, since w=0 in the original point), but with a z != 0, the end perspective is NOT at infinity. I''m sure I''m missing something super-obvious, but I haven''t been able to wrap my brain around it (and I''ve reread the relevant part in the Projective Shadow Mapping paper many times and haven''t been able to get any new information from it).
Can anyone help in this regard?
(I know I learned this stuff somewhere along the line, but it seems to have slipped out of the ol'' brain!)
Josh
Can anyone help in this regard?
(I know I learned this stuff somewhere along the line, but it seems to have slipped out of the ol'' brain!)
Josh
#9 Members - Reputation: 286
Posted 15 September 2003 - 03:21 AM
I haven't implemented PSMs yet, but this is my understanding...
Isn't the post-perspective light position at infinity because post-perspective w is zero ? I thought if post-perspective z is non-zero then that only meant the post-perspective light direction has a component along the z-axis. Actually I thought post-perspective z was zero anyway (which means pre-perspective and post-perspective light directions are the same) because pre-perspective z and w are both zero and that's all post-perspective w depends on. For camera-space directional lights this is the only case (camera_light_z=0) where the post-perspective light is also directional (as opposed to a point light) so I think transforming the camera-space light direction into post-perspective space, so that you can subsequently determine your light projection, needs to be treated specially for this case so that you don't get the perspective divide by zero. I think one way to do this is push your post-perspective light x and y position components some large enough distance and use perspective projection or just use an orthographic projection.
AnonymousPoster: There's a bare-bones of how PSM is done at http://www.tulrich.com/geekstuff/psm/
[edited by - soiled on September 15, 2003 10:35:22 AM]
Isn't the post-perspective light position at infinity because post-perspective w is zero ? I thought if post-perspective z is non-zero then that only meant the post-perspective light direction has a component along the z-axis. Actually I thought post-perspective z was zero anyway (which means pre-perspective and post-perspective light directions are the same) because pre-perspective z and w are both zero and that's all post-perspective w depends on. For camera-space directional lights this is the only case (camera_light_z=0) where the post-perspective light is also directional (as opposed to a point light) so I think transforming the camera-space light direction into post-perspective space, so that you can subsequently determine your light projection, needs to be treated specially for this case so that you don't get the perspective divide by zero. I think one way to do this is push your post-perspective light x and y position components some large enough distance and use perspective projection or just use an orthographic projection.
AnonymousPoster: There's a bare-bones of how PSM is done at http://www.tulrich.com/geekstuff/psm/
[edited by - soiled on September 15, 2003 10:35:22 AM]
#10 Members - Reputation: 996
Posted 15 September 2003 - 03:56 AM
Let me better explain my issue. I have a perspective matrix:
1 0 0 0
0 1 0 0
0 0 -1.02 -1
0 0 -2.02 0
(Note that this is the transpose of a GL projection matrix - I use D3D)
Now, with a light direction of
-1, 0, 0
we get a point at infinity" light of
1, 0, 0, 0 <- w = 0, it''s at infinity
Run that through the projection matrix and you get the same vector.
Now, with a "point at infinity" light of
0, 0, 1, 0 <- again, w=0
we run it through the projection matrix and get
0, 0, -1.02, -1
This is not at infinity. And in this case, that just seems wrong somehow.
Josh
1 0 0 0
0 1 0 0
0 0 -1.02 -1
0 0 -2.02 0
(Note that this is the transpose of a GL projection matrix - I use D3D)
Now, with a light direction of
-1, 0, 0
we get a point at infinity" light of
1, 0, 0, 0 <- w = 0, it''s at infinity
Run that through the projection matrix and you get the same vector.
Now, with a "point at infinity" light of
0, 0, 1, 0 <- again, w=0
we run it through the projection matrix and get
0, 0, -1.02, -1
This is not at infinity. And in this case, that just seems wrong somehow.
Josh
#11 Members - Reputation: 286
Posted 15 September 2003 - 04:11 AM
Oh I see - I misunderstood your question - I had thought you meant post-perspective z!=0 when you meant pre-perspective z!=0.
As far as my understanding is concerned what you say is correct but it's also not a problem.
With a point at infinity light of (0,0,1,0) the post-perspective light position is (0, 0 ,zf/(zf-zn), 1) which is not at infinity, as you say, but it is on the infinity plane. The infinity plane is at z = zf/(zf-zn) which is just a little bit past the far plane (and because it's just a little bit past it's what makes this camera-space light direction cause problems for PSMs - ie causes your shadowmap projection to have a very wide angle). The only case where you get a directional light (ie point light at infinity) in post-perspective space (assuming we're only talking about directional lights in camera space) is when the light direction in camera space is (x,y,0,0) - in other words when camera-space z is zero.
[edited by - soiled on September 15, 2003 11:13:45 AM]
As far as my understanding is concerned what you say is correct but it's also not a problem.
With a point at infinity light of (0,0,1,0) the post-perspective light position is (0, 0 ,zf/(zf-zn), 1) which is not at infinity, as you say, but it is on the infinity plane. The infinity plane is at z = zf/(zf-zn) which is just a little bit past the far plane (and because it's just a little bit past it's what makes this camera-space light direction cause problems for PSMs - ie causes your shadowmap projection to have a very wide angle). The only case where you get a directional light (ie point light at infinity) in post-perspective space (assuming we're only talking about directional lights in camera space) is when the light direction in camera space is (x,y,0,0) - in other words when camera-space z is zero.
[edited by - soiled on September 15, 2003 11:13:45 AM]
#12 Members - Reputation: 996
Posted 16 September 2003 - 04:12 AM
Now, instead of changing the shape of the frustum via projection, what if we were to change the shape of the light's projection? Make it a trapezoid or something, to account for the shape of the camera frustum?
It probably wouldn't be quite as good as PSMs, but it might end up being a whole lot easier!
Josh
EDIT: I'd like to add that, when the light is in a top-down perspective, the results should end up being the same as they are with perspective shadow maps (it's the ideal case for both of them). Hmm...as a matter of fact, they both break down in similar cases. Also, after posting this, I looked up "trapezoid shadow maps" on google and found this: http://www.comp.nus.edu.sg/~tants/tsm.html
Interesting. Sounds like what I was thinking of...(now I think I've seen this before - maybe it's where I got the idea).
Anyway, the paper isn't published yet (which is too bad - it looks like it'd be good reading), but I wonder if what I was thinking is the same (or better -- or worse) as what they have.
I don't know if I can wait until the end of 2003 to find out
EDIT #2: I don't know if it would work well for point lights either...but I'm only looking at large-scale directional lights, so I guess for my purposes it doesn't really matter.
[edited by - Drilian on September 16, 2003 11:23:57 AM]
[edited by - Drilian on September 16, 2003 11:26:02 AM]
It probably wouldn't be quite as good as PSMs, but it might end up being a whole lot easier!
Josh
EDIT: I'd like to add that, when the light is in a top-down perspective, the results should end up being the same as they are with perspective shadow maps (it's the ideal case for both of them). Hmm...as a matter of fact, they both break down in similar cases. Also, after posting this, I looked up "trapezoid shadow maps" on google and found this: http://www.comp.nus.edu.sg/~tants/tsm.html
Interesting. Sounds like what I was thinking of...(now I think I've seen this before - maybe it's where I got the idea).
Anyway, the paper isn't published yet (which is too bad - it looks like it'd be good reading), but I wonder if what I was thinking is the same (or better -- or worse) as what they have.
I don't know if I can wait until the end of 2003 to find out
EDIT #2: I don't know if it would work well for point lights either...but I'm only looking at large-scale directional lights, so I guess for my purposes it doesn't really matter.
[edited by - Drilian on September 16, 2003 11:23:57 AM]
[edited by - Drilian on September 16, 2003 11:26:02 AM]
#13 Members - Reputation: 996
Posted 16 September 2003 - 10:25 AM
Upon further reflection, my "trapezoidal map" idea has a few major flaws. Which makes me certain that whatever it is I''m doing, it''s not the same as the people that did the "Trapezoidal Shadow Mapping" paper.
Hmm...maybe I can get around those problems.
The main one is that a linear pre-perspective z difference is not a linear post-perspective z. Which means that, while the texels from the left side of the screen to the right side of the screen may have a higher resolution than otherwise, front to back there is no gain. Grrrr....
Dividing up the frustum in novel ways (like Yann mentioned with regard to PSMs) might solve some of the issues, but it''ll never be as good in this regard as PSMs.
I really need to set up a testbed in which I could try these things, to see if they''d really work.
Or I could apply some sort of crazy transformation that''s similar to perspective that...
hmm....
I''ll get back to you guys
(Again, sorry I manage to ramble so much in my posts...it seems that, as much as I think about what I''m going to say before I post, I end up thinking up so much new material as I post that my ideas and posts quickly become disjointed. Apologies.)
Hmm...maybe I can get around those problems.
The main one is that a linear pre-perspective z difference is not a linear post-perspective z. Which means that, while the texels from the left side of the screen to the right side of the screen may have a higher resolution than otherwise, front to back there is no gain. Grrrr....
Dividing up the frustum in novel ways (like Yann mentioned with regard to PSMs) might solve some of the issues, but it''ll never be as good in this regard as PSMs.
I really need to set up a testbed in which I could try these things, to see if they''d really work.
Or I could apply some sort of crazy transformation that''s similar to perspective that...
hmm....
I''ll get back to you guys
(Again, sorry I manage to ramble so much in my posts...it seems that, as much as I think about what I''m going to say before I post, I end up thinking up so much new material as I post that my ideas and posts quickly become disjointed. Apologies.)
#14 Members - Reputation: 286
Posted 17 September 2003 - 07:45 AM
I''m also trying to figure out what "Trapezoidal Shadow Maps" do since the paper is not yet available. Also Thatcher Ulrich and some others have sketched an idea that they are confident should work for directional lights in all cases (they''ve not tried it out yet AFAIK) - it''s at http://tulrich.com/geekstuff/psm_notes2.html. Though I''m having difficulties filling in the details. They''re proposing to match a light projection to a *section* of the view frustum so that a trapeziodal face of view frustum maps to a shadow map. This method can apparently require up to 5 light projections (and associated shadow maps) - one for each face of view frustum visible to the light. "Trazpezoidal Shadow Maps" OTOH (according to the abstract) seem to use one trapezoid to *approximate* entire view frustum. Whereas Thatcher splits view frustum into up to 5 light frustums by extruding each face of view frustum (that''s facing light) in the light direction (orthographic I assume) and some of these faces have a trapezoidal appearance when viewed by light - so trapezoids of some sort seem the way to go. It seems to me that using a single trapezoid to cover *entire* view frustum fails like PSMs when light is shining into viewer''s eyes(which is what you were saying I think) - because trapezoid then becomes same as view frustum far-plane face (ie a rectangle) and you lose the squishing benefits of a trapezoid.
Is my understanding of your idea correct in the following paragraph ? ...
Instead of approximately fitting light projection to post-perspective view frustum as done in PSMs you approximately fit a light projection to the pre-perspective view frustum (I think this change in thinking is the way forward). Your trapezoid idea is that the light projection has a near face that''s trapezoidal (and perpendicular to the light direction) and which extrudes orthographically in the light direction such that resultant light frustum (which is like a regular perspective frustum but with two sides parallel) contains the entire view frustum. Actually I tried to generate this projection on paper and I can''t do it (seems you''d have to use a regular perspective frustum - just with the near face now becoming one of the side faces). Geez this is hard to describe.
Which brings me to your comment about left-to-right vs front-to-back gain which I''m having trouble understanding so I''ll wait and see if the above paragraph is correct first.
I think Thatcher''s idea is worth exploring as he fits the shadow map *exactly* to the view frustum (though uses multiple maps) so no lost texels. And he claims the shadow map resolution is distributed nicely throughout the view frustum irrespective of light direction (which PSMs don''t guarantee). You still need to use multiple shadow maps when rendering objects but this only happens for objects that intersect multiple light frustums (which hopefully isn''t many).
The part I''m stuck on is how to generate the light frustum in Thatcher''s idea. And also I don''t see how it fixes the light-shining-into-viewer''s-eyes problem. Any ideas ?
...that ended up being a bit long-winded and muddled.
Is my understanding of your idea correct in the following paragraph ? ...
Instead of approximately fitting light projection to post-perspective view frustum as done in PSMs you approximately fit a light projection to the pre-perspective view frustum (I think this change in thinking is the way forward). Your trapezoid idea is that the light projection has a near face that''s trapezoidal (and perpendicular to the light direction) and which extrudes orthographically in the light direction such that resultant light frustum (which is like a regular perspective frustum but with two sides parallel) contains the entire view frustum. Actually I tried to generate this projection on paper and I can''t do it (seems you''d have to use a regular perspective frustum - just with the near face now becoming one of the side faces). Geez this is hard to describe.
Which brings me to your comment about left-to-right vs front-to-back gain which I''m having trouble understanding so I''ll wait and see if the above paragraph is correct first.
I think Thatcher''s idea is worth exploring as he fits the shadow map *exactly* to the view frustum (though uses multiple maps) so no lost texels. And he claims the shadow map resolution is distributed nicely throughout the view frustum irrespective of light direction (which PSMs don''t guarantee). You still need to use multiple shadow maps when rendering objects but this only happens for objects that intersect multiple light frustums (which hopefully isn''t many).
The part I''m stuck on is how to generate the light frustum in Thatcher''s idea. And also I don''t see how it fixes the light-shining-into-viewer''s-eyes problem. Any ideas ?
...that ended up being a bit long-winded and muddled.
#15 Members - Reputation: 996
Posted 17 September 2003 - 09:55 AM
I'd read that bit by Ulrich. It makes sense, and seems to solve every problem with PSMs. However, it does introduce a fairly sizeable one, in which there are (up to) 5 shadow maps. But I do agree that it doesn't lose pixels, which is something that my method was lacking, as there are going to be "extra" parts of the trapezoid hanging off of the edge. For instance, if this is the camera frustum:
You can see the trapezoid edge (in blue). Wasted space.
But if you project that trapezoid into light space, you get a column of space, which is what the light can see (Remember I'm working with directional lights).
Like that, where the bottom would be the far extent (the border of the camera frustum) and the top would be the extent of farthest shadow-casting object. This eliminates alot of problems, most importantly the issues with objects behind the camera casting shadows onto the scene, since those objects would be within this column.
However, it does have issues of its own:
One problem (which is solvable) is that, if you look at that frustum (top picture), you want the pixel density to be greater on the left side than on the right. Now, if you warp a square texture to fit that shape, getting the top to bottom density to increase on the left is no problem (512 pixels from top to bottom on the left side makes for smalelr pixels than 512 on the right). But you also want the "x-direction" of pixels to shrink. Of course, I've solved this problem in my head (but haven't yet done the math) by doing perspective divides to accomplish the same thing (like a perspective-correct texture is squished towards the far end).
The biggest problem is that you can't always use the method. Specifically, in cases like this:
Which begs the question: where's the cutoff between being able to use it and not?
I'm slowly losing faith in my idea.
However, I do like the basics behind Ulrich's idea. If you look at each side of the frustum as a trapezoid (like I have been) and do the whole directional-light column thing for each one (as in my diagrams above), that would do exactly what they're thinking of. Remember, it's dealing with all objects between the light and that side of the frustum, not just the side of the frustum.
Pretty much the only thing I don't like about his method is that it takes so many buffers. I can get that down to four buffers with a bit of overlap and a tiny bit of waste. Hmm. Damn I wish I had the time to implement this stuff right now (cuz I really want to know how it works/how it runs).
Yann said (in some other thread somewhere) that he uses four shadow map textures for large-scale shadow casting. I suppose that I could do the same thing, only doing it this way.
I need to hurry up and finish the landscape engine so I can try and implement this.
As for "Trapezoidal Shadow Mapping," I'm baffled. I'd like to think that it's similar to my original idea, but I really don't know that for sure, so I'm just guessing. I emailed them for info, but their paper is unpublished currently, so I doubt they'll give me any information. Which is perfectly understandable.
Anyway, thanks for the help Soiled! This is fun work (And more entertaining than doing what I should be doing)
[edited by - Drilian on September 17, 2003 4:57:02 PM]
You can see the trapezoid edge (in blue). Wasted space.
But if you project that trapezoid into light space, you get a column of space, which is what the light can see (Remember I'm working with directional lights).
Like that, where the bottom would be the far extent (the border of the camera frustum) and the top would be the extent of farthest shadow-casting object. This eliminates alot of problems, most importantly the issues with objects behind the camera casting shadows onto the scene, since those objects would be within this column.
However, it does have issues of its own:
One problem (which is solvable) is that, if you look at that frustum (top picture), you want the pixel density to be greater on the left side than on the right. Now, if you warp a square texture to fit that shape, getting the top to bottom density to increase on the left is no problem (512 pixels from top to bottom on the left side makes for smalelr pixels than 512 on the right). But you also want the "x-direction" of pixels to shrink. Of course, I've solved this problem in my head (but haven't yet done the math) by doing perspective divides to accomplish the same thing (like a perspective-correct texture is squished towards the far end).
The biggest problem is that you can't always use the method. Specifically, in cases like this:
Which begs the question: where's the cutoff between being able to use it and not?
I'm slowly losing faith in my idea.
However, I do like the basics behind Ulrich's idea. If you look at each side of the frustum as a trapezoid (like I have been) and do the whole directional-light column thing for each one (as in my diagrams above), that would do exactly what they're thinking of. Remember, it's dealing with all objects between the light and that side of the frustum, not just the side of the frustum.
Pretty much the only thing I don't like about his method is that it takes so many buffers. I can get that down to four buffers with a bit of overlap and a tiny bit of waste. Hmm. Damn I wish I had the time to implement this stuff right now (cuz I really want to know how it works/how it runs).
Yann said (in some other thread somewhere) that he uses four shadow map textures for large-scale shadow casting. I suppose that I could do the same thing, only doing it this way.
I need to hurry up and finish the landscape engine so I can try and implement this.
As for "Trapezoidal Shadow Mapping," I'm baffled. I'd like to think that it's similar to my original idea, but I really don't know that for sure, so I'm just guessing. I emailed them for info, but their paper is unpublished currently, so I doubt they'll give me any information. Which is perfectly understandable.
Anyway, thanks for the help Soiled! This is fun work (And more entertaining than doing what I should be doing)
[edited by - Drilian on September 17, 2003 4:57:02 PM]
#16 Members - Reputation: 286
Posted 18 September 2003 - 07:43 AM
Nice explanation and diagrams ! That cleared things up for me :-)
In your first diagram - the lost shadowmap texels probably don''t have a noticeable effect on shadow quality since they affect the back of the view frustum.
I''m not sure it''s possible to generate a 4x4 projection matrix for the light frustum in your second diagram though since it''s perspective in one direction and orthographic in the other and perspective affects all directions (ie x/w,y/w,z/w).
As far as your third diagram is concerned it seems to highlight the fact that more than one light frustum is required (at least in these bad cases).
"View Frustum Optimization To Maximize Object''s Image Area" at http://www.cs.unc.edu/~lowk/research/writings/lowk_max_image.pdf
describes how to warp an arbitrary quadrilateral (eg trapezoid) in world space such that it exactly fills the viewport - which is exactly what we want for our shadow maps. However it only works for perspective frustums (ie point lights) and not for orthographic frustums which is what we''re interested in since we''re using directional lights like the sun (of course for points lights it might be worth looking into). So for directional lights I was thinking it would be good to convert them to point lights and this is what PSMs do (ie we get a point light in post-perspective space except for one case where it remains directional but that case is the best case so no probs). In post-perspective (or NDC) space the view frustum is a box (x,y=[-1,1], z=[0,1] in d3d) and the light position is always at z = 1 + zViewNear/(zViewFar-zViewNear) (ie a little bit past z=1) so we can take the back faces of NDC box (when viewed from light position) and generate light frustums as described in the above paper - actually since the geometry is so simple you can hardwire it into your code without having to solve a 8x9 linear system every frame (as done in the paper) - the idea is to make the near plane of light frustum parallel to a back face of NDC box (which is also light frustum''s far plane) - actually near and far planes must be parallel anyway so this means the light frustum is restricted to NDC box which is what you want (ie, so you''re not drawing objects outside the view volume (ie NDC box) that don''t cast shadows into view frustum) - I think my argument here is a bit circular. The following diagram shows the setup for one light frustum - more are needed but only one it drawn (light frustum is blue, top face of NDC box which is also far plane of light frustum is green, the near clip plane is red)...
...and this shows two light frustums (of the four needed in this case) when the light position slides along the infinity plane upwards so that it''s above the NDC box...
...as it turns out the near distance to far distance ratio for any of these light frustums is greater-equal to zViewNear/zViewFar (it''s equal for the bad cases) so it does cancel out the non-linear z of the view frustum (ie so objects near viewer, when rendering scene with shadows, have lower shadow z resolution - but with 24-bits on hardware shadowbuffers and second-depth mapping this might be ok). Also there''s need to reverse z-compares depending on camera-space light direction (just like in PSMs). You can see the difference in shadow map resolution here (the longer the green lines are the less shadow map resolution - this is especially noticeable for the front face of view frustum which maps to the left face in diagram)...
So all up this is really just Thatcher Ulrich''s idea except done in post-perspective space instead of camera space (since I can''t find suitable projections to do what he does in camera space - ie frustums like the second diagram in your post). Doing it in camera space is still better in that you don''t need to stretch the view frustum back when the light is behind viewer in order to avoid that problem mentioned in PSM paper - actually doing it in post-perspective space (as described above) might also avoid the problem without resorting to stretching the view frustum back since none of the light frustums include the view plane (which is where you get divide-by-zeros and inverted images due to the view frustum projection).
In your first diagram - the lost shadowmap texels probably don''t have a noticeable effect on shadow quality since they affect the back of the view frustum.
I''m not sure it''s possible to generate a 4x4 projection matrix for the light frustum in your second diagram though since it''s perspective in one direction and orthographic in the other and perspective affects all directions (ie x/w,y/w,z/w).
As far as your third diagram is concerned it seems to highlight the fact that more than one light frustum is required (at least in these bad cases).
"View Frustum Optimization To Maximize Object''s Image Area" at http://www.cs.unc.edu/~lowk/research/writings/lowk_max_image.pdf
describes how to warp an arbitrary quadrilateral (eg trapezoid) in world space such that it exactly fills the viewport - which is exactly what we want for our shadow maps. However it only works for perspective frustums (ie point lights) and not for orthographic frustums which is what we''re interested in since we''re using directional lights like the sun (of course for points lights it might be worth looking into). So for directional lights I was thinking it would be good to convert them to point lights and this is what PSMs do (ie we get a point light in post-perspective space except for one case where it remains directional but that case is the best case so no probs). In post-perspective (or NDC) space the view frustum is a box (x,y=[-1,1], z=[0,1] in d3d) and the light position is always at z = 1 + zViewNear/(zViewFar-zViewNear) (ie a little bit past z=1) so we can take the back faces of NDC box (when viewed from light position) and generate light frustums as described in the above paper - actually since the geometry is so simple you can hardwire it into your code without having to solve a 8x9 linear system every frame (as done in the paper) - the idea is to make the near plane of light frustum parallel to a back face of NDC box (which is also light frustum''s far plane) - actually near and far planes must be parallel anyway so this means the light frustum is restricted to NDC box which is what you want (ie, so you''re not drawing objects outside the view volume (ie NDC box) that don''t cast shadows into view frustum) - I think my argument here is a bit circular. The following diagram shows the setup for one light frustum - more are needed but only one it drawn (light frustum is blue, top face of NDC box which is also far plane of light frustum is green, the near clip plane is red)...
...and this shows two light frustums (of the four needed in this case) when the light position slides along the infinity plane upwards so that it''s above the NDC box...
...as it turns out the near distance to far distance ratio for any of these light frustums is greater-equal to zViewNear/zViewFar (it''s equal for the bad cases) so it does cancel out the non-linear z of the view frustum (ie so objects near viewer, when rendering scene with shadows, have lower shadow z resolution - but with 24-bits on hardware shadowbuffers and second-depth mapping this might be ok). Also there''s need to reverse z-compares depending on camera-space light direction (just like in PSMs). You can see the difference in shadow map resolution here (the longer the green lines are the less shadow map resolution - this is especially noticeable for the front face of view frustum which maps to the left face in diagram)...
So all up this is really just Thatcher Ulrich''s idea except done in post-perspective space instead of camera space (since I can''t find suitable projections to do what he does in camera space - ie frustums like the second diagram in your post). Doing it in camera space is still better in that you don''t need to stretch the view frustum back when the light is behind viewer in order to avoid that problem mentioned in PSM paper - actually doing it in post-perspective space (as described above) might also avoid the problem without resorting to stretching the view frustum back since none of the light frustums include the view plane (which is where you get divide-by-zeros and inverted images due to the view frustum projection).
#17 Members - Reputation: 996
Posted 19 September 2003 - 06:39 AM
Ahh...but I wasn't thinking about doing a 4x4 projection (Well, initially I was but I reached the same conclusion). I was planning on using the fact that I'm doing this with vertex shaders to my advantage
The problem is you'll still get that divide by zero or reverse projection problem, as you're still doing the calculation in post-perspective space. As stated, I think with vertex shaders that the math becomes very doable. I figure there's a rotation (to get the objects into "z is near-far on the trapezoid, x is the end that varies in size, and y is the orthogonal direction" space, then do the perspective divide on just x (And have 1/z, also). That orientation is, for some stupid reason, causing me issues. Also, I've come up with a "cheat" sort of way to handle the 5 textures necessary case of Thatcher Ulrich's method, such that only 4 textures are necessary (hint: there's overlap on the near plane). I'll draw up all sorts of diagrams and stuff later
I'm up to my ears in the math of how to do the trapezoid projection, as well as trying to make sure that only four maps are needed at any point in time. Hopefully they don't have to be very high-resolution maps (though I imagine that they will ).
As soon as I have the math all set the way I want it, I'll post it here.
EDIT: Whoops, hit send too quick
[edited by - Drilian on September 19, 2003 1:49:29 PM]
(Well, initially I was but I reached the same conclusion). I was planning on using the fact that I'm doing this with vertex shaders to my advantage The problem is you'll still get that divide by zero or reverse projection problem, as you're still doing the calculation in post-perspective space. As stated, I think with vertex shaders that the math becomes very doable. I figure there's a rotation (to get the objects into "z is near-far on the trapezoid, x is the end that varies in size, and y is the orthogonal direction" space, then do the perspective divide on just x (And have 1/z, also). That orientation is, for some stupid reason, causing me issues. Also, I've come up with a "cheat" sort of way to handle the 5 textures necessary case of Thatcher Ulrich's method, such that only 4 textures are necessary (hint: there's overlap on the near plane). I'll draw up all sorts of diagrams and stuff later
I'm up to my ears in the math of how to do the trapezoid projection, as well as trying to make sure that only four maps are needed at any point in time. Hopefully they don't have to be very high-resolution maps (though I imagine that they will
).As soon as I have the math all set the way I want it, I'll post it here.
EDIT: Whoops, hit send too quick
[edited by - Drilian on September 19, 2003 1:49:29 PM]
#18 Members - Reputation: 286
Posted 19 September 2003 - 09:17 AM
Vertex shaders... of course ! Thanks, I took a detour into post-perspective land there for a while with its divide-by-zero and reverse projection problems 
Back on track now...
I''ll just throw this in without diagrams (cause it''s 5am here) in case it helps or needs correcting once you''ve done yours...
(1) Translate, to the origin, the midpoint of shorter line of parallel lines belonging to the trapezoid in world space.
(2) Apply 3x3 rotation (Rx, Ry, Rz) where Rx,... are column vectors (using d3d matrices here). Rz is light direction, Rx is normalise(D-(D.Rz)Rz) where D is direction of one of parallel lines of trapezoid and Ry = Rz x Rx.
(3) Apply shear 3x3 matrix to remove trapezoid tilt in x-dir...
1 0 sx
0 1 0
0 0 1
...where sx = -(D.Rz)/(D.Rx)
(4) Apply shear 3x3 matrix to remove trapezoid tilt in y-dir...
1 0 0
0 1 sy
0 0 1
...where sy = -(E.Rz)/(E.Ry) and E is vector from midpoint of shorter to midpoint of longer of parallel lines of trapezoid (in original space - the space before rotation is applied).
(5) translate along y-axis to line up centre of projection of trapezoid (ie where non-parallel lines intersect in current space)
(6) Calculate x = x/y and scale appropriately into [-1,1].
(7) Calculate y = a + b/y where a and b are chosen to map yn to -1 and yf to 1. yn is translation distance in step 5 and yf is yn + |E|.
(8) Scale z by inverse of depth of trapezoid extrustion (ie column length) to get into [0,1].
(9) Set w to 1.
Steps 1-5 can be merged into a single 4x4 matrix. The remaining steps, as you pointed out, can only be done in a vertex shader.
Actually I think this''ll cause problems when we apply shadow maps to our geometry because we want our shadow map to be perspective-correct per-pixel and hence we need to use rational linear interpolation to interpolate our x and y (since they''re non-linear in y) and this is done in rasterizer which calculates ((s/w)/(1/w), (t/w)/(1/w), (r/w)/(1/w)) per-pixel - so we could set w to y but then it''d get applied to all three shadow map tex coords (s,t,r) when we only want it applied to (s,t) since r is the z-component which is supposed to be orthographic but it''ll have this unwanted warping between vertices and hence our shadow map z compare will be incorrect. Not sure what to do about this ?
Back on track now...I''ll just throw this in without diagrams (cause it''s 5am here) in case it helps or needs correcting once you''ve done yours...
(1) Translate, to the origin, the midpoint of shorter line of parallel lines belonging to the trapezoid in world space.
(2) Apply 3x3 rotation (Rx, Ry, Rz) where Rx,... are column vectors (using d3d matrices here). Rz is light direction, Rx is normalise(D-(D.Rz)Rz) where D is direction of one of parallel lines of trapezoid and Ry = Rz x Rx.
(3) Apply shear 3x3 matrix to remove trapezoid tilt in x-dir...
1 0 sx
0 1 0
0 0 1
...where sx = -(D.Rz)/(D.Rx)
(4) Apply shear 3x3 matrix to remove trapezoid tilt in y-dir...
1 0 0
0 1 sy
0 0 1
...where sy = -(E.Rz)/(E.Ry) and E is vector from midpoint of shorter to midpoint of longer of parallel lines of trapezoid (in original space - the space before rotation is applied).
(5) translate along y-axis to line up centre of projection of trapezoid (ie where non-parallel lines intersect in current space)
(6) Calculate x = x/y and scale appropriately into [-1,1].
(7) Calculate y = a + b/y where a and b are chosen to map yn to -1 and yf to 1. yn is translation distance in step 5 and yf is yn + |E|.
(8) Scale z by inverse of depth of trapezoid extrustion (ie column length) to get into [0,1].
(9) Set w to 1.
Steps 1-5 can be merged into a single 4x4 matrix. The remaining steps, as you pointed out, can only be done in a vertex shader.
Actually I think this''ll cause problems when we apply shadow maps to our geometry because we want our shadow map to be perspective-correct per-pixel and hence we need to use rational linear interpolation to interpolate our x and y (since they''re non-linear in y) and this is done in rasterizer which calculates ((s/w)/(1/w), (t/w)/(1/w), (r/w)/(1/w)) per-pixel - so we could set w to y but then it''d get applied to all three shadow map tex coords (s,t,r) when we only want it applied to (s,t) since r is the z-component which is supposed to be orthographic but it''ll have this unwanted warping between vertices and hence our shadow map z compare will be incorrect. Not sure what to do about this ?
#19 Members - Reputation: 996
Posted 19 September 2003 - 10:43 AM
Hmmm...I see your point. I didn't even think about the problem of projection in the texture coordinates. Well, that certainly makes this trickier.
As long as the z column in the light map is the distance (in pre-projection units) to the light, then we only need one instance of the distance value on the geometry (not four). So it could be stored in some other vector (like another texture coordinate or the vertex color coordinate or something), thus avoiding that pesky divide. I think that would work, though I may be missing something obvious.
This would all be really easy to do with pixel shaders v 2.0 (or up, I guess). I was hoping to get away with using ps1.1. I haven't come up with a good way to combine the four textures into one depth reading. Any ideas?
EDIT: By the way, thanks for doing all that math! That's exactly what I was working towards, but you're faster than I am Not bad for posting at 5 AM
[edited by - Drilian on September 20, 2003 2:06:09 AM]
As long as the z column in the light map is the distance (in pre-projection units) to the light, then we only need one instance of the distance value on the geometry (not four). So it could be stored in some other vector (like another texture coordinate or the vertex color coordinate or something), thus avoiding that pesky divide. I think that would work, though I may be missing something obvious.
This would all be really easy to do with pixel shaders v 2.0 (or up, I guess). I was hoping to get away with using ps1.1. I haven't come up with a good way to combine the four textures into one depth reading. Any ideas?
EDIT: By the way, thanks for doing all that math! That's exactly what I was working towards, but you're faster than I am
Not bad for posting at 5 AM [edited by - Drilian on September 20, 2003 2:06:09 AM]
#20 Members - Reputation: 286
Posted 20 September 2003 - 07:40 AM
There are a few errors in my steps and I incorrectly assumed an isoceles trazepoid so an extra shear would be needed in there somewhere, but the jist of it is there. Actually those shears are only in there because I'm fitting the near face of light frustum to a face of the view frustum but this isn't necessary. In fact with your idea of a single trapezoid covering entire view frustum or four overlapping trapezoids covering 5 frustum faces (which I'm interested to find out about) you probably can't do this. The only reason I did it was to improve z-resolution - because objects between light and view frustum don't need shadow z (because viewer can't see them) and hence can be projected, into shadow map, with a z value of zero.
I'm also aiming for ps.1.1. However I'll be using gf4 shadow buffers in d3d which automatically use tex coord 'r' when doing z-compare so unfortunately I can't stick 'z' in another tex coord or vertex colour But you're right, it does look like ps.2.0 can handle this type of shadowing. So that pretty much means I'm forced to either (a) put up with incorrect shadow map z-interpolation between vertices (and find some way to make it unnoticeable), (b) divide z by y so that all x,y,z are divided by y and hence use a slightly different light frustum than we want or © go back to post-perspective space. I'll have a bit more of a think about options (a) and (b).
With shadow maps that can overlap in some areas and not in other areas (I assume your max 4 maps idea does this) I don't know how you would blend them.
OTOH if they line up next to each other (ie Thatcher Ulrich's max 5 maps) where light frustums are perfectly adjacent to each other then you'd only need to remove the seams. Assuming bilinear shadows, the border edge of a shadow map should be zero if border is adjacent to another shadow map otherwise it's a regular shadowmap value.
This is so you're addition of shadow maps (eg for 4 maps this would be 0.25*(t0+t1+t2+t3)) looks like (for adjacent borders)...
_____ _____
map1 \/ map2
map1 /\ map2
...so when border is zero you put edge of light frustum one texel inside boundary (so it's halfway between border texel and next inner texel) and when border is not zero you put light frustum half texel inside (right on border texel). This would require both shadow viewport adjustments and tex coord adjustments. So when the light is directly behind viewer so that all five view frustum faces are visible to the light you get 4 borders that aren't adjacent to another border and 16 borders that are.
[edited by - soiled on September 20, 2003 2:42:08 PM]
[edited by - soiled on September 20, 2003 2:43:16 PM]
[edited by - soiled on September 20, 2003 2:45:36 PM]
[edited by - soiled on September 20, 2003 2:47:27 PM]
I'm also aiming for ps.1.1. However I'll be using gf4 shadow buffers in d3d which automatically use tex coord 'r' when doing z-compare so unfortunately I can't stick 'z' in another tex coord or vertex colour
But you're right, it does look like ps.2.0 can handle this type of shadowing. So that pretty much means I'm forced to either (a) put up with incorrect shadow map z-interpolation between vertices (and find some way to make it unnoticeable), (b) divide z by y so that all x,y,z are divided by y and hence use a slightly different light frustum than we want or © go back to post-perspective space. I'll have a bit more of a think about options (a) and (b).With shadow maps that can overlap in some areas and not in other areas (I assume your max 4 maps idea does this) I don't know how you would blend them.
OTOH if they line up next to each other (ie Thatcher Ulrich's max 5 maps) where light frustums are perfectly adjacent to each other then you'd only need to remove the seams. Assuming bilinear shadows, the border edge of a shadow map should be zero if border is adjacent to another shadow map otherwise it's a regular shadowmap value.
This is so you're addition of shadow maps (eg for 4 maps this would be 0.25*(t0+t1+t2+t3)) looks like (for adjacent borders)...
_____ _____
map1 \/ map2
map1 /\ map2
...so when border is zero you put edge of light frustum one texel inside boundary (so it's halfway between border texel and next inner texel) and when border is not zero you put light frustum half texel inside (right on border texel). This would require both shadow viewport adjustments and tex coord adjustments. So when the light is directly behind viewer so that all five view frustum faces are visible to the light you get 4 borders that aren't adjacent to another border and 16 borders that are.
[edited by - soiled on September 20, 2003 2:42:08 PM]
[edited by - soiled on September 20, 2003 2:43:16 PM]
[edited by - soiled on September 20, 2003 2:45:36 PM]
[edited by - soiled on September 20, 2003 2:47:27 PM]
