English Welcome Kecy Programování 3D - Engine Guestbook Odkazy Downloady O autorovi Napiš mi Mailform
box_cz 3D - Engine 11 - lightmapy box_cz

No nazdar !

    Přišel další tejden (teda vejkend) a zase mám šanci sednout k počítači, kterej nezvládne přehrávat mp3-ku a zároveň mít otevřenej notepad, takže si rozbaluju hudbu do vawů a píšu :-) (ono mi moc jinýho nezbývá - je pravda, že sem moh vyrazit na Citadelu do Brna, ale holt zase plánuju update svýho miláčka, takže nikam nerazím kvůli penězům - mimochodem mě můžete vidět v Pardubicích, jak pobíhám ve slušivým oblečku (oranžová je out :-() městských služeb a dělám ze sebe vola za 150,- na hodinu) ... a za měsíc tradá ! GeForce FX 5900 ! a potom dva 120 GB disky a krásné pole raid0. ... a pak už mám všechno.
    Dneska máme slíbený ty lightmapy, takže se na to vrhnem, jak nebožtík na útulnou rakev ! Lightmapy jsou, jak název napovídá mapy, obsahující světlo. Je to skoro doslova. Lightmapy jsou textury, nabalené zvlášť na každý face světa (tudíž žádná lightmapa se neopakuje) a do nich se předpočítá světlo i se stíny. Předpokládá to sice bohužel - narozdíl od stencilu statickou geometrii, ale dá se to se stencilem kombinovat. Cílem programu tedy je :
  • Napočítat lightmapy a nějak je uložit
  • Renderovat scénu s texturou materiálu a tu modifikovat tetxturou lightmapy
    ... z toho plyne, že lightmapy se nepočítají realtime, takže můžeme použít tak náročnou a přesnou osvětlovací metodu, že ji ani nezvládneme naprogramovat :-)     Pokud jste někdy dělali levely do Quaka, víte že existuje program, který udělá BSP strom, potom program, který spočítá světlost a potom volitelně program, který spočítá viditelnost a až nakonec přijde pařan a spustí quaka !     Jen tak mimochodem, s lightmapama podle všeho začal Quake I a od té doby ... to je všude. Half Life, dokonce i Black & White a víceméně všechny FPS hry. (v novějších se víc používá stencil - Half Life 2) ... takže doufám že tenhle model nebudete moc preferovat a vymyslíte pro svou hru něco lepšího. No, ale pustíme se do problému.

lowres-maps
Standardní lightmapovací artefakt - všimněte si,
že stín je takový hrbatý (nízké rozlišení lightmapy)



Jak namapovat lightmapu

    Jak jsme si řekli, lightmapy budeme mapovat po všech facech světa. Dál by to chtělo, aby texely lightmap měly na všech polygonech zhruba stejnou velikost a byly zhruba čtvercové (to znamená pro větší povrch použít větší lightmapu) Nejjednodušší pro nás bude tzv. planární mapování, které se ve většině případů používá. To se vezme normála facu a určí se její největší složka. Potom se vezme obdélník, který se na normálu jakoby "napíchne" (je na ni kolmý) a v tom obdélníku se promítnou vertexy facu. Jak správně tušíte - podle pozice projekcí se určí souřadnice v lightmapě. Potom se ještě určí velikost lightmapy a máme hotovo. Je tu ale pár věcí na probrání :
  • Jedna lightmapa může obsahovat víc trojúhelníků (třeba u takové krychle je logické že dva trojúhelníky ležící na jedné stěně mohou mít společnou lightmapu)
  • Lightmapa nevyjde téměř nikdy s velikostí mocniny dvou
    S prvním problémem se vpořádáme snadno. Prostě vezmeme sousední facy, ležící v jedné rovině a seskupíme je.
    Druhý problém je trochu složitější - pokud prostě vnutíme mocninu dvou, texely budou prostě obdélníkové a to nevypadá dobře. Novější 3D karty sice podporují textury, které nemusí mít velikost mocnin dvou, ale dá se předpokládat že to je pomalejší. Řešením je uspořádat lightmapy inteligentně do jedné velké textury (o rozlišení třeba 1024×1024). To má řadu výhod :
  • Tím, že lightmap je v textuře hodně se minimalizuje poměr nevyužitého místa v textuře
  • Pokud budeme později renderovat pod hardwarem, zjistíme že přepínání textur stojí čas, takže tohle bude rychlejší, protože lightmapy budou všechny v jedné nebo více málo texturách.
  • Texely v lightmapách budou přesně čtvercové
Nevýhodu je, že někdo musí napsat algoritmus, který lightmapy poskládá :-) (z nějakého důvodu tuším že to asi budu zase já :-))


Jak lightmapy naplnit

    Jakkoli. Můžeme použít jakýkoliv stínovací model. My prostě vezmeme normálu na povrchu, vynásobíme s ní paprsek, jdoucí z texelu lightmapy do světla a to ještě vynásobíme barvou světla a viditelností. (viditelnost nemusí být jen 0 / 1, protože lightmapy se nepočítají realtime) Lightmapy se taky můžou počítat pomocí radiosity, photon tracingu, raytracingu, nebo čehokoli.


Jak udělat animované lightmapy

    To už je jednoduché. Vzpomínte si na scénu z Half Life, kde procházíte rozbitým komplexem, nad vámi poblikávají rozbité zářivky a do toho ještě ty zvuky ? Dokonalá atmosféra - a pomocí lightmap je jednoduché ji navodit. Jednoduše spočítáme pro každé světlo lightmapy zvlášť (ne všechny, ale jen ty kam světlo svítí) a ty potom sčítáme do speciální sady lightmap, která se bude renderovat. Nemusíme je tedy sčítat každý snímek, v pohodě to stačí tak desetkrát za sec. Světla se tedy mohou rozsvěcet nebo zhasínat, poblikávat, nebo se postupně ztlumovat a rozsvěcet. Je to sice dost náročné na paměť, ale dneska ... Taky můžete vzít stencil a lightmapy kombinovat s ohledem na stíny (a stíny vrhají jen věci, které nejsou v lightmapách už započítané, tzn. jen pohybující se věci jako hráči, dveře a výtahy ...)
    Dynamická světla s lightmapami - jednoduše vezmete lightmapy, které používáte pro dočasné součty a do nich napočítáte světla jako normálně. Problém je, že touhle cestou pravděpodobně nespočítáte stíny. Můžete zkusit do lightmapy promítnout stěny, vrhající stín a vykreslit je černě, říká se tomu projection shadows - problém je, že když se to počítá tzakhle, musíte zahrnout geometrii celého světa, nejen pohybujících se věcí, jak by tomu bylo u statických světel se stencilem. Možností je hromada, ale tím se nebudeme zabývat.


Jak lightmapy renderovat

    Když kreslíme face, namapujeme texturu a navíc příslušnou lightmapu a při kreslení pixelů je násobíme. Nevýhodou tohoto systému je, že světlost může být maximálně 1 (255). Takže textura pod světlem má své "původní" barvy. Dnes se ale začíná prosazovat tzv. HDR - high dynamic range. To znamená hodnoty nula až nekonečno. Takže můžeme vidět stěnu pod světlem až bílou, což se víc blíží reálnému světu. HDR používá třeba Half Life 2 :

hl2 1

hl2 2

    Krása, co ? (Half - Life 2 teda nepoužívá lightmapy, jak jsem už říkal, ale stencil) Oprava ! Po analýze zdrojáků Half - Life 2 jsem byl zjištěn, že tam jsou taky lightmapy :-( škoda ! Dělá se to tak, že textury jsou dvě - jedna pro hodnoty 0 - 255 a druhá je vlastně vyšší řád, kterým se násobí výsledná barva, ale už se nedělí 256. Takže hodnoty jsou opravdu od nuly do "nekonečna". (nekonečno = 256 - násobek původní textury. Za předpokladu, že textury budou focené, žádný pixel nebude mít žádnou složku nulovou, takže to úplně stačí na bílou ve všech případech. Možná by to mohlo být jen trochu přesnější na vyšších řádech, ale tluče nás paměť a (n+1)-násobný počet operací oproti klasickému RGB, kde n je počet přídavných textur pro vyšší hodnoty barev v naší lightmapě) Musí se taky hlídat, aby nějaká ze složek barvy nepřetekla 255. To si ukážeme u radiosity, která výsledky světlosti od "nuly do nekonečna" dává - přesně, jak je tomu v reálu.

    Teď se pustím do psaní examplu a za chvíli ho tady popíšu. Chvilku počkejte.

Psal jsem to pomalu, protože vím že to budete pomalu chápat (vím, že to je starý ale nemoh sem si prostě pomoct) Podíváme se na funkci, která seskupuje facy podle toho, jak budou spolu ležet v lightmapách.


enum {
    Plane_yz = 0,
    Plane_xz,
    Plane_xy
};

struct Group {
    int n_id;
    //
    int n_plane;
    Vector v_u, v_v;
    //
    Vector v_min, v_max;
    //
    int n_face_num;
    int n_face_used;
    //
    Face **p_face;
};
// group - facy, ležící ve stejné
// rovině a navzájem si sousedící

Group_Data *Group_Faces(World *p_world, float f_max_size)
{
    Group_Data *p_data;
    int i, j, k, l, m;
    int b_found;
    int b_skip;

    if((p_data = (Group_Data*)malloc(sizeof(Group_Data))) == NULL)
        return NULL;
    p_data->n_group_num = 0;
    p_data->p_group = NULL;
    // naalokuje strukturu
    
    for(i = 0; i < p_world->n_object_num; i ++) {
        for(j = 0; j < p_world->object[i].n_face_num; j ++) {
            for(k = 0, b_found = false; k < p_data->n_group_num; k ++) {
                if(!Check_GroupSize(&p_data->p_group[k],
                   &p_world->object[i].face[j], f_max_size))
                    continue;

                for(l = 0; l < p_data->p_group[k].n_face_used; l ++) {
                    if(b_Neighbour(&p_world->object[i].face[j],
                       p_data->p_group[k].p_face[l])) {
                        b_found = true;
                        if(!Add_FaceToGroup(&p_data->p_group[k],
                           &p_world->object[i].face[j]))
                            return false;
                        p_world->object[i].face[j].n_group = k;
                        // přidá se do groupu ...

                        for(k ++; k < p_data->n_group_num; k ++) {
                            for(l = 0; l < p_data->p_group[k].n_face_used; l ++) {
                                if(b_Neighbour(&p_world->object[i].face[j],
                                   p_data->p_group[k].p_face[l])) {
                                    // groupy p_world->object[i].face[j].n_group
                                    // a k přijdou propojit ...

                                    b_skip = false;
                                    for(m = 0;
                                       m < p_data->p_group[k].n_face_used; m ++) {
                                        if(!Check_GroupSize(&p_data->p_group[
                                           p_world->object[i].face[j].n_group],
                                           p_data->p_group[k].p_face[m],
                                           f_max_size)) {
                                            b_skip = true;
                                            continue;
                                        }
                                        if(!Add_FaceToGroup(&p_data->p_group[
                                           p_world->object[i].face[j].n_group],
                                           p_data->p_group[k].p_face[m]))
                                            return false;
                                    }
                                    // přidá všechny facy z groupu k ...

                                    if(!b_skip) {
                                        free((void*)p_data->p_group[k].p_face);
                                        p_data->p_group[k --] =
                                            p_data->p_group[-- p_data->n_group_num];
                                    }
                                    // smaže group, pokud v něm nic nezůstalo

                                    break;
                                }
                            }
                        }
                        // hledá, jestli patří ještě do nějakého groupu ...

                        break;
                    }
                }
            }
            // hledá jestli face patří do jednoho (více) groupů ...

            if(!b_found) {
                if(!p_data->p_group) {
                    p_data->n_group_num = 1;
                    if(!(p_data->p_group = (Group*)malloc(sizeof(Group))))
                        return false;
                } else {
                    if(!(p_data->p_group = (Group*)realloc(p_data->p_group,
                       sizeof(Group) * ++ p_data->n_group_num)))
                        return false;
                }
                // realokuje groupy ...

                p_data->p_group[p_data->n_group_num - 1].n_id =
                    p_data->n_group_num - 1;
                p_data->p_group[p_data->n_group_num - 1].n_face_num = 0;
                p_data->p_group[p_data->n_group_num - 1].n_face_used = 0;
                p_data->p_group[p_data->n_group_num - 1].p_face = 0;
                //
                if(!Add_FaceToGroup(&p_data->p_group[p_data->n_group_num - 1],
                   &p_world->object[i].face[j]))
                    return false;
                p_world->object[i].face[j].n_group = p_data->n_group_num - 1;
                // přidá první face ...

                Init_Group(&p_data->p_group[p_data->n_group_num - 1]);
                // spočítá vektory
            }
        }
    }
    // hledá sousedící facy

    return p_data;
}

    Je to docela jednoduché. Tak, máme tam strukturu pro group. Group bude ona skupina faců se společnou lightmapou. No a teď co to dělá ? Volá se funkce Group_Faces(), které se předá svět (předpokládá se že souřadnice jsou natransformované) a prochází se face po facu. Pro každý face se procházejí groupy a zjišťuje se, jestli v nich nebude nějaký face, na který by navazovala. Pokud ne, založí se nový group. Pokud navazuje, přidá se již do existujícího groupu a zkontroluje se, jestli právě přidaná face nespojila dva nebo víc groupů dohromady. V tom případě by se spojily. Taky se tam několikrát volá Check_GroupSize(). Ta zjišťuje, jestli je group přípustně velký. Představte si velký dům - celé patro bude mít rovnoběžné polygony podlahy a group by vyšel v podstatě stejně velký jako půdorys domu. My jsme ale omezeni nějakým maximálním rozlišením lightmap, takže musíme dělat jen tak velké groupy aby se do lightmapy bez zmenšování vešly. Check_GroupSize() vypadá takhle:


int Check_GroupSize(Group *p_group, Face *p_face, float f_max_group_size)
{
    Vector v_new_min, v_new_max, v_new_size;
    int i;

    v_new_min = p_group->v_min;
    v_new_max = p_group->v_max;
    //
    for(i = 0; i < 3; i ++) {
        if(v_new_min.x > p_face->vertex[i]->x)
            v_new_min.x = p_face->vertex[i]->x;
        if(v_new_min.y > p_face->vertex[i]->y)
            v_new_min.y = p_face->vertex[i]->y;
        if(v_new_min.z > p_face->vertex[i]->z)
            v_new_min.z = p_face->vertex[i]->z;
        //
        if(v_new_max.x < p_face->vertex[i]->x)
            v_new_max.x = p_face->vertex[i]->x;
        if(v_new_max.y < p_face->vertex[i]->y)
            v_new_max.y = p_face->vertex[i]->y;
        if(v_new_max.z < p_face->vertex[i]->z)
            v_new_max.z = p_face->vertex[i]->z;
    }
    //
    v_new_size = v_new_max;
    v_new_size.x -= v_new_min.x;
    v_new_size.y -= v_new_min.y;
    v_new_size.z -= v_new_min.z;
    if(_Dot(v_new_size, p_group->v_u) > f_max_group_size ||
       _Dot(v_new_size, p_group->v_v) > f_max_group_size) {
        if(v_new_size.x - (p_group->v_max.x - p_group->v_min.x) > .1f ||
           v_new_size.y - (p_group->v_max.y - p_group->v_min.y) > .1f ||
           v_new_size.z - (p_group->v_max.z - p_group->v_min.z) > .1f)
            return false;
        // pokud už byl moc velký, přidáním facu se nemusel zvětšit
    }
    // pokud by po přidání facu byl group už moc velký ...

    p_group->v_max = v_new_max;
    p_group->v_min = v_new_min;
    // zupdatuje rozměry ...

    return true;
    // true = face se může přidat
}

Tahle funkce používá minimální a maximální souřadnice bodů faců v groupu k určení velikosti. Při zakládání nového groupu se určí mapovací rovina. Už sme si říkali že budeme určovat pro každou skupinu faců obdélník, ležící buď rovnoběžně s rovinou xy, xz nebo yz, jenž se tak stane rovinou mapovací. Jak tuhle rovinu vybereme ? Jednoduše určíme největší složku normály nějaké z faců v groupu (v každém groupu všechny facy leží na jedné rovině) a podle toho i příslušnou rovinu. Z té určíme vektory v_u a v_v, které ukazují kterými směry se zvyšuje souřadnice u a v lightmapy. Potom lze určit velikost pomyslného obdélníku lightmapy, promítnutého do mapovací roviny jako skalární součet vektoru v_max - v_min a v_u, resp. v_v. Ještě se podíváme na funkci, která tyhle hodnoty připraví hned po vložení prvního face do groupu:


void Init_Group(Group *p_group)
{
    Vector v_new_min, v_new_max;
    float v_f[3];
    int i;

    v_f[0] = (float)fabs(p_group->p_face[0]->normal.a);
    v_f[1] = (float)fabs(p_group->p_face[0]->normal.b);
    v_f[2] = (float)fabs(p_group->p_face[0]->normal.c);
    //
    for(i = 0; i < 2; i ++) {
        if(v_f[i] > v_f[(i + 1) % 3] &&
           v_f[i] > v_f[(i + 2) % 3])
            break;
    }
    //
    p_group->n_plane = i;
    // najde největší složku normály (rovinu na kterou se bude mapovat)

    memset(&p_group->v_u, 0, sizeof(Vector));
    memset(&p_group->v_v, 0, sizeof(Vector));
    switch(p_group->n_plane) {
    case Plane_yz: // mapování po rovině yz
        p_group->v_u.z = 1;
        p_group->v_v.y = 1;
        break;
    case Plane_xz: // mapování po rovině xz
        p_group->v_u.x = 1;
        p_group->v_v.z = 1;
        break;
    default: // mapování po rovině xy
        p_group->v_u.x = 1;
        p_group->v_v.y = 1;
        break;
    }
    // najde u a v vektory mapovací roviny

    v_new_min.x = p_group->p_face[0]->vertex[0]->x;
    v_new_min.y = p_group->p_face[0]->vertex[0]->y;
    v_new_min.z = p_group->p_face[0]->vertex[0]->z;
    v_new_max.x = p_group->p_face[0]->vertex[0]->x;
    v_new_max.y = p_group->p_face[0]->vertex[0]->y;
    v_new_max.z = p_group->p_face[0]->vertex[0]->z;
    for(i = 1; i < 3; i ++) {
        if(v_new_min.x > p_group->p_face[0]->vertex[i]->x)
            v_new_min.x = p_group->p_face[0]->vertex[i]->x;
        if(v_new_min.y > p_group->p_face[0]->vertex[i]->y)
            v_new_min.y = p_group->p_face[0]->vertex[i]->y;
        if(v_new_min.z > p_group->p_face[0]->vertex[i]->z)
            v_new_min.z = p_group->p_face[0]->vertex[i]->z;
        //
        if(v_new_max.x < p_group->p_face[0]->vertex[i]->x)
            v_new_max.x = p_group->p_face[0]->vertex[i]->x;
        if(v_new_max.y < p_group->p_face[0]->vertex[i]->y)
            v_new_max.y = p_group->p_face[0]->vertex[i]->y;
        if(v_new_max.z < p_group->p_face[0]->vertex[i]->z)
            v_new_max.z = p_group->p_face[0]->vertex[i]->z;
    }
    //
    p_group->v_min = v_new_min;
    p_group->v_max = v_new_max;
    // najde min. a max. vektor faců z groupu ...
}

Funkce Add_FaceToGroup() slouží jen k přidáváni pointeru na face do seznamu groupu, případně onen seznam zvětší:


int Add_FaceToGroup(Group *p_group, Face *p_face)
{
    if(p_group->n_face_used == p_group->n_face_num) {
        if(p_group->n_face_num) {
            if(!(p_group->p_face = (Face**)realloc
               (p_group->p_face, (p_group->n_face_num + 4) * sizeof(Face*))))
                return false;
            p_group->n_face_num += 4;
        } else {
            if(!(p_group->p_face = (Face**)malloc(2 * sizeof(Face*))))
                return false;
            p_group->n_face_num = 2;
        }
    }
    // pokud je potřeba, zvětší zásobník

    p_group->p_face[p_group->n_face_used ++] = p_face;
    // přidá face

    return true;
}

Tohle by mělo být jasné. Funkce b_Same_Vertex() už byla v example na stenciů a jen porovnává dva vrcholy a b_Neighbour_Face() je taky jen mírně upravená ze stencil example. Jedinný rozdíl je, že počítá trošku precizněji odchylku rovin dvou faců pomocí rovnoběžné roviny, posunuté na jeden z vertexů testovaného facu:


int b_SameVertex(Vertex *p_vertex_a, Vertex *p_vertex_b)
{
    float f, d;

    f = (p_vertex_a->x - p_vertex_b->x);
    f *= f;
    d = (p_vertex_a->y - p_vertex_b->y);
    f += d * d;
    d = (p_vertex_a->z - p_vertex_b->z);
    // vzdálenost mezi vrcholy
    
    return ((f + d * d) < 0.01f);
}

int n_ClassifyVertex(Plane t_plane, Vertex *p_vertex)
{
    float f;

    if((f = p_vertex->x * t_plane.a + p_vertex->y * t_plane.b +
       p_vertex->z * t_plane.c + t_plane.d) > .1f)
        return 1;
    else if(f < -.1f)
        return -1;
    return 0;
}

int b_Neighbour(Face *p_face_a, Face *p_face_b)
{
    int n_edge_a, n_edge_b;
    int n_edge_c, n_edge_d;
    Plane t_plane;

    t_plane = p_face_a->normal;
    t_plane.d = -(p_face_a->normal.a * p_face_b->vertex[0]->x +
          p_face_a->normal.b * p_face_b->vertex[0]->y +
          p_face_a->normal.c * p_face_b->vertex[0]->z);

    if(n_ClassifyVertex(t_plane, p_face_b->vertex[1]) ||
       n_ClassifyVertex(t_plane, p_face_b->vertex[2]))
        return false;
    // facy neleží v rovině

    t_plane = p_face_b->normal;
    t_plane.d = -(p_face_b->normal.a * p_face_a->vertex[0]->x +
          p_face_b->normal.b * p_face_a->vertex[0]->y +
          p_face_b->normal.c * p_face_a->vertex[0]->z);

    if(n_ClassifyVertex(t_plane, p_face_a->vertex[1]) ||
       n_ClassifyVertex(t_plane, p_face_a->vertex[2]))
        return false;
    // facy neleží v rovině (znova)

    for(n_edge_a = 0; n_edge_a < 3; n_edge_a ++) {
        n_edge_b = (1 + n_edge_a) % 3;
        // indexy vertexů hrany (a, b)

        for(n_edge_c = 0; n_edge_c < 3; n_edge_c ++) {
            n_edge_d = (n_edge_c + 1) % 3;
            // indexy vertexů druhé hrany (c, d)

            if((b_SameVertex(p_face_a->vertex[n_edge_a],
                            p_face_b->vertex[n_edge_c]) &&
               b_SameVertex(p_face_a->vertex[n_edge_b],
                            p_face_b->vertex[n_edge_d])) ||
               (b_SameVertex(p_face_a->vertex[n_edge_a],
                            p_face_b->vertex[n_edge_d]) &&
               b_SameVertex(p_face_a->vertex[n_edge_b],
                            p_face_b->vertex[n_edge_c])))
                return true;
        }
    }
    // zjišťuje sousední facy

    return false;
}

Výsledkem volání popisovaných funkcí je, že se všechny facy spojí do groupů ve kterých budou mít společnou lightmapu. Jak to vypadá se můžete podívat na obrázku, kde každá barva znamená příslušnost k nějakému groupu:

lightmap groups
Facy v groupech

    Když teď máme facy rozdělený po skupinkách, nebylo by od věci dokončit mapování lightmap. Co máme ? Máme minimální a maximální souřadnici našeho pomyslného obdélníku, máme vektory které ukazují kudy půjde osa u a v. Pomocí toho jsme už schopní dopočítat souřadnice lightmap v jednotlivých facech a spočítat pozici každého texelu lightmapy ve worldspace. Založíme si další strukturu a hurá na to:


struct Mapping_Info {
    Vector v_org;
    Vector v_u, v_v;
    //
    float f_width;
    float f_height;
    //
    int n_plane;
};
// informace o tom, kde která lightmapa leží


Mapping_Info *Generate_Map_Coords(Group_Data *p_group_data)
{
    Mapping_Info *p_map_info;
    Vector v_min, v_max;
    Vector v_u, v_v;
    Group *p_group;
    int i, j, k;

    if(!(p_map_info = (Mapping_Info*)malloc(p_group_data->n_group_num *
       sizeof(Mapping_Info))))
        return 0;
    // počet prvků vraceného pole je stejný jako počet groupů

    for(i = 0; i < p_group_data->n_group_num; i ++) {
        p_group = &p_group_data->p_group[i];

        v_min.x = p_group->p_face[0]->vertex[0]->x;
        v_min.y = p_group->p_face[0]->vertex[0]->y;
        v_min.z = p_group->p_face[0]->vertex[0]->z;
        v_max = v_min;
        //
        for(j = 0; j < p_group->n_face_used; j ++) {
            for(k = 0; k < 3; k ++) {
                if(v_min.x > p_group->p_face[j]->vertex[k]->x)
                    v_min.x = p_group->p_face[j]->vertex[k]->x;
                if(v_min.y > p_group->p_face[j]->vertex[k]->y)
                    v_min.y = p_group->p_face[j]->vertex[k]->y;
                if(v_min.z > p_group->p_face[j]->vertex[k]->z)
                    v_min.z = p_group->p_face[j]->vertex[k]->z;
                //
                if(v_max.x < p_group->p_face[j]->vertex[k]->x)
                    v_max.x = p_group->p_face[j]->vertex[k]->x;
                if(v_max.y < p_group->p_face[j]->vertex[k]->y)
                    v_max.y = p_group->p_face[j]->vertex[k]->y;
                if(v_max.z < p_group->p_face[j]->vertex[k]->z)
                    v_max.z = p_group->p_face[j]->vertex[k]->z;
            }
        }
        // najde min a max souřadnice

        p_map_info[i].v_org = v_min;
        // počáteční vrchol (pomáhá zjistit, kde leží jaký bod na lightmapě)

        v_u = p_group->v_u;
        v_v = p_group->v_v;
        // u a v vektory mapovací roviny

        p_map_info[i].n_plane = p_group->n_plane;
        // rovina, na které se mapuje ,,,

        p_map_info[i].f_width = _Dot(v_max, v_u) - _Dot(v_min, v_u);
        p_map_info[i].f_height = _Dot(v_max, v_v) - _Dot(v_min, v_v);
        // může se použít normálně mínus, protože vždycky
        // bude aktivní jen jedna souřadnice. normálně by
        // se použila vzdálenost dvou vektorů. jinak počítá
        // šířku a výšku (už 2D) mapovacího obdélníku

        p_map_info[i].v_u = v_u;
        p_map_info[i].v_v = v_v;
        // vektory hran

        for(j = 0; j < p_group->n_face_used; j ++) {
            for(k = 0; k < 3; k ++) {
                p_group->p_face[j]->vertex[k]->lu =
                    ((p_group->p_face[j]->vertex[k]->x - v_min.x) * v_u.x +
                    (p_group->p_face[j]->vertex[k]->y - v_min.y) * v_u.y +
                    (p_group->p_face[j]->vertex[k]->z - v_min.z) * v_u.z) /
                    p_map_info[i].f_width;
                p_group->p_face[j]->vertex[k]->lv =
                    ((p_group->p_face[j]->vertex[k]->x - v_min.x) * v_v.x +
                    (p_group->p_face[j]->vertex[k]->y - v_min.y) * v_v.y +
                    (p_group->p_face[j]->vertex[k]->z - v_min.z) * v_v.z) /
                    p_map_info[i].f_height;
            }
        }
        // spočítá koordináty lightmapy ve všech vertexech faců, patřících do groupu
    }

    return p_map_info;
}

    ... abych to trošku vysvětlil. Naše funkce Generate_Map_Coords() dostane pole všech groupů a jejich počet a pro každý group vygeneruje strukturu ve které jsou uložené informace o lightmapě, o jejím počátku v_org ve 3D světě (počátek = levý horní roh) a dva vektory v_u a v_v, které ukazují kterými směry se zvyšuje souřadnice u a v, které jsme už spočítali při vytváření groupů. Potom je tam také šířka a výška (f_width a f_height) obdélníku ve worldspace.
    Potom už jen vezmeme každý vrchol každého face v groupu a jednoduše se jeho souřadnice promítnou do obdélníku lightmapy a určí se u a v. (vzhledem k tomu že obdélník leží rovnoběžně se souřadnými rovinami a není nějak natočený je to triviální úloha, ale ani kdyby nebyl by se už ten kód moc nezměnil) Teď máme svoje obdélníkové textury (on to občas vyjde čtverec, ale opravdu ne moc často), ale my potřebujeme textury o velikosti mocnin dvou, co s tím ? Jednoduše vezmeme větší texturu (třeba 1024x1024) a do ní uložíme všechny textury. Pokud se nevejdou do jedné, uděláme jich víc ...
    Jak na to ? No, nemusíme nad tím moc přemýšlet. Nejjednodušší nápad je udělat pole hodnot, které bude znázorňovat nejvyšší zaplněný řádek textury. Pokud chceme vložit texturu, musíme najít takové místo, kde součet nejvyššího použitého řádku s výškou lightmapy je menší, než výška textury. Pokud se tam lightmapa vejde, naplníme pole novou hodnotou nejvyššího použitého řádku. Je to jednoduché, ale nějak mi to nejde vysvětlit, třeba to pochopíte ze zdrojáku:


struct TLightmapTex {
    int n_width, n_height;
    //
    int *p_frontline;
    //
    unsigned __int32 *p_bytes;
};
// informace o vlastních texturách

TLightmapTex *p_Lightmap(int n_width, int n_height)
{
    TLightmapTex *p_lightmap;

    if(!(p_lightmap = (TLightmapTex*)malloc(sizeof(TLightmapTex))))
        return 0;
    // naalokuje data pro lightmapu ...

    p_lightmap->n_width = n_width;
    p_lightmap->n_height = n_height;
    // nastaví rozměry lightmapy ...

    if(!(p_lightmap->p_frontline = (int*)malloc(n_width * sizeof(int))))
        return 0;
    memset(p_lightmap->p_frontline, 0, n_width * sizeof(int));
    // naalokuje a vynuluje data pro vkládání dílků ...

    if(!(p_lightmap->p_bytes = (unsigned __int32*)malloc(n_width *
       n_height * sizeof(unsigned __int32))))
        return 0;
    memset(p_lightmap->p_bytes, 0, n_width * n_height * sizeof(unsigned __int32));
    // naalokuje buffer pro texely a vymaže ho ...

    return p_lightmap;
}

int b_InsertTile(int n_width, int n_height, TLightmapTex *p_lightmap,
                 int *p_x, int *p_y, Matrix *p_coord_transform)
{
    int i, j, n_max;

    n_width += 2;
    n_height += 2;
    // přidáme každé lightmapě jednopixelový rámeček ...

    if(n_width > p_lightmap->n_width || n_height > p_lightmap->n_height)
        return false;
    // nevejde se ...

    for(i = 0, j = 0, n_max = 0; i < p_lightmap->n_width; i ++) {
        if(p_lightmap->p_frontline[i] + n_height >= p_lightmap->n_height) {
            n_max = 0;
            j = 0;
            continue;
        } else {
            if(n_max < p_lightmap->p_frontline[i])
                n_max = p_lightmap->p_frontline[i];
            j ++;
        }
        // hledá, jestli dílek nebude přesahovat z lightapy,
        // zároveň hledá nejvyšší uložený dílek v oblasti ...

        if(j == n_width) {
            for(*p_x = (i -= j - 1); i < (*p_x) + j; i ++)
                p_lightmap->p_frontline[i] = n_max + n_height;
            // vyplní data kde bude další dílek ...

            *p_y = n_max;
            // souřadnice kde bude dílek uložen ...

            (*p_x) ++;
            (*p_y) ++;
            // posuneme o jeden pixel doprava a dolů,
            // aby dílek byl uprostřed svého rámečku

            n_width -= 2;
            n_height -= 2;

            Matrix_Init(p_coord_transform);
            //
            (*p_coord_transform)[0][0] *= (float)n_width /
                (float)p_lightmap->n_width;
            (*p_coord_transform)[0][1] *= (float)n_width /
                (float)p_lightmap->n_width;
            (*p_coord_transform)[0][2] *= (float)n_width /
                (float)p_lightmap->n_width;
            //
            (*p_coord_transform)[1][0] *= (float)n_height /
                (float)p_lightmap->n_height;
            (*p_coord_transform)[1][1] *= (float)n_height /
                (float)p_lightmap->n_height;
            (*p_coord_transform)[1][2] *= (float)n_height /
                (float)p_lightmap->n_height;
            //
            (*p_coord_transform)[3][0] = (float)(*p_x - .5f) /
                (float)p_lightmap->n_width;
            (*p_coord_transform)[3][1] = (float)(*p_y - .5f) /
                (float)p_lightmap->n_height;
            // vytvoří matici, která se použije
            // k přetransformování souřadnic do nové lightmapy

            return true;
        }
    }
    // hledá kam by se mohla lightmapa vejít ...

    return false;
}

    Tak. Máme svoji strukturu, která obsahuje rozměry textury, potom p_frontline, což je pole s nejvyššími použitými řádky (pro každý sloupec rastru jedna hodnota) a nakonec vlastní obrazová data, o která se tady celou dobu snažíme. Potom je tam funkce p_Lightmap(), která jen naalokuje strukturu takže nás nezajímá. Zato další funkce nás zajímat bude.
    b_InsertTile() se pokusí vložit obdélníček o nějaké výšce a šířce. Pomocí parametrů vrací pozici, kam obdélníček umístila a návratová hodnota funkce znamená true - vešel se a false - nevešel se. Funguje tak, že prochází pole frontline, hledá nejvyšší použitý řádek a kontroluje, jestli se nám sem náš obdélníček ještě vleze. Zároveň odpočítává počet sloupců a kontroluje, jestli nám to už nestačí. Pokud se objeví sloupec, nad který už nevyjdeme, vynuluje počítadlo sloupců a začíná znovu od dalšího. Nakonec buď zjistíme že se nevejdeme nikam a vyskočíme, nebo se vejdeme a máme naše x y souřadnice.
    Teď přijde na řadu jedna věc - budeme chtít lightmapu filtrovat. Filtr ale potřebuje předchozí (další) texely pro správnou interpolaci, takže uděláme okénko o jeden pixel větší na každé straně (+= 2 na začátku funkce).
    Vyplníme tedy oblast kde bude naše textura za obsazenou a spočítáme transformační matici pro souřadnice lightmapy. Ona je totiž naše lightmapa namapovaná tak, že souřadnice [0, 0] je v jednom rohu mapovacího obdélníku a [1, 1] je v protějším. Teď ale náš obdélník přenášíme do textury a potřebujeme souřadnice jednak někam posunout a také trochu zmenšit. Pro řešení jsem zvolil matici, protože je to (doufám) pro vás dobře pochopitelné. Touhle maticí tedy později natransformujeme všechny souřadnice lightmap (= u, v) v groupu, který jsme právě přidali.
    Teď už máme konkrétní souřadnice v rastru takže nám nic nebrání sáhnout po raytraceru a spočítat vlastní lightmapy. Nebudeme vymýšlet žádné složitosti. Napíšeme lambertovu rovnici, vyhodíme jeden paprsek pro zjištění, jestli světlo bude vidět a přičteme ambient. Výsledná funkce vypadá takhle:


void Raytrace_Tile(Group *p_group, Mapping_Info *p_mapping_info, World *p_world,
                   int n_x, int n_y, int n_h, int n_w, int n_p_w,
                   unsigned __int32 *p_buffer, unsigned __int32 n_ambient)
{
    Vector v_texel_pos;
    Vector v_pos_v;
    float r, g, b;
    Vector v_ray;
    int x, y;
    float a;
    int j;

    for(y = 0; y < n_h; y ++) {
        v_pos_v = p_mapping_info->v_org;
        v_pos_v.x += p_mapping_info->v_v.x * (float)y /
            (float)n_h * p_mapping_info->f_height;
        v_pos_v.y += p_mapping_info->v_v.y * (float)y /
            (float)n_h * p_mapping_info->f_height;
        v_pos_v.z += p_mapping_info->v_v.z * (float)y /
            (float)n_h * p_mapping_info->f_height;
        //
        for(x = 0; x < n_w; x ++) {
            v_texel_pos.x = p_mapping_info->v_u.x * (float)x /
                (float)n_w * p_mapping_info->f_width + v_pos_v.x;
            v_texel_pos.y = p_mapping_info->v_u.y * (float)x /
                (float)n_w * p_mapping_info->f_width + v_pos_v.y;
            v_texel_pos.z = p_mapping_info->v_u.z * (float)x /
                (float)n_w * p_mapping_info->f_width + v_pos_v.z;
            // spočítá pozici texelu lightmapy ve worldspace

            switch(p_mapping_info->n_plane) {
            case Plane_xy:
                v_texel_pos.z = -(v_texel_pos.x * p_group->p_face[0]->normal.a +
                                  v_texel_pos.y * p_group->p_face[0]->normal.b +
                                  p_group->p_face[0]->normal.d) /
                                  p_group->p_face[0]->normal.c;
                break;
            case Plane_xz:
                v_texel_pos.y = -(v_texel_pos.x * p_group->p_face[0]->normal.a +
                                  v_texel_pos.z * p_group->p_face[0]->normal.c +
                                  p_group->p_face[0]->normal.d) /
                                  p_group->p_face[0]->normal.b;
                break;
            case Plane_yz:
                v_texel_pos.x = -(v_texel_pos.y * p_group->p_face[0]->normal.b +
                                  v_texel_pos.z * p_group->p_face[0]->normal.c +
                                  p_group->p_face[0]->normal.d) /
                                  p_group->p_face[0]->normal.a;
                break;
            }
            // promítne pozici texelu z našeho obdélníku
            // do roviny, ve které leží facy ...

            r = (float)((n_ambient >> 16) & 0xff) / 256;
            g = (float)((n_ambient >> 8) & 0xff) / 256;
            b = (float)(n_ambient & 0xff) / 256;
            // tady by neměly být nuly, ale ambient ...

            for(j = 0; j < p_world->n_light_num; j ++) {
                v_ray.x = p_world->light[j].v_position.x - v_texel_pos.x;
                v_ray.y = p_world->light[j].v_position.y - v_texel_pos.y;
                v_ray.z = p_world->light[j].v_position.z - v_texel_pos.z;
                //
                a = - p_group->p_face[0]->normal.a * v_ray.x +
                    - p_group->p_face[0]->normal.b * v_ray.y +
                    - p_group->p_face[0]->normal.c * v_ray.z;
                a /= _Len(v_ray);
                // spočítá úhel, který svírá vektor texel - světlo s normálou

                if(a <= 0)
                    continue;

                if(a > 0 && (/*!p_world->light[j].b_cast_shadows ||*/
                   Cast_Ray(p_world->light[j].v_position, v_texel_pos, p_world))) {
                    a = (a > 1)? p_world->light[j].f_multiplier :
                        p_world->light[j].f_multiplier * a;
                    // započítá násobič světla (možnost 3ds)

                    r += p_world->light[j].v_color.x * a;
                    b += p_world->light[j].v_color.y * a;
                    g += p_world->light[j].v_color.z * a;
                    // spočítá světlost
                }
                // pokud bude světlo vidět, a buď
                // nevrhá stíny, nebo na texelu není stín
            }
            // počítá světlost ...

            r = (r > 1)? 255 : r * 255;
            g = (g > 1)? 255 : g * 255;
            b = (b > 1)? 255 : b * 255;
            // sjede rgb do <0, 1>

            p_buffer[(x + n_x) + (y + n_y) * n_p_w] =
                ((int)r << 16) + ((int)g << 8) + (int)b;
            // převede barvu do RGB a uloží do příslušného dílku v textuře ...
        }
    }
}

    Raytrace_Tile() dostane group, mapovací informace, geometrii, pozici v rastru (a šířku rastru, abychom mohli počítat index), vlastní buffer textury a ambientní světlo. Na začátku každé smyčky se spočítá část souřadnice ve worldspace, a to pomocí počátku obdélníku a vektorů v_u a v_v. To je ale pozice právě na tom obdélníku. Pokud si ale dobře pamatujete, některé facy můžou být skloněné, lae obdélník leží vždy rovnoběžně s nejbližší souřadnou rovinou, takže je třeba dopočítat rozdíl pomocí řešení rovnice roviny. Potom už je tam jen smyčka pro každé světlo, kde se spočítá Lambertova rovnice, pokud vyjde nějaká světlost tak se vystřelí paprsek a určí se, jestli je pixel lightmapy ve stínu. Nakonec se hodnoty ořežou do intervalu <0, 255> a uloží se do rastru. Tím máme hotové generování lightmap a pomalu přejdeme na jejich zobrazování.

lightmap texture page
Hotová textura

    Než to ale uděláme, ještě musím připomenout abyste nezapomněli vyplnit jednopixelový rámeček okolo lightmapy hodnotami z ní, aby jsme neměli v rozích zvláštní hodnoty. Je také dobré lightmapu trošku rozmazat, vypadá potom líp, ale nesmí se to přehánět, jinak začnou být vidět hrany kde lightmapa kvůli rozmazání nenavazuje.

LtmUtil

 počítadlo lightmap

    Počítadlo pracuje s kódem, který jsem tady popsal, pouští se z příkazové řádky, kde první parametr musí být název .3ds světa s vloženými světly (nebo i bez, to je jedno - jen nebude nic vidět), Další parametry můžou být "-axxxxxx", kde "xxxxxx" je hexadecimálí číslo, určující ambient barvu. Dál "-qx" kde "x" je float násobek velikosti lightmap oproti světu (.5 je dobrá hodnota), nebo "-rx" kde "x" je rozlišení stránek lightmap (já jsem používal 512) a nakonec "-bx" kde "x" je poloměr rozmazávání (0 = bez rozmazání) ... Program si chvíli chroustá a potom zapíše lightmapy jako bitmapy a přepíše kompletně celou geometrii, protože k ní přibyly souřadnice lightmap (.3ds pak už není potřeba). Teď si ukážeme jak lightmapy kreslit. V zásadě na tom není nic těžkého, ale jsme v software renderingu a vzhledem k tomu, že lightmapy můžou být dost velké textury a můžou obsahovat dost širokou škálu barev, rozhodl jsem se že je nemůžeme dát do palety a dělat bilineární filtrování jako u textur ... Proto se naučíme jeden trik, kterému se říká dithering.


Dithering

    Dithering je anglicky rozptylování. Co to znamená ? My nebudeme počítat nové barvy pomocí pomalé interpolace, kterou jsme si předtím spočítali do tabulky barev, ale prostě rozházíme podobné barvy do různých vzorů tak, že ve výsledku se bude oku zdát že plocha byla vyplněna novou barvou. Tahle technika je dost jednoduchá a taky rychlá. Výsledek vypadá asi takhle:

dithered lightmap
Dithering lightmapy

Tohle je hodně přiblížené a je vidět, jak se ze dvou sousedních pixelů skládají různé vzory, které z větší vzdálenosti vypadají jako plynulý barevný přechod. Jak na to ? Potřebujeme znát nějakou ditherovací tabulku. Tabulek je víc (ony jsou generované stejným způsobem, jen čím větší tabulka, tím komplikovanější vzory) Já jsem někde vyhrabal tabulku 4x4. Co taková tabulka obsahuje ? Obsahuje desetinná čísla od nuly do jedné, systematicky rozházená po tabulce. Těmito čísly budeme vychylovat souřadnici lightmapy. V závislosti na čem ? Na pozici na obrazovce. Slyšíte správně ! Budeme sledovat pozici každého pixelu na obrazovce a podle toho určíme hodnotu z tabulky. Někdo může říct: "No jo, ale my máme jednu tabulku a potřebujeme vychylovat dvě souřadnice !" To je pravda. Potřebujeme ještě jednu tabulku, která vznikne jednoduchým převrácením pořadí hodnot z první tabulky. Myslím že už jsem to vysvětlil dost, abyste pochopili zdroják:


int dither_u[] = {
    (int)(0 / 15.0 * 0x10000),    (int)(14 / 15.0 * 0x10000),
    (int)(3 / 15.0 * 0x10000),    (int)(13 / 15.0 * 0x10000),
    (int)(11 / 15.0 * 0x10000),    (int)(5 / 15.0 * 0x10000),
    (int)(8 / 15.0 * 0x10000),    (int)(6 / 15.0 * 0x10000),
    (int)(12 / 15.0 * 0x10000),    (int)(2 / 15.0 * 0x10000),
    (int)(15 / 15.0 * 0x10000),    (int)(1 / 15.0 * 0x10000),
    (int)(7 / 15.0 * 0x10000),    (int)(9 / 15.0 * 0x10000),
    (int)(4 / 15.0 * 0x10000),    (int)(10 / 15.0 * 0x10000)
};
// tabulka s koeficienty pro dithering (hodnoty jsou fixed point)

int dither_v[] = {
    (int)(10 / 15.0 * 0x10000),  (int)(4 / 15.0 * 0x10000),
    (int)(9 / 15.0 * 0x10000),    (int)(7 / 15.0 * 0x10000),
    (int)(1 / 15.0 * 0x10000),    (int)(15 / 15.0 * 0x10000),
    (int)(2 / 15.0 * 0x10000),    (int)(12 / 15.0 * 0x10000),
    (int)(6 / 15.0 * 0x10000),    (int)(8 / 15.0 * 0x10000),
    (int)(5 / 15.0 * 0x10000),    (int)(11 / 15.0 * 0x10000),
    (int)(13 / 15.0 * 0x10000),    (int)(3 / 15.0 * 0x10000),
    (int)(14 / 15.0 * 0x10000),    (int)(0 / 15.0 * 0x10000)
};
// ta sama s opacnym poradim


static void __fastcall Interpolate_Segment_Bilerp(int u1, int du, int v1, int dv,
    int lu1, int ldu, int lv1, int ldv,
    unsigned __int32 *video, unsigned __int32 *v2, int x, int y)
{
    register int frac, tex;

    y = (y & 3) << 2;
    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

        frac = y | (x & 3);
        tex = _lightmap[(((lu1 + dither_u[frac]) >> 16) & LA_1) +
            (((lv1 + dither_v[frac]) >> LB_1) & LA_2)];
        *video = ((((*video & 0xff0000) * (tex & 0xff) & 0xff000000) |
                  (((*video & 0x00ff00) * ((tex >> 8) & 0xff)) & 0x00ff0000) |
                  (((*video & 0x0000ff) * ((tex >> 16) & 0xff))) & 0x0000ff00)) >> 8;
        // osvětlí ...

        video ++;
        x ++;
        // nova pozice

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

Na začátku máme svoje tabulky. Našel jsem tabulky s koeficienty 1 - 15, takže jsem je vydělil šestnácti, aby vzniklo desetinné číslo a vynásobil 0x10000 abych měl desetinné číslo ve fixed pointu. Funkce pod tabulkami je naše upravená texturovací smyčka, která bilineárně filtruje texturu, potom spočítá index v ditherovací tabulce a přičte ho k souřadnicím lightmapy. Po určení barvy lightmapy moduluje výslednou barvu pixelu a pokračuje dál ...
    Example umí přepínat mezi třemi módy filtrování: textura i lightmapa ditheringem (F9), textura bilineárně a lightmapa ditheringem (F10) a nakonec jsem napsal i pomalejší funkci, která bilineárně filtruje jak lightmapu tak texturu (F11). Výsledek ale není tak rozdílný, jak by se dalo očekávat:

bilinear-filtered lightmap
bilineárně zfiltrované lightmapy

dithered lightmap
ditherované lightmapy

dithered lightmap with quincunx
ditherované lightmapy s quincunxem - téměř nepoznáte že to není bilineární filtr

    Co říct nakonec ? Snad jen že se omlouvám, pokud jsem někde nechal nějakou chybku. Jsou tři dny před vánocema a já jsem fakt ve skluzu, potřebuju dodělat ještě dva tutorialy a přeložit tři do angličtiny. Ještě jsem plánoval změnu designu, ale to by bylo na úkor vzhledu ... Takže si stáhněte ještě engine, kterej vypočítaný lightmapy používá:

S-buffer lightmap 2

 S-buffer lightmap 2

no a zase někdy ...

    -tHE SWINe-

zpět


Valid HTML 4.01!
Valid HTML 4.01