c++ - 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. 如果它们都在前面，则使该多边形成为根的右 child 。如果它们都落后，则使该多边形成为根的左 child 。
7. 如果多边形中的所有点都不在由根多边形的法线定义的平面的前面或后面，那么您需要将多边形分成两个部分，即平面的前面和后面的部分。对于从此拆分创建的两个新多边形，将它们添加到队列的后面，并从步骤 #4 开始重复。
8. 从队列中弹出另一个 poly。
9. 针对根测试此多边形。由于根有一个 child ，一旦您测试多边形是在根的前面还是后面(记住可能需要拆分的第 7 步)，请根据右侧的子节点测试多边形，如果它在-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);
    }
}

一旦您完成了树的创建，您就可以对树进行按顺序搜索并从后到前对多边形进行排序。对象是否透明并不重要，因为您是根据多边形本身而不是它们的 Material 属性进行排序。