Was ist die kd-Baumschnittlogik?

Ich versuche herauszufinden, wie man einen KD-Baum implementiert.

Auf Seite 322 von "Echtzeit-Kollisionserkennung" von Ericson

Der Textabschnitt ist unten enthalten, falls Sie ihn in der Google Buchvorschau nicht sehen können, wenn Sie auf den Link klicken

Textabschnitt

Relevanter Abschnitt:

Die Grundidee, einen Strahl oder ein gerichtetes Liniensegment mit einem kd-Baum zu schneiden, ist einfach. Die Linie wird gegen die Teilungsebene des Knotens geschnitten, und der t-Wert der Schnittmenge wird berechnet. Befindet sich t innerhalb des Intervalls der Linie, 0 <= t <= tmax, so überspannt die Linie die Ebene, und beide untergeordneten Elemente des Baums werden rekursiv herabgestuft. Wenn nicht, wird nur die Seite mit dem Segmentursprung rekursiv besucht.

Folgendes habe ich also: ( Bild in neuem Tab öffnen, wenn der Schriftzug nicht zu sehen ist)

Der logische Baum

Hier geht der orange Strahl durch die Szene 3d. Die x repräsentieren den Schnittpunkt mit einer Ebene. Von LINKS trifft der Strahl:

• Die Vorderseite des umgebenden Würfels der Szene,
• Die (1) Teilungsebene
• Die (2.2) Aufteilungsebene
• Die rechte Seite des umgebenden Würfels der Szene

Aber hier ist, was passieren würde, naiv nach Ericsons grundlegender Beschreibung oben:

• Gegen Spaltfläche (1) prüfen. Der Strahl trifft auf die Teilungsebene (1), sodass die linken und rechten Kinder der Teilungsebene (1) in den nächsten Test einbezogen werden.
• Test gegen Spaltfläche (2.1). Ray trifft tatsächlich dieses Flugzeug (weit rechts), sodass beide Kinder in die nächste Teststufe einbezogen werden. (Dies ist kontraintuitiv - sollte nicht nur der untere Knoten in nachfolgenden Tests enthalten sein)

Kann jemand beschreiben, was passiert, wenn der orangefarbene Strahl die Szene korrekt durchläuft?

Es ist wirklich ziemlich einfach; Der Test gegen die Teilungsebene (2.1) sollte aus folgenden Gründen fehlschlagen:

Wenn der Strahl die Teilungsebene (1) trifft, "teilen" Sie den Strahl, oder; Sie legen den tGültigkeitsbereich fest und fahren mit den resultierenden Teilen im Baum fort.

Wenn Sie also gegen Ebene (2.1) prüfen, sollten Sie prüfen, ob sich nur der Teil des Strahls, der von Ebene (1) übrig ist, mit Ebene (2.1) schneidet, was nicht der Fall ist. Der Schnittpunkt "weit rechts", von dem Sie sprechen, hat einen t> tWert, bei dem Sie den Strahl mit der Ebene teilen (1).

Ich hoffe das ist klar genug.

Zusammenfassung: Nachfolgende Schnittpunkte zwischen Strahl und Ebene sollten nur mit dem Teil des Strahls durchgeführt werden, der nach dem Teilen mit der betreffenden Ebene übrig bleibt.