Sign in to follow this  
JakeOfFury

A Robust Alternative to Perspective Shadow Mapping

Recommended Posts

JakeOfFury    156
I came up with this procedure while working on my portfolio. It occured to me that there is no reason shadowmapping should not offer 100% correct shadows in *appearance* because in theory we should be able to map every shadowmap pixel to a screen pixel, or in other words, give objects that are bigger on screen more shadowmap space. I came up with the idea I present here, then dropped it in favor of light space PSM because it is slower than LiSPSM, but the main drawback of any kind of PSM is that those procedures revert to naive shadowmapping when the light is behind the viewer. For large scenes this means the same problems as with naive shadowmapping (for instance, an outdoor scene with a setting sun, etc). So anyway.. moving on.. my idea is to simply alter the shadowmap texture coordinates based on a vertex's distance from the user viewpoint. The disadvantage of this scheme is that it involves a few more operations per vertex that result in around 3%-5% slower vertex throughput per shadowmap than PSM (or LiSPSM) but the advantage is that shadows near the user are always increased in detail, even if the view direction coincides with the light direction. My procedure involves (for directional lights, since they need the most help): 1) Optimize the light frustrum to fit the view frustrum as close as possible on the 4 sides, and to enclose all possible casters by setting the near plane just in front of the first caster in the scene. 2) Pass in the transformed user view location to the vertex shader. 3) Within the shader, scale each vertex based on its distance from the transformed view origin. This effectively biases the vertices based on their distance from the user *as projected onto the shadowmap plane*. The equation I use is similar to the z transform (since the goal is to mimic the size falloff that the z transform produces in scene geometry): _shift.x = oPos.x - g_frustrumCenter.x; _shift.y = oPos.y - g_frustrumCenter.y; _weight = g_shadowDistanceWeight / (g_shadowDistanceWeight - 1); if(_shift.x >= 0) { oPos.x = (1 - g_frustrumCenter.x)*(_weight - _weight / (_shift.x * (g_shadowDistanceWeight - 1) + 1)); } else { oPos.x = (1 + g_frustrumCenter.x)*(-_weight - _weight / (_shift.x * (g_shadowDistanceWeight - 1) - 1)); } if(_shift.y >= 0) { oPos.y = (1 - g_frustrumCenter.y)*(_weight - _weight / (_shift.y * (g_shadowDistanceWeight - 1) + 1)); } else { oPos.y = (1 + g_frustrumCenter.y)*(-_weight - _weight / (_shift.y * (g_shadowDistanceWeight - 1) - 1)); } oPos.x += g_frustrumCenter.x; oPos.y += g_frustrumCenter.y; Here oPos is the vertex location (shadowmap tex coord) ,_shift is a temporary variable, and g_frustrumCenter is the transformed user viewpoint. g_shadowDistanceWeight is the "far plane" in the z transform equation, with the "near plane" always being set to 1 for simplicity. That is, if this weight is set to a high number (say, 100), the biasing effect will be very high. If it is set to 2, no change in coordinates takes place. This shader fragment essentially does this: a) Translates the vertex so that the user viewpoint would be at (0,0). b) Scales the vertex by the weight - 1, then adds 1. This puts all vertex values between 1 and the "far plane" value. c) Applies the z transform type of scaling to the vertices. d) Scales the vertex back to the maximum possible coordinate it could have had. e) Translates the vertex by putting the view location back where it was. If anyone has a better idea on how to do this, please tell me, because as you can see this shader fragment doesn't move as fast as I would like it to.

Share this post


Link to post
Share on other sites
Schrompf    1035
Have you tried it? Is there maybe a demo available? I'm interested how much of an improvement you achieved with this.

The technique you described sounds similar to a method I developed last year. The main difference is a) you distort both texture axises seperated, I use a combined distortion method and b) I use a different distortion formula.

I wrote an article on the method. Unfortunatly, it's in german. I haven't found time to translate it, yet. I don't know how far babelfish got in the meantime but maybe you want to give it a try: [url]http://www.softgames.de/developia/viewarticle.php?cid=27884[/url]

The main points in short:

A function to describe how "good" the resolution should be. Could be any, but for the sake of simplicity, parametrization and integration I chose

x = 1 / (t + 1/k)

t is the distance from the viewer at the shadow texture, x is the desired relative shadow resolution there. x==k for t=0 and x~=1 for t=1. The constant k can be used to scale the effect, good values are 50 to 100.

Because this function describes the "density" of texels, we have to integrate over it to get an actual distortion function. This results in

V(x) = ln(k * t + 1)

It's a nice function with a rapid ascend at beginning and a low slope at the end. It has to be normalized, though, so it ends exactly at 1.

V'(x) = ln(k * t + 1) / ln(k + 1)

This is our final distortion function. It maps an undistorted, "plain" shadow map texture coord to a distorted texture coord. Because of the rapid ascend at the beginning, much texture space is used close to the distortion origin, improving the texture resolution there. With increasing distance from the distortion centre, the slope of the function gets lower and lower. Close to the end (t == 1) the slope is much lower than 1, thus lowering the texture resolution there. So this distortion function basically increases the shadow map resolution close to the viewer at the cost of lowering the resolution for most scene parts farther away from the viewer.


You simply use it in the vertex shader a) when rendering shadows and b) when rendering the scene with the light. The vertex shader fragment looks like this:

// calculate texture coords and depth just like uniform shadow mapping
float3 shadowTextureCoords = CalculateShadowTextureCoords();

// subtract the distortion origin (where the viewer resides) from it
float2 texDiff = shadowTextureCoords.xy - gShadowViewerPos.xy;

// calculate undistorted distance from viewer position at the texture
float t = length( texDiff) * 2.0f;

// do the distortion: calculate new t from old t,
// then divide by old t because it's contained twice as length of texDiff
// The formula is ln( k*t + 1) / ln( k + 1)
// gShadowViewerPos.z is "k", gShadowViewerPos.w is "1 / ln( k + 1)"
float nt = gShadowViewerPos.w * log( gShadowViewerPos.z * t + 1) / t;

// transform to absolute distorted shadow texture coords
shadowTextureCoords.xy = gShadowViewerPos.xy + texDiff * nt;


Works well over here. We have a view distance of 1000 virtual meters and a shadow map of 2048x2048. With plain uniform shadow mapping this would result in appr. 2 shadow pixels per meter. With the distortion described above (k == 100) we get an improvement factor of 20, increasing the resolution to 40 shadow pixels per meter. And the improvement is completely independend from the view direction and the light direction.

Downsides:

* additional vertex processing time. Less than 1% here so not much of an issue.

* the distortion is NONLINEAR.

Thats a problem, because the interpolation of values at the graphics board are linear. For long face edges, the interpolated shadow texture coords at the middle of the edge differs from the real distorted value that would be calculated for this position. In our game, this is mostly no problem as the scene is tesselated enough close to the player. But for example a billboard tree casting shadow from a hundred meters behind distorts quite heavily. It looks like the shadow bends outwards in direction of the camera. You have to make sure that everything casting or receiving shadows is well tesselated when close to the player. In our world, edges should not be longer than about 2 meters before the distortion gets visible.

Well... sorry for that quick breakdown. I should really do an more detailed paper on this method. It works quite well for us, except for the distortion problem stated above. I'm curious if your method would do better at this topic.

Pictures available if needed.

Bye, Thomas

Share this post


Link to post
Share on other sites
JakeOfFury    156
Thanks for replying Schrompf!

I only choose to distort the axes separately because I thought the length operation would take too much time in a shader. I would actually prefer to do it the way you do, because as I do it objects at certain angles from the viewer receive improper texture space. I will write up your version and compare speeds.

Also, thank you for providing another equation. I spent a day looking for other possible "mappings" that would do what I want. I will try your way and see if there is any advantage/disadvantage.

Finally, my version also suffers from the interpolation artifacts when the surface isn't tesselated sufficiently. While this doesn't really matter as far as models go (since they are so tesselated these days), it is a shame when it comes to ground surfaces, because it would be nice to get away with low vertex counts. After all, one of the best things about per-pixel lighting is the reduction in necessary vertices to achieve realism. I am still working out the math to fix this, my current idea is to pass in another value to the pixel shader that can be used to scale the interpolated coordinates to what they should be.

Can you please send me a message (rocketdodger@yahoo.com) with an email contact so we can discuss this more formally? It would be nice if we could find a way to overcome these artifacts, then there would no longer be an advantage to PSM (except for the speed).

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Warping and Partitioning for Low Error Shadow Maps

http://gamma.cs.unc.edu/wnp/

Share this post


Link to post
Share on other sites
Quote:
Original post by Schrompf

// calculate texture coords and depth just like uniform shadow mapping
float3 shadowTextureCoords = CalculateShadowTextureCoords();



This method sounds very interesting..But can you elaborate a bit more?

When you say "caculate texture coords" what exactly do you mean here? What texture coords need to be calculated in the depth pass?

i have a shadow mapping system implemented, and I have a hard time figuring out what the relevance of this code is. I dont calculate any texture coords in the depth pass.


Share this post


Link to post
Share on other sites
JakeOfFury    156
Quote:
Original post by Matt Aufderheide

This method sounds very interesting..But can you elaborate a bit more?

When you say "caculate texture coords" what exactly do you mean here? What texture coords need to be calculated in the depth pass?

i have a shadow mapping system implemented, and I have a hard time figuring out what the relevance of this code is. I dont calculate any texture coords in the depth pass.


You do, you just don't know it. What we actually mean are "shadowmap coordinates."

The relevance of the technique we are discussing is that it makes objects closer to the viewer larger in the shadowmap, which means their shadows will be much more refined. This doesn't matter for small scenes, but think of directional lights where the view frustrum has a far plane miles away -- if you want shadows that look decent you have to find a way weight the shadow detail based on distance.

Share this post


Link to post
Share on other sites
Cypher19    768
It's a good idea, but you might want to write up a demo demonstrating it. Right now, I'm a bit skeptical as to how robust it'd be since you're applying nonlinear transformations to your vertices, so the linear interpolations that the hardware does could get a bit weird or create undesirable results in some situations (esp. with low to moderate tesselation).

Share this post


Link to post
Share on other sites
JakeOfFury    156
Ok Schrompf I tried your equation and I like it better -- plus it runs faster, although I don't see how, since it involves two log() functions! I have a feeling its because of shader model 2.0, my version might be faster in 3.0 where dynamic branching operates as it should.

The artifacts due to linear interpolation between vertices are much less pronounced with your equation than with my version, so I am changing over. Hopefully in the future more people will get into this so we can find better and faster equations.

RE Cypher19 -- I agree, I don't like the fact that the transformations give strange abnormalities with low tesselation. Plus, I don't like how slow it is. I would much rather use LSPSM, but the problem is that LSPSM doesn't work when the viewer is looking down the light direction. I am waiting for someone to find a matrix transformation similar to LSPSM that does what we are doing with the texture coords, but so far I can't think of anything.

Share this post


Link to post
Share on other sites
Schrompf    1035
First: thank you all for your interest. I don't have a isolated demonstration that shows the method but I have a WIP game engine that implements it. The only difference is that the data is much larger. Once I get home again this evening I'll try to trim down the package to the minimum and upload it. Download size will still be around 50 MB so pack a lunch. SM2.0 minimum.

Till evening I can only show pictures. They're taken from the (german) article I wrote some months ago: without distortion, with distortion, k == 50

Comparing against LSPSM: You basically exchange one set of problems with another. LSPSM is dependend on angle between view dir and light dir. The distortion method has problems with nonlinearity <-> linear interpolation. On the scene we're operating on, it works out fine. But it IS a problem for smaller scenes, where the slope change per scene meter is larger. You may try this out in the demo, i'll add some console vars to adjust view distance and the distortion factor.

Oh, and another advantage: It's possible to silence the shadow border flickering caused by readjusting the shadow map area every frame. The demo at present has no flickering when rotating the view and a occasional flickering when moving the view.

BTW: Vertex Shader performance is not an issue. Starting from SM2.0, a full precision log() does cost a single instruction slot and a single clock cycle AFAIK. The length() is approx. 3 cycles, the other math adds maybe another 5 cycles. As most of the games today are pixel shader limited anyways, this is no problem.

@Matt Aufderheide

JakeOfFury already answered this, but I want to make sure it's clear: CalculateShadowTextureCoords() does a simple transform into light space to calculate the shadow map texture coords for that vertex. Because it's the standard operation for uniform shadow mapping I moved it out of the code snippet and only left dummy function there. I hoped to show this way that the distortion method jumps in right after the standard shadow map texture coord calculation.

[edit] on a second read: You have to apply the same distortion a second time on the vertex positions when rendering the depth pass. Without, the occluder position at the shadow map would not match the position where this shadow map part is applied at the scene.

After projection, pos.xy are in the range -1..+1 and pos.z is 0..1. You have to expand the distortion center and the formula accordingly. Namely, remove the " * 2.0f" at the formula and do a "* 2 - 1" on the distortion center. [/edit]

Bye, Thomas

Share this post


Link to post
Share on other sites
Inigo Quilez    499
JakeOfFury, Schrompf, this is a quite an imaginative technique, the nicest one in my "shadow map techinque of the month" ranking :) Congrats.

Now, I tried it and I had quite bad results because my geometry is not tesselated enought (I have 20 meters long objects). I don't think I can inmediatly go for any of the obvious solutions:

1] statically subdivide my geometry (what I cannot affort, I have hundred of million of triangles)
2] add a distance based dynamic tesselation system (an aggresive LOD basically) 3] use Shader Model 4.0 and tesselate the stuff on the GPU as needed.

By the way, I cannot really tell if these is a good one, but I also tryed this other distortion function

sqrt( (t^2 h)/t^2) )

with the parameter h going from 0 (no distitoion at all) to infinity (total distition) and "good" values around 1/4. It translates to just 1 RSQ and 1 RCP in ShaderModel 2.0

DP3 nt.x, texDiff, texDiff;
ADD t.x, nt.x, h;
RCP t.x, t.x;
MUL nt.x, nt.x, t.x;
RSQ nt.x, nt.x;

but the log()/log() formula one is also fast anyway, and "more correct", you know what I mean (by the way JakeOfFury, it only involves one log() because the complete divisor can be passed as a constant to the shader).

Again, this is a cool technique that can be applied in some specific cases (as yours), and interesting because I think its the first shadowmapping method that moves the problem to the vertex count side (as opposed to multiplass solutions) and the first one I know about that works with arbitrarilty big view frustum (not like PPSM, TSM and all the other frustum based methods). As bonus, you don't have to change your current software, just add few lines in the vertex shader; no complex frameworks at all !!

It worths a try, really.

Share this post


Link to post
Share on other sites
cpiasminc    156
Quote:
The distortion method has problems with nonlinearity <-> linear interpolation.

In theory, though, it should be possible to not rely on the hardware's bilinear interpolation (use nearest-neighbour instead) and take multiple warped position samples or a nonlinear-weighted blend yourself. For that matter, it's also just as well that you hide these errors by softening the shadows anyway with some sort of PCF or Variance Shadow Mapping. And soft shadows are anyway perceived as more realistic.

Share this post


Link to post
Share on other sites
Schrompf    1035
Ok. As usual, much more work was needed than I expected, but it should demonstrate the basic quite well. It's even instrumented to be analysed by NVPerfHUD if you have this wonderful tool handy. A readme is included.

It's also larger than expected, mainly due to the demo world we use. I wasn't able to create a smaller world in the short time so I had to use this one. I hope your internet connection is a flat fee.

Zipped Demo, 90 MB (still uploading, ETA 03:15 AM) [edit]Done. I'm off to bed.[/edit]

Just decompress it somewhere, read the ReadMe and run it. All DLLs are included, I hope. Needs SM2.0 minimum. Could maybe cause problems like crashes or very slow framerates on cards with 128MB VideoRAM or less. Again: Work In Progress. Could crash, burn your monitor or fuck up your system any time. It wasn't me, I'm not responsible. Please don't hurt me.

Shadows look ok at the default config, I think. The large tree you see when loading camera position 1 causes some shadow distortion artefacts because it's billboard leaves are too large. Well... we wanted to redo it anyways. All other trees turn to billboard at a certain distance. If you manage to have a shadow of it close to you, maybe on sunset, you can watch a heavy shadow distortion. These are the nonlinear artefacts I wrote about in an earlier post. Looks like the tree shadow is chasing the viewer. Not nice.

On a second thought, there's room for improvement. When rendering the scene, shadow map distortion could be done in the PixelShader. No more linear/nonlinear conflicts there. This way is impossible when rendering the depth pass, though. Maybe onthefly tesselation with SM4.0 could work. In combination it should be possible to increase the distortion factor to get even better shadows close to the viewer.

Another idea is to use another density function. The cause of this linear/nonlinear artefacts is the slope change of the distortion function, thus the slope of the density function. If we choose a density function which starts even at t==0 and then descends rapidly, the beginning of the distortion functin close to the viewer would be linear, thus interpolating fine. The nonlinear artefacts would at least be moved away from the viewer to scene parts a bit farther away.

Bye, Thomas

Share this post


Link to post
Share on other sites
JakeOfFury    156
Quote:
Original post by krausest
There's a siggraph session Practical Logarithmic Shadow Maps next week. Maybe - there's not much information available - it's a similar idea. Let's hope nvidia will make that presentation available as a download soon.


I looked at that flyer just now, I bet it is the same idea, because they mention "non-linear rasterization."

Luckally, by me and schrompf posting here before the public presentation at siggraph, this technique won't be patented. Booooo Creative Labs...

Oh yeah, and the fact that Schrompf says he had this idea a year ago and there is a German paper on it... that should keep it publicly available.

Share this post


Link to post
Share on other sites
pixalot    145
Why not use 1/x as the weight function and let the W divide do the distorsion. Also if you split your shadow map in 4 different regions along the axes and render each of them with a normal 4x4 projection matrix you can use the linear interpolation as well.
I've just finished implementing this type of shadows in a commercial game and it looks pretty well, but no screenshots I'm afraid since it is still in development.

Share this post


Link to post
Share on other sites
edwinnie    122
Quote:
Luckally, by me and schrompf posting here before the public presentation at siggraph, this technique won't be patented. Booooo Creative Labs...


The date of acceptance of the research article is usually around 4-6 months before the actual presentation. Furthermore, they could easily apply for a Preregistration even before that. However, i tend to believe it wont be patented (unless its a university graduate who is graduating via a PhD in which their procedure might require a patent).

Edwin

Share this post


Link to post
Share on other sites
krausest    146
Sorry to bother you, but I don't get it working well so I'm asking for your help.

Let's start with the formula:

1. I don't understand what scaling to apply for t. If the viewer position and current vertex position is in [-1,1]^2 and the input paramter t for the formula has to be in [0,1] then I'd get
nt = ln( k*t/sqrt(4.0) + 1) / ln( k + 1) * sqrt(4) / t.
Actually sqrt(4) might be replaced with the maximum length from the projected viewerPosition to all four corners.

2. When the light position is fixed but the viewer changes the shadows move too - Even a change in k makes the shadows move.
I guess one reason is that (when rendering the scene with light) CalculateShadowTextureCoords() returns a w coordinate != 1. Dividing by w in the vertex shader makes things much worse. Keeping w and computing shadowTextureCoords.xy = w * (gShadowViewerPos.xy + texDiff * nt) helps a bit but it's still very noticeable. How do you handle the w coordinate?

Thanks,
Stefan

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Quote:

Till evening I can only show pictures. They're taken from the (german) article I wrote some months ago: without distortion, with distortion, k == 50



344 to 34 fps? Man I dont know If I would want to use that algorithm. Seems quite slow to me.

Share this post


Link to post
Share on other sites
Hexus    193
Quote:
Original post by Anonymous Poster
Quote:

Till evening I can only show pictures. They're taken from the (german) article I wrote some months ago: without distortion, with distortion, k == 50



344 to 34 fps? Man I dont know If I would want to use that algorithm. Seems quite slow to me.


Looks like 344 to 341 to me.

Share this post


Link to post
Share on other sites
krausest    146
Quote:
Original post by krausest
There's a siggraph session Practical Logarithmic Shadow Maps next week. Maybe - there's not much information available - it's a similar idea. Let's hope nvidia will make that presentation available as a download soon.


There's more info online (SIGGRAPH sketch slides) on http://gamma.cs.unc.edu/logsm/, but from what I understand it's not what you propose.

Still I have some questions regarding your method. The warping you apply is only 2D. How do you guarantee that every vertex inside the view frustum (i.e. inside the unit cube after projection) stays inside? nt depends on the distance from the viewer only, but what if the viewer and a vertex are close to a side of the unit cube? Couldn't it happen that the vertex is warped outside the unit cube?

Share this post


Link to post
Share on other sites
MrSparkle    148
Your shadow algorithm really is fascinating! Thank you for the demo application. I also read your article at softgames.de. I recommend to take a look at the English versions translated by Google and Babelshish here and here, although it's more a Pidgin English version of the article ;)

In the demo application, I noticed a strong flickering effect when the shadow moves. Is this caused only by the moving light source or does this also occure when moving the camera? I couldn't find out, because I didn't find a way to stop the light moving around.
Can you tell me which size the shadow map in the demo has?

Great work!

Christian

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this