Swine'z pages

English Welcome Kecy Programování 3D - Engine Guestbook Odkazy Downloady
 
O autorovi Napiš mi Mailform
box_cz 3D - Engine 06 - BSP-Stromy box_cz
Ahoj ! Tak jsem tu zase s dalším pokračováním seriálu o 3d-enginech. Jak se vám líbil poslední program na Z-Buffer ? Doufám, že aspoň trochu jo.. Pochopili jste tu texturovací smyčku ? Minule jsem to dodělával na poslední chvíli a tak už jsem to moc nevysvětlil. No nic.. Tak se podíváme na ty BSP_Stromy. Co to takový strom je ? Přesně to, co znamená zkratka : Binary Space Partitioning Trees. V překladu to je : "Stromy binárně dělící prostor". A protože všichni víme, co to je binární, víme jak vypadají BSP_Stromy. Nebo nevíme ? Binární znamená dvojkové. No a už je jednoduché to domyslet - v binárním stromu má prostě každá větev dvě děti. Abych to vysvětlil, tak jako každý strom se skládá z kořene, kde je svět celý a potom z větví, kde jsou jednotlivé části světa. Abych to rozepsal : Každá větev (Node), nebo i kořen (Root) může mít další dvě větve : Front a Back. Mám tu pro vás malou ukázku, kvůli které jsem musel naformátovat disk :-) :


tree


Tak a teď si řekneme jak takový strom vytvořit.


Vytváření BSP-Stromu

To se dělá tak, že se vezme polygon, jehož rovina dělí prostor na dvě půlky, které by měly být zhruba stejně velké a podle ní se svět rozdělí na části ležící před a za rovinou, přičemž polygony, ležící v obou prostorech musí být rozděleny. S každou půlkou se pak provede to samé (rekurzivně) až dokud nejsou polygony na řazení, nebo netvoří konvexní útvar (potom by byly všechny polygony vždycky na jedné straně). Dáme si malý příklad takového stromu. Obyčejně je to místnost s jedním pilířem, tak to použijeme taky :


bsp-example


Na obr.1 je naše (2D) místnost s pilířem uprostřed. Na obr.2 je stejná místnost, rozdělená ideálním způsobem : První rovina (třeba šikmá zleva doprava) dělí svět na dvě stejné půlky. Každá půlka je pak rozdělena další rovinou (šikmou zprava doleva) na opět stejné půlky. Výška stromu potom bude dvě a nepřibudou nám žádné polygony, vzniklé dělením. No a konečně třetí obrázek je to, co udělá náš BSP-Kompilátor. Roviny vedou od pilíře (leží na jeho polygonech) a dělí zdi místnosti. Možná se ptáte, proč to nejde tak jako na obr.2 ? Je to proto, že neexistuje žádný způsob, jak najít takovou rovinu v prostoru (pokud v daném případě vůbec existuje..) , a tak nám nezbývá, než se s tím smířit.


Výběr root polygonu

Jak je vidět, musíme vybrat polygon, který by definoval rovinu, nejlépe splňující naše požadavky. Jednoduše uděláme smyčku, která projde svět a pro každý face určí počet faců, ležících před jeho rovinou, za jeho rovinou a ty, co jsou jeho rovinou děleny. (To se udělá tak, že se proti rovině kandidáta na rootpoly testují jednotlivé vertexy právě testovaného facu. Pokud leží všechny na jedné straně, polygon leží na té straně. Pokud ne, je třeba ho rozdělit.) Potom se spočítá jeho "skóre" : 


const int k_balance = 5;
const int k_split = 100;

int frontnum; // pocet face, lezicich "pred rovinou"
int backnum;  // pocet face, lezicich "za rovinou"
int splitnum; // pocet delenych face

int score;

/* Pocitani vsech tech cisel... */

score = abs(frontnum - backnum) * k_balance + splitnum * k_split;

Je vidět, že jsme použili ještě dvě konstanty. První (k_balance) určuje důležitost rovnováhy stromu (stejný počet polygonů na jedné a druhé straně) a druhá(k_split) určuje důležitost zachování co nejmenšího počtu polygonů. No a teď, který polygon má nejnižší skóre, vyhrál a stává se root polygonem. Teď už máme vybranou face, která určuje dělení prostoru, ale ještě neumíme rozdělit face podle roviny.


Dělení face

Když jsem řekl, že to ještě neumíme, neměl jsem docela pravdu. Umí to klipovací pyramida. Ale ta dělí face na polygon. My potřebujeme dělit face na více faců. Zkusíme to rovnou v c-čku : 


struct Plane {
    float a, b, c, d;
};

struct Vector {
    float x, y, z;
};

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

struct Face {
    int n_id, n_used;
    int n_material;
    //
    Vertex *vertex[3];
    //
    Plane normal;
};

struct Vertex_List {
    Vertex **vertex;
    int n_vertex_num;
};

struct Face_List {
    Face **face;
    int n_face_num;
};

Vertex IntEdgePlane(Vertex *p_v1, Vertex *p_v2, Plane *p_plane)
{
    float a, b, t;
    Vertex vertex;

    a = p_plane->a * p_v1->x + p_plane->b * p_v1->y +
        p_plane->c * p_v1->z + p_plane->d;
    b = p_plane->a * p_v2->x + p_plane->b * p_v2->y +
        p_plane->c * p_v2->z + p_plane->d;
    // spočítá vzdálenosti vertexů od roviny

    if(b - a == 0)
        return *p_v1;
    // singulární případ (oba leží ve stejné vzdálenosti
    // od roviny na stejné straně, nebo na rovině)

    t = a / (b - a);
    // poměr vzdáleností

    vertex.x = p_v1->x + t * (p_v1->x - p_v2->x);
    vertex.y = p_v1->y + t * (p_v1->y - p_v2->y);
    vertex.z = p_v1->z + t * (p_v1->z - p_v2->z);
    vertex.u = p_v1->u + t * (p_v1->u - p_v2->u);
    vertex.v = p_v1->v + t * (p_v1->v - p_v2->v);
    // musi se spočítat i odpovídající souřadnice textur

    return vertex;
}

int SplitPolygon(BSP_Node *p_node, Face *p_face,
    Face_List *list_front, Face_List *list_back)
{
    int i, n_f_num, n_b_num, n_o_num, n_i_front, n_i_back;
    Vertex *v_one, *v_two, v_intersection;
    Face tmp;

    n_f_num = 0;
    n_b_num = 0;
    n_o_num = 0;
    for(i = 0; i < 3; i ++) {
        switch(ClassifyVertexPl(&p_node->rootpl, p_face->vertex[i])) {
        case _Front:
            n_i_front = i;
            n_f_num ++;
            break;
        case _Back:
            n_i_back = i;
            n_b_num ++;
            break;
        case _OnPlane:
            n_i_front = i;
            n_f_num ++;
            n_o_num ++;
            break;
        }
    }
    // spočítá počty vertexů v závislosti
    // na poloze a zapamatuje si vertex
    // ležící na, před a za rovinou

    tmp.n_id = p_face->n_id;
    tmp.n_material = p_face->n_material;
    tmp.normal = p_face->normal;
    // nastaví společné vlastnosti faců

    if(n_f_num == 3) {
        AddFaceToList(p_face, list_front);
        poly_cnt ++;
        // všechno je před rovinou / na ní

        return 1;
    } else if(n_b_num == 3 || ((n_f_num - n_o_num) == 0)) {
        AddFaceToList(p_face, list_back);
        poly_cnt ++;
        // všechno je za rovinou / na ní

        return 1;
    } else if(n_f_num == 1 && n_o_num == 0) {
        v_intersection = IntEdgePlane(p_face->vertex[n_i_front],
           p_face->vertex[(n_i_front + 1) % 3], &p_node->rootpl);
        v_one = AddVertexToList(&v_intersection, p_node->vertex);
        //
        v_intersection = IntEdgePlane(p_face->vertex[(n_i_front + 2) % 3],
           p_face->vertex[n_i_front], &p_node->rootpl);
        v_two = AddVertexToList(&v_intersection, p_node->vertex);
        // spočítá průsečíky a přidá je do globálního seznamu vrcholů

        poly_cnt += 2;
        // zvýší počet polygonů o dva

        tmp.vertex[0] = p_face->vertex[n_i_front];
        tmp.vertex[1] = v_one;
        tmp.vertex[2] = v_two;
        AddFaceToList(&tmp, list_front);
        //
        tmp.vertex[0] = v_one;
        tmp.vertex[1] = p_face->vertex[(n_i_front + 1) % 3];
        tmp.vertex[2] = p_face->vertex[(n_i_front + 2) % 3];
        AddFaceToList(&tmp, list_back);
        //
        tmp.vertex[0] = p_face->vertex[(n_i_front + 2) % 3];
        tmp.vertex[1] = v_two;
        tmp.vertex[2] = v_one;
        AddFaceToList(&tmp, list_back);
        // jeden vertex je před rovinou, ostatní jsou za

        return 1;
    } else if(n_b_num == 1 && n_o_num != 2) {
        v_intersection = IntEdgePlane(p_face->vertex[n_i_back],
           p_face->vertex[(n_i_back + 1) % 3], &p_node->rootpl);
        v_one = AddVertexToList(&v_intersection, p_node->vertex);
        //
        v_intersection = IntEdgePlane(p_face->vertex[(n_i_back + 2) % 3],
           p_face->vertex[n_i_back], &p_node->rootpl);
        v_two = AddVertexToList(&v_intersection, p_node->vertex);
        // spočítá průsečíky a přidá je do globálního seznamu vrcholů

        poly_cnt += 2;
        // zvýšení počtu polygonů o dva

        tmp.vertex[0] = v_one;
        tmp.vertex[1] = p_face->vertex[(n_i_back + 1) % 3];
        tmp.vertex[2] = v_two;
        AddFaceToList(&tmp, list_front);
        //
        tmp.vertex[0] = p_face->vertex[(n_i_back + 1) % 3];
        tmp.vertex[1] = p_face->vertex[(n_i_back + 2) % 3];
        tmp.vertex[2] = v_two;
        AddFaceToList(&tmp, list_front);
        //
        tmp.vertex[0] = v_one;
        tmp.vertex[1] = v_two;
        tmp.vertex[2] = p_face->vertex[n_i_back];
        AddFaceToList(&tmp, list_back);
        // jeden vertex je za rovinou, ostatní před

        return 1;
    }

    return 0;
}

Mnno, pokusím se to trochu osvětlit. Tak Vertex je klasický 3d-vertex, Face je face a Face_List jak napovídá název je list faců (Vertex_List je to samé). Funkce IntEdgePlane() určík úsečky, definované body p_v1 a p_v2 s rovinou p_plane. No a konečně ve funkci SplitPolygon() je p_face face, kterou chceme rozdělit, p_plane je rovina, podle které se face bude dělit, front a back jsou listy faců před a za rovinou, kam se budou ukládat výsledky a vertex je seznam vertexů pro celý svět (je tam proto, že při dělení face musí vzniknout nové verterxy). A funguje to tak, že se napřed určí pozice každého bodu proti rovině a najdou se indexy bodů před za a na rovině. Podle počtů vertexů před, za a na rovině se určí, co se bude s face dělat. Potom už se využije jen naše IntEdgePlane() pro určení nových bodů a AddVertexToList() pro přidání bodu do seznamu.


Vlastní vytváření stromu

No, teď už snad umíme všechno a tak se pustíme do vytváření stromu. Takže předpokládáme že máme náš svět, v němž je každá face tvořena třemi vrcholy z nichž každý má x, y, z, u a v souřadnici. (u a v jsou pro textury) Vertexy jsou v jednom seznamu, fejsy ve druhém. Každá face má taky index textury a předpočítanou normálovou rovinu. Tak, nadefinovali jsme si vlastně kořen našeho stromu. Co teď budeme potřebovat ? Napřed musíme najít nejlepšího kandidáta na root polygon. Co to znamená jsme si už říkali. Takže procházíme svět polygon po polygonu a pro každý spočítáme kolik ostatních polygonů leží před ním, za ním a které mají vertexy na obou jeho stranách. Potom podle několika konstant a jednoduché rovnice spočítáme skóre fejsu a hledáme face s nejnižším skóre. Když ho najdeme, zapamatujeme si jeho index a naalokujeme si paměť pro nové větve. Podle počtu polygonů před a za rovinou rootu určíme, jestli bude vůbec nějaké větve mít (a které). Pak už se jen jede a seznam fejsů se pěkně rozděluje do pření a zadní nody podle toho kde leží vůči rovině rootu. Pokud je potřeba nějaký polygon rozdělit (leží na obou stranách zároveň), musíme zjistit průsečíky jeho hran s rovinou a potom se přidá jako nový bod do seznamu všech vertexů. Nesmí se zapomenout dopočítat i jeho uv souřadnice ! Samotný face se potom rozdělí na tři, protože z trojúhelníku jde udělat jen trojúhelník a čtyřúhelník, který ve světě není definovaný, a proto se musí rozdělit na dva trojúhelníky. Taky se nesmí zapomenout do nových face zkopírovat normála a textura. Takhle rozdělíme fejsy do dvou větví když leží před nebo za rovinou rootu. Ale co když leží 'na' ní ? Řešení je jednoduché : každá noda má seznam fejsů, ležících v rovině s rootem. Tak, tím jsme se vypořádali s jednou nodou a dál už se vlastně jenom volá stejná funkce pro její děti, dokud je co rozdělovat. Snad jste to pochopili. Pokud ne, napište a já vám zkusím poradit. No a pomalu přejdeme ke zdrojáku tradičního samplu. Napřed si nadefinujeme nějaké ty struktury : 


enum {
    _Front   = 0x01,
    _Back    = 0x02,
    _OnPlane = 0x04,
    _Split   = 0x08
};

enum {
    _Have_Front_Node = 0x01,
    _Have_Back_Node  = 0x02
};

struct BSP_Material {
    char name[256];
};

struct BSP_Node {
    int flags;
    struct BSP_Node *front, *back;
    int rootpoly;
    Plane rootpl;
    Face_List face, onplane;
    Vertex_List *vertex;
};

struct BSP_Tree {
    Vertex_List vertex;
    Face_List face;
    BSP_Node *root;
    int n_material_num;
    BSP_Material *material;
};

Tak si to trochu vysvětlíme. Konstanty _Front, _Back, _Split a _OnPlane jsou vraceny funkcí, která počítá polohu budu (face) proti rovině. _Have_Front_Node a _Have_Back_Node jsou v BSP_Node.flags a značí, zda má noda tu či onu větev. BSP_Material je název materiálu (textury). To je pro vás asi novota, ale jestli jste si prohlíželi 3ds loader, asi jste zjistili, že každá face má položku material a potom jsou tam jména všech materiálů, použitých ve světě. To pomáhá při nahrávání textur, protože v praxi se nenahrává každá textura ručně, ale právě tímhle způsobem. No, BSP_Node je větev stromu. Je tady už vzpomínané flags (0 - nemá děti, 1 - má front, 2 - má back a 3 - má obě děti). Potom tam jsou pointery na obě děti, potom index polygonu, který byl zvolen jako root, jeho rovina, potom listy fejsů a to všech v nodě a těch, které leží v rovině s root a pointer na list všech vertexů ve světě (ukazuje vždy do BSP_Tree.vertex). No a BSP_Tree je základ stromu, takže tam je seznam všech vertexů scény, všech fejsů původního světa (řekli jsme si, že některé fejsy se budou rozdělovat a právě ty nově vzniklé už tam nebudou - ty budou v nodách, kde vznikají dělením.) Pak je tam kořen stromu (root), který je, jak vidíte, taky větví a potom už tam jsou jen ty materiály. Budeme začínat z našeho oblíbeného 3ds souboru : 


#define Epsilon (0.001f)

#define _Len(A) ((float)sqrt(A.x*A.x+A.y*A.y+A.z*A.z))
// délka vektoru

#define _Normalize(A) {float s=LEN(A); A.x/=s;A.y/=s;A.z/=s;}
// vytvoří jednotkový vektor

#define _Cross(A,B,C) C.x = B.y*A.z-A.y*B.z; \
                      C.y = B.z*A.x-A.z*B.x; \
                      C.z = B.x*A.y-A.x*B.y;
// vektorový součin

static int level;
static int mx_level;
static int poly_cnt;
static int poly_done;
static int nod_num;

// vytvori bsp-strom z 3ds-sveta
BSP_Tree *CreateTree(World *svet)
{
    BSP_Tree *tmp;
    long start;
    Face *face;
    int i, j;

    start = clock();

    printf("   Creating BSP_Tree\n");
    if((tmp = (BSP_Tree*)malloc(sizeof(BSP_Tree))) == NULL) {
        ErrMsg("Not enough memory to create a tree structure !");

        return NULL;
    }
    // naalokuje paměť pro bsp-strom

    tmp->n_material_num = svet->n_material_num;
    if((tmp->material = (BSP_Material*)malloc
       (tmp->n_material_num * sizeof(BSP_Material))) == NULL) {
        ErrMsg("Not enough memory to create a tree structure !");
        return NULL;
    }
    for(i = 0; i < tmp->n_material_num; i ++)
        strcpy(tmp->material[i].name, svet->material[i].name);
    // zkopíruje jména materiálů (textur) ;-)

    tmp->vertex.n_vertex_num = 0;
    tmp->vertex.vertex = NULL;
    printf("    ĚÍ Creating Vertex - list  \\");
    for(i = 0; i < svet->n_object_num; i ++) {
        for(j = 0; j < svet->object[i].n_vertex_num; j ++)
            AddVertexToList(&svet->object[i].vertex[j], &tmp->vertex);
        UpdateStatus();
    }
    printf("\n");
    // vytvoří vertex - list

    tmp->face.n_face_num = 0;
    tmp->face.face = NULL;
    printf("    ČÍ Adding faces to list  \\");
    for(i = 0; i < svet->n_object_num; i ++) {
        for(j = 0; j < svet->object[i].n_face_num; j ++) {
            face = AddFaceToList(&svet->object[i].face[j], &tmp->face);
            face->vertex[0] = tmp->vertex.vertex[FindVertexInList
               (svet->object[i].face[j].vertex[0], &tmp->vertex)];
            face->vertex[1] = tmp->vertex.vertex[FindVertexInList
               (svet->object[i].face[j].vertex[1], &tmp->vertex)];
            face->vertex[2] = tmp->vertex.vertex[FindVertexInList
               (svet->object[i].face[j].vertex[2], &tmp->vertex)];
            UpdateStatus();
        }
    }
    printf("\r    ĚÍ Adding faces to list\n");
    // vytvoří face - list

    for(i = 0; i < tmp->face.n_face_num; i ++)
        tmp->face.face[i]->n_id = i;
    // přiřadí každému face id

    if((tmp->root = (BSP_Node*) malloc(sizeof(BSP_Node))) == NULL) {
        ErrMsg("Not enough memory to save a root node structure !");
        return NULL;
    }
    tmp->root->flags = 0;
    tmp->root->front = NULL;
    tmp->root->back = NULL;
    tmp->root->rootpoly = 0;
    tmp->root->vertex = &tmp->vertex;
    memcpy(&tmp->root->face, &tmp->face, sizeof(Face_List));
    // vytvoří root - node (kořen) stromu
    
    level = 0;
    mx_level = 0;
    poly_cnt = tmp->face.n_face_num;
    poly_done = 0;
    nod_num = 0;
    CreateNode(tmp->root);
    // vytváří rekurzivně další subnody

    printf("\n    ČÍ Done [%d secs, %d nodes, %d faces, %d width]\n",
       (clock() - start) / CLOCKS_PER_SEC, nod_num, poly_cnt, mx_level);
    // vytiskne jak dlouho to trvalo, počet faců ..

    return tmp;
}

Tady se vlastně připravuje kořen stromu. Zkopírují se všechny datové struktury (vertexy by se měly ještě transformovat..) a naalokuje se paměť pro první nodu - root (kořen). Ty globální proměnné na začátku jsou (popořadě) aktuální výška větve, výška stromu, počet všech faců (při dělení se zvyšuje), počet zpracovaných faců a počet větví. Makra jsou převážně na operace s vektory (délka, normalizace a vytvoření vektoru c, který je kolmý na vektory a a b) Konstanta _Epsilon určuje maximální odchylku rovnice roviny, aby se ještě uznalo že bod leží na rovině. Jo, ty divný znaky Ě, Č, Í jsou dosový znaky, bude to vidět v konzoli.. Teď přijde něco zajímavějšího : 


int CreateNode(BSP_Node *nod)
{
    nod_num ++;
    level ++;
    if(level > mx_level)
        mx_level = level;
    // počítá úroveň a výšku stromu

    printf("\r    ĚÍ Level %3d -ALC- %5d Faces [%3d%%]  ",
        level, nod->face.n_face_num, (int)(0.5 +
        (float)poly_done / (float)poly_cnt * 100));
    //
    if((nod->front = (BSP_Node*)malloc(sizeof(BSP_Node))) == NULL)
        return 0;
    //
    nod->front->vertex = nod->vertex;
    //
    if((nod->back = (BSP_Node*)malloc(sizeof(BSP_Node))) == NULL)
        return 0;
    //
    nod->back->vertex = nod->vertex;
    // alokuje paměť pro nodu, subnody

    printf("\r    ĚÍ Level %3d -FRP- %5d Faces [%3d%%]  ",
        level, nod->face.n_face_num, (int)(0.5 +
        (float)poly_done / (float)poly_cnt * 100));
    //
    nod->rootpoly = FindRootPoly(nod);
    //
    if(nod->rootpoly == -1) { // noda je konvexní
        nod->flags = 0;
        nod->onplane = nod->face;
        poly_done += nod->onplane.n_face_num;
        //
        printf("\r    ĚÍ Level %3d -BCK- %5d Faces [%3d%%]  ",
            level, nod->face.n_face_num, (int)(0.5 +
            (float)poly_done / (float)poly_cnt * 100));
        //
        level --;

        return 1;
    }
    memcpy(&nod->rootpl, &nod->face.face[nod->rootpoly]->normal, sizeof(Plane));
    // hledá root face stromu

    printf("\r    ĚÍ Level %3d -PPL- %5d Faces [%3d%%]  ",
        level, nod->face.n_face_num, (int)(0.5 +
        (float)poly_done / (float)poly_cnt * 100));
    PartitionSpace(nod);
    poly_done += nod->onplane.n_face_num;
    // rozděluje prostor podle roviny root

    if(nod->flags & _Have_Front_Node) {
        if(!CreateNode(nod->front)) {
            printf("\r    ĚÍ Level %3d -BCK- %5d Faces [%3d%%]  ",
                level, nod->face.n_face_num, (int)(0.5 +
                (float)poly_done / (float)poly_cnt * 100));
            level --;

            return 0;
        }
    }
    // vytvoří přední nodu

    if(nod->flags & _Have_Back_Node) {
        if(!CreateNode(nod->back)) {
            printf("\r    ĚÍ Level %3d -BCK- %5d Faces [%3d%%]  ",
                level, nod->face.n_face_num, (int)(0.5 +
                (float)poly_done / (float)poly_cnt * 100));
            level --;

            return 0;
        }
    }
    // vytvoří zadní nodu

    printf("\r    ĚÍ Level %3d -BCK- %5d Faces [%3d%%]  ",
        level, nod->face.n_face_num, (int)(0.5 +
        (float)poly_done / (float)poly_cnt * 100));
    level --;
    // jde o patro níž

    return 1;
}

Na začátku se zvýší úroveň ve stromu o jedno patro, naalokuje se paměť pro nody (průběžně se vypisuje informace kolik je toho hotovo a tak podobně. Pak se hledá rootpoly, když je jeho výsledek -1, znamená to že polygony v nodě tvoří konvexní útvar, takže už nemá smysl ji dál zpracovávat. Konvexní znamená že rovina žádného polygonu neprotíná jiný polygon, takže když budeme takový útvar kreslit, bude jedno v jakém pořadí polygony půjdou. (Například krychle, koule ...) Potom se funkcí PartitionSpace() rozdělí polygony mezi nody a plynule se přejde k vytváření dětí nody (pokud je má) Teď si popíšeme FindRootPoly() 


void UpdateStatus()
{
    char stat[] = "/|\\-";
    static int a = 0, b = 0;
    
    if(b ++ > 50) {
        b = 0;
        a ++;
        if(a > 3)
            a = 0;
        printf("\b%c", stat[a]);
    }
    // kreslí "mrnící" se čáru
}

int ClassifyVertexPl(Plane *p_plane, Vertex *p_vertex)
{
    float p_eq;

    p_eq = p_plane->a * p_vertex->x + p_plane->b * p_vertex->y +
           p_plane->c * p_vertex->z + p_plane->d;
    // spočítá rovnici roviny

    if(p_eq > Epsilon)
        return _Front;
    if(p_eq < -Epsilon)
        return _Back;

    return _OnPlane;
}

int ClassifyFacePl(Plane *p_plane, Face *p_face)
{
    int i, n_f_num = 0, n_b_num = 0, n_o_num = 0;

    for(i = 0; i < 3; i ++) {
        switch(ClassifyVertexPl(p_plane, p_face->vertex[i])) {
        case _Front:
            n_f_num ++;
            break;
        case _Back:
            n_b_num ++;
            break;
        default: // _OnPlane
            n_o_num ++;
            break;
        }
    }
    // spočítá počty vertexů před, za a na rovině

    // vyhodnotí výsledek
    if(n_o_num == 3)
        return _OnPlane;
    if(n_f_num == 3)
        return _Front;
    if(n_b_num == 3)
        return _Back;
    if(n_f_num + n_o_num == 3)
        return _Front;
    if(n_b_num + n_o_num == 3)
        return _Back;

    return _Split;
}

int FindRootPoly(BSP_Node *nod)
{
    int n_tot_f_num, n_tot_b_num, n_tot_s_num;
    int n_min_score, n_cur_score, n_min_i;
    int n_f_num, n_b_num, n_s_num;
    int i, j;

    n_min_i = -1;
    n_min_score = 0xffff;
    // nastaví proměnné pro hledání nejlepšího skóre

    n_tot_f_num = 0;
    n_tot_b_num = 0;
    n_tot_s_num = 0;
    // pomocí těchhle proměnných se zjistí, zda je noda konvexní

    for(i = 0; i < nod->face.n_face_num; i ++) {
        n_f_num = 0;
        n_b_num = 0;
        n_s_num = 0;
        // vynuluje počítadla

        for(j = 0; j < nod->face.n_face_num; j ++) {
            if(i == j)
                continue;
            switch(ClassifyFacePl(&nod->face.face[i]->normal,
               nod->face.face[j])) {
            case _Front:
                n_f_num ++;
                break;
            case _Back:
                n_b_num ++;
                break;
            case _Split:
                n_s_num ++;
                break;
            }
        }
        // spočítá počty faců za, před a okolo roviny

        n_tot_f_num += n_f_num;
        n_tot_s_num += n_s_num;
        n_tot_b_num += n_b_num;
        // přičte počty faců k totálnímu součtu

        n_cur_score = abs(n_f_num - n_b_num) * 5 + n_s_num * 75;
        if(n_cur_score < n_min_score) {
            n_min_score = n_cur_score;
            n_min_i = i;
        }
        // porovná skóre s minimálním

        UpdateStatus();
    }

    if(n_tot_s_num == 0 && (n_tot_f_num == 0 || n_tot_b_num == 0))
        return -1;
    // větev je konvexní (tvoří kuloid / krychloid / ..)

    return n_min_i;
}

Napřed UpdateStatus() - funkce tiskne otáčející se čáru (vytváření stromu občas trvá docela dlouho a tak je dobré vědět, že windows jsou ještě při životě). Pak tam je funkce na klasifikaci pozice bodu a fejsu proti rovině. Vlastní funkce FindRootPoly() spočítá počty polygonů na jedné straně a na druhé straně roviny a ty co jsou potřeba rozdělit. Zároveň je přičítá k totálním součtům, které pomáhají zjistit, zda je noda konvexní. To pak nejsou žádné polygony rozdělované (n_s_num = 0) a všechny leží jen na jedné straně (n_f_num = 0 a n_b_num = počet polygonů * (počet polygonů - 1) nebo naopak). Z aktuálních součtů se potom vypočítá skóre a vytiskne se motající se čára UpdateStatus(). Na konci se udělá test konvexnosti a vrátí se buď -1 (noda je konvexní) nebo index polygonu. Měl bych říct že tohle je asi nejpomalejší způsob hledání root polygonu. Jde to i jinak - polygony se na začátku uspořádají do tzv. gaussovské mapy (do skupin, rozdělených podle normály a seřazených podle vzdálenosti roviny od nuly) a potom se v každé skupině půlením intervalu najde polygon, který svět dělí na nejlepší půlky a z těch nejlepších se vybere ten s nejmenším skóre. To je o dost rychlejší, ale předpokládá to, že hodně polygonů bude ležet v rovině. (Mapy ve Quake 1 to splňovaly dokonale, protože podlaha a zdi skoro vždycky byly rovně) Teď už nám k úplnosti schází jen PartitionSpace() : 


int PartitionSpace(BSP_Node *nod)
{
    int i;

    Init_FaceList(&nod->front->face);
    Init_FaceList(&nod->back->face);
    Init_FaceList(&nod->onplane);
    // nastaví facelisty na prádné

    nod->flags = 0;
    // nastaví nodu na "bezdětnou"

    for(i = 0; i < nod->face.n_face_num; i ++) {
        // vezme face a podivá se, kde lezi
        switch(ClassifyFacePl(&nod->rootpl, nod->face.face[i])) {
        case _OnPlane:
            AddFaceToList(nod->face.face[i], &nod->onplane);
            // leží v rovine s root face (=> zůstane
            // v rodičovské nodě jako "OnPlane")
            break;
        case _Front:
            AddFaceToList(nod->face.face[i], &nod->front->face);
            nod->flags |= _Have_Front_Node;
            // leží před rovinou root facu, zároveň
            // nastaví přední větev na plnou
            break;
        case _Back:
            AddFaceToList(nod->face.face[i], &nod->back->face);
            nod->flags |= _Have_Back_Node;
            // leží za rovinou root facu, zároveň
            // nastaví zadní větev na plnou
            break;
        case _Split:
            // případně face podle roviny rozdělí na další (face, ne polygony)
            if(!SplitPolygon(nod, nod->face.face[i],
               &nod->front->face, &nod->back->face)) {
                ErrMsg("Internal program error (maybe windows found ?)");
                return 0;
            }
            nod->flags |= _Have_Front_Node;
            nod->flags |= _Have_Back_Node;
            // a označí obě větve za plné ...
            break;
        default:
            return 0;
        }
        UpdateStatus();
        // vytiskne ukazatel akce
    }

    return 1;
}

Na začátku se nastaví facelisty na prázdné, flagy aktuální nody se nastaví na 0 - nemá žádného potomka a facy se rozdělují do svých listů, když je potřeba, nechají se rozdělit. S facelisty se tady rozepisovat nebudu, to snad pochopí každý. Zase se tiskne vrtící čára, za chvíli vám poleze krkem ;-) Když jsem odlaďoval svůj první BSPátor, viděl jsem ji pak všude na zdech, na lidech a zvířatech a dokonce se mi o ní i zdálo :-). SplitPolygon() už jsme si popsali na začátku, takže můžeme přejít k použití BSP stromu. Ještě vám sem hodím link na zdrojáky kompilátoru. Pokud chcete, můžete si ho zaintegrovat do windows. Dělá se to tak, že v možnostech složky si najdete typ souboru pro příponu 3ds (většinou ho musíte vytvořit) a přidáte k němu novou akci. Do pole popis akce napíšete něco jako 'Vytvořit BSP' a do pole program napíšete třeba 'bsp_comp.exe "%1"'. To bsp_comp.exe musí být i s adresou. Pak to všechno odklikáte a když kliknete pravým tlačítkem na 3ds soubor, v menu bude položka Vytvořit BSP a když na ni kliknete tak se spustí náš program..


bsp compiller

 BSP Kompilátor


Základní použití BSP-Stromu

Možná jste si všimli že jsem vynechal část kde se zapisuje do souboru, ale tam není nic zákeřného. Celý strom se prostě v binárním módu zapíše do souboru. Pokud něco nechápete, podívejte se do učebnice v c-čku na téhle stránce a nebo mi radši napište. Možná jestli jste procházeli nějakej web o 3d-enginech a hrách, zjistili jste že BSP Stromy používají třeba Quakové, Half - Life a oblíbená Counterstrike. Nepoužívají je ale tak, jak je teď použijeme my, ale k určení viditelnosti. Vezměte si mapu. Asi tak 10000 nebo víc fejsů rozházených po prostoru. Přitom nejmíň polovina se jich nemusí kreslit, protože prostě nejsou vidět. Proto se vytvoří BSP - Strom, ale nezajímají nás polygony v rovině s root, ale polygony ležící v nodě. Potom se vytvoří tzv. sektory - jsou to vlastně obaly jednotlivých nod. Stěna každého obalu je tzv. portál. Každý portál má u sebe informaci, na které sektory navazuje. Z toho už jde renderovat. Napřed vykreslíte polygony sektoru, ve kterém je kamera a potom se rekurzivně kreslí ještě sektory, jejichž portály jsou viditelné. Tak to dělá myslím Half - Life a CS. Quake je více předpočítané. Pro každý sektor je předpočítaná sada všech potenciálně viditelných polygonů (PVS - potencial visibility set). To jsou všechny polygony, viditelné z jakéhokoli místa v sektoru. Obě metody mají své výhody a nevýhody, ale do toho se pustíme až někdy jindy. Teď jsem chtěl říct něco o základním použití BSP - Stromů. Říká se tomu 'traversal'. Je to taky rekurzivní proces, při kterém se prochází strom a při každé nodě se určuje, zda kamera je před, nebo za ní. Podle toho se určuje pořadí vykreslování polygonů tak, že se vykreslují odzadu dopředu. Takže trochu pseudo-c : 


void Traverse_Node(BSP_Node *node)
{
    if(ClassifyVtxPl(node->rootpl, viewport) == _Front) {
        if(node->flags & _Have_Back_Node)
            Traverse_Node(node->back);

        DrawPolylist(node->onplanelist);

        if(node->flags & _Have_Front_Node)
            Traverse_Node(node->front);
    } else {
        if(node->flags & _Have_Front_Node)
            Traverse_Node(node->front);

        DrawPolylist(node->onplanelist);

        if(node->flags & _Have_Back_Node)
            Traverse_Node(node->back);
    }
}

To byl základní traversal. Kreslí polygony prostě odzadu dopředu (kdybyste to chtěli zepředu, musíte prohodit kreslení back a front nody v obou podmínkách :-).) Jinak je to kreslení jako třeba u malířova algoritmu - polygony se natransformují, oklipují a kreslí. Nic na tom není, tak to snad ani nebudu komentovat. Pokud k tomu máte nějakej dotaz, namajlujte mi. Tady je okomentovanej zdroják :

bsp-engine

 BSP Engine



Nevýhody a výhody BSP

Určitou nevýhodou je překreslování polygonů. Kreslí se odzadu, takže se kreslí všechno, i to, co není vidět. Ale narozdíl od Z-Bufferu je zase rychlejší vykreslování jednotlivých polygonů, protože se neinterpoluje a neporovnává z-souřadnice. Velkou nevýhodou je rozdělování polygonů. Když se podíváte na kopmpilátor, konečný počet polygonů je i několikrát větší než v původním 3ds. Takže co BSP přinášejí ? Rychlé určení pozice kamery ve světě a jinak nic. Teda nic samy o sobě - pokud jsou použité pro PVS nebo portály, šetří hromadu času. Taky by mohly být použité s nějakým jednodušším algoritmem pro určení viditelnosti, ne z-bufferem, protože je pomalý, ale třeba takový S-Buffer, o kterém si něco pobvíme příště, nebo C-Buffer, to je potom slušné urychlení.


Různé varianty BSP

To, co jsme si popsali, jsou BSP - stromy. Existují ještě OCTrees, to jsou "oktálové" stromy. Stejně jako u BSP to znamená, že každá noda má osm dětí. Svět se napřed zabalí do krychle, která ho celý pojme a poté se ta krychle vždy rozdělí třemi rovinami na osm menších krychlí. Potom se rekurzivně vezme každá další krychle a přerozděluje se až do určitého počtu polygonů, nebo do určité úrovně přerozdělení. Tím vznikne krychloidní strom, podle kterého sice nelze kresli, jako podle BSP, ale mnohem lépe funguje pro zjišťování viditelnosti třeba v závodních hrách, kde je terén 'placka', a proto ho BSP nemá šanci přerozdělit tak dobře. Některé implementace OCTree taky pracují s kvádry a ne krychlemi. Tím se však vůbec nemusíme zabývat. Dalším bratříčkem BSP jsou KD-trees (dělící rovina je vždycky kolmá na nějakou osu - x nebo y nebo z). Ale ty vám vysvětlí někdo jiný, už je to dneska trochu moc dlouhý.

Jo, ještě lidi, napište co si o tom myslíte (o stránkách) - výklad, čeština, examplesáky ..

    -tHE SWINe-

zpět


Valid HTML 4.01!
Valid HTML 4.01