Archive for July, 2011

On Error

Tuesday, July 26th, 2011

Doing my best impersonation of someone who blogs with more regularity than I really do…

I glossed over (flubbed?) the error analysis a little in my last post, and should really do a better job. I’ll look at CLEAN/LEAN mapping, but the analysis methods are useful in lots of situations where you compute something from a texture.

To keep things simple, I’ll use a simplified form of the (C)LEAN variance computation:

[latex]V = M – B^2[/latex]

The error in this expression is especially important in (C)LEAN mapping since it determines the maximum specular power you can use, and how shiny your objects can be. For specular power s, 1/s has to be bigger than the maximum error in V, or you’ll get some ugly artifacts.

M and B come from a texture, so have inherent error of [latex]\epsilon_M[/latex] and [latex]\epsilon_B[/latex] due to the texture precision. The error in each will be 1/2 of the texel precision. For example, with texel values from 0 to 255, a raw texel of 2 could represent a true value anywhere from 1.5 to 2.5, all of which are within .5 of the texel value.

In general, we’ll scale and bias to use as much of the texture range as we can. The final error for an 8-bit texture then is range/512. For data that ranges from 0 to 1, the range is 1 and the representation error is 1/512; while for data that ranges from -1 to 1, the range is 2, so the representation error is 2/512 = 1/256.

The error in each parameter propagates into the final result scaled by the partial derivative. [latex]\partial{V}/\partial{M}[/latex] is 1, so error due to M is simple:


The error due to B is a little more complicated, since [latex]\partial{V}/\partial{B}[/latex] is 2 B. We’re interested in the magnitude of the error (since we don’t even know if [latex]\epsilon_B[/latex] was positive or negative to start with), and mostly interested in its largest possible value. That gives

[latex]\epsilon_{VB}=2\ \textrm{max}(\left|B\right|)\ \epsilon_B[/latex]

Generally, you’re interested in whichever of these errors is biggest. The actual error is dependent on the maximum value of B, and how big the texel precision ends up being after whatever scale is used to map M and B into the texture range. So, for a couple of options:

B range -1 to 1 -2 to 2 -1/2 to 1/2
Max Bump Slope 45° 63.4° 26.6°
[latex background=”#eeffee”]\epsilon_B[/latex] 1/256 1/128 1/512
[latex background=”#eeffee”]\epsilon_{VB}[/latex] 2*1/256
= 1/128
= 1/32
= 1/512
M range 0 to 1 0 to 4 0 to 1/4
[latex background=”#eeeeff”]\epsilon_{VM}=\epsilon_M[/latex] 1/512 1/128 1/2048
[latex background=”#ffeeee”]\epsilon_V[/latex] 1/128 1/32 1/512
[latex background=”#ffeeee”]s_{max}[/latex] 128 32 512

We can make this all a little simpler if we recognize that, at least with the simple range-mapping scheme used here, [latex]\epsilon_B[/latex] and [latex]\epsilon_M[/latex] are also dependent on [latex]B_{max}[/latex].

\epsilon_{VM} &= B_{max}^2/512\\
\epsilon_{VB} &= 4 B_{max}^2/512 = B_{max}^2/128\\
s_{max} &= 128/B_{max}^2

So, this says the error changes with the square of the max normal-map slope, and that the precision of B is always the limiting factor. In fact, if there were an appropriate texture format, M could be stored with two fewer bits than B. For 16-bit textures, rather than 2-9 for the texture precision, you’ve got 2-17, giving a maximum safe specular power of 215=32768 for bumps clamped to a slope of 1. There’s no need for the slope limit to be a power of 2, so you could fit it directly to the data, though it’s often better to be able to communicate a firm rule of thumb to your artists (spec powers less than x) rather than some complex relationship (steeper normal maps can’t be as shiny according to some fancy formula — yeah, that’ll go over well).

Shiny and CLEAN

Sunday, July 24th, 2011

Inspired by Stephen Hill’s post over on his self shadow blog, I wanted to put down some thoughts about LEAN mapping and CLEAN mapping for specular highlight filtering.

About a year and a half ago, Dan Baker and I published LEAN mapping, a method we developed for filtering normal maps to avoid aliasing for the water in Civilization V. A shiny bumpy surface should look less shiny once it is far enough away that you can’t see the individual bumps. At the Game Developer’s Conference this year, Dan presented a new lighter weight version we’re calling CLEAN mapping (Compact LEAN mapping, where LEAN mapping was Linear Efficient Antialiased Normal Mapping).

What is this LEAN mapping?

You can read the paper for the nitty-gritty details, but the gist of LEAN mapping is to models the bumps with off-center 2D Gaussian distributions of normal vectors in the surface tangent space. A 2D Gaussian has a center (mean) and elliptical shape (described by a 2×2 symmetric covariance matrix). You can stick the mean into a texture, and regular texture filtering does the right thing. The same is not true for the covariance, but you can compute the covariance from the raw second moment, and that does do the right thing when filtered. LEAN mapping needs to store at least five pieces of texture data, scaled to fit into the range of a texel. Two for the mean bump direction

B_x = N_x/N_z\\B_y = N_y/N_z

and three for the raw second moments

M_{xx} = B_x B_x\\
M_{xy} = B_x B_y\\
M_{yy} = B_y B_y

At the top level of the MIP chain, these are initialized directly from the normal data. You apply your favorite MIP generation method for the rest of the MIP chain, and the difference between the way the B and M terms filter is what captures the conversion of bump directions into highlight shape. Given those five values in a couple of textures, we can reconstruct the main bump direction and shape of the distribution (= size and shape of the specular highlight). It’s simple, amazingly stable (we used specular powers over 13,000 with 16-bit textures), and has the cool bonus of turning grooved bumps into an anisotropic highlight shape, which happens in real life too.

To use it, you look up M and B from the texture and use them to reconstruct a covariance matrix for the distribution of normals. A few levels down, [latex]M_{xx}[/latex] won’t equal [latex]B_x B_x[/latex] anymore, and it’s this difference that matters.

Cov = \left(\begin{matrix}
M_{xx} & M_{xy}\\
M_{xy} & M_{yy}\end{matrix}\right) –
B_x B_x & B_x B_y\\
B_x B_y & B_y B_y\end{matrix}\right)

The determinant of this matrix, [latex]\left|Cov\right|[/latex], might come out negative due to numerical error (more on that later). If it is, I just clamp the matrix to 0. I like to add the specular power into the covariance at render-time, though you could add it into [latex]M_{xx}[/latex] and [latex]M_{yy}[/latex] when creating the texture. Then the specular term is computed using a Beckmann distribution (basically a projected Gaussian distribution). Given Blinn-Phong specular power s, and normalized tangent-space light and view vectors Lt and Vt:

[latex]Cov\ +=
\left(\begin{matrix}1/s & 0\\
0 & 1/s\end{matrix}\right)\\
Ht = \textrm{normalize}(Lt + Vt)\\
H = (Ht_x, Ht_y)/Ht_z – (B_x, B_y)\\
e = (H_x H_x Cov_{yy} – 2 H_x H_y Cov_{xy} + H_y H_y Cov_{xx})/\left|Cov\right|\\
spec = exp(-\frac{1}{2}e)/\sqrt{\left|Cov\right|}

LEAN thoughts

Any method has its drawbacks, and for basic LEAN mapping there are two. The first is the number of texture elements needed. Five values need two textures, which is often too many. If we give up the anisotropic highlight shape, we get CLEAN mapping. Now we just compute three texture elements at the top MIP level:

B_x = N_x/N_z\\B_y = N_y/N_z\\
M = B_x\ B_x + B_y\ B_y

When you look these up with standard texture filtering, the difference between the way they’re filtered gives you a single variance rather than the 2×2 covariance matrix. You don’t get the highlight stretching from grooved bumps, but you do get the bump antialiasing that avoids bump sparkling and shimmering.

The second, thougher, problem is the numerical error alluded to above. The variance SHOULD always be positive, or covariance matrix SHOULD always end up with a positive determinant, but especially at the finest MIP levels, we’re subtracting pairs of very similar values. The specular term adds some padding to that, but if a 1-bit error in the normal is bigger than 1/s, there will be artifacts. In Civ 5, we used 16 bit texture, which gives a good amount of headroom. If you do it using 8-bit textures, you’ll have to limit the steepness of your bumps and/or maximum specular power to avoid problems. For example, if [latex]B_x[/latex] and [latex]B_y[/latex] are limited to -1 to 1, one bit in an 8-bit texture is 1/128, which limits the effective specular power to under 128. Compressed textures are out of the picture as the errors are just too big. So really, direct LEAN mapping is most useful if you have and can afford 16-bit textures.

16-bit textures are feasible for a PC game like Civ V, but for consoles, methods like directly storing the variance in a texture as suggested in Stephen Hill’s post are necessary avoid the numerical errors. Variance doesn’t filter linearly like the LEAN moments do, so you’ll see some texture filtering issues, but they’re better than the precision errors. Of course, you’ll need to build all of the MIP levels from a high-precision or floating point LEAN map source, or filter each level directly down from the base texture (so don’t just let the automatic MIP generation do it). Then, at least, the raw variances stored in the texture levels will be right, and the errors will be limited to the hardware texture filtering.

Edit: There are some problems with the error analysis in this post. See this follow up for a full (and better) analysis.