Mip Map Folding

2019-01-10

by Paul Nasdalack

mip map folding

Introduction

A while ago Julian, a good friend of mine, contacted me about a problem he faced while following Alan Zucconi's tutorial about the Glitter Reflections in Journey. He just finished the main Glitter Effect and it looked great! Until you zoomed out or showed dunes in the distance. Most of the Glitter was lost and the few Glitter Sparkles that remained showed obvious and repetitive patterns.

Anyone who has worked with large scale terrains should be familiar with the latter. Regardless of how much you try to hide your texture tiling, at a distance it will always become apparent. Our brains are just too damn optimized for pattern recognition.

The first problem should not come at a surprise to anyone who had a look into mip maps at any point in their life. For those who did leave the little Mip Map checkbox in most engines alone until now, I've written a short introduction to what they are and why they are actually useful in most cases.

What is Mip Mapping

When rendering textures, there are two important pixel resolutions at work. One of them is your screen size. The higher-res the screen, the more detail you will be able to display to the viewer. The second one is the texture resolution itself. A 4K monitor won't do you much good in terms of displaying textures, when you're playing a game from 2001.

a low res texture up close

Even if you manage to crank the display resolution up to render at native 4K, it won't do you no good, as the detail in the textures simply isn't there. The textures are to low res and as long as you don't go through the hassle of installing a questionable High Res Texture Mod, no 4k or 8k monitor is going to change that.

Another situation where this happens even with regular screens is if you go up real close to a model in a 3D game. At some point you've reached the limits of the texture resolution and you're just staring at a blob of mushy or pixelated colors.

This problem is called oversampling. You are taking too many samples (with your screen) from a source with not enough resolution (the texture).

Sadly mip mapping does not solve the problem of oversampling. Unless you're doing some weird generative functions, there are very few ways to create convincible detail where there is none.

Mip Mapping actually solves the opposite problem: Undersampling.

Undersampling happens when your screen resolution is not high enough to properly display all the detail contained in a texture. This is mainly a problem for 3D games, where textures can be far away. Like Julians sand dunes in the Glitter Shader. The texture is displayed so small that it's impossible to display every pixel on screen. While this is mostly fine for still frames, the problem becomes obvious as soon as we move the camera the tiniest bit.

a texture without mipmap

Every screen pixel can be assigned only one texture pixel and if the pixel density in the texture is too high, we simply skip a few pixels before rendering the next one. As soon as we move the camera, though some pixels, we previously skipped now show up and others suddenly disappear.

Instead of a continuously moving texture we now get a mess of noisy pixels and potential 'firefly' effects (bright pixels suddenly showing up and disappearing). While this already works better for the Glitter effect, most of the times we do not want to show such noisy textures to the player.

So this time we are sampling with a low res sampling device (our screen) from a high res source (a distant texture).

Upping the screen resolution would solve the problem and there are techniques like MSAA that simulate exactly that, mitigating some of the problem. But we can't require the player to turn on MSAA or buy a new 4k monitor whenever they are looking at a building in the distance.

The alternative is lowering the resolution of the texture. And mip mapping does exactly that. Instead of displaying the full res texture, we display a downscaled version to the viewer. Of course this is only done for textures that are far away from the camera.

In order to be able to show the full res textures up close, we need to store multiple texture variants on the GPU. This is called the mip chain

the mip map chain

The chain consists of the original texture and all its divided by two variants. So a 1024px texture would store the following variants in its mip chain:

  • 1024px (original)
  • 512px (mip level 1)
  • 256px (mip level 2)
  • 128px (mip level 3)
  • 64px (mip level 4)
  • 32px (mip level 5)
  • 16px (mip level 6)
  • 8px (mip level 8)
  • 4px (mip level 9)
  • 2px (mip level 10)
  • 1px (mip level 11)

This is part of the reason why power of two texture sizes are so common. The cool thing is that mip maps are evaluated on a per pixel level, meaning a huge mesh of let's say a star destroyer flying overhead can display different mip maps at different distances to the camera.

a texture with mipmap

Mip Mapping implementation

The problem in Julians Glitter case was that the noisy normal map lost its noisiness in the distance, because the low res mip levels blurred the noise to one uniform shade of gray.

the mip map chain of the normal map from Alan Zucconis Tutorial

So while disabling mip mapping kind of solved the Glitter fading in the distance problem.

But without mip maps the undersampling problem became apparent even with a noisy glitter shader. Glitter is not totally random and one would expect when moving the head ever so slightly to the left wouldn't have a huge effect on the glitter. Sadly thanks to undersampling we were getting a completely different glitter pattern.

We also had the tiling pattern problem, which got even worse now that the mip maps weren't blurring all the detail out of existence anymore.

This is when an idea popped to our heads. What if instead of halfing the texture resolution with each mip map step, we would instead double the texture scale, effectively keeping the same distance but blown up to bigger size the further away it is from the camera.

Usually GPUs do the mip mapping automatically with the tex2D call. There is a variant without mip mapping called tex2Dlod, which we could use to avoid the gpu using the wrong mip level from our up-scaled texture.

Now we just need to determine the mip level by hand. Luckily the mip level function is documented in the OpenGL Specification document.

float
mip_map_level(in vec2 texture_coordinate)
{
  // The OpenGL Graphics System: A Specification 4.2
  // - chapter 3.9.11, equation 3.21

  vec2 dx_vtc    = dFdx(texture_coordinate);
  vec2 dy_vtc    = dFdy(texture_coordinate);
  float delta_max_sqr = max(dot(dx_vtc, dx_vtc), dot(dy_vtc, dy_vtc));

  //return max(0.0, 0.5 * log2(delta_max_sqr) - 1.0); // == log2(sqrt(delta_max_sqr));
  return 0.5 * log2(delta_max_sqr); // == log2(sqrt(delta_max_sqr));
}

Converted to hlsl/cg it looks like this:

// Texture coordinate has to be multiplied with the texture resolution
float mipmapLevel(float2 textureCoordinate)
{
  // Original source:
  // The OpenGL Graphics System: A Specification 4.2
  // - chapter 3.9.11, equation 3.21

  float2 dx = ddx(textureCoordinate);
  float2 dy = ddy(textureCoordinate);
  float1 deltaMaxSqr = max(dot(dx, dx), dot(dy, dy));

  return 0.5f * log2(deltaMaxSqr);
}

If you are wondering what the ddx/ddy and dFdx/dFdy functions are doing, here is a pretty good writeup on what they do. But essentially they are measuring how fast a value is changing from one pixel to another. In this case we are using them to check how fast our texture pixels are changing compared to the screen resolution.

Texture Folding

Instead of using the mip level to pick a lower scale texture we simpy divide our texture coordinate by 2 to the power of the mip level to keep a constant texel density.

Sadly interpolating this scaling factor continuously over the distance from the camera leads to very weird warping artifacts.

So instead we sample the texture at the two bordering whole number mip levels using ceil() and floor() and blend them together with a lerp. The lerp factor is simply the fractional part of our mip level. This way we get nicely blended textures.

For convenience we've written a function to sample a Texture that's folding on itself called tex2Dfold.

// Texture coordinate has to be multiplied with the texture resolution
float mipmapLevel(float2 textureCoordinate)
{
  // Original source:
  // The OpenGL Graphics System: A Specification 4.2
  // - chapter 3.9.11, equation 3.21
  float2 dx = ddx(textureCoordinate);
  float2 dy = ddy(textureCoordinate);
  float1 deltaMaxSqr = max(dot(dx, dx), dot(dy, dy));

  return 0.5f * log2(deltaMaxSqr);
}
// function written by littleBugHunter 2020-01-10
// uvParams.xy are the uv coordinates and uvParams.zw contain the texture size in pixels
float4 tex2Dfold(sampler2D s, float4 uvParams)
{
  float mipGrad = mipmapLevel(uvParams.xy * uvParams.zw);
  float mip = floor(mipGrad);
  float mipLerp = frac(mipGrad);
  fixed4 col1 = tex2Dlod(s, float4(uvParams.xy / (pow(2,mip)  ), 0, 0));
  fixed4 col2 = tex2Dlod(s, float4(uvParams.xy / (pow(2,mip) * 2), 0, 0));
  return lerp(col1, col2, mipLerp);
}

The function can be used like this in a Unity Shader:

//_MainTex_TexelSize.zw contains the texture size of _MainTex. 
tex2Dfold(_MainTex, float4(i.uv, _MainTex_TexelSize.zw);

The big benefit of doing this is that not only you are keeping your pixel density pretty constant, but you are also avoid patterns at far distances, as the texture is always scaled up to fit the distance.

Another benefit is that it also works for the oversampling problem. When getting up close, the texture will get scaled down and avoid being blurred out.

Of course this technique doesn't work well for realistic textures, as they usually have very distinct features, which give away their scale. But for more abstract effects like the glitter or even detail maps, that are layered on top of regular textures, this proves to be a great alternative to regular mip mapping. It certainly worked well for Julians Glitter Shader:

Credits

I'd like to thank Alan Zucconi for all of his excellent tutorials (go check them out on his blog, if you have the time!)

This Technique was developed in collaboration with Julian Oberbeck, a good friend of mine, who is an excellent Tech Artist. If you are looking for someone with great knowledge about anything from shader programming to rigging or just need someone to solve your pipeline problems, write him a mail!

The Grass Texture was taken from Textures.com