Czech Welcome Guff Coding 3D - Engine Guestbook Links Downloads About author Mail me Mailform
box_en 3D Engine 8 - mip-mapping and texture filtering box_en

Hi ! I'm back again ... today i'll talk a bit about texture filtering and mip-mapping. Let's move on !


What the Mip-Mapping is ?


rushing pixelsrushing pixels

Look at these beautiful images ! They are both from the previous part and there is something similar in each of them - they contain surfaces where detail of the texture is quite larger than the screen resolution. In the left one these are for example far walls or floor, on the second one it's floor again and ceiling.
When you draw a static image, it looks bad, but it's still allright. But if it's animation or game, it's terrible : when you move, all textures are rushing and blinking ... How to prevent that ? Look at these screenshots from quake (I) :


q1 mip-mappingq1 mip-mapping

Look at the "Exit" sign. On the left image, camera is more far off the wall than on the right one - so the left sign has a texture with less detail. On the right image player is a bit nearer and the texture switches to version with more detail. It's the very basic function of mip-mapping. It's important to create lower-detail textures with some good scaling routine (or some gfx program like Photoshop / etc ...) I'll put here one more example. It's my old game, source is availbale in download section. There's no mip-mapping at the top image :

ijsila nomip

ijsila mip

(notice the far passages or wall behind the light ...)


Mip-Mapping in practice

There are two versions of mip-mapping : ordinary (i think most of games / rendering engines) nad bi-directional. Ordinary means texture is scaled in both directions with the same coefficient. Bi-directional will have mipmaps of all possible power-of-two sizes up to original texture sizes (ie. separate scaling coefficients for texture's width and height).
Another division could be per-polygon and per-scanline. Per-polygon means that whole polygon will be textured using single mip-map (ie. one scaled down version of texture). Per-scanline means that each scanline can have another mip-map when necessary. Mip-mapping per scanline has one modification, implemented in hardware - for each vertex the corresponding texel size is computed and then interpolated across whole surface, serving as mip-map level selector. You can see it in all HW-accelerated gamse :

q3 mip-mapping

There is one more improvement, called trilinear filtering - texel size value isn't used for deciding which mip-map level to use, but to precisely mix between two nearest levels - so you can't see the "step" as on the image above (marked with red lines).
We will use per-poly mipmapping as it's the most simple to implement. When doing that it's recomended to subdivide polygons. Consider situation with two rooms, each one have one-polygon floor. When standing in one, looking to the other, the level of detail for mipmap in first room will be quite different to second room so you will see significant change in texture quality in place floor polygons are meeting.
Most of games uses BSP-trees that can do subdivision for us, like in Quake 2 (can't find another game that would use per-polygon mip-mapping)

q2 mip-mapping

Quake ][ takes advantage of it's BSP to simply divide polygons


Ordinary Mip-Mapping

As i told you above, mip-maps will have constant proportions. So for texture 64×64 pixels will be 32×32, 16×16, 8×8, 4×4, 2×2 and 1×1 mip-maps. Engine will switch between them. Whole thing will take 1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 .. = 2 times more of memory than original texture. I don't exactly know how it's in non-power-of-two sized textures (new opengl implementation allows such ones) - maybe mipmaps are generated power-of-two or just half-size. I simply don't remember.


Bi-Directional Mip-Mapping

Bi-directional mip-mapping will use different proportions of original texture. It will look like this :

bi-directional mip

There's an original (128×128) texture in the upper left corner and all possible smaller textures are all arround. You can see it will take four times more memory than original texture. (maybe that's why noone use that)


How to generate Mip-Maps ?

As i told you above, you should use some better resampling routine (search for bicubic / lanczos or like that ...) I've written a very simplified program (using no lanczos, just average every two pixels an you have half-sized image) Download it here. It's called from command-line and does support plenty of graphic formats (as far as i remember - bmp, pcx, tga, jpg, gif (when animated, put frames one below another)) The image in section "Bi-Directional Mip-Mapping" was generated using this ... I think you can do whatever you want with it (routines for loading images can be reused ...)


How to choose the right Mip-Map ?

Mip-level = level of mignification is given by texel size in particular place on screen. So - when texel (ie. pixel in texture just for case i didn't mention this yet) takes one or more pixels, nothing happens (i mean texel in original texture), but when it's smaller than half of pixel (in practice you will see two different texels, blinking in one pixel as you move) - it's time to switch to first mipmap. You will see slight twitch as texture change resolution, what you can solve by using trilinear filtering that will mix two nearest mipmaps - so no twitching. We won't do this sort of mipmapping since it requires two times more of CPU time (need to get texel from both mip-maps) + some time to mix resulting colour.
Let's talk a bit about texel size ! When you're interpolating a texture over your poly, you have some delta numbers. You could compute texel size using formula like this :

    sqrt(dudx^2 + dudy^2) * sqrt(dvdx^2 + dvdy^2)

It's simply area of texel (in pixels). But in our case, there's a tiny lapse - we multiply our deltas with 1 / z so the result would be useless. (but this would be practical when doing trilinear filtering)
We will simply compute area of our polygon as it lies on screen and on texture (or to be more accurate - in screenspace & texturespace) - and by dividing these two values get - our texel size. Some c-code :


struct Vertex {
    float x, y, z;
    float u, v;
    //
    Vector normal;
};

struct Polygon {
    int n_vertex_num;
    Vertex vertex[7];
};

struct Mip_Map {
    int n_Width, n_Height;
    unsigned char *texture;
    int A_1, A_2, A_3, B_1;
};

struct Texture {
    int n_Width;
    int n_Height;
    int n_mip_num_x;
    int n_mip_num_y;
    unsigned __int32 *palette;
    Mip_Map *mip_map;
};

float Calc_Mip_Factor(Polygon *p, Texture *texture)
{
    float scr_area, txt_area;
    float x1, y1, u1, v1;
    float x2, y2, u2, v2;
    float mip_map_factor;
    int i, v_num, tW, tH;

    v_num = p->n_vertex_num;
    tW = texture->n_Width;
    tH = texture->n_Height;
    scr_area = 0;
    txt_area = 0;

    x1 = p->vertex[v_num - 1].x;
    y1 = p->vertex[v_num - 1].y;
    u1 = p->vertex[v_num - 1].u * tW;
    v1 = p->vertex[v_num - 1].v * tH;

    for(i = 0; i < v_num; i ++) {    
        x2 = p->vertex[i].x;
        y2 = p->vertex[i].y;
        u2 = p->vertex[i].u * tW;
        v2 = p->vertex[i].v * tH;
        //
        scr_area += x1 * y2 - y1 * x2;
        txt_area += u1 * v2 - v1 * u2;
        //
        x1 = x2;
        y1 = y2;
        u1 = u2;
        v1 = v2;
    }

    mip_map_factor = (float)fabs(txt_area / scr_area);
    // calc 1 / texel area

    return mip_map_factor;
}

// tell texture mignification corresponding with mip-factor
int MipFactor_ToScale(float mip_map_factor)
{
    if(mip_map_factor > 262000)
        return 9;
    else if(mip_map_factor > 65500)
        return 8;
    else if(mip_map_factor > 16000)
        return 7;
    else if(mip_map_factor > 4000)
        return 6;
    else if(mip_map_factor > 1000)
        return 5;
    else if(mip_map_factor > 250)
        return 4;
    else if(mip_map_factor > 70)
        return 3;
    else if(mip_map_factor > 20)
        return 2;
    else if(mip_map_factor > 5)
        return 1;

    return 0;
}

What does it do ? In first part it calculate polygon areas in screenspace and texturespace (adding more and more spaces, huh?) and simply calculate relative texel area. When too small, texel takes more than one screen pixels, when too large, it would result in noise since more texels would occupy single screen pixel. So next function tells us level of mip-map to use in order to display correctly. Where did i get those numbers ? Well, i spent afternoon flying over textured rectangle, adjusting these.


Example #1

nomip
no Mip-Mapping


ord-mip
ordinary Mip-Mapping


bidir-mip
and here Bi-Directional ...


These images are pretty stupid example and i'll have to replace it. Because we have per-polygon mip-mapping and the quad with "fans" consist of two polygons, you can't see what really happens. I'll have to replace these when less busy ...
Example is identic (excempt mip-maps) with recent s-buffer example here. I'd almost forget! There's also new font-engine, displaying bitmap fonts a-la Half-Life. Now the main part. In Raster.cpp we have a few more new lines:


#define MIPMAPNO_MIPMAPPING 0
#define ORDINARY_MIPMAPPING 1
#define BIDIRECT_MIPMAPPING 0
// one must be set to 1

It's mipmapping-method switch. Next some functions for calculating mip-map level:


float Calc_Mip_Factor_X(POLYGON *p, TEXTURE *texture)
{
    float x[2], y[2], u[2];
    float a, b, c;

    a = (float)texture->Width;

    x[0] = p->vertex[1].x - p->vertex[0].x;
    x[1] = p->vertex[2].x - p->vertex[0].x;

    y[0] = p->vertex[1].y - p->vertex[0].y;
    y[1] = p->vertex[2].y - p->vertex[0].y;

    u[0] = p->vertex[1].u * a - p->vertex[0].u * a;
    u[1] = p->vertex[2].u * a - p->vertex[0].u * a;

    a = y[0] * u[1] - y[1] * u[0];
    b = u[0] * x[1] - u[1] * x[0];
    c = x[0] * y[1] - x[1] * y[0];
    // cross product

    if(c == 0) 
        return 0;
    
    a /= c;
    b /= c;

    return (float)(a * a + b * b);
    // calc 1 / texel area in u-coord
}


This code compute texel area from delta values. As i said - we can't use our deltas because they're perspective correct so this function compute it's own ones. It's more like experiment, but it seems to work, a bit. Textures are in the same format our mip-map creator produce, it should be a bit more economical to compute mipmaps on-the-fly.
So much for mipmaps, now something on texture filtering.


Texture filtering

Since now, our engines had no filtering. Why ? Because of speed. But we have faster processors and can do something with it using bilinear filter:


Bilinear filtering

In classical texturing we used single pixel of texture, culling fractional part of it's coordinates. But we should put here a bit more care: we take fixed-point coordinate and extract integer and fractional part of it. Next we take four pixels (the one we'd use without filtering and three more, lying next texel - fractional parts are always positive) I'll add nice picture in order to explain it a bit more:

tex-sampling
texture sampling

Red lines are FP coordinates. Violet texel is texel we'd use with no filter (we used it since now) and green lines mark pixel quad we're going to use. How ? We will need to calculate weight factor for each of pixel (sum of weight factor is always one) and mix them together, resulting in final pixel color. Can we optimalise it ?
We can precompute weight factors for u and v fractional values. They're stored in table, called "multab" in references. It contain four weight factor arrays (two-dimensional ones - we have u and v coordinate) We can compute weight-factors fairly simple:
  • 1. Uf * Vf
  • 2. (1 - Uf) * Vf
  • 3. (1 - Uf) * (1 - Vf)
  • 4. Uf * (1 - Vf)
So, Uf and Vf are fractional parts of u and v texture coordinates. We'll let Uf and Vf in fixed-point in order to be able to directly index the table. Multab would then contain unsigned chars (0 - 255) to simply color weighting. It could be done wery effectively using MMX instructions, but when i wrote this tutorial i had old Pentium 120 processor which has obviously no MMX. What now ? Doing it pixel by pixel was incredibly slow since i had to decompose four r/g/b's, multiply them by corresponding value, divide 256 and sum. Once i was told human eye can recognize 64 shades of single color. So i decided to precompute all brightness levels of each texture. No, stop creeping, i'm not going to make 64 versions of each texture. You should understand there were no 512 MB RAM modules coming with P 120. I had to make all textures 256-colors and precompute only color tables. I won't make another quake-like monochromatic engine and make each texture have it's own color table, which is most times absolutely sufficient. So, each color table will take 64kB. You shouldn't use less than 64 shades, because texture with 100% black and 100% white pixels will be blocky again. So we can write multab-calculation code (now when we now it will contain values in 0 - 63 range):


static char multab[4][4096]; // 4096 = 64^2

void PreCalc_Multabs()
{
    int u, v, total;
    int i;

    for(u = 0; u < 64; u ++) {
        for(v = 0; v < 64; v ++) {
            i = u + (v << 6);

            multab[0][i] = (((63 - u) * (63 - v)) >> 6);
            multab[1][i] = ((u * (63 - v)) >> 6);
            multab[2][i] = (((63 - u) * v) >> 6);
            multab[3][i] = ((u * v) >> 6);

            total = multab[0][i] + multab[1][i]
                + multab[2][i] + multab[3][i];

            if(total < 63)
                multab[0][i] += 63 - total;
        }
    }
}

It was simple as it always is. The only unexpected lines could be the only those with total. I won't have to decompose colors to rgb since i don't have to scale them. But i have to sum them. When they're all correctly scaled, maximal value of resulting r/g/b should never be larger than 255 so i neither need to handle r/g/b when adding colors. Take a look at texturing loop:


int W_0, W_1;
int A_1, A_2, A_3, B_1;
unsigned char    *_texture;
unsigned __int32 *_palette;

// draw textured span with length =< 16pix.
static void _fastcall Interpolate_Segment_Bilerp(int u1, int du, int v1, int dv,
    unsigned __int32 *video, unsigned __int32 *v2)
{
    int frac, tex;
    do {
        tex = ((u1 >> 16) & A_1) + ((v1 >> B_1) & A_2);
        // texel address (int)

        frac = ((u1 >> 10) & 0x3f) + ((v1 >> 4) & 0xfc0);
        // fractional part of address (6 bits of V + 6 bits of U)

        *video = _palette[(_texture[tex] << 6) + multab[0][frac]] +
                 _palette[(_texture[(tex + 1) & A_3] << 6) + multab[1][frac]] +
                 _palette[(_texture[(tex + W_0) & A_3] << 6) + multab[2][frac]] +
                 _palette[(_texture[(tex + W_1) & A_3] << 6) + multab[3][frac]];
        // fetch correct shade from palette and sum together

        video ++;
        // next pixel

        u1 += du;
        v1 += dv;
        // coord interpolation
    } while(video < v2);
}

For each pixel we get integer index to texture (tex) and it's fractional part (frac), containing 12 bits (212 = 4096 = dimension of multab) - 6 bits of each coordinate fractional part (0000 VVVV VVUU UUUU). There are also some new constants : A_3 is texture pixel count - 1 (for 256x256 it's 0xffff). Next W_0 is width of texture (in order to get pixel at next texture scanline) and W_1 is W_0 + 1 to get next pixel without unnecessary adding. So we have all our indices, it's enough to get our weighting factors from multab. Now i can see i wrote it bad. I should've switched multab dimensions in order to take advantage of memory caching. Try it yourself and see if it's faster (you have to switch multab dimensions to [4096][4] and also all indirections to it) It will read first value of multab and in same read burst store three next to cache which is far faster than memory - it should be quite well visible speedup.
A reader who pay attention propably found error in this. Where ? In computing texel indices. We can't use index + 1 to get next pixel. In middle of texture, it's allright. But on the right edge we'll get pixel one step right, but also one step bottom! (this problem is for u only, v will compute allright) If you really wanted to do it right, you'd have to:


// draw textured span with length =< 16pix.
static void _fastcall Interpolate_Segment_Bilerp(int u1, int du, int v1, int dv,
    unsigned __int32 *video, unsigned __int32 *v2)
{
    int frac, tex, tex_1;
    do {
        tex = ((u1 >> 16) & A_1) + ((v1 >> B_1) & A_2);
        tex_1 = (((u1 >> 16) + 1) & A_1) + ((v1 >> B_1) & A_2);
        // texel address

        frac = ((u1 >> 10) & 0x3f) + ((v1 >> 4) & 0xfc0);
        // fractional part of address (6 bits of V + 6 bits of U)

        *video = _palette[(_texture[tex] << 6) + multab[0][frac]] +
                 _palette[(_texture[tex_1] << 6) + multab[1][frac]] +
                 _palette[(_texture[(tex + W_0) & A_3] << 6) + multab[2][frac]] +
                 _palette[(_texture[(tex_1 + W_0) & A_3] << 6) + multab[3][frac]];
        // bilinear interpolation

        u1 += du;
        v1 += dv;
        // texcoord interpolation
    } while(video < v2);
}

Meaning of W_0 remains the same, we won't need W_1 but it's gonna be a bit slower. Visual error of previous version is only poor visible jump at right border of texture so it's a bit better visible repetitivness of texture, but you really have to search for it, unless texture contain some contrast horizontal lines - then it's quite well visible. I'll use the faster version from now on.

How does it look then ? Nice, definitely !



Bilinear filter


No filter


Example can make screenshot (by pressing F12). Textures are in TGA format which is (i suppose) well known one. Download it right here:




 Bilinear filter (arrows mark error)

What about next time ? I guess something about light and lighting techniques. But for now ... bye!

    -tHE SWINe-



Valid HTML 4.01!
Valid HTML 4.01