mipmap_zorder

Save memory resources during mipmap generation by using z-order curve (Morton order, Lebesgue Curve)

The problem

Generating mipmaps of gamma corrected textures requires to "ungamma" the texel values, compute the resulting texel in the current mipmap level and reapply the gamma correction.

A simple solution is to convert the source texture to a destination texture containing only floating point data channels and resize its dimensions to power of two values. During this conversion the gamma correction is removed.

The mipmaps are now generated by subsequentially halving the resolution in both dimensions (2D texture) by merging neighbouring groups of two by two pixels.

When all mipmap levels are generated convert to the target format (which may need to reapply the gamma correction.)

The major drawback here is the memory usage: intermediate texture + destination texture (The source texture can be dropped when converted to the intermediate texture.)

Generating a mipmapped target would need this memory resources:

MemoryUsage = Width * Height * Channels * sizeof(float) // intermediate texture
  + Width * Height * Channels * (4.0/3.0);    // target texture including mipmaps
<=>
MemoryUsage = Width * Height * Channels * 16.0 / 3.0;  

For a target texture containing 4 8bit channels this means:

Width	Height	Memory usage (bytes)
1024	1024	22.369.622
2048	2048	89.478.486
4096	4096	357.913.942
8192	8192	1.431.655.766
16384	16384	5.726.623.062

The idea

By traversing the source texture using the space filling Z-order curve (Morton order, Lebesgue curve) the intermediate texture is not needed anymore. Instead a much smaller datastructure can be used which contains just intermediate results really needed when generating the texels of the mipmap.

The table above scales down by a factor of 1.0/4.0 and looks like this. (The size of the intermediate datastructure is neglectible.)

MemoryUsage = Width * Height * Channels * (4.0/3.0);    // target texture including mipmaps

Width	Height	Memory usage (bytes)
1024	1024	5.592.405
2048	2048	22.369.622
4096	4096	89.478.486
8192	8192	357.913.942
16384	16384	1.425.371.222