flipcode - Mip-Mapping (Including Bi-Directional)

Mip-Mapping (Including Bi-Directional)
by (13 January 1999)

Introduction

I have been playing around a bit with mipmapping in Focus recently, and now it seems to be working quite nice. Because I encountered several problems, I think it's good to write some of my experiences down to ease the life of other coders.

The Theory

There are two types of mipmapping: The first I will call ordinary mipmapping, as used by Quake and most 3D accelerators. For this approach you calculate a scaled down version of the original texture, half the width, half the height. This scaled down version should of course be calculated by a good graphics program, or you should write your own near-perfect scaling tool. The scaled down version of the texture is used when the texels that you fetch from the texture are smaller than a single pixel on screen. You never draw anything smaller than a pixel of course, so effectively you are stepping through your textures with steps greater than 1. In the scaled down version, steps between 1 and 2 become steps between 0.5 and 1, so you are not skipping texels anymore. This prevents details on the texture from flashing, so the image quality and stability goes up. Of course, once the mipmap is too small again, you need another mipmap, and so on. The total memory needed for a full set of mipmaps is 1.333 times the size of the original texture:

1: The original texture (e.g., 16x16, 1)
2: The first mipmap (e.g., 8x8, 1/4th)
3: The second mipmap (e.g., 4x4, 1/16th)
4: The third mipmap (e.g., 2x2, 1/256th)
5: The final mipmap, a single pixel.

So you get: 1+1/4+1/16+1/256 and so on, and this becomes 1 1/3 in the end.

The other approach is 'bi-directional mipmapping': In this case you do not just scale the texture in both directions at the same time, but you also determine a mipmap for a stepsize in the U-direction (horizontally over the texture) that is between 1 and 2, and one for the V direction. So, you get the original texture, a mipmap scaled in the U direction, and a mipmap scaled in the V direction, and a mipmap scaled in both directions. Theoretically, this should look even better than standard mipmapping, since you do not have to use a full scaled down version of the texture if it's just too small in the U direction on screen. The mipmaps look like this:

 _______________________
|            |     |  | |
| original   |     |  | |
| texture    |     |  | |
|            |     |  | |
|____________|_____|__|_|   V
| scaled in  |     |  | |
| V direction|     |  | |   |
|------------|-----|--|-|   |
|____________|_____|__|_|   v
|____________|_____|__|_|

                    U ====>

As you can see, in the end there's again a single pixel for the last mipmap. The total amount of memory needed for this approach is 4 times the amount needed for the original texture.

Mipmapping in Practice

Implementing this is harder than it seems. The problem is not calculating the mipmaps, it's determining wich one to use. Imagine you are plotting pixels, using a delta-U and a delta-V. Coders will know what I mean. Now you could simply use the size of delta-U and delta-V to determine wich mipmap to use, but that won't work. If you are looking at a texture straight on, and it isn't tilted, delta-U will be a positive value, and delta-V will be zero. If on the other hand the texture is tilted 90 degrees, delta-U is zero, and delta-V is a positive value.

So you have to take into account a bit more. How about the delta-U and delta-V that you use when you move to the next line? If you use both horizontal and vertical delta's, you can indeed determine the size of a texel on-screen this way: It's something like:

sqrt (dUhor^2 + dUver^2) * sqrt (dVhor^2 + dVver^2)

This might be fine for the ordinary mipmapping described above, but how do you extract the U and V portions for this? At this time I decided to drop two ideas: The bi-directional mipmapping, and the mipmapping per scanline. Bi-directional mipmapping was dropped for three reasons:

Four times the amount of memory is quite a lot.

The U and V delta's for moving down the screen are hard to calculate in Focus, since I maintain only delta-U and delta-V along the edges of polygons, but edges are not neccessarely vertical.

Mipmap flashing completely wasted the results: You have to decide where to start using the next mipmap. Since the calculations are already complex, this starts to get a bit unpredictable, causing spans to switch between two mipmaps rapidly.

Mipmapping per scanline was mainly dropped because of the last note mentioned above: Flashing. You can manage flashing for entire polygons, but not for scanlines.

Mipmapping The Entire Polygon

So how do we mipmap an entire polygon? There are a few possibilities; you could simply 'do something' with the distance of the polygon, or you could go for a more precise approach: If you calculate the area of the polygon in screen coordinates, and the area of the polygon in texture space, you have two exact values that you can compare. The area of a polygon can be determined using a simple formula (from Graphics Gems III):

area = SUM (i=0, n-1) x[i] * y[i+1] - y[i] * x[i+1]

where 'n' is the number of vertices in the polygon, and x and y are arrays containing the screen coordinates of the vertices.

This is a signed value, so you have to take the absolute value.

The area in texture space is calculated the same way:

area = SUM (i=0, n-1) u[i] * v[i+1] - v[i] * u[i+1]

Now determine the 'mipmap factor':

mm = texture_space_area / screen_space_area

Last step is determining the boundaries. If 'mm' is 1, the texture is exactly as large on screen than originally. If 'mm' equals two, it's time to act. Currently Focus uses a boundary of 2.5 for the first mipmap-level, and 5 for the second. Maybe I should use 1.5 and 3 however, I need to give that some thought.

Closing

OK, that's it. A few last remarks:

Really large polygons are not so good for this. In Focus, there are two adjacent rooms, quite large, with the same texture on the floor. The first room is entirely rendered using the original texture, the second room entirely with mipmap level 2. That means that the original texture touches the second mipmap level, and that's not a pretty sight. This could only be prevented by splitting the floor in more polygons.

That's all, happy coding, and keep me informed if you have more advanced knowledge/thoughts on this matter.

Jacco Bikker, a.k.a. "THE PHANTOM"