{"id":77,"date":"2010-03-03T18:22:04","date_gmt":"2010-03-03T18:22:04","guid":{"rendered":"http:\/\/the-witness.net\/news\/?p=77"},"modified":"2010-03-03T18:35:57","modified_gmt":"2010-03-03T18:35:57","slug":"graphics-tech-shadow-maps-part-1","status":"publish","type":"post","link":"http:\/\/the-witness.net\/news\/2010\/03\/graphics-tech-shadow-maps-part-1\/","title":{"rendered":"Graphics Tech: Shadow Maps (part 1)"},"content":{"rendered":"

The Witness<\/em> contains a mixture of indoor and outdoor scenes, but much of the game takes place outdoors with a very long view distance (you can see the entire island at once if you have a good vantage point). \u00a0So I wanted to implement a shadow system that would work robustly, provide high visual quality, and allow the player to see everything at once. \u00a0I have some experience with shadow systems of this type, but the last one I designed was for computers and graphics cards circa 2004, so I was interested to see how much more would be possible today.<\/p>\n

We've implemented such a modern shadow map system for The Witness<\/em>. \u00a0In the process, we've made some improvements to shadow mapping algorithms beyond anything we've seen published, so we are going to detail the improvements here. \u00a0Also, our shadow map system is still being improved, so I'll talk about what we have yet to try and why we think it's a good idea.<\/p>\n

Before we get to those details, though, I'd like to establish some context so that the motivation for these design decisions is clearly explained.<\/p>\n

The Literature<\/strong><\/p>\n

I have a somewhat cynical attitude toward graphics research literature: most of it describes techniques that don't generally work, but the authors of the papers do the best they can to \"sell\" the technique to you anyway (using cherry-picked examples, glossing over or completely ignoring failure cases that would be obvious to anyone who understands the algorithm, etc). \u00a0As the reader, eventually you come to understand all the problems, but not after investing a lot of your time and energy (possibly months) implementing and understanding an algorithm that behaves so poorly that you never would have bothered if you had known the truth from the outset.<\/p>\n

<\/p>\n

I've had this experience many times, with many different techniques. \u00a0Shadow maps, though, have been one of the big ones. \u00a0There are many published shadow map techniques that simply don't work well enough to be taken seriously. \u00a0And often when I've heard someone say \"so-and-so shadow technique is good,\" it usually turns out they haven't tried it themselves, so it's just hearsay, or else that person has low quality standards.<\/p>\n

So I'd like to put forth the statement that I have high quality standards and will only endorse things that have been found to robustly function; I will be open and honest about the degree to which things don't work, and what the specific problems are. \u00a0In an ideal world this would not be necessary to say, but the situation in the literature today makes it otherwise.<\/p>\n

Quality Goals; Previous System<\/strong><\/p>\n

Many shadow map schemes have been developed that try to maximize the effective resolution of shadows in the scene by performing transformations that are heavily view-dependent. \u00a0An extreme example of this is Perspective Shadow Maps. \u00a0I have learned through experience not to use these techniques. \u00a0They cause shadows to swim and flicker in annoying ways, and many of the algorithms break down severely as the player approaches certain viewing angles.<\/p>\n

For\u00a0the 2004 system<\/a>, I took as a core design goal that shadows should appear rock-solid on nonmoving objects, regardless of any viewpoint motion. \u00a0The clearest way to achieve this was to center the shadow map on the viewpoint at all times, never letting the shadow map scale or rotate. \u00a0Because a single shadow map cannot cover the world at high resolution within memory and fill constraints, I used a scheme where 4 or more shadow maps of increasing worldspace size were centered on the viewpoint like square doughnuts. \u00a0In order to prevent crawling or shimmering, one just ensures that shadow map worldspace positions are snapped to integer multiples of their texel size. \u00a0(A family of related techniques, but which don't necessarily center the maps on the viewpoint, soon came into more-common use and took on the moniker Cascaded Shadow Maps.)<\/p>\n

On fixed-function pipeline hardware, this scheme was never quite satisfying (I had to use clip planes to render the scene in many slices, and there were small 1-pixel artifacts due to the resulting imprecision; rendering all the slices was a bit slow). \u00a0Modern hardware is able to do this kind of thing much \u00a0better. \u00a0Also, this scheme wastes a large amount of shadow map memory, because with all the shadow maps centered on the viewpoint, most of the map texels are going to be out of view at any given time.<\/p>\n

Despite the drawbacks, the visual stability of this technique, and its ability to reach across the entire game world, were extremely appealing to me. \u00a0Having seen how nicely shadow mapping could behave in practice, this visual stability became a very-high-priority goal in my mind for any future shadow systems.<\/p>\n

So, going into this new system, the goals were (listed in approximate order of importance):<\/p>\n

    \n
  1. High performance<\/li>\n
  2. Complete stability under camera motion<\/li>\n
  3. Long view distance<\/li>\n
  4. Visuals can be controlled to suit the style of the game<\/li>\n
  5. Efficient use of texture memory<\/li>\n<\/ol>\n

    The New System<\/strong><\/p>\n

    I started working on the new system by looking at the 2004 system and trying to make it more memory-efficient. \u00a0Most likely this would involve moving the shadow maps around in world space, but it wasn't initially clear to me how to do this without introducing problems. \u00a0Ignacio pointed me at Michal Valient's article \"Stable Rendering of Cascaded Shadow Maps\" in ShaderX 6<\/a>, which was exactly what I wanted. \u00a0Valient computes bounding spheres around the slices of the view frustum that tell him how much he can move the shadow maps in world space without introducing gaps.<\/p>\n

    To illustrate, here are a couple of figures reproduced from his article. \u00a0I don't want to unduly step on anyone's copyright, so if you are interested in cutting-edge shadow map techniques, buy ShaderX 6! \u00a0(Click for full size.)<\/em><\/p>\n

    \"figure_411\"<\/a><\/p>\n

    \"figure_412\"<\/a><\/p>\n

    So basically, you take the a frustum slice in worldspace, ensure that it is completely enclosed in a sphere, and then ensure that the sphere is completely enclosed in a square cylinder; the square is your shadow map.<\/p>\n

    You can render multiple frustum slices for multiple shadow maps, so long as the bounding spheres overlap enough to cover the whole frustum when put together (see 4.1.2 c and d).<\/p>\n

    The reason they are spheres is: because the shadow map is never allowed to change size (we voluntarily imposed that constraint in order to get solid shadows!), then we need to find a shape that conservatively encloses any possible orientation that a frustum slice could occupy as the camera rotates in space. \u00a0That's a sphere. \u00a0Then we make sure that our shadow map covers that entire sphere, and we have then guaranteed that every point in the view frustum is covered by a valid shadow map \u00a0texel.<\/p>\n

    On top of this, Valient suggests the very helpful optimization of packing all your shadow maps into one atlas texture, so that when it's time to render the scene, you can draw all your shadowed objects in one pass without having to sample multiple textures; you just figure out which frustum slice each pixel lands in, then use that information to determine the offset into the atlas, add that offset to your texture coordinates, and sample the texture. \u00a0This works great. \u00a0Valient suggests a 2x2 arrangement of textures, as this is convenient on a wide variety of hardware, for example, GPUs that only support power-of-two textures. \u00a0So if a single shadow map would be 1024x1024, then you can create a 2048x2048 texture map that contains 4 shadow maps packed in a 2x2 array:<\/p>\n

    \"\"<\/a><\/p>\n

    So my first shot at a new system was basically a reimplementation of everything Valient describes. \u00a0It didn't take too long, and when it was done, I was very happy with it -- it was clearly much better than the 2004 system.<\/p>\n

    But...<\/p>\n

    Memory Usage<\/strong><\/p>\n

    This technique is still a memory hog. \u00a0The image stability constraints, which result in us wrapping the frustum slice in a sphere and then the sphere in a box, add margins of unused and barely-used texture space at each step. \u00a0Looking at Figure 4.1.2, you can see that a frustum slice only occupies about 50% or 60% of the area of the square that represents your shadow texture. \u00a0This implies that half the square is wasted. \u00a0However, the actual situation is worse than this, because the diagram is misleading.<\/strong><\/p>\n

    The problem is that the view frustum represented in the diagram is much narrower than the view frustum used in an actual game, and if you re-draw the diagram in realistic proportions, it looks very different. \u00a0For an accurate 2D diagram, you are finding a circle that encloses the widest part of your view frustum, which is the 2D trapezoid you get by cutting your frustum in half diagonally (Valient discusses this in his paper as well). \u00a0Suppose your game is rendering at a 16:9 aspect ratio, and your field of view is 90 degrees horizontally (this is what we use for The Witness <\/em>currently.) \u00a0The vertical field of view is then going to be about 59 degrees, and the diagonal field of view will be about 98 degrees<\/strong> (click on image below for explanation).<\/p>\n

    \"\"<\/a><\/p>\n

    The frustum slice in Valient's diagram is only about 30 degrees, a huge difference! \u00a0So if we have a 98 degree frustum slice, and inscribe that in a circle, and inscribe that circle in a square, what does that look like? \u00a0Something like this:<\/p>\n

    \"\"<\/p>\n

    Recall that the square is your shadow map texture and the innermost trapezoid\u00a0is your frustum slice (the texels of your texture that may potentially be used). \u00a0It covers only a small \u00a0area of that square -- and there's no way to make it bigger! \u00a0The reason is that for wide frusta like this, the diagonal at the far plane is so long that it dominates the bounding sphere computation, and so the center of the circle has to land on that diagonal so that its diameter can be just barely large enough to enclose it. \u00a0(In The Witness<\/em>, our frustum slices are not proportional, and the way we divided them up, this isn't exactly true for the first 2 shadow maps -- but it is very close to true). \u00a0The fact that the circle is centered on the far plane means that automatically half the map is wasted at this orientation -- but the wide angle ensures that much of the other half is wasted too!<\/p>\n

    You can rotate the view frustum to other orientations and make it look like you are covering more of the shadow map... for example, if you orient the frustum so that the view vector is going straight down into the page, then the frustum's projection onto the paper will be a rectangle, and it will appear to cover much more of the square. \u00a0But then you have to keep in mind that some of this coverage is worth a lot more than other coverage in terms of impact on the scene: think about how much space is covered by the texels toward the middle of the frustum projection, versus how much is covered toward the edges (almost none!)<\/p>\n

    If I add two more frustum slices, so that the total is 3 slices as in 4.1.2, it looks like this:<\/p>\n

    <\/a>\"\"<\/a><\/p>\n

    That innermost shadow map is just a tiny smudge (now you know why Valient chose a narrow field of view -- for clarity of his figures!) \u00a0But notice what else is going on: each shadow map is fully contained within the next-larger shadow map, as with the concentric-square-doughnut system from 2004! \u00a0Valient's scheme is better since it gives you more view distance (the squares are not concentric) -- but it can't give you nearly as much view distance as it would like, due to the wide angle of the frustum.<\/p>\n

    For Next Time<\/strong><\/p>\n

    So, whereas on one level I was very happy with this shadow system's performance and visual quality, it still seemed somewhat wasteful in terms of memory usage. \u00a0 Next time I'll talk about how we addressed that problem. \u00a0Subsequent postings after that will talk about issues like softening the shadow border, blending between slices, and various other implementation tricks.<\/p>\n


    \n<\/strong><\/p>\n

    To be continued.<\/strong><\/p>\n


    \n<\/span><\/div>\n","protected":false},"excerpt":{"rendered":"

    The Witness contains a mixture of indoor and outdoor scenes, but much of the game takes place outdoors with a very long view distance (you can see the entire island at once if you have a good vantage point). \u00a0So I wanted to implement a shadow system that would work \u2026<\/p>\n

    Continue reading<\/i><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[7],"tags":[],"_links":{"self":[{"href":"http:\/\/the-witness.net\/news\/wp-json\/wp\/v2\/posts\/77"}],"collection":[{"href":"http:\/\/the-witness.net\/news\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/the-witness.net\/news\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/the-witness.net\/news\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/the-witness.net\/news\/wp-json\/wp\/v2\/comments?post=77"}],"version-history":[{"count":16,"href":"http:\/\/the-witness.net\/news\/wp-json\/wp\/v2\/posts\/77\/revisions"}],"predecessor-version":[{"id":107,"href":"http:\/\/the-witness.net\/news\/wp-json\/wp\/v2\/posts\/77\/revisions\/107"}],"wp:attachment":[{"href":"http:\/\/the-witness.net\/news\/wp-json\/wp\/v2\/media?parent=77"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/the-witness.net\/news\/wp-json\/wp\/v2\/categories?post=77"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/the-witness.net\/news\/wp-json\/wp\/v2\/tags?post=77"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}