Virtual Shadow Maps

Jaker

Senior Frog @ GP

Justin Hall

Rendering Wayfinder

LVSTRI

GPU Whisperer

This is a copy of a near-final version of the article we published in GPU Zen 3, translated from LaTeX to Markdown.

The code associated with this article can be found in Timberdoodle (Vulkan). In developing the technique, we have also published implementations in Frogfood (OpenGL/Vulkan, article) and StratusGFX (OpenGL, article).

Shadow mapping is ubiquitous in real-time applications due to its good performance and compatibility with existing rasterization pipelines. However, the growing demands for graphical fidelity and performance continue to increase the complexity of shadow mapping techniques. The simplest way to increase the quality of a shadow map−-−increasing its resolution−-−scales its memory cost quadratically and increases the likelihood of cache misses when sampling, leading to worse performance. This makes it an impractical way to achieve acceptable quality in diverse scenes. Moreover, shadow maps suffer from two major forms of aliasing: perspective aliasing and projective aliasing, shown in figure 1.

Figure 1: Left: shadows exhibiting perspective aliasing from insufficient shadow map resolution. Right: projective aliasing can be seen by the jagged shadow edges on the wall.

Perspective aliasing occurs when screen pixels do not map to shadow texels in a one-to-one manner. In a basic shadow map implementation, this can be observed by simply moving the viewer closer to or farther from the edge of a shadow. When close, the edge has a jagged appearance due to individual shadow texels mapping to many screen pixels. Even when filtered, a slight shift in occluding geometry or the casting light will appear jittery. When far from the shadow, the shadow map over samples the scene and consumes more memory than necessary.

When the direction of incident light is almost parallel to the surface, projective aliasing occurs. In this case, the projection of a texel onto that surface will cover a large area, making the depth sample an inaccurate representation of the blocker. For an observer, this gives the edges of shadows a jagged appearance, even when there is otherwise no visible perspective aliasing.

Cascaded Shadow Maps (CSMs) is a popular algorithm used to alleviate both types of aliasing in directional lights [Dim07]. In CSMs, the viewer's frustum is partitioned into smaller frusta, each fit with its own light space matrix and assigned a shadow map. The scene is then rendered to each shadow map using the cascade's frustum. The result is an improved distribution of shadow texels. A denser shadow map is placed near the viewer where detail is most needed, while distant regions receive coarser shadows. Sample Distribution Shadow Maps (SDSMs) improve CSMs by using a per-frame analysis of the scene to calculate tight-fitting frusta, maximizing the efficiency of the shadow sample distribution regardless of scene content [LSL11].

Although these techniques reduce aliasing, the fundamental compromise between shadow quality and memory cost remains. It is thus common for rendering engines to provide several options for shadows, each with their own set of trade-offs. For example, screen-space ray tracing is often used for sharper and more detailed contact shadows in contrast to those provided by shadow mapping implementations.

With the release of Unreal Engine 5 (UE5), Epic Games added Virtual Shadow Maps which scale to support the detailed geometry enabled by Nanite [epi22, Kar21].

Virtual Shadow Maps (VSMs), as the name might suggest, are an application of virtual textures [vW09, Bar] for shadow mapping. Virtual texturing itself is essentially a generalization of virtual memory.

By separating the logical address space (seen by the user) from its physical backing, the appearance of a very large contiguous memory space can be achieved without the need to reserve physical memory for it. This is done by dividing the logical address space into pages that are dynamically backed by physical memory.

Virtual memory provides numerous benefits in operating systems. For virtual texturing and thus also for VSMs, its primary purpose is to provide an abstraction allowing for a highly reduced texture memory footprint. That is, only the pages of a VSM that are visible need to be allocated.

As mentioned above, it is common to combine multiple shadowing algorithms to achieve the best visual result. The efficient distribution of shadow texels that VSMs offer makes them viable as a standalone technique. Thus, VSMs also serve to unify multiple shadowing paths, making it easier to author scenes without having to consider how each path may be affected.

Inspired by UE5, we re-derive and implement Virtual Shadow Maps in our renderer. This article and the accompanying demo application serve as pedagogical tools to understand this technique. This is mainly motivated by the lack of resources that describe this technique in detail at the time of writing. [Haa15] is the only resource we could find that mentioned VSMs, and it only does so in passing.

Figure 2: Virtual memory system overview.

Our implementation supports a VSM for a directional light, consisting of 16 overlapping 4096×40964096\times40964096×4096 cascades arranged in a concentric manner. Every cascade consists of a sparsely allocated set of pages, with each page spanning 128×128128\times128128×128 texels. Each cascade's frustum is twice the size of the previous cascade's. The size of the first cascade, specified in world-space units, thus determines the resolution and quality of the entire VSM. In our implementation, we chose to make our first cascade 2×22\times22×2 meters wide, with the last cascade covering a diameter of 65 km. The virtual resolution of cascades, their number, and the resolution of pages can vary.

A virtual page table (VPT) is used to map virtual addresses to physical addresses when we sample the shadow map. The VPT also contains metadata: page allocation status, visibility status, and a dirty flag. The allocation status flag marks pages that are backed by a physical page. The visibility status flag indicates whether the page is visible to the viewer in this frame. The dirty status flag indicates that the physical page contents are no longer valid and should be redrawn. We further define a physical page table (PPT) which provides the mapping of physical pages to virtual pages (the inverse of the VPT).

Sparse (or tiled) resources in graphics APIs initially seem like an obvious choice for VSMs. However, the API for sparse resources does not allow for an indirect GPU-driven approach. To know which VSM pages need to be backed by physical memory would require GPU readback. This adds unacceptable latency and leads to shadow pop-in. Our implementation opts for a manual allocation scheme that allows for execution of every part of the algorithm on the GPU and avoids this round trip latency.

Caching is a common and important optimization for shadow mapping in the semi-static scenes frequently found in real-time applications. We implement a per-page caching scheme for VSMs. After a page is drawn and sampled, it is not discarded. Instead, its contents are preserved, and the allocation is left untouched, continuing its lifetime into the next frame. By doing this, we minimize the number of required draws and allow for more efficient culling.

To support caching, individual cascade frustums are snapped to the page grid. Further, the light position is constrained so that, when modified, it slides along a plane parallel to the near-plane of the respective light matrix. This constraint is necessary for the depth stored in cached pages to remain valid even after translating the light matrix.

As the cascade frustum moves to follow the main camera, new pages, previously located on the edge just outside of the cascade frustum, might need to be drawn. In order to preserve previously cached pages, we utilize a sliding window, also called 2D wraparound addressing [AH05]. As new pages enter the frustum when it moves, old pages exit. With a sliding window, the newly entered pages are mapped to the location in the VPT previously occupied by old, exiting pages. This requires us to store a per-cascade offset of the respective light matrix position from the origin. Therefore, a translation function projecting from virtual page coordinates into wrapped coordinates is given by listing 1. The wrapped coordinates are then used to lookup VPT entries.

ivec3 virtual_page_coords_to_wrapped_coords(ivec3 page_coords, ivec2 cascade_offset) { // Make sure that the virtual page coordinates are in page table bounds to prevent erroneous wrapping if( any(lessThan(page_coords.xy, ivec2(0))) || any(greaterThan(page_coords.xy, ivec2(VSM_PAGE_TABLE_RESOLUTION - 1))) ) { return ivec3(-1, -1, page_coords.z); } const ivec2 offset_page_coords = page_coords.xy + cascade_offset.xy;

const ivec2 wrapped_page_coords = ivec2(mod(offset_page_coords.xy, vec2(VSM_PAGE_TABLE_RESOLUTION))); // Third coordinate specifies the VSM cascade level return ivec3(wrapped_page_coords, page_coords.z); }

Function used to convert from coordinates obtained by projecting by cascades light matrix into wrapped coordinates.

In dynamic scenes, it is sometimes necessary to invalidate cached pages. For example, changing the direction of a directional light will invalidate all its pages. A mechanism to invalidate cached pages overlapped by moving objects is also necessary.

We will now explain in further detail each step of our approach to implementing Virtual Shadow Maps. Figure 2 gives an overview of our implementation of VSMs.

The bookkeeping phase comprises a set of smaller tasks that prepare the data to draw the shadow map. This consists of five steps, which will be described in detail in this section. The execution flow diagram, along with all the resources used, can be seen in Figure 4.

The first step in bookkeeping is to free cached pages that have been invalidated by a change in the position of the light matrix or by the page intersecting a moving object. From the CPU, we receive a per-cascade input containing the number of pages the light matrix moved compared to the previous frame and a bitmask representing the set of pages invalidated by dynamic objects. We then simply free the appropriate entries in the VPT by resetting their allocation status to 0.

The code freeing invalidated pages is then given by listing 2.

// Cascade shift gives the offset in pages relative to the cascade position previous frame // Cascade offset is the offset used for the sliding window void free_wrapped_pages(ivec2 cascade_shift, ivec2 cascade_offset) { const ivec3 page_coords = ivec3(gl_LocalInvocationID.xyz);

const bool should_clear_wrap = (clear_offset.x > 0 && page_coords.x < cascade_shift.x) || (clear_offset.x < 0 && page_coords.x > VSM_PAGE_TABLE_RESOLUTION + (cascade_shift.x - 1)) || (clear_offset.y > 0 && page_coords.y < cascade_shift.y) || (clear_offset.y < 0 && page_coords.y > VSM_PAGE_TABLE_RESOLUTION + (cascade_shift.y - 1)); const bool should_clear_dynamic = extract_page_bit_from_mask(page_coords, bitmask); const ivec3 wrapped_page_coords = virtual_page_coords_to_wrapped_coords(page_coords, cascade_offset);

if(should_clear_wrap || should_clear_dynamic) { const uint page_entry = imageLoad(virtual_page_table, wrapped_page_coords).r; if(get_is_allocated(page_entry)) { imageStore(virtual_page_table, wrapped_page_coords, uvec4(0)); } } }

Listing 2: Function used to free invalidated pages. First, we determine if the virtual page needs to be freed from the data sent from CPU. If the page does need freeing, we translate into wrapped corrdinates and reset its state.

Figure 5: Overview of the depth analysis used to select a suitable cascade for each pixel.

Each screen pixel is assigned a shadow cascade index based on a heuristic. A heuristic is used because simp