It is no secret that a part of Nvidia's hardware rollout ritual is to dig up previously difficult-to-implement techniques and write up a demo, alongside a whitepaper, showcasing how they managed it with their latest architecture. They don't make a habit out of completely dropping the ball on the whitepaper. Alas, the one on clipmaps from February 2007 was one of them. "A clipmap can be defined as a partial representation of a mipmap pyramid which holds all information needed for texturing at every single frame.", begins the Nvidia whitepaper on the subject from early 2007.

A valid definition. It is, however, slippery without proper elaboration. Each level of a clipmap does not cover the same extent of the "source" level of the mipmap which it is virtualizing. The extent varies as the clipmap has the same number of texels across most of the levels of a conventional mipmap pyramid. Thus, you can't just take screen-space derivatives to compute a mip level and sample into it blindly, as the whitepaper lazily and partially outlines. This is, in fact, a key aspect of clipmaps and a key failing of the Nvidia whitepaper.

My preferred way of thinking about clipmaps is in line with Tanner et al. A clipmap is, for all intents and purposes, a virtual mipmap. Therefore, we shall first refresh ourselves on the merits of mipmaps and smoothly transition from there.

As you probably know, textures slapped across geometry come in a variety of sizes. Even the practical upper limit for non-virtual, fully resident textures is a staggering 16384x16384. These objects often end up projected to a very small area on the screen, invariably leading to aliasing as there may be thousands of texels competing for a single screen pixel. One could, ludicrously, filter this at runtime every single time... Or realize all of this can be precomputed at texture creation. Enter the mipmap.

A mipmap ("Multum In Parvo" means "much in little space") is a hierarchical structure representing a source texture (conventionally and historically, a "bitmap"). Each level is half the resolution of its predecessor, all the way down to 1x1. Any filter can be used to perform the downsampling, even a 2x2 box filter. A precomputed solution to avoiding aliasing. Mipmaps also have secondary interpretations which are equally valid. One is that they inherently serve as a texture level-of-detail solution which alleviates bandwidth issues by only accessing the optimal resolution of the texture wrt what can be seen given the camera distance to the surface.

This immediately leads us to the motivation behind clipmaps. Consider the opposite scenario. When the source texture is massive (eg. 65536x65536) and covers a large element in the game world which seldom (if ever) fits inside the view frustum (think terrain, planets, world-spanning acceleration structures), only aperture-sized parts of a mipmap are actually utilized and the available memory should be focused on those rather than being wasted on stuff that's offscreen at the moment. Thus, if one dynamically "clips" off the unneeded sections of the mipmap, you essentially convert an inherently static mipmap pyramid into a dynamic clip stack with a residual, potentially static mipmap pyramid stump, collectively known as a clipmap.

Before we can actually deal with transforming the logical mipmap coordinates into "physical" clip stack coordinates, we need to make sure that the input coordinates are not going to transform out of bounds, resulting in a repeating pattern. How do we compute the appropriate level? We will need to derive a function $l(?)$ which computes the appropriate level given the least amount of arguments.

The current stack center in normalized texture coordinates $\mathbf{C}$ will definitely be involved, the desired "logical" coordinates $\mathbf{P}$ and the ratio of the source image and the clip stack size $s$. For simplicity, we will derive this in one dimension as it works identically vertically.

To figure out this function, we take the difference $d_n = |\mathbf{P}_x - \mathbf{C}_x|$. Due to the whole wraparound business, we actually work with a maximum of $0.5$, so $d = \min(d_n, 1-d_n)$. At which $d$ do we need to jump to a higher level? Let's work out some concrete examples!

If our source image is four times as large as the clip stack, we have to move to level 1 when horizontal distance from the clip stack center $d$ reaches $0.125$ (remember, centered, so not $0.25$!), level 2 at $0.25$, level 3 at $0.5$, etc. If, on the other hand, $s=8$, then we'd have to hit $0.0625$ for level 1, $0.125$ for level 2 and so on. A pattern begins to emerge. As $d$ doubles, $l(d)$ changes logarithmically (base 2). Scale also appears to factor into it linearly, $l^s(d)$.

The transformation of coordinates is rather pedestrian. As we move from the virtual mipmap space to the actual clip stack space, we know there is a constant $1/2$ offset. We also know that due to varying extents across levels, the most detailed level covers the least amount of area of the original texture.

At level 0, the extent of the clip stack level in normalized coordinates ends at $1/s$ (mipmap logical normalized coordinates). This is obviously $1$ in clip stack space for that particular level. Thus, we scale the coordinates by $s$. At each successive level, the extent doubles as the clip stack size remains constant, meaning we also divide by $2^i$ where $i$ is the previously chosen clip stack level. And finally, we add the center offset of $1/2$, producing the final transform:

That's all there is to it. Falling back onto the residual mipmap pyramid is trivially predicated by the computed level: if it exceeds the clip stack depth, sample it. Happy coding.