* 원본 링크 : http://www.3dtechdev.com/tutorials/leafbsp/3db1sptrees.html

• 저자 : Gerald Filimonov k9megahertz@yahoo.com
• BSP 중에서도 leaf bsp라는 방식의 아티클입니다.
  
  

Ever since Quake came out I had wanted to program a 3d engine just like I saw in the game. I learned that the Quake engine used BSP Trees to do its rendering. So I few years ago I began scouring the internet trying to find out what I could about this mysterious rendering technique. Unfortunately at that time there wasn뭪 a whole lot of good information available to figure out how to do an engine using BSP Trees. Sadly, that is still somewhat true today. Until a month ago I was still missing a few key pieces of information that would help me fully understand BSP Trees and their implementation in games such as doom and Quake. I had read the BSP FAQ until I was blue in the face. It laid out the basic principles behind BSP Trees and how to use them, but it didn't go into any great detail, which is what a beginner needs, lots of details. Fortunately a month or two ago I had finally concentrated on it enough that things were beginning to come together and I was starting to understand them more and more. It is within this text that I hope to share the knowledge I have gained in writing a simple Quake-style engine with the rest of the community. I hope that by you reading this text you will leave with a clearer and shaper understanding of BSP Trees, and even more importantly, how to use this knowledge in creating your own engine. Ill start off reviewing and explaining the content that's already out there on the Internet and build upon that.

Ok now that we've divided up the level using partition A into two separate subspaces, we need to recursively do the same with the front subspace and then the back subspace. Let's work on the front subspace first. Take a look at bsp03.gif, you'll notice we're faded the backside of partition A to show that we are focusing only on the front side of it in this step. We treat the front side like it was a level of its own and ignore everything else for now. We can see that this new subspace is not convex because there are some walls that could be used as partitions to divide the walls into front and back subspaces. Now that we're determined that we need to subdivide this subspace down further we need to select one of the walls and use it to create a partitioning line. We'll select wall 8 to use as a guide and create partitioning line B, which is shown in bsp04.gif. We then need to classify all of the walls in this subspace against partitioning line B, adding ones that are on the front side of it to the front list of walls, adding the ones that are on the back side of it to the back list of walls. Also if partitioning line B splits any walls we take care of those as well, but in this case we don't have any. Once we've added all the walls to the appropriate sides we again look at the front side of the partitioning line, (in this case and if necessary process it. Just for clarity I want to reiterate that we will only be dealing with this new front portion as if it were its own level and totally ignoring everything else for now. If we take a look at bsp05.gif we can see that the walls that make up the front area of partition B form a convex space. We can prove this by observing that no matter what wall we try to use as a new partition all the other walls are on the same side, which in this case would be the front.

struct BSP_node {
    int nodeid; //unique identification number given to the node
    Plane3d partition; //well use this to store the partitioning plane that divides our
                               //nodes up
    BSP_node *backnode; //pointer to the node that is on the back side of our partitioning plane
    BSP_node *frontnode; //pointer to the node that is on the front side of our partitioning plane
    bool leaf; //true or false value for a node saying that this node has no children and only
                   //contains polygons
    int numpolys; //number of polygons in the node, this will be 0 if the node is not a leaf
    Polygon3d *nodepolylist; //pointer to the list of polygons in the leaf node, again this list will be empty if the node is not a leaf
};

BSP_node *root;
root = (BSP_node *)malloc(sizeof(BSP_node));

BuildBSP (BSP_node *node)
{
    partplane = SelectPartitionfromList (node->nodepolylist, node->numpolys);

    if (partplane = -1 ) {
        node->leaf=true;
        return;
    }

    //Count how many polygons will end up on the front of this partition as well as on the back
    //Allocate memory for a front and back node

    //Classify each polygon in the current node with respect to the partitioning plane.

    //If it's on the front add it to the list of polygons in the front node

    //If it's on the back add it to the list of polygons in the back node

    //If it crosses the partition, split the polygon along the partition and add fragment that falls on the front of the partition to the front node, 
    //and the fragment that falls on the back to the back node

    //If its coplanar with the partition, compare the normals of the polygon with that of the partition, 
    //if they are the same add the polygon to the front node, otherwise add to the back.

    BuildBSP (node->frontnode);
    BuildBSP (node->backtnode);
}

int RenderBSP (BSP_node *node)
{

    int side;
    Vector3d Position;

    //The current position of the player/viewpoint
    Position.x=xpos;
    Position.y=ypos;
    Position.z=zpos;

    if (!node->leaf) {

        side=ClassifyPoint (&node->partition, &Position);

        if (side==CP_BACK) {
            RenderBSP (node->frontnode);
            RenderBSP (node->backnode);
        }
        else {
            RenderBSP (node->backnode);
            RenderBSP (node->frontnode);
        }
    }

    if (node->leaf) {
        //Draw polygons that are in the leaf
        }
    }
    return 1;
}