BSP樹會在單個透明物體上工作嗎？

Question

我一直在嘗試實現一個三維BSP樹來渲染單個對象（一個立方體，一個圓柱體的盒子等），它們是透明的。據我瞭解，這應該工作，但它不是，我不明白爲什麼。我讀過的所有東西都是指BSP樹在兩個維度或多個對象中使用，所以我想知道是否我一般誤解了BSP樹可以應用到什麼地方，而不是在我的代碼中出現錯誤。我在網上查了很多東西，我的代碼看起來和布雷頓韋德的一樣（ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html），所以如果任何人有任何樣本BSP代碼單個對象/特別是透明度，這將是美好的。

謝謝。

Answer 1

BSP樹可以抽象到任何N維空間，因爲根據定義，N維超平面會將空間平分爲兩部分。換句話說，對於N維空間中的給定點，它必須位於超平面上，或者在超平面在N維空間中創建的一個二分空間中。

對於2D，可以通過繪製一條線來創建一個BSP樹，然後在該線的哪一側進行測試。這是因爲一條線平分了二維空間。對於3D，您需要一個平面，這通常是從法線到您用作測試的多邊形曲面形成的。

所以，你的算法將是類似以下內容：

1. 創建一個包含所有從立方體的多邊形的隊列。最好將隨機數添加到隊列中，而不是按照某種順序。
2. 從隊列的前面彈出一個poly ...將它作爲BSP樹的「根」。
3. 從聚
4. 創建一個正常從隊列
5. 測試彈出另一聚在於聚所有的點是否是在前面或後面從根產生的正常。
6. 如果它們都在前面，那麼將該多邊形作爲根的右孩子。如果他們都在後面，將這個多邊形作爲根的左孩子。
7. 如果多邊形中的所有點不在前面或後面，那麼您需要將多邊形分爲兩部分，分別位於平面前後的部分。對於從該分割創建的兩個新的多邊形，將它們添加到隊列的後面，並從步驟＃4開始重複。
8. 從隊列中彈出另一個poly。
9. 測試這個聚對根。由於root有一個孩子，所以一旦你測試了poly是在前面還是在根後面（記住步驟＃7可能需要拆分），對於右邊的子節點測試poly，如果它在如果它位於後面，則位於左側的子節點。如果沒有子節點，則可以停止在樹中移動，並將該多邊形添加到樹中作爲該子節點。
10. 對於任何子節點，如果您碰到當前poly不在前或後的位置，則需要在步驟＃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); 
    } 
} 

一旦你完成了樹的創建，然後你可以做一個有序的搜索樹，並獲得多邊形從後到前排序。這些對象是否透明並不重要，因爲您基於聚合物本身進行排序，而不是它們的材料屬性。