BSP树是否可以在单个透明物体上工作？

Question

我一直在尝试实现一个三维BSP树来渲染单个对象(一个立方体,一个带有圆柱体的盒子等),这些对象是透明的.据我所知,这应该有效,但事实并非如此,我无法弄清楚原因.我读过的所有内容都指的是在两个维度或多个对象中使用的BSP树,所以我想知道我是否只是误解了可以应用哪些BSP树而不是在我的代码中出错.我在线查看了很多内容,我的代码与Bretton Wade(ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html)相同,所以如果有人有任何样本特别是单个对象/透明度的BSP代码,这将是美妙的.

谢谢.

Answer 1

BSP树可以被抽象到任何N维空间,因为根据定义,N维超平面将空间分成两部分.换句话说,对于N维空间中的给定点,它必须位于超平面上,或者在超平面在N维空间中创建的一个二等分空间中.

对于2D,将通过绘制一条线来创建BSP树,然后测试该点的哪一侧.这是因为一条线将二维空间平分.对于3D,您需要一个平面,该平面通常由您用作测试的法线到多边形表面形成.

所以你的算法将类似于以下内容:

1. 创建一个包含多维数据集中所有多边形的队列.最好将多边形随机添加到队列中,而不是按某种顺序.
2. 从队列的前面弹出多边形...使其成为BSP树的"根".
3. 从该poly创建法线
4. 从队列中弹出另一个多边形
5. 测试该多边形中的所有点是否位于从根创建的法线的前面或后面.
6. 如果它们都在前面,那么将poly作为根的右子.如果它们都落后了,那么将poly作为根的左子.
7. 如果多边形中的所有点都不在根多边形法线定义的平面的前面或后面,那么您需要将多边形分成两部分,用于前面和后面的平面部分.对于从此拆分创建的两个新多边形,将它们添加到队列的后面,并从步骤#4开始重复.
8. 从队列中弹出另一个多边形.
9. 根据root测试此poly.由于root有一个子节点,一旦你测试poly是在前面还是在后面(请记住步骤#7可能需要拆分),测试poly对照右边的子节点,如果它在-front,如果它在后面,则为左侧的子节点.如果没有子节点,则可以停止在树中移动,并将多边形作为该子项添加到树中.
10. 对于任何子节点,您遇到当前多边形不在前面或后面的位置,您需要在步骤#7中执行拆分,然后返回到步骤#4.
11. 继续重复此过程,直到队列为空.

该算法的代码在概念上看起来像:

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

完成树的创建后,您可以对树进行有序搜索,并从后到前对多边形进行排序.对象是否透明无关紧要,因为您要根据多边形本身进行排序,而不是它们的材质属性.