Category: Graphics Tricks (Page 2 of 2)

This one is all about MIP mapping. If that’s greek to you, go find another window and look it up. This time, how big is that MIP chain? Turns out there are closed form equations for a lot of the common cases.

Each level of a MIP chain is ¹/₄ the size of the next level up. So the first step is remembering how to find a closed form equation for an infinite sum. In terms of the original size, the rest MIP chain is about this fraction of the base level:

scale = ¹/₄ + ¹/₄² + ¹/₄³ + … = ¹/₄*(1 + ¹/₄ + ¹/₄² + …)
scale = ¹/₄*(1 + scale)
scale = ¹/₃

So, the rest of the MIP chain is about ¹/₃ the original, or the whole thing is about ⁴/₃ the original. Seems I remember learning that in grade school (well maybe not grade school, but a while ago). But what’s with the “about”? Well, this infinite sum overcounts by some fractional pixels after the last level. How many? All of the pseudo-MIP levels below the last level, or ¹/₃ of the size of the last level. Assuming a nice square texture where the last level is 1 pixel, it over counts by ¹/₃ pixel. In general, it’s

size = base*⁴/₃ – last*¹/₃

or if you want something you can use integer math for

size = (4*base – last)/3

For example, for a 1024 x 1024 texture, it’s

size = (4*1024*1024 – 1)/3 = 4,194,303/3 = 1,398,101

All integers. I think that’s pretty cool. You’re welcome to do the sum by hand to be sure:

size = 1024*1024 + 512*512 + 256*256 + 128*128 + 64*64 + 32*32 + 16*16 + 8*8 + 4*4 + 2*2 + 1*1 = 1,398,101

But it gets even more fun. What if you pack all the levels of an X x Y MIP texture into a contiguous block of memory (How big? See the size equation). Where does level N start? Well, if you pack smallest level first, it’s just the size equation for level N-1. But if you pack base level first, it’s the size equation from the base through level N-1

Start(N) = (4*base – last)/3

Or avoiding potential problems for the very first level, you can rewrite it in terms of the size of the base level and the size of level N:

Start(N) = (base − next)*4/3

For that 1024 x 1024 texture, this is where it says the levels start

Start(0) = (1024*1024 – 1024*1024)*4/3 = 0
Start(1) = (1024*1024 – 512*512)*4/3 = 1,048,576 (= 1024*1024)
Start(2) = (1024*1024 – 256*256)*4/3 = 1,310,720 (= 1024*1024 + 512*512)
Start(3) = (1024*1024 – 128*128)*4/3 = 1,376,256 (= 1024*1024 + 512*512 + 256*256)

Just throw in a multiplier to handle different size texels, or cube faces if packed together.

A few caveats though. First, it works great for non-square textures or non-power of two textures if you stop when you hit the last full pixel. So, if your 1024×256 texture stops at 4×1, all is good, but not if you toss in an extra 2×1 level, since the equations think it should be a 2 x ¹/₂ level. Nobody likes half pixels. Also, textures formats like DXT that round up to 4×4 blocks work only as long as you stick to levels that don’t actually need any padding (powers of 2 down to 4×4 are OK, but 14×18 gets padded to 16×20 with those troublesome extra pixels)

Marc

I’ve seen code floating around that computes a normal map from a height map by estimating tangent vectors and doing a cross product. That includes a bit of unnecessary extra math, so here’s a better way to compute the same thing.

First, let’s write the height field as a function of x & y (ok, it’s a texture, so call them u and v if it makes you feel better). So a height field is basically a texture that defines

z = h(x,y)

The tangent-based code already estimated the partial derivatives of h(x,y) with respect to x and y. Let’s call those h_x and h_y. There are several ways to do this: forward differences

h_x = h(x+1) – h(x)

central differences:

h_x = (h(x+1) – h(x-1)) / 2

Sobel filter (no, I’m not going to write that one out), or other derivative of a filter.

The trick comes in rewriting this thing as an implicit function of x,y,z that’s 0 on the surface, negative under the surface and positive outside the surface. That’s actually pretty easy:

f(x,y,z) = z – h(x,y)

So the neat thing is that the normal to an implicit surface like this is just the gradient of the implicit function:

N = (f_x, f_y, f_z) = (-h_x, -h_y, 1)

That’s it. Much friendlier than cross( (1,0,h_x), (0,1,h_y) ). You could actually get exactly the same result by expanding out the cross product, but I think it’s much cooler (and more applicable in other situations) to know about the normal to an implicit function trick.

Marc

While on sabbatical at Firaxis games, I started sending out periodic “graphics tricks”, with useful stuff that isn’t often covered in a graphics class. I’m going to start putting some of them up here. Definitely for the hardcore programmer, but if you’re programming for games, what other kind is there? The first one should be up shortly…