# Sparse Virtual Texture 

This tech is based on popular Megatexture technique developed for Rage by John Carmack, working at id software.

The key idea boils down to having a very large texture that is impractical to keep in memory, and only load and keep in memory pieces of it that are relevant to the current view.

There are 2 parts to this technique, offline and online.

## Offline

The original texture is mip-mapped, down to the size of a single tile, for the sake of this document let it be 128x128 pixels. Each mip level is then cut into tiles and stored on disk. A good intuition for this is to think of each tile as a separate pixel, representing non-color data.

## Online

This is achieved by pre-rendering the scene with a special shader that records UV and mip-level information, which we call `Usage`, this is then analysed to build a list of used tiles (mip level, x, y) and by counting occurrence of this tile in the `Usage` texture we get a much more useful data structure.

Based on the `Usage` data, we populate our `Physical` texture of pages, and based on what's currently in the `Physical` texture - we populate the `Reference` texture that stores information about the entire mip pyramid, and for each tile contains a pointer to the `Physical` texture, where representative tile can be found. 


## Considerations


### Filtering

Most papers suggest introducing a border into each tile of ~4 pixels. 
4 pixel border on a 128x128 pixel tile is going to take up 12.1% of space, which is quite a lot.
We can do filtering in software, that is - sample individual pixels and perform interpolation inside the shader.

### Speeding up WebGL read-back

From [Babylon](https://github.com/BabylonJS/Babylon.js/blob/90dbafed8de9de752cdc399604f9c7c51116d630/src/Engines/engine.ts#L1772)
```ts
public _readPixelsAsync(x: number, y: number, w: number, h: number, format: number, type: number, outputBuffer: ArrayBufferView) {
    if (this._webGLVersion < 2) {
        throw new Error("_readPixelsAsync only work on WebGL2+");
    }

    let gl = <WebGL2RenderingContext>(this._gl as any);
    const buf = gl.createBuffer();
    gl.bindBuffer(gl.PIXEL_PACK_BUFFER, buf);
    gl.bufferData(gl.PIXEL_PACK_BUFFER, outputBuffer.byteLength, gl.STREAM_READ);
    gl.readPixels(x, y, w, h, format, type, 0);
    gl.bindBuffer(gl.PIXEL_PACK_BUFFER, null);

    const sync = gl.fenceSync(gl.SYNC_GPU_COMMANDS_COMPLETE, 0);
    if (!sync) {
        return null;
    }

    gl.flush();

    return this._clientWaitAsync(sync, 0, 10).then(() => {
        gl.deleteSync(sync);

        gl.bindBuffer(gl.PIXEL_PACK_BUFFER, buf);
        gl.getBufferSubData(gl.PIXEL_PACK_BUFFER, 0, outputBuffer);
        gl.bindBuffer(gl.PIXEL_PACK_BUFFER, null);
        gl.deleteBuffer(buf);

        return outputBuffer;
    });
}
    
private _clientWaitAsync(sync: WebGLSync, flags = 0, intervalms = 10): Promise<void> {
    const gl = <WebGL2RenderingContext>(this._gl as any);
    return new Promise((resolve, reject) => {
        const check = () => {
            const res = gl.clientWaitSync(sync, flags, 0);
            if (res == gl.WAIT_FAILED) {
                reject();
                return;
            }
            if (res == gl.TIMEOUT_EXPIRED) {
                setTimeout(check, intervalms);
                return;
            }
            resolve();
        };

        check();
    });
}
```

more links:
https://forum.babylonjs.com/t/speeding-up-readpixels/12739


## References

* [Shadertoy: Anisotropic filtering in a shader](https://www.shadertoy.com/view/4lXfzn)
* ["Adaptive Virtual Texture Rendering in Far Cry 4" by Ka Chen, Ubisoft. 2015](https://ubm-twvideo01.s3.amazonaws.com/o1/vault/gdc2015/presentations/Chen_Ka_AdaptiveVirtualTexture.pdf)
* "id Tech 5 Challenges: From Texture Virtualization to Massive Parallelization" by J.M.P. van Waveren, id Software, SIGGRAPH 2009
* "Using Virtual Texturing to Handle Massive Texture Data" by J.M.P. van Waveren, id Software, 2010
* "Software Virtual Textures" by J.M.P. van Waveren, id Software, 2012
* "Advanced Virtual Texture Topics" by Matrin Mittring, Crytek GmbH, SIGGRAPH 2008
* "Atlas Shrugged: Device-agnostic Radiance Megatextures" by Mark Magro et al, University of Malta, VISIGRAPP 2020
* ["Sparse virtual textures" by Nathan Gauër, 2022](https://studiopixl.com/2022-04-27/sparse-virtual-textures)
* "Terrain in Battlefield 3: A modern, complete and scalable system" by Mattias Widmark, EA Digital Illusions (DICE), GDC 2012
* "Virtual Texturing in Software and Hardware" by Juraj Obert (AMD) et al, SIGGRAPH 2012
* "Virtual Texturing" by Albert Julian Mayer, 2010

## WebGL fails

WebGL doesn't seem to support mipmaps on integer textures

## Anisotropic filtering:

```glsl
// R is viewport resolution
// p is UV
vec4 textureAniso(sampler2D T, vec2 R, vec2 p) {
    mat2 J = inverse(mat2(dFdx(p),dFdy(p)));       // dFdxy: pixel footprint in texture space
    J = transpose(J)*J;                            // quadratic form
    float d = determinant(J), t = J[0][0]+J[1][1], // find ellipse: eigenvalues, max eigenvector
          D = sqrt(abs(t*t-4.*d)),                 // abs() fix a bug: in weird view angles 0 can be slightly negative
          V = (t-D)/2., v = (t+D)/2.,                     // eigenvalues. ( ATTENTION: not sorted )
          M = 1./sqrt(V), m = 1./sqrt(v), l =log2(m*R.y); // = 1./radii^2
          
    //if (M/m>16.) l = log2(M/16.*R.y);                     // optional
    
    vec2 A = M * normalize(vec2( -J[0][1] , J[0][0]-V )); // max eigenvector = main axis
    vec4 O = vec4(0);
    for (float i = -7.5; i<8.; i++)                       // sample x16 along main axis at LOD min-radius
        O += textureLod(T, p+(i/16.)*A, l);
    return O/16.;
}
```