Will BSP trees work on single, transparent objects?

BSP trees can be abstracted into any N-dimensional space, since by definition an N-dimensional hyperplane bisects the space into two parts. In other words, for a given point in N-dimensional space, it must either be on a hyperplane or in one of the dividing spaces created by a hyperplane in N-dimensional space.

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

So your algorithm will be something like this:

• Create a queue containing all the polices from the cube. It would be better to randomly add the policies to the queue rather than in some order.
• Put poly at the front of the queue ... make it the "root" of the BSP tree.
• Create a normal one from this poly
• Get another poly out of line
• Check if all points are in this poly or before the normal one created from the root.
• If they are all in front, make this poly the correct root edge. If they are all behind, make this poly the left child of the root.
• If all the points in the poly are not in front of or behind the plane defined by the normal root polygon, then you need to split the poly in two for the parts that are in front and behind the plane. For the two new policies created from this split, add them to the back of the queue and repeat from step 4.
• Get another poly out of line.
• Test this poly against the root. Since the root has a child, once you check if the poly is at the beginning or behind the root (given step 7, which may require splitting), check the poly against the child node that is on the right if it is in front, or the child node on the left if he's behind. If there is no child node, you can stop navigating the tree and add a polygon relative to the tree as that child.
• For any child node you run into the current poly is not in front or back, you need to do the split in step # 7 and then go back to step 4.
• Keep repeating this process until the queue is empty.

The code for this algorithm conceptually looks like this:

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

      

        
        
        
      

    

After you finish creating the tree, you can search in tree order and get the polygons sorted from the back. It doesn't matter if the objects are transparent or not, as you are sorting based on the policies themselves, not their material properties.