English Welcome Kecy Programování 3D - Engine Guestbook Odkazy Downloady O autorovi Napiš mi Mailform
box_cz 3D - Engine 08 - mip-mapping a filtrování textur box_cz

Ahoj ! Tak tady máme prázdniny a taky nový díl seriálu o enginech. Doufám, že vás minule nezmátly ty grafy na konci. To první číslo je délka segmentu (podle toho je to seřazené) a to číslo v závorce je jejich počet. Sloupec je potom jejich relativní počet. Kód na generování byl ve zdrojáku a spouštěl se klávesou "Home", můžete si to zkusit, pokud jste si toho nevšimli. Minule jsem sliboval něco o Mip-Mapách, tak jdeme na to !


Co to je Mip-Mapping ?


rushing pixelsrushing pixels

To byly obrázky z minulého dílu. Oba mají jedno společné : obsahují plochy, kde detail textury převyšuje detail obrazovky. Na tom prvním je to třeba podlaha, ale i zdi, i když to na nich není tolik vidět a na druhém to jsou "větráky" (ty díry ve stropě). Když je to jako obrázek, ještě se to dá přežít, ale když se ve světě hýbete, obraz všelijak šumí a přeblikává. To řeší právě Mip-Mapy. Podívejte se na screenshot z Quaka I :

q1 mip-mappingq1 mip-mapping

Nalevo se podívejte na ten nápis "Exit" a porovnejte ho s tím napravo : nalevo je hráč od té stěny trochu dál a textura má menší detail. Potom přijde blíž a textura se přepne na její verzi s vyšším rozlišením. Tím se odstraní šum na stěnách, vzdálených polygonech s "proužkatou" (kontrastní) texturou, kde je moc detailu na moc malou plochu. Ještě vám sem dám dva obrázky (snad to bude prohlížitelné, na 56k modemu asi jo :-) ) Jsou z mé hry, která se tady taky za chvíli vyskytne. Na tom horním jsou vypnuté Mip-Mapy :

ijsila nomip

ijsila mip

(všimněte si zdi za světlem, chodeb vedoucích dozadu... )


Mip-Mapy v praxi

Mip-Mapping má dva klony : Ordinary Mip-Mapping (Quake, většina gfx karet včetně GeForce), nebo Bi-Directional Mip-Mapping. Potom je ještě rozdělení podle toho na co se mipmapa aplikuje, a to Mip-Mapping per poly a per scanline. My si ukážeme per poly, to znamená, že na celý polygon je použitá jedna mipmapa (Quake |, ][). Mip-Mapping per scanline používá třeba Unreal Tournament, Morrowind a Quake ]|[ Arena (maybe Doom ]||[). Opravdu jde jen velmi těžko rozeznat (v Unrealu to opravdu najít skoro nešlo) :

q3 mip-mapping

Při používání per poly se doporučuje přerozdělovat velké polygony na menší části. Představte si situaci, kdy jsou dva pokoje vedle sebe, podlaha jednoho jsou dva polygony, podlaha toho druhého taky. Pro první pokoj pravděpodobně vyjde textura v plném detailu, pro druhý třeba o dva stupně zmenšenější a na rozhraní podlah vznikne nehezký skok. Kdyby se poldahy přerozdělily na víc polygonů, budou skoky menší. Přerozdělení můžete vidět třeba ve Quake ][ ve velkých místnostech :

q2 mip-mapping

Rozdělení větších polygonů na dílce (Quake ][)



Ordinary Mip-Mapping

Znamená to, že se mip-mapy vygenerují jako zmenšené verze textury s konstantním poměrem velikosti stran. Tudíž, když máme texturu velikosti 64×64, budeme mít mip-mapy 32×32, 16×16, 8×8, 4×4, 2×2 a 1×1. Mezi těmi se potom bude přepínat. Celé to zabere 1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 .. = 2 krát více paměti, než jen klasická textura bez mip-map. (Textury v našem engine smějí mít velikost jen mocnin dvou, tudíž se dělí vždycky na poloviny. To ale není výsada jen našeho engine, hodně grafických karet taky nepodporuje jiné velikosti, teď nevím jak to přesně je, je možné že dosud ne a texturu upraví -zvětší- rozhraní pro práci s grafickou kartou - OpenGL, Direct 3D)


Bi-Directional Mip-Mapping

Bi-directional mip-mapping má mip-mapy zmenšené vždy po x-ové, y-ové a obou osách. Vypadá to takhle :

bi-directional mip

V levém horním rohu je originální textura (128×128), a ta se potom zmenšuje. Jak asi vidíte, zabere to 4× víc paměti, ale výsledek není zase o tak moc lepší, takže se od tohoto nápadu všeobecně upustilo. My si to ale napíšeme, zčásti proto že ukládat mip-mapy takhle je docela dobrý nápad.


Jak generovat Mip-Mapy ?

Mip-Mapy by měly být generovány buď dobrým grafickým programem, nebo nějakou téměř dokonalou rutinou. Určitě ne jen obyčejným převzorkováním, protože pak výsledek vypadá hrozně. Napsal jsem pro vás program, který Mip-Mapy vygeneruje. Volá se z příkazové řádky a podporuje bitmapy, PCX-ka, Targy a GIFy. Výstup vypadá stejně jako obrázek v sekci Bi-Directional Mip-Mapping, je možnost generovat i ordinární Mip-Mapy. Dělá to jednoduchý průměr RGB. Větší problém, než mip-mapu vygenerovat je při renderování vybrat, se kterou se bude kreslit.


Jak vybrat tu správnou Mip-Mapu ?

Mip-Level - stupeň zmenšení - se určuje podle velikosti texelu na obrazovce. Když texel (tj. bod textury namapované na nějakou face) zabere více, nebo jeden pixel, nic se neděje, ale když se zmenší natolik, že už nezabere ani jediný pixel, náš milý rasterizer určí, že se použije třeba každý čtvrtý pixel - při dalším snímku zase jiný, výsledkem čehož je šum, kterého se chceme zbavit, takže je čas nasadit mip-mapu o level dál, takže texely zase zaberou více místa, protože mip-mapa bude mít menší (poloviční) rozlišení. Pří této operaci však v jednom snímku bude mít textura velké rozlišení a v dalším poloviční, tudíž "blikne". Tento problém sice řeší trilineární filtrování, které určí, že z mip-mapy 1 se použije 20% a z mip-mapy 2 zbylých 80%, takže mip-mapy nepřeblikávají, ale postupně se prolínají. Tenhle způsob je v software modu takřka nezvládnutelný, takže ho používat nebudeme (ono stejně přepínání probíhá většinou ve větší vzdálenosti od kamery, takže není vidět) ale v example možná bude... No a teď si řekneme něco o velikosti texelu. Když mapujeme texturu, počítáme si "delty" souřadnic (dudx, dvdx...) ze kterých jde velikost texelu spočítat podle velice jednoduché rovnice :

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

Podle tohohle vzorce se spočítá plocha (v pixelech), kterou pokrývá texel. Má to ale jeden háček - delty, které spočítáme my jsou perspektivně korektní - vynásobené 1/z, ale to se pro tenhle vzorec nehodí, takže nezbývá než buďto znovu spočítat další, nebo se na to podívat z trochu jiného úhlu. Další jednoduchý algoritmus je vzít polygon a spočítat jeho povrch na obrazovce a "na textuře" - podílem potom dostaneme přibližně stejné číslo (nějakou tu nepřesnost zapříčiní rasterizer zokrouhlováním) V C-čku by to vypadalo nějak takhle :


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);
    // spocita 1 / plocha texelu

    return mip_map_factor;
}

// prevede mipfactor na potrebne zmenseni textury
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;
}

Co to dělá ? V první části si to připraví pár proměnných, potom následuje smyčka, počítající povrchy polygonu na textuře a obrazovce a nakonec se spočítá mip_map_factor - poměr obou ploch. Druhá funkce podle "by watchko" určených konstant vrátí, kterou mipmapu by bylo dobré použít. (ono až zase tak od oka - jedno odpoledne strávené poletováním s kamerou nad potexturovaným obdélníkem a dolaďování)


Example #1

nomip
Tak tady jsou MipMapy vypnuté


ord-mip
Tady se používá ordinary MipMapping


bidir-mip
A tady zase Bi-Directional ...


Tak, můžu si být na 100% jistý že až tohle bude někdo číst, že mě kvůli těm obrázkům zabije :-).. (snad jich nebude moc) Example je S-Buffer Engine z minulého čísla, stáhnout ho můžete tady. Tak, co je nového ? Je tam vylepšený "Font Engine", který teď umí zobrazit písmo transparentně (na obrázku) ve stylu á-la Half-Life :-). Potom je tam ta hlavní část: mipmapy v souboru Raster.cpp přibylo na začátku pár řádek :


#define MIPMAPNO_MIPMAPPING 0
#define ORDINARY_MIPMAPPING 1
#define BIDIRECT_MIPMAPPING 0
// aspon jedno musi byt 1, ostatni 0
// (prepinac stylu mipmappingu)

To je switch pro mipmapping - ke kterému řádku dáte jedničku, ten styl se použije. Potom je tam několik funkcí pro zjišťování velikosti texelu, z nichž jednu už jsem popsal před chvílí a další je tady :


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 - normala polygonu

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

    return (float)(a * a + b * b);
    // spocita 1 / plocha texelu v souradnici u
}


Tahle varianta počítá plochu texelu právě z "delt" je to dost podobné funkci pro počítání delt pro texturování, ale chybí tu perspektivní korekce, která je tady nežádoucí. Jinak je to asi stejné. Samotná funkce pro výpočet texturovacích delt doznala trochu optimalizací, ušetřilo se několik dělení a unárních "-", to snad pochopíte z komentářů.. Textury jsou ve stejném formátu jako vyplivne Mip_Map "Creator", asi by bylo trochu ekonomičtější je počítat přímo při startu.. Tak, to by bylo k mipmapám a my se můžeme pustit do filtrování.


Filtrování textur

Až doteď naše engine nepoužívaly žádné filtrování, ale když teď snižujeme detail textur, začíná se projevovat že je všechno "zubaté". To řeší bilineární filtrování :


Bilineární filtrování

Při klasickém texturování, jak jsme to dělali až doteď se bere fixed point souřadnice pixelu v textuře, která se zaokrouhlí a vykreslí se barva pixelu na té souřadnici. Při Bilineárním filtrování se tomu dá trochu víc péče : Vezme se fixed point souřadnice texelu a oddělí se jeho celá a desetinná část. Potom se vezme čtveřice texelů, a to ten na souřadnici kterou bychom uvažovali bez filtru a tři na souřadnicích o 1 větších : (větších proto, že desetinná část je vždycky kladná :-) )

tex-sampling
Vzorkování při normálním a bilineárně filtrovaném texturování

Mnno.. červeně jsou souřadnice textury ve FP. Fialově je označený pixel, který jsme do teď brali jako korektní a zeleně jsou pixely, které se použijí pro přefiltrování. Jak se to dělá ? Pro Filtrování potřebujeme tabulku váhových faktorů, říká se jí "Multab". V ní jsou uložené váhové faktory všech čtyř texelů pro uřčité odchylky X a Y, pomocí ní se pak určí, že z prvního texelu se použije 30%, z druhého 45%.. a namíchá se výsledná barva. Jak ale Multab vygenerovat ? Podle jednoduchých a myslím snadno odvoditelných rovnic se dají váhové faktory rychle spočítat :
  • 1. Uf * Vf
  • 2. (1 - Uf) * Vf
  • 3. (1 - Uf) * (1 - Vf)
  • 4. Uf * (1 - Vf)
Tak, Uf je U-fractional, tedy desetinná část souřadnice U, Vf je to samé pro V. Ale v praxi se fixed point většinou nechává fixed pointem, takže pomocí pár úprav jde tabulka indexovat. A co obsahuje tabulka ? Ta by měla obsahovat hodnoty, kterými budeme násobit RGB hodnoty texelů, přičemž suma hodnot pro všechny čtyři texely musí být vždycky konstantní. Takže třeba 256, to se potom budou dobře míchat barvy.. takhle by to samozřejmě fungovalo, ale bude to příšerně pomalé. Co s tím ? Na pomoc přichází tabulky barev. Pro každou texturu si předpočítáme váhy jejích jednotlivých barev a potom při texturování už je jen sečteme. Tabulka barev tady není žádné velké minus, protože každá textura má svou vlastní tabulku, takže obraz rozhodně nebude tak jednobarevný jako třeba Quake I / Quake ][, kde byla tabulka barev společná pro všechny textury. Řekněme, že si předpočítáme 64 hloubek od každé barvy, to by se ještě mělo vejít do paměti.. (256-ti barevná tabulka bude mít 64kB - pokud se vám to zdá moc, můžete použít míň, ale zkoušel jsem 16 odstínů, kdy přechod bílá-černá už je kostkovaný) Samotný výpočet multabu bude vypadat nějak takhle :


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;
        }
    }
}

Bylo to zase jako obvykle :-) jednoduché - snad jediný zádrhel je dopočítávání "zbytku", abychom odstranili chyby při zaokrouhlování. Teď se ještě zbývá podívat na texturovací smyčku :


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

// vykresli texturovany bilinearne filtrovany segment o delce =< 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);
        // adresa texelu

        frac = ((u1 >> 10) & 0x3f) + ((v1 >> 4) & 0xfc0);
        // desetinna cast adresy (6 bitu z V + 6 bitu z 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]];
        // bilinearni interpolace

        video ++;
        // nova pozice

        u1 += du;
        v1 += dv;
        // interpolace souradnic
    } while(video < v2);
}

Na začátku se určí index texelu v mapě (tex) a jeho desetinná část (frac), která se skládá z šesti bitů desetinné části v a šesti bitů desetinné části u (0000 VVVV VVUU UUUU). Šest bitů proto, že dva na šestou je 64, jak jsme si předtím určili coby počet odstínů. Pak už se jen odkazuje na multab a texturu. Přibylo ale pár konstant : A_3 je maska textury, to znamená maximální index textury -1 (pro 256×256 je to 0xffff), prostě číslo které zabrání, aby se vlezlo do části paměti kde textura už není, ale zpátky na její začátek. Potom W_0, to je šířka textury a W_1 = W_0 + 1. K čemu to je ? Řekli jsme si že budeme potřebovat čtyři texely, a jejich index je právě [pix] (první), [(pix + 1) & A_3] (ten vpravo od něj) - pozor nemusí být vpravo - pokud se jedná o poslední pixel na řádku, bude to ten vpravo, ale ještě pod ním. [(pix + W_0) & A_3] (ten pod ním) a [(pix + W_0) & A_3] (ten "naproti němu"). Kdybyste opravdu chtěli aby pixely navazovaly správně i na posledním sloupci textury, bude smyčka vypadat takhle :


// vykresli texturovany bilinearne filtrovany segment o delce =< 16pix.
static void _fastcall Interpolate_Segment_Bilerp(int u1, int du, int v1, int dv,
    unsigned __int32 *video, unsigned __int32 *v2)
{
    int frac, tex_x, tex_y;
    do {
        tex_x = (u1 >> 16);
        tex_y = (v1 >> B_1);
        // adresa texelu

        frac = ((u1 >> 10) & 0x3f) + ((v1 >> 4) & 0xfc0);
        // desetinna cast adresy (6 bitu z V + 6 bitu z U)

        *video = _palette[(_texture[(tex_x & A_1) +
                 (tex_y & A_2)] << 6) + multab[0][frac]] +
                 _palette[(_texture[((tex_x + 1) & A_1) +
                 (tex_y & A_2)] << 6) + multab[1][frac]] +
                 _palette[(_texture[(tex_x & A_1) +
                 ((tex_y + 1) & A_2)] << 6) + multab[2][frac]] +
                 _palette[(_texture[((tex_x + 1) & A_1) +
                 ((tex_y + 1) & A_2)] << 6) + multab[3][frac]];
        // bilinearni interpolace

        video ++;
        // nova pozice

        u1 += du;
        v1 += dv;
        // interpolace souradnic
    } while(video < v2);
}

Význam W_0 zůstane stejný, odpadne W_1 a A_3, ale je to o dost pomalejší. Předchozí verze způsobí jen "skok" v textuře tam kde se opakuje - není to ale moc vidět..

A jak to potom vypadá ? Hezky :-) >>


filter on
Bilineární filtr

filter off
Bez filtru


Example umí udělat screenshot (F12), Bilineární filtr se vypíná / zapíná funkcí Switch_Bilerp(int), kde parametr je "1" nebo "0", podle toho zda chcete filtrování aktivovat / vypnout. Textury tentokrát mají formát 256color TGA, to je formát který používají američtí hackeři a třeba Quake ]|[ Arena. Obrázek na TGA můžete převést třeba pomocí ACD-See, ale předtím ho musíte dát do GIFu, nebo něčeho co musí mít 256 barev, protože TGA může být i truecolor. Stáhnout si ho (Examplesák + source) můžete tady :

source code downoad

 s-buffer engine (šipky značí chybu)

Tož v tomhle díle jste museli stáhnout 350kB obrázků.. To snad není tak hrozný.. No řekněte sami - už jste viděli někoho zabít člověka kvůli půl mega ? (to budu asi první :-P ...) No a o čem to bude příště ? Mnno - asi si povíme něco o světle, stínování, stínovacích modelech a technikách. Tož bye !

    -tHE SWINe-

zpět


Valid HTML 4.01!
Valid HTML 4.01