MipMapping (Including BiDirectional) by (13 January 1999) 
Return to The Archives 
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 nearperfect 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 'bidirectional 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 Udirection (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 ____________________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 deltaU and a deltaV.
Coders will know what I mean. Now you could simply use the size
of deltaU and deltaV 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, deltaU will be a positive value, and deltaV
will be zero. If on the other hand the texture is tilted 90
degrees, deltaU is zero, and deltaV is a positive value. So you have to take into account a bit more. How about the deltaU and deltaV 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 onscreen 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 bidirectional mipmapping, and the mipmapping per scanline. Bidirectional mipmapping was dropped for three reasons: 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, n1) 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, n1) 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 mipmaplevel, 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" 
