Czech Welcome Guff Coding 3D - Engine Guestbook Links Downloads About author Mail me Mailform
box_en 3D Engine 6 - BSP-Trees box_en

Hi ! I don't know what to tell you ... wait ... welcome to our great 3d show ! That was terrible. Doesn't matter ... So i hope you liked previous part about z-buffer and texturing ... So today we'll have look at BSP - trees.
What's such tree ? BSP extends to Binary Space Partition (trees). The word binary means two. So each space is divided into two sub-spaces. How ? By a plane. When you try connect it with tree, you find it quite useful. We have root (whole space), it has two nodes (front and back subspace) and each node ... Here is some directory structure, looking like BSP (i had to format my harddisc. well, i didn't have to, but i did, because i like you ... ;P)) :

binary tree

Now i should tell you how to create such a tree ...

Growing BSP-Tree

It's simple i told you you have to subdivide space into two halfs by some plane. What plane should that be ? It should be such a plane to make tree as small as possible. You should know that subdivision proceeds until the subspace is empty (ie. all polygons are lying on subdividing planes in their respective subspace) So it should cut as few polygons as possible and it should divide them approximately in half (unbalanced tree would be bigger) A real-life situation :

bsp partitioning

On fig.1 there's our 2D room with pillar. Fig.2 shows same room, ideally subdivided - no surfaces are split and tree is quite small. (every surface is in one subspace and lying on it's own plane) Fig.3 shows situation that should possibly generate our algorithm (we are going to design it) You can see it will try to find such a surface (= face / polygon), whose plane seems to be best splitting plane. It will split some polygons, but it will be still a very good sollution. It would be nearly impossible to try every possible plane, because each world would contain quite a lot of them (ok, not every plane, but every plane, defined by some three vertices of the world ...) Now we have to write some algorithm for finding our splitting polygon.


Split polygon selection

You see what we need to do. I already said tree must be balanced and we should reduce polygon splitting. We will simply make a loop, going over each face in our subspace and count faces that would be split by it's plane and faces, lying in front and behind that plane. Then create some score from these values and simply select the best face :


const int c_balance = 5;
const int c_split = 100;

int frontnum; // count of faces, lying in front of plane
int backnum;  // count of faces, lying behind the plane
int splitnum; // count of faces, being split by plane

int score;

/* compute all that numbers for each face */

score = abs(frontnum - backnum) * c_balance + splitnum * c_split;

We used also two constants, that tells us importance of balance hint and reduce-split hint. Polygon with the smallest score is the winner and his plane will be used for splitting his subspace. In that process all faces lying on dividing plane (including the winner) will be put into onplane list and the rest will be divided into two (front and back) subspaces.


Dividing face

We have been already doing it in clipping pyramid, but the result was polygon. We need the result to be face. It's actualy simpler than you may think :


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;
    // distances to plane for both points

    if(b - a == 0)
        return *p_v1;
    // we could solve this case, but we should
    // never get such segment to divide (both vertices are
    // on the same side in the same distance)

    t = a / (b - a);
    // compute distance ratio

    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);
    // split segment in that ratio

    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;
        }
    }
    // counts vertices, lying in front of and behind plane
    // and remembers the last one in front / back ...

    tmp.n_id = p_face->n_id;
    tmp.n_material = p_face->n_material;
    tmp.normal = p_face->normal;
    // copy some properties to new face

    if(n_f_num == 3) {
        AddFaceToList(p_face, list_front);
        poly_cnt ++;
        // everything is in front / on plane

        return 1;
    } else if(n_b_num == 3 || ((n_f_num - n_o_num) == 0)) {
        AddFaceToList(p_face, list_back);
        poly_cnt ++;
        // everything is behind / on plane

        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);
        // compute intersections and add them into global vertex list

        poly_cnt += 2;
        // there will be two more faces

        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);
        // one vertex is in front, others behind

        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);
        // compute intersections and add them into global vertex list

        poly_cnt += 2;
        // two more faces

        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);
        // one behind, others in fron of

        return 1;
    }

    return 0;
}

So, we have our Vertex and Face. But next is a Face_List - that will be structure holding list of faces (actually pointers to faces - when list grows, program call realloc and array pointer change - so this is the way to keep these pointers constant) and Vertex_List is the same. Function IntEdgePlane() computes intersection of segment, given by vertices p_v1 and p_v2 with plane p_plane. And finally in SplitPolygon() function is face p_face split (or not split when it actually doesn't intersect plane) by plane p_plane into three faces. Next parameters are front and back facelists for storing results. Algorithm simply gets numbers of vertices on each side of plane in order to classify face position and remember last front and last back vertex index. There is always one vertex lying on one side of plane and the other two on the other side of plane, so the alone vertex is always remembered as the last one. Next, the intersections are computed (based on vertices positions we know where should it lie) and new faces created (and added to list)


Creating tree itself

We should know everything to create our tree. Suppose vertices with x, y, z, u and v coordinate. (u and v are for textures) Vertices will be in one global list and faces in the other one. Every face has it's texture and precomputed plane. This all will be in root of the tree. What next do we need ? As i mentioned we should find splitting plane and then ... New nodes. We will determine from counts of faces lying in front of and behind the splitting plane if there will be any nodes and if they will, allocate memory for them. Next we take our facelist and one by one split faces nicely between nodes. New vertices, originated when splitting face are added into glogal vertex-list. (don't forget about u, v coordinates !) So we have faces split into two nodes, but what with the faces, lying onplane ? I mentioned this situation aswell. These faces will be added into an onplane list (that's his name). And that list will remain in our current node (or root) Now retype it to C. Begin with structures :


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

We will slowly go over them. Constants _Front, _Back, _Split and _OnPlane are returned by function, classifying face / plane position. Next _Have_Front_Node and _Have_Back_Node are used in BSP_Node::flags and marks if node has one, the other one or both nodes (they actually are used as masks) BSP_Material is material, for now it's only texture name. That should be new for you, but we need some kind of records on texture names, because bsp file will be standalone thus we cannot load them later from original (source) .3ds file. BSP_Node is node of the tree here is flags i mentioned above (0 - no children, 1 - has front node, 2 - has back node, 3 - both nodes). Next there are pointers to front and back child - node, plane rootpl of face, selected as splitting face and then lists of faces (face contain all face in node itself and it's subnodes and onplane contain onplane faces) and pointer to global vertexlist. (BSP_Tree::vertex) And BSP_Tree contain complete tree, that are global lists of geomethry (ie. vertices and faces), pointer to root node (node containing all faces) and list of materials we will need for texturemapping in future. We will start creating tree from 3ds-world :


#define Epsilon (0.001f)

#define _Len(A) ((float)sqrt(A.x*A.x+A.y*A.y+A.z*A.z))
// vector length

#define _Normalize(A) {float s=LEN(A); A.x/=s;A.y/=s;A.z/=s;}
// make unit vector

#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;
// cross product

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

// create BSP-tree
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;
    }
    // alloc memory for tree structure

    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);
    // copy material (= texture) names

    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");
    // create 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");
    // create face list

    for(i = 0; i < tmp->face.n_face_num; i ++)
        tmp->face.face[i]->n_id = i;
    // set unique id to every face

    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));
    // create root - node
    
    level = 0;
    mx_level = 0;
    poly_cnt = tmp->face.n_face_num;
    poly_done = 0;
    nod_num = 0;
    CreateNode(tmp->root);
    // recursively create next subnodes

    printf("\n    ? Done [%d secs, %d nodes, %d faces, %d width]\n",
       (clock() - start) / CLOCKS_PER_SEC, nod_num, poly_cnt, mx_level);
    // print info on elapsed time, polygon counts ...

    return tmp;
}

It's code, preparing the root of the tree. Every data structure is copied (vertices should be transformated by it's object matrices since BSP-tree will be static and it will be in fact single object) Also memory for first node (root) is allocated. The global variables are current height of tree, maximal achieved height of tree, number of faces, number of processed faces and number of processed nodes. You should already know all the macros, aparts from _Epsilon, that's maximal variance that is taken as zero (mainly for classifying face (vertex) / plane position) Yes - and the strange characters '', '', '' are dos graphic characters, you'll see it in console. Now some interesting stuff :


int CreateNode(BSP_Node *nod)
{
    nod_num ++;
    level ++;
    if(level > mx_level)
        mx_level = level;
    // add one to our level, compute maximal level (= height of tree)

    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;
    // alloc memory for subnodes

    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) { // node is convex so stop right here
        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));
    // find splitting plane ...

    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;
    // split space across our splitting plane

    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;
        }
    }
    // create front node

    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;
        }
    }
    // create back node

    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 --;
    // go one level down

    return 1;
}

At the beggining is done some level computing, then memory for subnodes is allocated (as process goes trough, the info on what's current level, polygon and node counts is plotted onto the screen) Then splitting plane is found, if result is -1, it means node is convex, so next subdividing is useless (convex means all faces are lying on one side of the other's faces planes - that's a bit bad told - simply when you would create next nodes, for example the front ones would be always empty and in the back ones would be always one face less - imagine BSP for sphere) Next function PartitionSpace() is called to split polygons between subnodes. After that, subnodes (if some) are recursively created. Now describe 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]);
    }
    // draw "jerkying" line
}

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;
    // compute plane equation

    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;
        }
    }
    // counts numbers of vertices in front of, behind and on plane

    // evaluate result
    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;
    // clear variables for seeking best face

    n_tot_f_num = 0;
    n_tot_b_num = 0;
    n_tot_s_num = 0;
    // using these variables will determine if node is convex

    for(i = 0; i < nod->face.n_face_num; i ++) {
        n_f_num = 0;
        n_b_num = 0;
        n_s_num = 0;
        // clear counters ...

        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;
            }
        }
        // count faces in front of, behind and on plane

        n_tot_f_num += n_f_num;
        n_tot_s_num += n_s_num;
        n_tot_b_num += n_b_num;
        // add to totals

        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;
        }
        // compute score and compare with best

        UpdateStatus();
    }

    if(n_tot_s_num == 0 && (n_tot_f_num == 0 /*|| n_tot_b_num == 0*/))
        return -1;
    // node is convex (it's spheroid / cuboid / planoid ...)

    return n_min_i;
}

First UpdateStatus() - function for printing rotating dash (since creating tree can last quite long it's good to know if it's stuck or it's doing something) Next there are simple functions for classifying vertex (face) relative position to plane. Function FindRootPoly() itself counts polygons on all sides of plane and the ones to split. At the same time add results to total sums of polygons, helping to tell if node is convex (it's convex if all polygons are lying on one side and there are no splits) It actually will be convex or concave or none of that. It depends on direction we want to draw (front-to-back or back-to-front) which one we allow to skip creating next node - so it will be necessary to modify this part ! Then actual score is computed, compared with the previous one and sometimes updated. Then do rotating dash. On the end of function, convexity test is made and -1 or splitting face index is returned. This will be propably the slowest possible way to find splitting face.
I know one more method for doing that - it was invented by Paul Nettle aka. Midnight (hope i'm not wrong). The face planes are put into so called gauss map (groups, divided by normal and sorted by prependicular distance from zero) and then in each group the plane with best balance is found. (since planes are sorted, you can use quick algorithm of interval halving or another name Newton search) From these best planes the one with fewest splits is selected as splitting plane. It will be quite faster, but it assumes some faces have the same normal vector (ie. parallel planes), but when considering common quake level, most of surfaces are prependicular to itself.
But back to our algorithm. Now we're missing only PartitionSpace() :


int PartitionSpace(BSP_Node *nod)
{
    int i;

    Init_FaceList(&nod->front->face);
    Init_FaceList(&nod->back->face);
    Init_FaceList(&nod->onplane);
    // set facelists empty

    nod->flags = 0;
    // set flags to "no children"

    for(i = 0; i < nod->face.n_face_num; i ++) {
        // take a face and classify it's position to splitting plane
        switch(ClassifyFacePl(&nod->rootpl, nod->face.face[i])) {
        case _OnPlane:
            AddFaceToList(nod->face.face[i], &nod->onplane);
            // it's onplane (=> will remain
            // in parent node as "OnPlane")
            break;
        case _Front:
            AddFaceToList(nod->face.face[i], &nod->front->face);
            nod->flags |= _Have_Front_Node;
            // it's in front of it
            // simultaneously sets flag "have front subnode"
            break;
        case _Back:
            AddFaceToList(nod->face.face[i], &nod->back->face);
            nod->flags |= _Have_Back_Node;
            // it's behind the plane
            // simultaneously sets flag "have back subnode"
            break;
        case _Split:
            // it's split - so split it, new faces add to subnodes ...
            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;
            // set flags "have both subnodes" ...
            break;
        default:
            return 0;
        }
        UpdateStatus();
        // rotating dash
    }

    return 1;
}

On the beginning the facelists are set clear, flags is set to zero (no subnodes) and faces are subdivided into their respective facelists. At the same time, flags are updated. It's simple.
I won't tell you how does facelists work, because it's really simple aswell as file writing / loading routines. If you find something difficult, just mail me or get some book about C.
By now, we should have everything we need to write the very basic BSP-compiller. You can download source codes, compille exe and watch the spinning dash ! (when debugging my first BSP, i even dreamed about it !)

BSP compiller

 BSP Compiller


Basic BSP tree ussage

If you are keen on games, you may know that lots of games are using BSP's. But it's a bit different (but offen) way than we will do today. We will use BSP-tree for sorting surfaces in order to be drawn correctly. For example Quake, Unreal or Half-life are using precomputed visibility sets (PVS) The BSP is taken to generate convex zones. Based on spawnpoint locations (that's where player is born) select zones where player can reach. From the other ones remove all the geometry (this part is called hidden surface removal, guess why ...) Then for each zone take all possible viewing points and determine which other zones are visible from it. So when drawing, you almost exactly knows that all of the faces you draw will be visible. This is ideal, because it elliminates overdraw so we can use Z-buffer. (almost all older games (Quake I, Unreal I and Half-life I) were using S-buffer as I'm going to tell you in next part) But there is one more way to use BSP tree. For example Descent (I, II) used portal - based rendering. You generate zones again, but you don't compute PVS, but create potrals. They're areas, connecting zones so when rendering, the area (and it's contents) containing camera was drawn. Then visible portal was taken and next area was drawn recursively, but clipped by that portal's edges. This method will make zero overdraw (assuming only BSP is drawn - ie. no objects, etc ...), but it's hard to make hardware accelerated (ok, i could use stencil buffer and clipping planes, but PVS will be faster - and simpler)
Now back to our source again. So we will use it to sort surfaces. When drawing with Z-buffer, we could only check if something was drawn before (it will be more likely C - coverage buffer) and when screen is full we can stop drawing. That's not bad, but for now we will show only simple BSP traversal :


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

That was the very basic ussage of BSP. It will draw polygons back to front. If you'd like to switch the order, you will have to swap order of sub-node drawing in both branches (or invert the condition) The rest will be just like paither's algorithm : clip, transform, rasterize. I won't go deeper now since you should be able to understand that. Here is source for BSP - engine :

BSP-Engine

 BSP Engine


Positives and negatives of BSP

The certain disadvantage is polygon overdraw. Next disadvantage is that world is static. Moving things can't be part of BSP. So what did it bring us ? We can tell where camera is very fast and we can do very fast raytracing. That's all - if you have pure BSP, but when using portals or PVS, it will be significant boost. It could be also used with some algorithm for visibility determination (hardware Z-buffer or S-buffer / C-buffer) for more speed-up. Something on S-Buffer in next part ...


Variants of BSP

We just described BSP-trees, but it's not the only sort of spatial subdivision. Very common are OcTrees (Octal) - world is in cube, it will have eight sub-cubes (divided in half by x, y and z - axis) That is useful when world doesn't contain any good surfaces for splitting (for example terrain ...) There are KD-trees, they are just like BSP, but dividing planes will be always prependicular to one of coordinate axes (x, y / z).
For BSP-trees - today we used BSP - tree with onplane lists, but for PVS is used so called leaf BSP. It focuses on faces inside of node, not just onplanelists. But more on that later when writing some PVS based OpenGL engine ... bye !

Yes, people - write your opinion about pages, my terrible english ... Should i translate also comments in source codes ??

    -tHE SWINe-

back


Valid HTML 4.01!
Valid HTML 4.01