Will BSP trees work on single, transparent objects?

Question

I've been trying to implement a three dimensional BSP tree to render single objects (a cube, a box with a cylinder in it, etc.) which are transparent. As far as I understand, this should work, but it is not, and I can't figure out why. Everything I've read refers to BSP tree being used in either two dimensions or on multiple objects, so I was wondering if I've just generally misunderstood what BSP trees can be applied to rather than had an error in my code. I've looked at a lot of things online, and my code seems to be the same as Bretton Wade's (ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html), so if anybody has any samples of BSP code for single objects/transparency in particular, that would be wonderful.

Thank you.

Answer 1

BSP trees can be abstracted to any N-dimensional space since by definition a N-dimensional hyperplane will bisect a space into two parts. In other words, for a given point in N-dimensional space, it must either be on the hyperplane, or in one of the bisected spaces that the hyperplane creates in the N-dimensional space.

For 2D, a BSP tree would be created by drawing a line, and then testing on what side of that line a point was. This is because a line bisects a 2D-space. For 3D, you would need a plane, which would typically be formed from the normal to the polygonal surface that you're using as the test.

So your algorithm would be something like the following:

1. Create a queue containing all the polys from the cube. It would be best to randomly add the polys to the queue rather than in some order.
2. Pop a poly from the front of the queue ... make this the "root" of the BSP tree.
3. Create a normal from that poly
4. Pop another poly from the queue
5. Test whether all the points in that poly are in front of or behind the normal created from the root.
6. If they are all in-front, then make that poly the right-child of the root. If they are all behind, make that poly the left-child of the root.
7. If all the points in the poly are not in front or behind the plane defined by the root polygon's normal, then you'll need to split the poly into two parts for the portions that are in-front and behind the plane. For the two new polys created from this split, add them to the back of the queue, and repeat from step #4.
8. Pop another poly from the queue.
9. Test this poly against the root. Since the root has a child, once you test whether the poly is in-front or behind the root (keeping in mind step #7 that may require a split), test the poly against the child node that is on the right if it's in-front, or the child node on the left if it's behind. If there is no child-node, then you can stop moving through the tree, and add the polygon as to the tree as that child.
10. For any child node you run into where the current poly is not in-front or behind, you'll need to perform the split in step #7 and then go back to step #4.
11. Keep repeating this process until the queue is empty.

Code for this algorithm would conceptually look something like:

struct bsp_node
{
    std::vector<poly_t> polys;
    bsp_node* rchild;
    bsp_node* lchild;

    bsp_node(const poly_t& input): rchild(NULL), lchild(NULL)
    {
       polys.push_back(input);
    }
};

std::queue<poly_t> poly_queue;
//...add all the polygons in the scene randomly to the queue

bsp_node* bsp_root = new bsp_node(poly_queue.front());
poly_queue.pop();

while(!poly_queue.empty())
{
    //grab a poly from the queue
    poly_t current_poly = poly_queue.front();
    poly_queue.pop();

    //search the binary tree
    bsp_node* current_node = bsp_root;
    bsp_node* prev_node = NULL;
    bool stop_search = false;

    while(current_node != NULL && !stop_search)
    {
        //use a plane defined by the current_node to test current_poly
        int result = test(current_poly, current_node);

        switch(result)
        {
            case COINCIDENT:
                stop_search = true;
                current_node->polys.push_back(current_poly);
                break;

            case IN_FRONT: 
                prev_node = current_node;
                current_node = current_node->rchild;
                break;

            case BEHIND: 
                prev_node = current_node;
                current_node = current_node->lchild;
                break;

            //split the poly and add the newly created polygons back to the queue
            case SPLIT:
                stop_search = true;
                split_current_poly(current_poly, poly_queue);
                break;
        }
    }

    //if we reached a NULL child, that means we can add the poly to the tree
    if (!current_node)
    {
        if (prev_node->rchild == NULL)
            prev_node->rchild = new bsp_node(current_poly);
        else
            prev_node->lchild = new bsp_node(current_poly);
    }
}

Once you've completed the creation of the tree, you can then do an in-order search of the tree and get the polygons sorted from back-to-front. It won't matter if the objects are transparent or not, since you're sorting based on the polys themselves, not their material properties.