Page Tables for Sparse Virtual Textures

A surface that is 64K by 64K texels at 4 bytes per texel is 16 GiB. Most of it is never seen: terrain tiles at one level of detail, building interiors behind doors, decal sheets where only a fraction is used. Mip chains help with distance but not with extent, since the chain still stores every level of every region. Virtual texturing decouples the address space of the texture from the memory that holds it, using a second level of indirection that functions like a page table. The sampler still computes one coordinate; that coordinate is translated to a page, and only the pages that matter occupy memory.

Two coordinate spaces and one indirection

The virtual texture has a logical resolution, the address space, which can be far larger than any allocation. It is divided into pages, conventionally 128 or 256 texels square. Physical memory is divided into the same page size and holds a fixed number of slots, the cache. A page table maps each virtual page to a slot or to a sentinel meaning “not resident”.

Sampling a virtual texture therefore costs an extra dependent fetch. From the virtual coordinate, the sampler computes a virtual page index and the offset within the page, reads the page table entry, and only then computes the physical address of the texel. That dependency chain is longer than a normal texture fetch, and it happens per sample, so the page table entry itself is cached in a small translation cache. Hardware exposes this pattern directly: sparse or partially resident textures let the application bind a page table as an array texture and treat the indirection as an ordinary indexed read, while software virtual texturing does the same with a manual translation in the shader.

The physical layout is chosen so that a page’s texels occupy a contiguous or at least tile-local region, which keeps the indirection cost from being multiplied by the cache misses inside the page. Page size is the main tuning parameter. A small page wastes less space on partially used regions and reduces the cost of a miss; a large page amortizes the table lookup and gives better locality within a page. A 128×128 page at 4 bytes per texel is 64 KiB, small enough to bound the waste of a partially used page and large enough that a page’s texels stay within a small number of cache lines at the tiled layout the storage uses.

Mip levels complicate the table

A single-level page table would give correct addressing but no filtering across distances. Virtual texturing needs mip levels, and it needs them per page, which means the table’s geometry changes. Each level halves the page count in each dimension, so level $n$ has one quarter the pages of level $n-1$. The usual arrangement is a single table storing entries for all levels, addressed by a tuple of (level, page x, page y), and a sampler that selects the level before reading the table.

The alternative is a chain of tables, one per level, with the level chosen first. Both cost one dependent fetch; the single-table version needs an index computation that accounts for the level’s reduced dimensions, which is a shift and an add rather than a multiply. Nearly all practical implementations pack the levels into one table because the reduction is geometric and the offsets are computable with clamps.

There is a subtler consequence: a page at level $n$ corresponds to exactly four pages at level $n-1$, and consistency between them is not automatic. If level $n$‘s page is resident and populated while three of the four contributing level $n-1$ pages have changed, the parent is stale. Updating the parent requires reduction over its children, which is the box filter described in mip chain construction but applied per page with the children’s residency as an input. Implementations either rebuild parents when a child is evicted or updated, or store the parent only when all four children are resident and fall back to sampling the children when they are not.

Sampling a page that is not there

A virtual texture must return something for a page whose entry is a sentinel. Blocking is not an option: a shader cannot wait, and a stall on a page fault would be hundreds of cycles of nothing for one fragment. Implementations choose a substitution instead, and the choice determines the artifact.

The common substitution is to sample the coarsest resident ancestor. If level $n$‘s page is missing, the sampler reads whichever higher level is present at that location, which gives a blurred but correctly coloured result. That requires the table lookup to walk up the chain, adding dependent fetches proportional to the number of missing levels, so implementations bound the walk or store in each entry a pointer to the nearest resident ancestor, precomputed when pages are admitted and evicted.

A cheaper substitution is a fixed fallback colour, which produces visible flat patches that pop when the page arrives. A middle option is to clamp the level of detail so that the sampler never requests a page that is not resident, which needs the residency knowledge in the table and biases the result toward blur in exactly the region where detail was requested. The walk-up-ancestor approach is preferred because it degrades continuously and the missing page is usually a fine level whose parent is a good approximation.

Anisotropic filtering interacts badly with all of this. The anisotropic kernel takes up to sixteen taps along an axis, and if any one of them lands in a non-resident page the whole sample falls back. A footprint that crosses page boundaries therefore returns a poorer result than its centre suggests, and the boundary is visible along page edges, especially at grazing angles where the footprint is long. Some implementations clamp the tap count near page boundaries or use the fallback only for the taps that miss, which requires per-tap branching in software and is not something fixed-function hardware offers.

Feedback decides what to load

The residency set is not known in advance. It depends on the camera, the visible surfaces, and how much screen area each covers. The standard mechanism is a feedback pass: render the scene with the sampler writing, per pixel, the virtual page and level it wanted, into a small buffer. The buffer is reduced and the set of requested pages is compared against the resident set; missing pages are scheduled for loading, and pages not requested recently become eviction candidates.

The buffer is small, one page-identifier per pixel at reduced resolution, and the pages requested in one frame are typically far fewer than the pixels shaded, because neighbouring pixels request the same pages. Reducing the buffer to a set of identifiers is a deduplication problem, and the practical approach is a per-page age counter rather than a full set, because the number of pages that could fit is bounded and the cache does not need an exact answer.

Two policies matter. Admission is bounded by the load budget: a fixed number of pages per frame, or a fixed bandwidth allowance, since the pages come from disk or from a decompression job. Eviction is bounded by the cache size and should prefer pages whose last request is oldest, with hysteresis so that a page oscillating at the edge of visibility does not thrash. Without hysteresis, a camera panning slowly across a boundary can evict and reload the same page every frame, and the load budget is consumed by pages that were about to be requested again.

The feedback pass also determines the level of detail at which pages are loaded. A page’s level is chosen from the screen-space footprint, so the same virtual region may be requested at level 3 in one frame and level 5 in the next as the camera moves away. Loading level 5 duplicates content that level 3 already holds, so implementations load the requested level and rely on the ancestor walk for the coarser requests, or load a chain segment so the transition is covered.

What the indirection costs and when it pays

The extra fetch is the primary cost. Each sample now requires a table read, which on a cache hit is a few cycles and on a miss is a full memory round trip. Because the table read precedes the data read, the two misses serialize, and the effective latency is roughly the sum rather than the maximum. Keeping the working set of table entries small is therefore as important as keeping the texel working set small, which is why pages are large: fewer pages means fewer table entries for the same texel coverage.

The bandwidth saving is the reason the technique exists. A scene whose visible texture footprint is a few hundred megabytes can run within a texture budget an order of magnitude smaller, at the cost of loading pages on demand and accepting a brief interval of low-resolution fallback while a page arrives. The saving is a ratio, not an absolute, and it scales with how sparse the address space is. A texture that is densely used at every level gains nothing and pays the indirection.

There is also a quality argument. Because residency is explicit, the implementation knows which levels are available and can choose a filtering strategy per page. It can keep a page’s whole chain resident for high-quality anisotropic filtering where it matters and accept coarser filtering elsewhere, which is a decision an ordinary texture cannot express because its chain is all-or-nothing.

The main structural limitation is that the address space is fixed at authoring time. Repacking a virtual texture to change page size invalidates every table entry, so page size and level count are settled once, and an asset that needs a different granularity needs a different virtual texture. That constraint, plus the feedback machinery and the load budget, is what separates virtual texturing from swizzled texel layouts: the latter changes where a texel lives, while the former changes whether it lives in memory at all.