c++ - BSP 树是否适用于单个透明对象？

我一直在尝试实现一个三维 BSP 树来渲染透明的单个对象(立方体、带有圆柱体的盒子等)。据我了解，这应该有效，但事实并非如此，我不知道为什么。我读过的所有内容都涉及在二维或多个对象上使用 BSP 树，所以我想知道我是否只是普遍误解了 BSP 树可以应用于什么而不是在我的代码中出现错误。我在网上看了很多东西，我的代码似乎和 Bretton Wade 的(ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html)一样，所以如果有人有任何样本特别是单个对象/透明度的 BSP 代码，那会很棒。

谢谢你。

最佳答案

BSP 树可以抽象为任何 N 维空间，因为根据定义，N 维超平面会将空间一分为二。换句话说，对于 N 维空间中的给定点，它必须要么位于超平面上，要么位于超平面在 N 维空间中创建的二等分空间之一中。

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

因此，您的算法将类似于以下内容:

创建一个包含立方体中所有多边形的队列。最好将多边形随机添加到队列中，而不是按某种顺序添加。

从队列的前面弹出一个多边形……使其成为 BSP 树的“根”。

从多边形创建法线

从队列中弹出另一个多边形

测试该多边形中的所有点是否位于从根创建的法线之前或之后。

如果它们都在前面，则使该 poly 成为根的右 child 。如果它们都在后面，则使该 poly 成为根的左子节点。

如果多边形中的所有点都不在由根多边形法线定义的平面的前面或后面，那么您需要将多边形分成两部分，分别位于平面的前面和后面。对于由此拆分创建的两个新多边形，将它们添加到队列的后面，并从步骤 4 开始重复。

从队列中弹出另一个多边形。

针对根测试此多边形。由于根有一个子节点，一旦您测试了多边形是在根的前面还是后面(记住第 7 步可能需要拆分)，请针对右侧的子节点测试多边形是否在-front，或者左边的子节点，如果它在后面。如果没有子节点，那么您可以停止在树中移动，并将多边形作为该子节点添加到树中。

对于当前多边形不在前面或后面的任何子节点，您需要在第 7 步中执行拆分，然后返回到第 4 步。

不断重复这个过程，直到队列为空。

该算法的代码在概念上类似于:

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 属性进行排序的。

关于c++ - BSP 树是否适用于单个透明对象？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9949484/