Funktionieren BSP-Bäume an einzelnen, transparenten Objekten?

Question

Ich habe versucht, einen dreidimensionalen BSP-Baum zu implementieren, um einzelne Objekte (ein Würfel, eine Box mit einem Zylinder darin usw.) transparent darzustellen. Soweit ich verstehe, sollte das funktionieren, aber es ist nicht, und ich kann nicht herausfinden, warum. Alles, was ich gelesen habe, bezieht sich darauf, dass der BSP-Baum entweder in zwei Dimensionen oder auf mehreren Objekten verwendet wird. Daher habe ich mich gefragt, ob ich im Allgemeinen missverstanden habe, auf welche BSP-Bäume ich einen Fehler habe. Ich habe viele Dinge online angeschaut und mein Code scheint derselbe zu sein wie Bretton Wade (ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html), also wenn jemand irgendwelche Beispiele hat von BSP-Code für einzelne Objekte/insbesondere Transparenz, das wäre wunderbar.

Vielen Dank.

Answer 1

BSP Bäume können eine N-dimensionale Hyperebene einen Raum in zwei Teile wird halbiert, da definitionsgemäß einen N-dimensionalen Raum abstrahiert werden. Mit anderen Worten, für einen gegebenen Punkt im N-dimensionalen Raum muss er entweder auf der Hyperebene oder in einem der halbierten Räume sein, die die Hyperebene im N-dimensionalen Raum erzeugt.

Für 2D würde ein BSP-Tree durch Ziehen einer Linie erstellt werden, und dann war ein Punkt zu testen, auf welcher Seite dieser Linie. Dies liegt daran, dass eine Linie einen 2D-Raum halbiert. Für 3D benötigen Sie eine Ebene, die normalerweise von der Normalen zu der Polygonfläche gebildet wird, die Sie als Test verwenden.

So würde Ihr Algorithmus so etwas wie die folgenden sein:

1. eine Warteschlange Erstellen Sie alle Polys aus dem Cube enthält. Es wäre am besten, die Polys nach dem Zufallsprinzip und nicht in einer bestimmten Reihenfolge zur Warteschlange hinzuzufügen.
2. Pop einen Poly aus der Vorderseite der Warteschlange ... Dies ist die „Wurzel“ des Baumes BSP machen.
3. Erstellen eines normalen von diesem Poly
4. andere Poly aus der Warteschlange Pop
5. Testen, ob alle Punkte in diesem poly sind vor oder hinter dem normalen von der Wurzel erstellt.
6. Wenn sie all in-Front sind, dann machen, dass das rechte Kind des Wurzel Poly. Wenn sie alle dahinter sind, mach das Poly zum linken Kind der Wurzel.
7. Wenn alle Punkte in der Poly sind nicht vor oder hinter der Ebene, die durch die Wurzel definiert Polygons normal, dann müssen Sie das Poly in zwei Teile für die Teile spalten, das in-Front und hinter dem Flugzeug. Fügen Sie für die zwei neuen Polys, die aus dieser Aufteilung erstellt wurden, diese der Rückseite der Warteschlange hinzu und wiederholen Sie den Vorgang ab Schritt 4.
8. Pop ein anderes Poly aus der Warteschlange.
9. Testen Sie diese Poly gegen die Wurzel. Da die Wurzel ein Kind hat, testen Sie, sobald Sie testen, ob die Poly vor oder hinter der Wurzel ist (unter Berücksichtigung von Schritt 7, der eine Teilung erfordern könnte), die Poly gegen den Kindknoten, der sich rechts befindet -front oder der Kind-Knoten auf der linken Seite, wenn er dahinter ist. Wenn kein untergeordneter Knoten vorhanden ist, können Sie sich nicht mehr durch den Baum bewegen und das Polygon wie der untergeordnete Baum hinzufügen.
10. Für jedes Kind-Knoten Sie laufen in dem der Strom Poly nicht-vor oder hinter, werden Sie die Spaltung in Schritt # 7 und dann zurück 4 # gehen durchführen müssen, um Schritt.
11. Wiederholen Sie diesen Vorgang, bis die Warteschlange leer ist.

-Code für diesen Algorithmus konzeptionell etwas aussehen würde: Suche nach dem Baum

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); 
    } 
} 

Sobald Sie die Erstellung des Baums abgeschlossen haben, können Sie dann tun, um eine in Ordnung und die Polygone erhalten von hinten nach vorne sortiert. Es spielt keine Rolle, ob die Objekte transparent sind oder nicht, da Sie nach den Polys selbst sortieren, nicht nach ihren Materialeigenschaften.