3

私は、3次元のBSPツリーを実装して、透明な単一のオブジェクト（立方体、円柱が入ったボックスなど）をレンダリングしようとしています。私の知る限り、これはうまくいくはずですが、そうではなく、その理由がわかりません。私が読んだものはすべて、BSPツリーが2次元または複数のオブジェクトで使用されていることを示しているため、コードにエラーがあるのではなく、BSPツリーを適用できるものを一般的に誤解しているのではないかと思いました。私はオンラインで多くのことを調べましたが、私のコードはBretton Wade（ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html）と同じように見えるので、誰かがサンプルを持っている場合特に単一オブジェクト/透明性のためのBSPコードの、それは素晴らしいでしょう。

ありがとうございました。

4

1 に答える 1

6

定義上、N次元超平面は空間を2つの部分に二分するため、BSPツリーは任意のN次元空間に抽象化できます。言い換えると、N次元空間の特定の点については、超平面上にあるか、超平面がN次元空間に作成する二等分された空間の1つにある必要があります。

2Dの場合、BSPツリーは、線を描画し、その線のどちら側にポイントがあるかをテストすることによって作成されます。これは、線が2D空間を二等分するためです。3Dの場合、平面が必要になります。平面は通常、テストとして使用しているポリゴンサーフェスの法線から形成されます。

したがって、アルゴリズムは次のようになります。

  1. 立方体のすべてのポリゴンを含むキューを作成します。ある順序ではなく、ランダムにポリゴンをキューに追加するのが最善です。
  2. キューの先頭からポリゴンをポップします...これをBSPツリーの「ルート」にします。
  3. そのポリから法線を作成します
  4. キューから別のポリゴンをポップします
  5. そのポリゴン内のすべてのポイントが、ルートから作成された法線の前または後ろにあるかどうかをテストします。
  6. それらがすべて前面にある場合は、そのポリゴンをルートの右の子にします。それらがすべて遅れている場合は、そのポリをルートの左子にします。
  7. ポリゴン内のすべてのポイントが、ルートポリゴンの法線によって定義された平面の前または後ろにない場合は、平面の前と後ろの部分について、ポリゴンを2つの部分に分割する必要があります。この分割から作成された2つの新しいポリゴンについて、それらをキューの最後に追加し、手順4から繰り返します。
  8. キューから別のポリゴンをポップします。
  9. このポリをルートに対してテストします。ルートには子があるため、ポリゴンがルートの前にあるか後ろにあるかをテストしたら（分割が必要になる可能性があるステップ＃7に注意してください）、右側にある子ノードに対してポリをテストします。 -前、または後ろにある場合は左側の子ノード。子ノードがない場合は、ツリー内の移動を停止し、その子としてツリーにポリゴンを追加できます。
  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);
    }
}

ツリーの作成が完了したら、ツリーを順番に検索して、ポリゴンを後ろから前に並べ替えることができます。オブジェクトが透明であるかどうかは関係ありません。これは、マテリアルのプロパティではなく、ポリゴン自体に基づいて並べ替えているためです。

于 2012-03-30T20:05:16.190 に答える