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. 从多边形创建法线
4. 从队列中弹出另一个多边形
5. 测试多边形中的所有点是在从根创建的法线的前面还是后面
6. 如果它们都在前面，那么使多边形成为根的右子。如果他们都落后了，那么让poly成为根的左子
7. 如果多边形中的所有点都不在由根多边形法线定义的平面的前面或后面，则需要将多边形拆分为平面前面和后面部分的两部分。对于从此拆分创建的两个新多边形，将它们添加到队列的后面，然后从步骤#4开始重复
8. 从队列中弹出另一个多边形
9. 对照根部测试这个多边形。由于根有一个子节点，一旦测试poly是在根的前面还是后面（请记住步骤#7，这可能需要拆分），请根据右边的子节点测试poly（如果它在前面），或者根据左边的子节点（如果它后面）测试poly。如果没有子节点，则可以停止在树中移动，并将多边形作为该子节点添加到树中
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);
    }
}

一旦完成了树的创建，就可以按顺序搜索树，并将多边形从后向前排序。对象是否透明并不重要，因为排序是基于多边形本身，而不是它们的材质属性。