spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ich habe das schonmal gemacht.
Du suchst ja die optimale Ebene, entlang der du einen Knoten weiter unterteilst (in einen vorderen und einen hinteren Knoten).
Dazu wird für jede Ebene, die in Frage kommt, eine Kostenabschätzung gemacht. Am Ende wählt man die Ebene mit den geringsten Kosten oder hört mit der Unterteilung auf, falls alle Möglichkeiten zu höheren Gesamtkosten führen.

Die Kosten bestehen aus drei Komponenten:
- Traverse: Jede Unterteilung bedeutet später eine weitere Iteration beim Verfolgen des Strahls, die mit gewissen Kosten verbunden ist.
- Intersect: Kosten, die durch die Schnitttests Strahl vs. Dreieck entstehen.
- Empty Leaf Boost: Hiermit kann man Unterteilungen einen Bonus geben, bei denen ein leerer Kindknoten entsteht (das ist gut!).

Die Traverse-Kosten muss man einfach experimentell ermitteln oder irgendwie schätzen.
Die Intersect-Kosten werden berechnet, man muss nur wissen, wie teuer ein einzelner Schnitttest ist (ebenfalls abschätzen oder messen).
Den Empty Leaf Boost kann man ebenfalls setzen wie man will und damit die Generierung des Baums steuern.

Wie werden jetzt die Kosten für eine bestimmte Unterteilungsebene bestimmt?

Sei §A§ die Oberfläche der Bounding Box des aktuellen Knotens, dessen beste Unterteilung wir bestimmen möchten (= Summe der Flächen der 6 Seiten).

Für jede Ebene, die als Splitting-Ebene in Frage kommt, berechnest du nun:
- §A_{Front}§ = Oberfläche der Bounding Box des vorderen Kindknotens
- §A_{Back}§ = Oberfläche der Bounding Box des hinteren Kindknotens
- §N_{Front}§ = Anzahl der Dreiecke im vorderen Kindknoten
- §N_{Back}§ = Anzahl der Dreiecke im hinteren Kindknoten

Anhand dieser Werte und der Tuning-Parameter von oben kann man nun die Kosten für diese Unterteilung bestimmen.
Dabei stellt man sich die Frage: Wie wahrscheinlich ist es, dass die vordere oder hintere Box von einem beliebigen Strahl getroffen wird? Und wie teuer wäre es dann, so einen Strahl zu verarbeiten? Dabei geht man davon aus, dass der Strahl mit allen im Kindknoten enthaltenen Dreiecken geschnitten werden muss, d.h. dass man nach dieser Unterteilung nicht mehr weiter unterteilen würde. Natürlich ist das in den meisten Fällen Quatsch, aber es ist eben nur eine Heuristik.

Die Wahrscheinlichkeit, dass ein Strahl, der den Knoten trifft, auch den vorderen Kindknoten trifft, wird mit §P_{Front} = \frac{A_{Front}}{A}§ abgeschätzt, analog für den hinteren Kindknoten.
Das heißt, dass ein Strahl im Mittel zu §P_{Front} \cdot N_{Front} + P_{Back} \cdot N_{Back}§ Schnitttests führt.

Jetzt bestimmt man die Gesamtkosten wie folgt:

§C = C_{Traverse} + C_{Intersect} \cdot \left( P_{Front} \cdot N_{Front} + P_{Back} \cdot N_{Back} \right)§

§C_{Traverse}§ und §C_{Intersect}§ sind dabei die Werte, die du experimentell ermittelt hast.

Wenn bei der Unterteilung einer der beiden Kindknoten leer bleibt, zieht man noch den Empty Leaf Boost von §C§ ab.

Ich hoffe, das war irgendwie verständlich

Hier ist noch der Code des kD-Baums meines Raytracers:
https://dl.dropbox.com/u/845597/kdtree.cpp
https://dl.dropbox.com/u/845597/kdtree.h

Der relevante Code ist recht weit unten in der Methode KDTree::Node::process.

Für jedes Dreieck berechne ich den minimalen und maximalen Wert entlang x-, y- und z-Achse.
All diese Werte werden dann als Kandidaten betrachtet. D.h. pro Dreieck werden 6 Splitting-Ebenen-Kandidaten erzeugt.
Das geht trotzdem noch recht schnell, auch bei großen Szenen.
In meinem Code siehst du, dass ich nicht für jede potenzielle Unterteilung die Anzahl der Dreiecke in beiden Kindknoten neu berechne, sondern einen Trick anwende ...
Ich sortiere zunächst die Kandidaten, das kostet O(n * log(n)), und dann das Durchlaufen nochmal O(n), für n = Anzahl der Dreiecke.