"We are doomed."
Star Wars IV - A New Hope, C3PO

BSP Bäume, 3D Indoor Level Rendering

Zu Beginn gleich die alles entscheidende Frage: Was zur Hölle ist ein BSP Baum?
Die einfache Antwort: BSP Baum steht für Binary Space Partitioning Baum und bedeutet, dass wir unsere simulierte 3D Welt damit in Partitionen unterteilen die in binären Bäumen gespeichert werden!
Aha, dann die vielleicht wichtigere Frage: Wozu sollte uns das interessieren?
Und die Antwort die alle zum Weiterlesen bringt: Quake (alle Teile) benutzt diese Technik beispielsweise um Indoor Level darzustellen!

Nachdem wir nun also genau wissen warum wir uns damit befassen wollen noch ein paar einleitende Worte. Natürlich gehört zu einer schnellen 3D Engine für das Rendering von Indoor Architektur mehr als ich hier darstellen kann. Wir haben in diesem Tutorial auch noch nicht so viele Techniken behandelt die uns bei der Erstellung einer schnellen Engine helfen müssten. Ich möchte trotzdem hier bereits ein BSP Demo in den Raum werfen da dies im Gegensatz zu allen anderen Themen im Internet schwer zu finden ist und auf Deutsch schon gar nicht. Wir beginnen unsere kleine Session hier mit einer Einführung in die Theorie die ich aber sehr anschaulich halten werde.
Es ist von äusserster Wichtigkeit dass man diese Theorie mit offenen Ohren empfängt, denn das eigentliche Programmieren eines solchen BSP Biests ist gar nicht mal so kompliziert wie es eventuell klingt. Daher sollte man aber bei der Theorie trotzdem voll mitziehen, weil man sonst keine Chance hat den Code zu verstehen. Ich konnte mich allerdings nicht zurückhalten und habe den Code etwas aufgepeppt, will sagen unsere Level werden auch Texturen und Culling unterstützen. Dadurch wird der Code leider etwas umfangreicher und komplexer, als es bei einem reinen BSP Baum der Fall wäre. Ich halte es aber dennoch für interessanter eine Lösung anzubieten, die nicht nur einfarbige, langsam renderbare graue Wände zeigt, sondern schon eine gewisse Portion des Quake Look and Feel verstreut. Ein Bild gefällig?

Referenzen

Informationen über BSP Bäume findet man heutzutage eigentlich wie Sand am Meer...aber es gibt solche und solche BSP Bäume, sprich Node-based und Leaf-based BSP Bäume. Erstere sind für die Spieleprogrammierung von wenig Interesse, werden aber meistens in Erklärungen im Internet verwendet. Letztere sind das, was wir wirklich wollen. Informationen über die findet man jedoch schon eher selten und schon gar nicht in guter Qualität. Ich habe aber im Laufe der Zeit neben der oben genannten noch zwei weitere Quellen entdeckt die hervorragend sind und mir alles notwendige beigebracht haben.
Das englische Tutorial von Gerald Filimonov hat die wunderbarste allgemeinverständliche Erklärung der Thematik die ich kenne, da kommt sogar das Tutorial von Mr. Gamemaker nicht ran (sorry Gary), da auch hier gilt: Es wird ohne den unnötigen Schnick-Schnack ein purer BSP beschrieben, leider ohne Demo. Aber insbesondere die grafische Einführung hat mir sehr gut gefallen und ich habe davon heftig geborgt um den BSP Baum Algorithmus ebenfalls grafisch anhand eines Beispiellevels vorzustellen.
Daneben gibt (beziehungsweise gab) es zwei Tutorials von Gary Simmons über BSP Bäume. Das erste über eben jene Node-based BSP Bäume und das zweite bereits mit Leaf-based BSP Baum inklusive PVS und allem drum und dran. Gary lieferte auch gleich läuffähigen Demo Code zu seinen Tutorials. Gary Simmons ist nun mit seinen Tutorials als BSP Instructor am Game Institute.

Wie auch immer, mein kleines BSP Demo siedelt also in der Mitte der vier genannten an und bietet ein Leaf-based BSP mit lauffähigem Demo allerdings ohne das recht aufwendige PVS System. Dieses Tutorial ist auch nur dazu gedacht, schnell in die grundlegenden Konzepte einzuführen. Aber wie bereits erwähnt gibt es in meinem Code beispielsweise auch Texturkoordinaten und Culling. Ich hoffe natürlich, dass mir die Gradwanderung zwischen einfacher, didaktischer Eleganz für die Erklärbarkeit einerseits und dem Hinzufügen von Komplexität zur wirklich sinnvollen Verwendbarkeit des Codes andererseits gelingt, aber urteilt selbst.

Ebenfalls lesenswert ist Michael Abrash's "Inside Quake" Artikelserie die es bei www.gamedev.net zu finden gibt. Für alle die den Mann nicht kennen: Michael Abrash ist einer der Programmierer von Quake 1, er weiss also wovon er spricht. Der Artikel liefert natürlich keinen Source Code, zeigt aber sehr gut diverse Techniken mit denen John Carmack herumgespielt hat bevor das BSP/PVS System der Quake Engine endlich dabei herauskam und man lernt auch, dass die Quake Basis-Engine nicht an einem Tag geschaffen wurde...das hat John Carmack ein ganzes Wochenende gekostet :-)

Warum ein BSP Baum?

Widmen wir uns der einleitenden Frage noch einmal etwas ausführlicher. Wir haben bereits gelernt, wie wir 3D Modelle aus X File Dateien laden können welche wir ganz einfach mit einem 3D Modellierungsprogramm wie AC3D erstellen können. Okay, warum nehmen wir dann nicht einfach unser tolles Modellierungsprogramm und erzeugen ein schönes Indoor Level von, sagen wir mal, unserer Wohnung (um klein anzufangen). Dann laden wir dieses Modell in unsere 3D Engine und schwups...schon haben wir unseren eigenen Quake Clone. Na gut, probiert es aus ich warte hier so lange...
...oh schön zurück?...Ah...ihr wartet immer noch darauf dass der erste Frame fertig gerendert wird *hehe*

In der Tat ist es wenig ratsam ein 3D Modell für Leveldaten zu verwenden. Stellen wir uns mal ein Quake Level vor welches im Durchschnitt so um die 10'000 Polygone haben wird die jeweils noch in Dreiecke zerlegt und als solche gerendert werden müssen. Gehen wir mal davon aus, dass jedes Polygon im Best-Case Szenario ein Viereck ist und damit nur aus zwei Dreiecken besteht. Selbst dann haben wir schon 20'000 Dreiecke die wir je Frame zum Rendern schicken. Selbst moderne 3D Beschleuniger machen da nicht mit, wenn wir noch Texturen auf den Polygonen haben und noch andere Berechnungen während eines Frames durchführen müssen.
Wo ist das Problem? Der Bottleneck einer 3D Engine ist immer das Rendern der Grafik. Die heutigen Prozessoren sind schnell genug um die eine oder andere nachlässig aufwendige Berechnung zu tolerieren. Aber immer wenn wir ein Dreieck an das Device zum Rendern schicken dann geht unsere Anwendung in die Knie. Die Vertices des Dreiecks werden zuerst mit der Weltmatrix in Weltkoordinaten transformiert, dann mit der View Matrix in Kamerakoordinaten und dann mit der Projektionsmatrix von 3D auf 2D projiziert. Zusätzlich muss noch die Beleuchtung für die Vertices berechnet werden, was auch viel Zeit kostet je nach Art der Lichtquelle. Wenn das alles passiert ist dann wird das Device das Dreieck rasterisieren (an die Pixel des Bildschirms anpassen) und dann versuchen es zu rendern, Pixel für Pixel. Jeder Pixel der wirklich im sichtbaren Bereich des Bildschirms liegt wird dann mit dem Wert im Z Buffer verglichen, auch das kostet viel Zeit. Dann erst wird der Pixel gerendert, oder auch nicht wenn der Z Buffer dagegen ist. Liegt der Pixel aber ausserhalb des Bildschirms, so wird er einfach verworfen. 
Nun haben wir zwei dicke Probleme. Das Device kontrolliert den Pixel auf Sichtbarkeit am Bildschirm erst nach allen Transformationen, Projektionen und Beleuchtungen für das Dreieck. Selbst wenn unser Dreieck zweihundert Kilometer hinter dem Spieler liegt wird es voll berechnet. Das zweite Problem ist, selbst wenn das Dreieck im Bereich des Bildschirms liegt, aber von anderen Dreiecken verdeckt wird, so wird das Device das Dreieck erst voll berechnen um es dann vom Z Buffer Test verwerfen zu lassen.

Lange rede kurzer Sinn. Stellen wir uns einen Wolkenkratzer in New York vor, den wir als 3D Indoor Level mit Liebe zum Detail als Leveldatei vorliegen haben. Jede einzelne Etage enthält Dutzende von Büros, Aufenthaltsräumen, Korridoren usw. Wenn wir den Level einfach als 3D Modell blind rendern, dann schicken wir selbstverständlich alle Dreiecke des Modells an das Device. Man sieht schnell ein dass die dann durchgeführten Berechnungen für 10'000sende von Dreiecken den Computer so zum Ächzen bringen, dass das Spiel unspielbar wird. Ausserdem zeugt dieser Ansatz davon, dass wir lieber einmal fett Zuschlagen anstatt einmal gescheit nachzudenken. Wir müssen also eine Möglichkeit finden, unsere 3D Level so in unsere Engine zu laden dass wir mit wenig Mühe herausfinden können welche von den 10'000 Polygonen am Bildschirm sichtbar sein könnten und welche eh neben oder gar hinter dem Spieler liegen und damit auf alle Fälle unsichtbar sind. Dann schicken wir einfach nur diejenigen Polygone unseres Levels zum Rendern, die vor dem Spieler liegen und damit potentiell sichtbar sind (falls sie nicht von anderen Wänden verdeckt werden). Der Z Buffer sorgt dann dafür, dass wir diese Polygone korrekt rendern können.
Nehmen wir einfach mal an, dass sich der Spieler genau in der Mitte des Wolkenkratzers befindet, also auch in der horizontalen Mitte auf einer Etage. Es ist leicht einzusehen, dass dann mindestens die Hälfte des Wolkenkratzers bereits hinter dem Rücken des Spielers liegt. Ohne die entsprechenden Dreiecke durch aufwendige Berechnungen zu schicken können wir sie einfach für diesen Frame ignorieren. Stellen wir uns weiter vor, dass der Spieler sich in einem Büroraum befindet. Wie viele Wände mag der haben? Vier, vielleicht auch fünf oder sechs. Selbst ein grosszügig gestalteter Raum wird kaum mehr als 30 Dreiecke haben und das ist alles was wir in diesem Frame wirklich rendern müssen. Das Problem ist aber, selbst wenn wir das Rendern nur auf diese eine Etage beschränken, so müssen wir wenigstens alle Räume an das Device schicken die vor dem Spieler liegen und damit potentiell sichtbar sind. Wir wissen ja nicht, ob man durch die Tür des Büros die dahinter liegenden Räume sehen kann, oder einen langen Flur mit vielen offenen Türen und den entsprechenden Räumen von denen man jeweils ein Stück sehen könnte.

Und hier kommt unser BSP Baum ins Spiel. Sinn des Baumes ist es nämlich, die Daten eines Levels so zu strukturieren, dass wir wesentlich schneller entscheiden können welche Teile des Levels im potentiellen Sichtbereich des Spielers liegen, also vor der Kamera. Alle anderen Bereiche (Dreiecke) des Levels können wir ohne kostspielige Berechnungen schnell für einen Frame verwerfen. Damit haben wir das erste Problem gelöst, nämlich wie wir die Teile über, unter, neben und hinter dem Spieler aussortieren. Bleibt immer noch das zweite Problem, mit den Bereichen die zwar vor dem Spieler liegen, aber von anderen Wänden verdeckt werden und daher unsichtbar sind.
Zwar verhindert der Z Buffer, dass wir grafische Fehlern beim Rendern haben. An der Tatsache dass wir einen sogenannten Overdraw haben ändert sich aber nix. Als Overdraw bezeichnet man die Tatsache, dass jeder Pixel des Bildschirms Vielfach angesprochen wird. Entweder übermalen wir weiter entfernte Wände ständig mit denen die näher am Spieler liegen oder der Z Buffer muss bemüht werden um zu verhindern dass wir eine bereits gemalte, nahe liegende Wand mit einer weiter entfernten übermalen, was grafische Fehler produzieren würde. 

Das zweite Problem adressieren kommerzielle Anwendungen wie beispielsweise Quake durch die Verwendung eines PVS Systems, welches ich am Ende dieses Kapitels noch einmal allgemein erklären werde. Dadurch wird dann übrigens auch das erstgenannte Problem mit gelöst. Allerdings kann man das zweite Problem auch ohne PVS durch einen reinen BSP Baum lösen, wenn man bei seiner Geometrie ein paar Zugeständnisse macht. Etwas detaillierter bedeutet dass für uns, dass wir keine allzugrossen Level verwenden sollten, aber was noch wichtiger ist: Wir müssen die Sichtweite des Spielers in einem massvollen Rahmen halten. Wenn der Spieler eben nicht durch einen langen Flur viele andere Räume sehen kann, dann können wir ein wenig tricksen. So lange der Spieler nur Geometrie sehen kann, die ein paar Dutzend Meter entfernt ist und nicht ein paar Hundert Meter sollten wir auch bei grösseren Level eine gute Framerate erreichen. Und genau das werden wir jetzt endlich versuchen, nachdem wir nun eingesehen haben, dass wir mit dem Hau-Drauf Ansatz eigentlich wenig erreichen, so wie im realen Leben auch. 

Fassen wir das ganze Blabla noch einmal zusammen. Mit einem BSP Baum können wir also

(a) ...die einzelnen Polygone so gruppieren dass man sie auf Sichtbarkeit hin prüfen kann und ganze Gruppen von Polygonen mit wenigen Tests vor dem Rendern aussortieren kann,  und dass man...

(b) ...die einzelnen Polygone so ordnen kann dass sie in korrekter Reihenfolge gerendert werden und sich nicht gegenseitig überdecken. Das ist heutzutage aufgrund des schnellen Z Buffers nicht mehr so wichtig, aber...
...was sehr wohl wichtig ist, das ist das Rendern der Polygone in korrekter Reihenfolge von hinten nach vorne aus der Sicht der Kamera wenn man mit Transparenzeffekten arbeitet! Das haben wir hier zwar noch nicht besprochen und werden das auch nicht tun, aber dennoch ein Satz: Transparenz wie beispielsweise Glasscheiben oder andere lichtdurchlässige Objekte im Level können nur korrekt dargestellt werden wenn zuvor alle dahinter liegenden Objekte gerendert wurden.

Ganz nebenbei fallen bei einem BSP Baum noch andere Goodies für uns ab, mit denen wir uns aber später beschäftigen werden. Jetzt sollten wir uns erst mal in die anschauliche Theorieeinführung stürzen die ich versprochen habe. Oh...eines habe ich noch vergessen. Wenn wir jetzt von Leveldaten sprechen dann bezieht sich das wirklich nur auf die Objekte die tatsächlich zu der Architektur des Levels gehören, und nicht zur Einrichtung. Unser Wolkenkratzer besteht also wirklich nur aus Wänden, Decken und Böden. Hochdetallierte statische Objekte wie beispielsweise Tische, Lampen, Stühle, Schränke und so weiter werden dem Level erst nach dem Erstellen des BSP Baumes zugefügt. Sie würden den Baum an sich unnötig kompliziert und zu gross machen. Dasselbe gilt natürlich insbesondere für nicht-statische (also animierte, bewegliche) Objekte wie beispielsweise Gegner, Monster usw. Ein BSP Baum eigent sich auch nur für wirklich statische Geometrie!!! Special Effects wie beispielsweise eine einstürzende Wand kann ein BSP nicht verarbeiten, dazu muss man dann spezielle Tricks anwenden.

Theorie und Algorithmus der BSP Bäume

Anders bei dem nicht-konvexen Objekt. Hier ist es eben nicht egal, wo in dem Raum wir stehen. Es gibt Stellen im Raum an denen wird eine Wand wenigstens teilweise durch eine andere verdeckt. In einer solchen Situation müssten wir die Polygone unseres 3D Levels umständlich sortieren um zu wissen welche Wand welche anderen Wände verdeckt. Wir können ohne Z Buffer nicht einfach die Wände des Levels blind durcheinander rendern und dann erwarten dass wir per Zufall die richtige Reihenfolge erwischt haben. Es ist sehr wahrscheinlich dass wir dann erst eine Wand malen die eine andere eigentlich verdecken sollte und danach jene besagte Wand die dann fälschlicherweise über die zuerst gerenderte Wand gemalt wird obwohl es umgekehrt sein sollte.

Okay, mögen die Spiele beginnen. Unser Job, oder vielmehr der des BSP Baumes, ist es nun diese Menge von Polygonen in konvexe Häppchen zu unterteilen. Unser Algorithmus zur Erstellung des BSP Baumes beginnt also damit, dass wir einem sogenannten BSP Compiler (einem Programm welches den BSP Baum erstellt) die Menge von Polygonen einfüttern aus denen unser Level besteht. Aus dieser vollkommen ungeordneten Suppe von Polygonen muss der BSP Compiler (also wir) jetzt eine sinnvolle Struktur erzeugen. Dazu werden wir jetzt eines der Polygone auswählen und unsere Menge an Polygonen durch die Ebene des ausgewählten Polygons unterteilen...Moment erst ein Bild:

Abbildung 3: Unterteilung des Levels

Die Abbildung 3 zeigt, dass wir das Polygon Nummer 8 verwendet haben, um die Menge der Polygone zu teilen. Wir werden später noch lernen wie wir ein Polygon geschickt für diesen Job auswählen. Jetzt begnügen wir uns erst mal mit der Erklärung, dass dieses Polygon die Menge der Polygone möglichst in zwei gleich grosse Hälften spalten sollte. 
Auf der rechten Seite der Abbildung sehen wir bereits den BSP Baum in der Entstehung. Diese Struktur nennt man übrigens Baum, weil sie grafisch aufgemalt wie ein umgedrehter Baum aussieht der sich in immer mehr Äste verzweigt. Binary heisst der BSP Baum weil jedes Baumelement immer genau zwei (=binär) neue Äste hat. Dazu sehen wir auch, warum der BSP Baum Space Partitioning heisst, denn er dazu dient Raum (=space) aufzuteilen (=partitionieren). Aber zurück zur Abbildung.
Wir nehmen einfach die Ebene in der das Teilungspolygon (hier Nummer 8) liegt. Diese Ebene ist in der Abbildung rot markiert und als A bezeichnet. Eine Ebene ist übrigens so etwas wie eine Fläche ohne Ränder die sich unendlich weit erstreckt. Stellen wir und das Ding also wie eine Art riesige Glasscheibe vor die kein Ende hat (hier holt der Mathe Prof zum zweiten Schlag aus). Nun prüfen wir alle Polygone der Polygonmenge auf welcher Seite der Teilungsebene sie liegen. Die Vorderseite (Front) der Ebene zeigt natürlich in die gleiche Richtung wie das Teilungspolygon (hier immer noch Nummer 8). Wir starten also unseren BSP Baum mit der Ebene A als sogenanntem Wurzelelement und geben diesem Baumelement A zwei Äste. Ein Ast wird als Front und der andere Ast wird als Back (Rückseite) bezeichnet. In diese beiden Äste füllen wir nun entsprechend die Polygone die vor beziehungsweise hinter der Teilungsebene liegen. 
Dabei gibt es (natürlich!) ein paar Sonderfälle. Was wäre die Welt ohne sie? Was sehr häufig vorkommen wird ist, dass einige Polygone auf beiden Seiten der Ebene liegen, will sagen sie werden durch die Ebene in zwei Teile geschnitten. Das passiert hier im Fall der Polygone Nummer 1 und Nummer 5. In so einem Fall müssen wir die Polygone teilen (splitten). Aus Polygon 1 und 5 werden jeweils zwei vollkommen neue Polygone, das ursprüngliche Polygon hört auf zu existieren. Die neuen Polygone erhalten jeweils die kleinen Buchstaben a und b um sie kenntlich zu machen. Der zweite Spezialfall ist der, dass ein Polygon genau in der Teilungsebene liegt. Das ist mindestens für das eine Polygon der Fall welches das Teilungspolygon war (jaja...immer noch Nummer 8). Für alle Polygone die in der Ebene liegen kontrollieren wir, in welche Richtung sie zeigen. Alle Polygone die in dieselbe Richtung wie die Ebene (also wie das Teilungspolygon) zeigen kommen in die Frontliste des BSP Baumes, so auch das Teilungspolygon selbst. Alle Polygone die in die andere Richtung kucken kommen in die Backliste des Baumes.

Easy oder? Also machen wir weiter. Nun nehmen wir jeweils eine der beiden Listen und wiederholen das Verfahren einfach. Dabei wird die Menge der Polygone nun auf diejenigen Polygone beschränkt die sich tatsächlich in der Liste befinden, und keine anderen. Ein weiteres Kriterium welches wir beachten müssen ist natürlich, dass wir jedes Polygon nur einmal als Teilungspolygon verwenden dürfen, daher hat Polygon Nummer 8 in der Liste eine entsprechende Markierung erhalten. Es hätte doch wenig Sinn, wenn wir jetzt noch einmal das Polygon Nummer 8 verwenden würden, da alle Polygone in der Frontliste sowieso schon auf einer Seite der Teilungsebene liegen. Die Abbildung 4 zeigt wie der BSP Baum das Level im nächsten Schritt unterteilt wenn wir zuerst die Backliste bearbeiten. Damit besteht die Menge aller Polygone in diesem Schritt also nur aus den Polygonen die hinter der Teilungsebene A (also in der entsprechenden Backliste) liegen.

Abbildung 4: Weitere Teilung des Levels

Hier wählen wir das Polygon Nummer 9 als Teilungspolygon und erstellen die Teilungsebene B. Im BSP Baum kommen dann wie gehabt alle Polygone die vor der Ebene liegen (oder auf ihr und in dieselbe Richtung blicken) in die Frontliste im linken Ast und die anderen Polygone in den rechten Ast zur Backliste. Sehen wir uns diese beiden Listen nun gut an. Die beiden entsprechenden Teilmengen aus den Polygonen [1a,9,10] beziehungsweise [5a,6,7] bilden nun konvexe Formen.
Weder die Frontliste noch die Backliste ist weiter unterteilbar. Egal welches der Polygone wir jeweils aus den Mengen auswählen und als Teilungspolygon verwenden, wir können die Menge einfach nicht weiter unterteilen. Die Backliste würde in jedem Fall leer bleiben. Damit haben wir auch schon unser Kriterium gefunden, ab wann wir es mit einem konvexen Raum zu tun haben und die weitere Unterteilung stoppen können.

Damit gehen wir zurück zu dem letzten unvollständig bearbeiteten Ast in unserem BSP Baum. Das ist hier die Frontliste der Teilungsebene A. Hier setzen wir also an und machen mit unserem Verfahren weiter. Dabei halten wir immer im Hinterkopf dass das Polygon Nummer 8 in dieser Liste bereits als Teilungspolygon verwendet wurde und die nicht noch einmal passieren darf. Daher ist die 8 auch mit einem zusätzlich Sternchen in der Liste versehen worden, wir wissen ja wie vergesslich wir manchmal sind ;-)

Abbildung 5: Weitere Teilung des Levels

Na, sehen wir alle ein was hier passiert ist? Wir haben das Polygon Nummer 3 als Teilungspolygon gewählt und dann einfach die anderen Polygone als Front oder Back klassifiziert. Aber an dieser Stelle gibt es noch zwei interessante Anmerkungen zu machen. Zum einen ist die neue Teilungsebene C identisch mit der alten Ebene B und wie wir sehen macht das dem Algorithmus gar nichts aus. Zum anderen hätten wir hier auch ein anderes Teilungspolygon wählen können, beispielsweise das Polygon Nummer 4. Dann hätten wir aber das Polygon 1b noch einmal splitten müssen und zwar in 1bx und 1by. Der Algorithmus hätte auch dann keine Probleme bekomme aber das wäre trotzdem unschön geworden. Dazu gleich mehr.
Hier sehen wir aber, dass unser BSP Baum schon fertig ist. Die neue Front- und Backliste ist ebenfalls jeweils von konvexer Form und kann nicht weiter geteilt werden. Wir haben jetzt einen BSP Baum mit vier sogenannten Leafs (Blättern) in denen sich jeweils drei Polygone einer konvexen Form befinden. Wir werden später einsehen dass uns die Struktur des BSP Baumes einige Kniffe erlaubt mit deren Hilfe wir das Rendern enorm beschleunigen können.

Höhere Geschwindigkeit durch Bounding Boxen...

Für das obige Beispiel mag das noch nicht so sichtbar sein. Stellen wir uns aber vor, dass die Elemente A, B und C ebenso wie die vier Leafs mit den eigentlichen Polygonen jeweils eine sogenannte Bounding Box gespeichert haben. Das ist einfach eine grosse Kiste die alle Polygone einschliesst die in allen unteren Ästen unter einem Element stehen. Die Bounding Box des Elementes A umfasst also alle Polygone der gesamten Welt (Nummer 1a, 1b, 2, 3, 4, 5a, 5b, 6, 7, 8, 9 und 10), die Box des Elementes B ist schon etwas kleiner und schliesst nur noch die Backlist Elemente von A ein (Nummer 1a, 5a, 6, 7, 9 und 10) und die Box des Backleafs von C ist dann beispielsweise nur noch so gross und so in der Welt positioniert, dass sie nur noch die Polygone der Backliste von C einschliesst (Nummer 4, 5b und 8). 
Der Sinn der Sache ist folgender. Während des Spiels kennen wir natürlich die Position des Spielers in der 3D Welt. Wir kontrollieren also ausgehend von der Wurzel A des Baumes ob die entsprechende Bounding Box im Sichtbereich des Spielers liegt. Ist dies der Fall so setzen wir den Test jeweils für die beiden Kinderäste fort und immer so weiter. Finden wir irgendwann eine Box die nicht im Sichtbereich des Spielers liegt, so können wir sofort sagen, dass ebenfalls keines der Elemente (ob Bounding Box, Node oder Leaf mit den eigentlichen Polygonen) in dem unterliegenden Ast im Sichtbereich des Spielers liegend wird...ohne dass wir jedes Element explizit prüfen müssten. Stellen wir in obigem Beispiel also fest, dass die Bounding Box von Element B ausserhalb des Sichtbereichs liegt so haben wir mit einem einzigen Test bereits die Hälfte aller Polygone in unserer Welt aussortiert. Wow, Klasse!
Und das gilt nicht nur für für unser Minibeispiel. Stellen wir uns den BSP Baum eines Levels in Quake Grösse vor. Wenn wir bereits im ersten oder zweiten Schritt unter der Wurzel eine Bounding Box finden die nicht im Sichtbereich liegt, so haben wir nach nur ein, zwei kurzen Tests bereits ca. 5'000 von 10'000 Polygonen eliminiert. In dem anderen Ast werden wir auch noch viele Elemente samt ihrer Kinderäste aussortieren können so dass wir wieder in die schwarzen Polygon Zahlen kommen, also eine Anzahl an Dreiecken die in Echtzeit am Bildschirm renderbar sind ohne dass der Prozessor schlapp macht. Das Entfernen von nicht sichtbaren Polygonen aus der Rendering Pipeline nennt man übrigens Culling und es ist die wichtigste Technik, um grosse Polygonmengen in Echtzeit behandelbar zu machen.
Natürlich unter der Voraussetzung dass unser View Frustrum nicht allzu gross ist. Je kleiner der View Frustrum desto mehr Bounding Boxen liegen ausserhalb...logisch. Den Frustrum können wir aber nur durch eine Variable kleiner machen, nämlich durch die Far Clipping Plane. Alle anderen 5 Flächen des Frustrums sind durch den FOV festgelegt worden. Der Nachteil dabei ist natürlich, dass wir in einem solchen System keine grossen, offenen Gebiete zulassen können. Wenn wir einen sehr langen Korridor haben, so wird dieser dann eventuell durch die Far Clipping Plane einfach nach der Hälfte abgeschnitten und nicht mehr gerendert. Wir müssen also unsere Level so konstruieren, dass der Spieler von keinem Punkt und in keiner Ausrichtung im Level weiter sehen können sollte, als wir es durch die Far Clipping Plane bestimmt haben. Das ist zwar bei weitem nicht so gut wie ein PVS (siehe unten) aber es  versetzt uns dazu in die Lage, sehr komplexe und insgesamt grosse Level trotzdem halbwegs schnell zu rendern.

...und sinnvolle Auswahl der Teilungsebene

Zurück zu den Teilungsebenen. Unser Ziel sollte es nicht nur sein, den BSP Baum möglichst gleichmässig zu halten, also mit möglichst gleich vielen Polygonen in jedem Ast des Baumes (das haben wir in obigem Beispiel unrealistischerweise zufällig genau getroffen).Ein zweites wichtiges Kriterium bei der Auswahl des besten Teilungspolygons ist nämlich, wie viele Polygone durch ein Teilungspolygon gesplittet werden müssen. Das splitten heisst hier wirklich splitten, denn wir werden die Polygone wirklich physisch teilen und aus einem Polygon zwei erzeugen. Wenn wir ein Level aus 10'000 Polygonen haben und jedes Polygon davon splitten müssten so enthält unser BSP Baum später wirklich 20'000 Polygone. Wenn wir also nachher das beste Teilungspolygon aus einer Menge von Polygonen auswählen so müssen wir beachten, dass die entsprechende Teilungsebene die Menge der Polygone (a) möglichst gleichmässig in zwei Teile teilt und (b) dabei möglichst wenige Splits durchführt. Diese beiden Ziele können durchaus gegensätzlich sein, wir müssen dann einen geeigneten Kompromiss finden. 

Kurze Pause!

Okay, wie geht es jetzt weiter? Im folgenden werde ich kurz und knapp den Pseudocode angeben, der zur Erstellung eines BSP Baumes nötig ist. Dann hat man später die nötige Übersicht, um den BSP Code in den Life-Fire Quelltexten schnell zu identifizieren, da die Einbindung von Bounding Boxen, Texturkoordinaten und allen Datenstrukturen dann noch etwas Overhead zufügt der dem Verständnis nicht gerade auf die Sprünge hilft.

Im Anschluss an die Darstellung des Algorithmus im Pseudocode folgt dann die reale Implementierung für das lauffähige Demo. Dort werden wir alles entwickeln was wir brauchen um unsere Indoorlevel auf den Schirm zu bringen. Im letzten Teil dieses Kapitels werde ich dann darauf eingehen was unserem Level noch fehlt und wie wir das alles einbinden können. Für diesen Teil gibt es aber nur noch Denkanreize und keinen Code mehr, der BSP Baum ist schon lang genug und selber coden macht ja bekanntlich auch schlau. Aber keine Panik, Ihr werdet dann genug wissen um selber weiter zu machen.

Erstellung des BSP Baumes in Pseudocode

Wie immer beginnt unsere Arbeit damit, eine Datenstruktur zu entwickeln. Sowohl für die Wurzel des Baumes als auch wie die Nodes und die Leafs verwenden wir allerdings dieselbe Struktur. Dabei ist aber zu beachten, dass die Leafs andere Daten speichern müssen. Wenn der BSP Baum erst mal fertig ist, dann werden die Nodes (auch die Wurzel ist ein normaler Node) jeweils ihre Teilungsebene speichern, eine Bounding Box um alle ihre Kinderäste und zwei Zeiger auf die beiden Kinderäste. Bei den Leafs sind diese beiden Zeiger dann entsprechend leer. Dafür speichern die Leafs jeweils eine Liste ihrer Polygone ebenso wie die Anzahl der Polygone in der Liste:

typedef struct XNODE_TYP {
   XEBENE     xEbene;     // NODE: Teilungsebene
   UCHAR      blnLeaf;    // NODE oder LEAF
   LONG       lAnz_Polys; // Anzahl der Polygone
   XPOLY     *pPolys;     // LEAF: Liste der Polygone
   XNODE_TYP *pFront;     // NODE: Frontliste
   XNODE_TYP *pBack;      // NODE: Backliste
   XBOX       xBox;       // Bounding Box
   } XNODE;

Um die entsprechenden Datentypen wie XEBENE oder XPOLY machen wir uns hier erst mal keine Gedanken. Das sind wiederum Datenstrukturen für die entsprechenden Elemente, die wir aber hier als existent und gegeben voraussetzen werden. Okay, dann können wir die Konstruktion unseres Baumes beginnen:

XNODE BSP_Baum;

BSP_Baum.pPolys     = Lies_Polygonliste_aus_Leveldatei();
BSP_Baum.lAnz_Polys = Lies_Anzahl_Polygone_aus_Leveldatei();

Erstelle_BSP_Baum(&BSP_Baum);

Wir benötigen also nur die Anzahl der Polygone des Levels und die Polygone in Form einer Liste. Beiden Informationen sind in der Leveldatei gespeichert und wir lesen sie einfach aus. Der simple Funktionsaufruf von Erstelle_BSP_Baum() erstellt dann den gesamten Baum. Betrachten wir uns also diese Funktion, in der korrekten Annahme dass sich dahinter etwas mehr verbirgt:

void Erstelle_BSP_Baum(XNODE *pNode) {
   // Suche beste Teilungsebene aus der Polygonliste
   pNode->xEbene = Finde_besten_Splitter(pNode->pPolys,
                                         pNode->lAnz_Polys);
   // Keine Teilungsebene gefunden => Muss ein konvexes Leaf sein
   if (!pNode->xEbene) {
      pNode->blnLeaf = TRUE;
      // Erzeuge die Bounding Box für die Polygone
      pNode->xBox = Erstelle_BoundigBox(pNode->pPolys, pNode->lAnz_Polys);
      pNode->pFront = NULL;
      pNode->pBack  = NULL;
      return;
      }

   XNODE xFrontnode, xBacknode;
   int   nKlasse;
   // Durchlaufe alle Polygone und sortiere sie
   for (LONG l=0; l<pNode->lAnz_Polys; l++) {
      // Klassifiziere Polygon auf welcher Seite der Ebene es liegt
      nKlasse = Klassifiziere_Polygon(pNode->xEbene, pNode->pPolys[l]);

      if (nKlasse == BSP_FRONT) {
         Füge_Polygon_ein(xFrontnode.pPolys, pNode->pPolys[l]);
         xFrontnode.lAnz_Polys++;
         }
      else if (nKlasse == BSP_BACK) {
         Füge_Polygon_ein(xBacknode.pPolys, pNode->pPolys[l]);
         xBacknode.lAnz_Polys++;
         }
      else if (nKlasse == BSP_SPAN) {  // Teile das Poly in a und b
         XPOLY xPolyA, xPolyB;
         Splitte_Polygon(pNode->xEbene, pNode->pPolys[l], &xPolyA, &xPolyB);
         Füge_Polygon_ein(xFrontnode.pPolys, pPolyA);
         xFrontnode.lAnz_Polys++;
         Füge_Polygon_ein(xBacknode.pPolys, pPolyB);
         xBacknode.lAnz_Polys++;
         }
      else if (nKlasse == BSP_PLANAR) {
         if (Poly_selbe_Ausrichtung_wie_Ebene(pNode->pPolys[l], pNode->xEbene)) {
            Füge_Polygon_ein(xFrontnode.pPolys, pPolyA);
            xFrontnode.lAnz_Polys++;
            }
         else {
            Füge_Polygon_ein(xBacknode.pPolys, pPolyA);
            xBacknode.lAnz_Polys++;
            }
         }
      } // for
   pNode->pFront = &xFrontnode;
   pNode->pBack  = &xBacknode;

   // Erzeuge die Bounding Box für die Polygone
   pNode->xBox = Erstelle_BoundigBox(pNode->pPolys, pNode->lAnz_Polys);

   // Die Polygonliste eines Nodes brauchen wir nicht mehr
   free(pNode->pPolys);
   pNode->pPolys = NULL;

   // Rufe Funktion rekursiv für Kinder auf
   Erstelle_BSP_Baum(pNode->pFront);
   Erstelle_BSP_Baum(pNode->pBack);
   } // Erstelle_BSP_Baum

Diese mächtige Funktion übernimmt eigentlich nur zwei Aufgaben. Zuerst muss sie aus der ungeordneten Suppe der Polygonliste ein Polygon auswählen, welches sich am besten als Teilungspolygon eignet. Dieses nennen wir ab jetzt aber nicht mehr Teilungspolygon, sondern Splitter - schliesslich handelt es sich dabei jetzt um eine Ebene und kein Polygon mehr. Die zweite Aufgabe der Funktion ist es dann, alle Polygone aus der Liste dieses Nodes in eine Front- und in eine Backliste (also die neuen beiden Kinder) zu teilen. Dies ist natürlich nur nötig, wenn wir einen Splitter gefunden haben. Ist das nicht der Fall, dann bildet die Liste der Polygone eine konvexe Menge und wir definieren diesen Node als Leaf.
Die Klassifizierungsfunktion entscheidet dann, auf welcher Seite des Splitters ein Polygon aus der Liste liegt. Im Falle dass es davor oder dahinter liegt sortieren wir es in die entsprechende Liste des neuen Astes ein. Liegt das Polygon auf beiden Seiten (=spanning) so müssen wir das Polygon in zwei neue Polygone teilen, eins vor und eins hinter der Ebene, die dann jeweils in die entsprechende Liste kommen. Im Falle eines planaren Polygons welches also in derselben Ebene wie der Splitter liegt, prüfen wir wie oben besprochen in welche Richtung das Polygon blickt und sortieren es in die entsprechende Liste ein.
Danach berechnen wir noch schnell eine Bounding Box um alle Elemente die in diesem Node vertreten waren. Nun können wir die Liste der Polygone für den aktuellen Node löschen, denn die brauchen wir nie wieder. Die eigentlichen Polygone sind an die beiden Kinderäste weitergegeben worden und eine Bounding Box um die Polygone haben wir auch schon gespeichert. 

Und jetzt der Clou: Die Erstellung der beiden Kinderäste und deren Kinderästen und deren Kinderästen und so weiter läuft doch genau so ab. Daher können wir die Funktion selbst wieder aufrufen, jeweils für die beiden Kinderäste. Dort wird dann ebenfalls ein Splitter ausgewählt, die Polygone auf zwei Liste sortiert usw. Wenn eine Funktion sich selbst aufruft dann nennt man das übrigens Rekursion. Erst wenn jeder Unterast des BSP Baumes in einem Leaf geendet hat dann wird ein Zweig des rekursiven Aufrufes beendet. Sind alle Äste mit Leafs abgeschlossen, dann ist unser gesamter BSP Baum fertig erstellt. 

STOP!
Die obige Funktion ist der Kern des gesamten BSP Baumes und jeder sollte sie an dieser Stelle verstanden haben. Es ist im Moment noch unwichtig zu wissen, wie wir eigentlich den besten Splitter finden oder Polygone klassifizieren, das ist Detailarbeit. Aber den eigentlichen Ablauf der Funktion sollte man schon verstanden haben. Wer damit jetzt noch Probleme haben sollte, der referiert am besten noch einmal zurück zu dem kleinen Demolevel welches wir weiter oben Schritt für Schritt zerlegt haben. Dort haben wir genau die Schritte ausgeführt die diese Funktion hier jetzt erledigt...nix anderes!

Und bevor man jetzt noch schlimmeres hinter den anderen Funktionen vermutet kann ich Euch beruhigen: Lediglich die Funktion zum Splitten eines Polygons ist nicht ganz trivial. Aber auch dazu kommen wir noch!

Auswahl des besten Splitters in Pseudocode

Machen wir uns an die Auswahl des besten Splitters. Diese ist wirklich mehr als trivial und wir haben eigentlich schon alles besprochen. Wir haben eine Suppe von Polygonen und wollen aus diesen ein Polygon auswählen dessen Ebene wir als Splitter verwenden werden. Wenn wir einfach irgendein beliebiges Polygon auswählen so haben wir ein paar Probleme am Hals. Vor allem wird unser Baum sehr unausgewogen. Der Splitter wird ja später dazu benutzt, die Suppe aus Polygonen in zwei Teile zu teilen die dann zwei neue Kinderäste im BSP Baum bilden. Wählen wir unsere Splitter so, dass viele Polygone auf einer Seite (Front oder Back) liegen und nur wenig Polys auf der anderen Seite, so wird unser Baum sehr unausgewogen. Das ist unschön und ungewünscht weil das Durchlaufen des Baumes, beispielsweise beim Rendern, dann länger dauert als nötig weil der Baum tiefer ist als idealerweise erforderlich.
Ebenso ist unser zweites Kriterium für einen guten Splitter zu berücksichtigen. Der Splitter soll wie eben besprochen bestenfalls in zwei gleich grossen Listen von Polygonen resultieren. Aber wir wollen auch so wenig wie möglich Polygone zerlegen. Der Splitter muss also auch so gewählt werden, dass möglichst wenig Polygone durch die Ebene des Splitters in zwei Teile zerlegt werden müssen (was in diesem Zusammenhang als Splitten von Polygonen bezeichnet wird).

Eventuell sind diese beiden Kriterien sogar gegensätzlich. Eine Teilungspolygonebene könnte unsere Polygonliste beispielsweise genau in zwei gleich grosse Hälften teilen, aber sehr viele Polygonsplits verursachen. Ein anderes Polygon dagegen könnte 0 Polygonsplits verursachen, aber sehr ungleiche Listen erstellen wo eine Liste nur halb so viele Polygone enthält wie die andere. Beide potentielle Splitter wären nicht sehr gut geeignet. In der Regel verwendet man eine Formel in folgender Form:

   Punkte = abs(Anz_Front - Anz_Back) + (Anz_Splits * 3);

Man prüft jedes Polygon der Liste als Splitter. Dabei zählt man jeweils wie viele Polygone ein Splitter in die beiden isten (Front und Back) einsortieren würde und wie viele Polygonsplits er verursachen würde. Aus diesen Werten erstellt man einen Punktewert für jeden möglichen Splitter und am Ende vergleicht man die Punktewerte aller Splitter. Derjenige mit dem kleinsten Wert ist der beste Splitter. 
Betrachten wir die obige Formel. Das erste Kriterium wird durch die Subtraktion berücksichtigt. Immer wenn die Anzahl der Polygone in der Front- und in der Backliste gleich sind, dann wird das erste Kriterium 0 und ist gut für einen Splitter. Je mehr die Anzahl in beiden Listen abweicht, um so mehr Punkte erhält ein Splitter (was schlecht für ihn ist). Das zweite Kriterium berücksichtigen wir, indem wir die Anzahl der Polygonsplits zählen und zu dem bisherigen Punktewert addieren. Je mehr Splits um so schlechter für den Splitter.
Wir hatten aber auch bereits geklärt, dass das Rendern der Polygone der Bottleneck jeder 3D Anwendung ist. Es ist daher schlimmer, wenn ein Splitter viele Polygone splittet als wenn er die Polygone ungleichmässig in Front- und Backliste einsortiert. Daher multiplizieren wir die Anzahl der Splits noch mit einem Faktor (hier 3) um jeden Polygonsplit eines Splitters strenger zu bestrafen als eine ungleiche Sortierung. Dieser Faktor könnte auch weniger oder mehr sein, je nach Gewichtung die man setzen möchte.

Nun zu den Implementierungsdetails: Wir nehmen einfach die Liste von Polygonen und lassen eine Schleife über sie laufen. In jedem Schleifendurchlauf wählen wir ein neues Polygon aus der Liste und markieren es als aktuellen Splitter. Dann starten wir wieder eine Schleife über alle Polygone der Liste in der Schleife. Nun klassifizieren wir alle Polygone für den aktuellen Splitter und erstellen seinen Punktewert.
Am Ende der beiden Schleifen haben wir dann alle Polygone der Liste als Splitter getestet und dasjenige gefunden, welches die wenigsten Punkte kassiert hat und damit der beste Splitter ist. Einfacher als Pfannkuchen essen, oder?

XEBENE Finde_besten_Splitter(XPOLY *pPolys, LONG lAnz_Polys) {
   XEBENE xBestSplitter, Akt_Splitter;

   for (LONG i=0; i<lAnz_Polys; i++) {
      Akt_Splitter = pPolys[i].xEbene;
      
      for (LONG j=0; j<lAnz_Polys; j++) {
         // Klassifiziere Polygon auf welcher Seite der Ebene es liegt
         nKlasse = Klassifiziere_Polygon(Akt_Splitter, pPolys[j]);

         // Erhöhe die entsprechenden Zähler und setze xBestSplitter
         // auf Akt_Splitter falls dessen Punktewert kleiner

         } // for [AnzPolys]
      } // for [AnzPolys]

   return xBestSplitter;
   } // Finde_besten_Splitter

Okay, den ganzen Zählerkrams habe ich hier ignoriert, das sehen wir nachher im echten Quellcode. Aber jetzt haben wir eine sehr gute Vorstellung davon, was diese Funktion tut. Eigentlich ist das nicht viel. Wir nehmen einfach jedes Polygon der Liste und prüfen dann alle Polygone damit durch um zu sehen ob es ein guter Splitter wäre oder nicht. Keine komplexen Berechnungen mit wilden mathematischen Formeln, sondern der gute alte Brute-Force Ansatz.

Splitten eines Polygons in Pseudocode

Das Splitten eines Polygons...irgendwo muss ja ein Haken sein da bis hier alles so einfach war. Eigentlich ist das Splitten an sich gar nicht so schwer, aber die Implementierung aller feinen Details wird schon sehr haarig so dass diese Funktion die komplexeste unseres gesamten Demos wird. Das hängt einfach damit zusammen, dass wir einerseits berücksichtigen müssen dass wir die Polygondaten irgendwie in Dreiecken halten müssen um Direct3D zufrieden zu stellen und dass wir auch Texturkoordinaten neu berechnen müssen und alle solche Lapalien halt. Das leppert sich ganz schön was zusammen und das hben wir uns für später auf. Hier also nur ein paar Pseudoworte was man im Grunde genommen machen muss: 

void Splitte_Polygon(XEBENE xEbene, XPOLY xPoly, XPOLY *xPolyA, XPOLY *xPolyB) {
   
   for (int i=0; i<xPoly.AnzVerts; i++) {
      // Klassifiziere aktuellen Vertex mit xEbene
      // Falls in Front füge Vertex i zu neuem Poly A
      // Sonst Vertex i zu neuem Poly B

      // Falls Linie von Vertex i-1 zu Vertex i die Ebene
      // schneidet erstelle einen neuen Vertex direkt auf
      // der Ebene und füge ihn in Poly A und B ein.
      } // for
   } // Splitte_Polygon

Wir man sieht ist auch das nix dramatischen an sich. Alle Vertices eines Polys werden durchlaufen und sortiert, je nachdem ob sie vor der hinter dem Splitter liegen. Das ist im Prinzip genau dasselbe wie das Teilen der Polygonliste in Front und Back. An den Stellen wo das Polygon aber die Ebene schneidet müssen wir einen neuen Punkt genau auf der Ebene erstellen und diesen Punkt den beiden neuen Polys A und B zuordnen. Damit haben wir dann zwei neue Polygone auf je einer Seite der Ebene.

Und jetzt geht es los

Bereits Sun Tzu hat es gewusst und seinem Buch The Art of War zur Grundlage gemacht: Ohne eine gute Strategie werden wir keine Schlacht gewinnen, am wenigsten die Schlacht um den BSP Baum oder die Schlacht um das Verständnis des Lesers. Es gibt sicherlich viele Strategien wie man den folgenden Code erklären kann. Man kann entweder Bottom-Up vorgehen und die kleinsten Teile wie das Splitten von Polygonen zuerst entwickeln. Danach werden dann alle kleinen Teile zum grossen Ganzen zusammengesetzt. 
Ich habe mich hier aber für den gegenteiligen Ansatz entschieden und werden das BSP Demo Top-Down entwickeln. Dass bedeutet ich werde mit der Initialisierung es Baumes beginnen und dabei die Existenz der ganzen kleinen Hilfsfunktionen als gegeben voraussetzen. Die Funktion Split_Poly() wird beispielsweise dazu da sein ein Polygon an einer Ebene zu teilen, ob wir diese Funktion vorher bereits implementiert haben oder nicht halte ich nicht für so entscheidend. Jeder kann schnell einsehen wozu die Funktion da ist und wir werden sie erst mal als Black Box verwenden. Erst später gehen wir dann in die ganzen dreckigen Details und schreiben diese Funktionen dann. Diese Strategie halte ich für besser was die Verständlichkeit betrifft. Also sammeln wir unsere Truppen und beginnen die Schlacht.

Inspektion der Truppen vor der Schlacht

Was brauchen wir als erstes für unser kleines BSP Projekt? Falsch, diesmal sind es nicht die Datenstrukturen, sondern ein paar Definitionen die ich hier gleich mal in den Raum schmeisse damit wir sie nachher gleich griffbereit haben:

// Maximale Baumgrösse
#define BSP_NODES_MAX 10000

// Polygon Klassifizierungen
#define BSP_FRONT 0
#define BSP_BACK 1
#define BSP_PLANAR 2
#define BSP_SPANNING 3

// Rechengenauigkeit:
#define BSP_DELTA 0.00001

// Für die Polygone:
#define MAX_VERTICES 20
#define MAX_INDICES 40
#define MAX_TEXTUREN 256

Ich habe mich hier dazu hinreissen lassen die maximale Grösse des Baumes doch als Konstante Zahl für ein statisches Array zu wählen. Natürlich sollten wir auch hier in einem echten Life-Fire Programm mit dynamischem realloc() arbeiten (siehe vorheriges Kapitel), das macht den Code aber nicht gerade überschaubarer. Okay, die Baumgrösse gibt also an, wie viele Elemente (Wurzel, Nodes und Leafs) unser Baum insgesamt haben darf. 

Die Polygonklassifizierungen drücken aus auf welcher Seite einer Ebene ein Polygon oder ein Punkt liegen. Vor oder hinter der Ebene (Front, Back), oder genau in der Ebene (Planar, hier würde mein Mathelehrer vermutlich wieder zum Schlag ausholen und lieber ein Coplanar hören wollen) oder ein Polygon kann die Ebene schneiden und damit auf beiden Seiten der Ebene existieren (Spanning). Letzteres geht logischerweise nicht für Punkte, es sei denn es handelt sich um tunnelnde Elementarteilchen oder eine extreme Form der Heisenbergschen Unschärferelation. Aber die Extremphysik lassen wir hier mal aussen vor.

Nun zur Rechengenauigkeit. Wenn wir bestimmen wollen ob ein Punkt oder ein Polygon auf dieser oder jenen Seite einer Ebene liegt so müssen wir dafür (wer hätte das gedacht) mathematische Berechnungen anstellen. Hierbei können wir durchaus mit sehr kleinen Kommazahlen zu tun bekommen und selbst der Datentyp float mit seinen acht Kommastellen reich hier nicht aus, um Rechenfehler durch Rundungen zu vermeiden. Wir definieren also einen Wert ab dem wir uns zufriedengeben. Sagen wir maleine Rechnung muss 0 ergeben wenn ein Punkt genau in einer Ebene liegt, kleiner als 0 für hinter der Ebene und grösser 0 für vor der Ebene. Mit der von uns gewählten Genauigkeit definieren wir nun, dass der Punkt hinter der Ebene liegt wenn das Ergebnis kleiner als -BSP_DELTA ist, vor der Ebene wenn das Ergbenis grösser als +BSP_DELTA ist und in der Ebene wenn das Ergebnis zwischen -BSP_DELTA und +BSP_DELTA liegt.

Zu guter Letzt haben wir noch definiert wie viele Vertices und Indices ein Polygon bei uns haben darf, das sehen wir dann später in der Polygondatenstruktur. Dazu noch die Anzahl von maximal möglichen Texturen. Und weil wir gerade dabei sind sehen wir uns mal zwei wichtige globale Variablen an. Ein Array für die Elemente des Baumes und einen Zähler wie viele Elemente sich in diesem Array gerade aufhalten. Immer wenn wir dem Baum einen neuen Node hinzufügen so erhöhen wir den Zähler und nehmen dessen Wert als Indes in das Array an dem sich der Neue Node befindet. 

XNODE g_aNode_Pool[BSP_NODES_MAX];
LONG  g_lPool_Index=0;

Keine Panik das wird später schnell klar. Erst mal sehen wir uns aber die wohl wichtigste Datenstruktur für den BSP Baum an, nämlich die eines Polygons, also jener Vielecke aus denen sich die Levelgeometrie zusammensetzt. 

/**
 * Struktur für ein Polygon
 */
typedef struct XPOLY_TYP {
   D3DLVERTEX vVerts[MAX_VERTICES];  // Vertices
   LONG       lAnz_Verts;            // Anzahl der Vertices
   WORD       wIndices[MAX_INDICES]; // Indices auf Vertices
   LONG       lAnz_Indices;          // Anzahl der Indices
   XEBENE     xEbene;                // Ebene des Polys
   BOOL       blnWar_schon_Splitter; // Schon mal Splitter gewesen?
   UCHAR      nTextur_Index;         // Textur des Polys
   } XPOLY;
/*------------------------------------------------------*/

Die meisten Felder der Struktur sind selbsterläuternd. Es gibt eine Liste von Vertices und eine Liste von Indices aus welchen Dreiecken sich das Polygon zusammensetzt. Dazu berechnen wir zu Beginn für jedes Poly die Ebene in der es liegt da wir diese ja für den BSP Algorithmus benötigen. Dazu brauchen wir ein Feld in dem wir uns merken ob dieses Polygon (bzw. seine Eben) schon einmal als Splitter verwendet wurde, das darf ja nur maximal einmal der Fall sein. Zu guter Letzt hat ein Polygon auch immer eine Textur und wir speichern hier den Index den Textur in dem Texturarray der BSP Baum Struktur, die wir nachher noch sehen werden.

Widmen wir uns erst mal der nächstwichtigeren Struktur, nämlich derjenigen die wir für Elemente des Baumes verwenden werden.

/**
 * Struktur für Root, Nodes und Leafs des BSP Baumes
 */
typedef struct XNODE_TYP {
   XEBENE     xEbene;    // NODE: Teilungsebene
   UCHAR      blnLeaf;   // NODE oder LEAF
   LONG       lAnz_Polys;// Anzahl der Polygone
   XPOLY     *pPolys;    // LEAF: Liste der Polygone
   XNODE_TYP *pFront;    // NODE: Frontliste
   XNODE_TYP *pBack;     // NODE: Backliste
   XBOX       xBox;      // Bounding Box
   } XNODE;
/*----------------------------------------------------*/

Wie wir sehen speichern wir an einem Node erst mal eine Ebene, das ist die wichtigste Information für den Node und sagt aus an welcher Ebene dieser spezielle Node das Level teilt. Als nächstes folgt eine Variable die aussagt ob es sich bei dem Baumelement um ein Leaf handelt. Dann haben wir einen Zähler wie viele Polygone sich in dem Leaf befinden. Handelt es sich um ein inneres Baumelement so sagt dieser Zähler aus wie viele Polygone in allen Leafs unter ihm stehen. Das brauchen wir zwar nicht unbedingt, es ergibt sich aber bei der Baumkonstruktion sowieso.
Als nächstes haben wir dann eine Liste aus Polygonen. Nach der Baumerstellung ist dieses Element nur für Leafs gültig. Nur für einen inneren Node gelten hingegen die beiden vorletzten Elemente die die Zeiger auf die beiden Kindern des Nodes sind. Zu guter Letzt haben wir die Bounding Box des Nodes die die gesamte Geometrie in den Leafs unter einem Node umschliesst. Das letzte was wir jetzt noch brauchen ist eine Struktur für die Texturen:

/**
 * Struktur für die Texturen
 */
typedef struct XTEXTUR_TYP {
   LPDIRECT3DTEXTURE8 lpTextur;
   char               achName[128];
   } XTEXTUR;
/*---------------------------------*/

Diese Struktur benötigen wir nur damit wir Texturen nicht mehrfach laden. Wir speichern alle verwendeten Bitmapgrafiken als Direct3D Texturobjekte in dieser Struktur zusammen mit dem Namen der Grafikdatei. Wie das genau funktioniert sehen wir dann später beim Laden der Texturen.

Erkunden des Schlachtfeldes

Der aufmerksame Leser wird festgestellt haben, dass uns bisher noch eine Struktur für den BSP Baum fehlt. Oder brauchen wir gar keine Struktur dafür weil ich alles irgendwie in C Funktionen quetschen werde? Nein, nein. Diesmal gibt es eine echte Klasse für den BSP Baum in der alles drinsteckt was nötig ist. Sehen wir uns diese Klassenfunktion jetzt mal an. Ich habe mich bemüht alles so zu kommentieren dass man gleich sehen kann was welchen Sinn erfüllt. Die einzelnen Funktionen werden wir uns dann Stück für Stück vornehmen.

Als erstes wird uns auffallen, dass diese Klasse (C++ Klassen sind für uns Pragmatiker nichts anderes als C Strukturen in die wir auch Funktionen stopfen können) drei öffentliche Funktionen hat die unser Programm beliebig aufrufen darf. Wie es der Zufall so will gibt es je eine Funktion für jede Phase des Spielablaufes. Ein Funktionsaufruf erstellt den Baum, der zweite Aufruf rendert den Baum und der dritte gibt den Speicher frei. Hier erst mal die vollständige Klassendefinition:

/**
 * Die Klasse des BSP Baumes:
 */
class XBSP {
   public:
      // Member Funktionen:
      // ==================
      BOOL Init(char *achDateiname);// PHASE 1: starten
      void Render(void);            // PHASE 2: Schleife
      void Kill(void);              // PHASE 3: beenden

   protected:
      // Member Variablen:
      // =================
      XNODE   xWurzel;
      UCHAR   Anz_Texturen;
      XTEXTUR aTextur[MAX_TEXTUREN];

      // Member Funktionen:
      // ==================
      // Laden der Leveldaten aus Datei
      BOOL  Lade_Leveldaten(char *achDateiname);
      UCHAR Textur_Manager(char *achDateiname);

      // Rekursive Erstellung des Baumes:
      void Erstelle_BSP_Baum(XNODE *pNode);
      XBOX Erstelle_BoundingBox(XPOLY *Polyliste, LONG lAnz_Polys);
      BOOL Finde_besten_Splitter(XPOLY *Polyliste,
                                 LONG lAnz_Polys,
                                 XEBENE *Splitter);

      // Rendern des fertigen Baumes
      void Render_rekursiv(XNODE *pNode, D3DVECTOR vPosition);
      void Render_Leaf(XNODE *pNode);

      // Hilfsfunktionen für 3D Mathemathik
      int Klassifiziere_Punkt(XEBENE xEbene, D3DVECTOR vPunkt);
      int Klassifiziere_Poly(XEBENE xEbene, XPOLY *pPoly);
      XEBENE Ebene_von_Poly(XPOLY *pPoly);
      void   Split_Poly(XPOLY *Poly, XEBENE *pEbene,
                        XPOLY *FrontSplit, XPOLY *BackSplit);

      // BSP Baum Speicher freigeben
      void Kill_rekursiv(XNODE *pNode);
   };
/*--------------------------------------------------*/

Okay, was die privaten Memberfunktionen (die nur von Funktionen der Klasse selbst aufgerufen werden dürfen) tun kann man eigentlich am Namen her erkennen. Jedenfalls hoffe ich mal dass Ihr ein nach der Lektüre des BSP Algorithmus sehen könnt was wozu da ist. Wir gehen das alles gleich im Detail durch, wichtig sind aber zunächst die drei Variablen der Klasse. Das xWurzel Feld ist der Startpunkt des gesamten Baumes. Dazu gibt es nur noch einen Zähler wie viele Texturen das Level verwendet und dann ein Array in dem sich die Texturen befinden. Na dann wollen wir unseren Level mal laden, oder?

Aufmunitionieren

Unsere BSP Klasse ist so designed, dass man später mit wenig Aufwand den Baum erstellen kann und das sieht dann im Programm wie folgt aus:

XBSP BSP_Baum;
BOOL blnErg;

blnErg = BSP_Baum.Init("testlevel.zfx");
if (blnErg == FALSE) {
   fprintf(Protokoll,"SpielInit: BSP Baum failed \n");
   return FALSE;
   }

Wow, cool. Das riecht aber ganz verdächtig danach, dass die Initialisierungsfunktion mehr macht als man auf den ersten Blick vermuten würden. Sehen wir sie uns also genau an um unsere Vermutung zu bestätigen:

BOOL XBSP::Init(char *achDateiname) {
   BOOL blnErgb;

   fprintf(Protokoll, "\nStarte BSP Baum Erstellung { \n");

   // Noch keine Texturen
   this->Anz_Texturen = 0;

   // Lade die Leveldaten und erstelle Wurzel-Polyliste
   blnErgb = this->Lade_Leveldaten(achDateiname);
   if (!blnErgb) {
      fprintf(Protokoll, "Fehler: BSP Lade_Level() failed\n");
      return FALSE;
      }

   // Erstelle den Baum von der Wurzel ausgehend
   this->Erstelle_BSP_Baum(&this->xWurzel);

   fprintf(Protokoll, " BSP Baum erstellt: \n");

   return TRUE;
   } // Init
/*------------------------------------------------------------*/

Wie man sieht passiert auch hier noch nix dramatisches. Wir verzweigen die Arbeit einfach auf zwei weitere Funktionen, nämlich einmal das Laden des Levels und zum anderen das Erstellen des BSP Baumes aus den geladenen Leveldaten. In diesem Abschnitt setzen wir uns nun damit auseinander wie wir die Leveldaten laden. Dazu müssen wir uns natürlich erst mal auf ein Format einigen in denen die Leveldaten vorliegen sollen und das definiere ich wie folgt (in Form einer ASCII Textdatei):

int
float float float float float
[...]
int
int int int hex
[...]
char

Die Textdatei listet einfach alle Polygone des Levels nacheinander auf und die Polygoninformationen sind wie folgt aufgebaut. Als erstes kommt eine Zahl die angibt wie viele Vertices dieses Polygon hat. Danach folgen diese Vertices mit ihren drei Koordinaten x, y und z sowie zwei weiteren Werten für die Texturkoordinaten u und v. Nachdem dann alle Vertices definiert wurden folgt eine Zahl die angibt aus wie vielen Dreiecken das Polygon besteht, Direct3D kann schliesslich nur Dreiecke rendern. Danach folgen dann jeweils die Dreiecke in Form von je drei Indices auf die oben definierten Vertices und zusätzlich ein Hexadezimalwert für die Farbe des Dreiecks. Abschliessend steht dann der Name der verwendeten Grafikdatei für die Textur des Polygons. Nun wiederholt sich das ganze Spielchen für jedes Polygon der Datei.

Easy, aber woher nehmen wir diese Dateien mit Leveldaten? Nun, ich habe AC3D zusammen mit einem selbstdefinierten Export Plugin verwendet um meine Testdaten zu erstellen. Das Plugin ist im Download enthalten, wer also über AC3D verfügt der kann bequem seine eigenen Level bauen. Und nun zur Funktion die uns die Leveldaten in unsere Datenstrukturen einliest.
Diese Funktion tut im Grunde genommen nichts anderes als einen Pointer vom Typ XPOLY zu definieren. Diesem wird dynamischer Speicher zugewiesen um ihn zu einem dynamischen Array zu machen so wie im letzten Kapitel besprochen. Wir öffnen also unsere Leveldatei, die ja nix anderes ist als eine grosse Liste von Polygondaten, und lesen dann die einzelnen Daten in die korrespondierenden Felder der Polygonliste. Zu guter Letzt speichern wir die fertige Polygonliste dann an der Wurzel des BSP Baumes:

BOOL  XBSP::Lade_Leveldaten(char *achDateiname) {
   DWORD  dwFarbe;
   FILE  *pDatei;
   XPOLY *vPolygon;
   int    n=0, nAnz_Dreiecke, nIndex;
   char   buffer[8], chFarbe[8], chTextur[50]; 

   // Öffne die Leveldatei
   pDatei = fopen(achDateiname, "r");
   if (!pDatei) {
      fprintf(Protokoll, "Fehler: BSP Level nicht gefunden\n");
      return FALSE;
      }

   // Stelle Speicher für die Verts bereit
   vPolygon = (XPOLY*)malloc(sizeof(XPOLY)*100);
   if (!vPolygon) {
      fprintf(Protokoll, "Fehler: malloc() Wurzel Verts\n");
      return FALSE;
      }

   // Hole alle Polygone aus der Leveldatei
   while (!feof(pDatei)) {
      // Anzahl der Vertices einlesen
      fscanf(pDatei, "%d", &vPolygon[n].lAnz_Verts);

      // Koords und Tex-Koords der Vertices einlesen
      for (LONG l=0; l<vPolygon[n].lAnz_Verts; l++) {
        fscanf(pDatei, "%f %f %f %f %f\n",
           &vPolygon[n].vVerts[l].x,  // Koordinaten
           &vPolygon[n].vVerts[l].y, 
           &vPolygon[n].vVerts[l].z,
           &vPolygon[n].vVerts[l].tu, // Text-Koords
           &vPolygon[n].vVerts[l].tv);
           } // for [Verts im Poly]

      // Anzahl der Dreiecke im Polygon bestimmen
      fscanf(pDatei, "%d", &nAnz_Dreiecke);
      vPolygon[n].lAnz_Indices = 0;

      // Indices und Farbe der Dreiecke einlesen
      for (LONG m=0; m<nAnz_Dreiecke; m++) {
         fscanf(pDatei, "%d %d %d %s\n",
            &vPolygon[n].wIndices[vPolygon[n].lAnz_Indices+0],
            &vPolygon[n].wIndices[vPolygon[n].lAnz_Indices+1], 
            &vPolygon[n].wIndices[vPolygon[n].lAnz_Indices+2],
            &chFarbe);

         sprintf(buffer, "0x%s", chFarbe);
         sscanf(buffer, "%i", &dwFarbe);

         // Speichere die Farbe für die drei Vertices des Dreiecks
         nIndex = vPolygon[n].lAnz_Indices;
         vPolygon[n].vVerts[vPolygon[n].wIndices[nIndex+0]].color =
            dwFarbe;
         vPolygon[n].vVerts[vPolygon[n].wIndices[nIndex+1]].color =
            dwFarbe;
         vPolygon[n].vVerts[vPolygon[n].wIndices[nIndex+2]].color =
            dwFarbe;

         // Drei Indices zugefügt
         vPolygon[n].lAnz_Indices += 3;
         } // for [Indices im Poly]

      // Textur laden und Index im Poly speichern
      fscanf(pDatei, "%s\n", &chTextur);
      vPolygon[n].nTextur_Index = this->Textur_Manager(chTextur);

      // Als unbenutzt markieren
      vPolygon[n].blnWar_schon_Splitter = FALSE;

      // Ebene des Dreiecks berechnen
      vPolygon[n].xEbene = this->Ebene_von_Poly(&vPolygon[n]);

      n++; // nächstes Dreieck

      // Falls Platz im Array nicht reicht:
      if ( (n%100) == 0) {
         vPolygon = (XPOLY*)realloc(vPolygon,
                                sizeof(XPOLY)*(n+100));
         if (!vPolygon) {
            fprintf(Protokoll, "Fehler: realloc() \n");
            return FALSE;
            }
         }
      } // while

   // endgültige Arraygrösse festlegen
   vPolygon = (XPOLY*)realloc(vPolygon, sizeof(XPOLY)*n);

   // Anzahl der Polygone und die Polyliste speichern
   this->xWurzel.lAnz_Polys = n; 
   this->xWurzel.pPolys     = vPolygon;

   return TRUE;
   } // Lade_Leveldaten
/*-------------------------------------------------------*/

Die Funktion fscanf() ist eigentlich selbsterklärend, oder? Sie funktioniert sozusagen wir fprintf() nur umgekehrt und lädt Daten aus einer Textdatei in Variablen des Programms. Ich habe hier aber noch Gebrauch von zwei weiteren unserer Funktionen machen müssen. Zum einen benötigen wir einen Texturmanager, den wir uns gleich ansehen, und zum anderen benötigen wir die Funktion die die Ebene eines Polygons berechnet. Wir glauben hier einfach mal ganz spontan dass das mit rechten Dingen zugeht, denn die Funktion ist erst weiter unten an der Reihe.

Jetzt zum Sinn und Zweck des Texturmanagers. Selbst wenn unser Level Tausende von Polygonen verwendet so ist es doch recht unwahrscheinlich, dass wir auch Tausende von verschiedenen Texturen haben. In der Regel werden wir mit zwanzig oder dreissig verschiedenen Texturen für die Levelarchitektur auskommen. Es ist daher Blödsinn und Speicherverschwendung diese wenigen Texturen Tausende Male zu laden. Jede Textur einmal zu laden reicht vollkommen aus. Die Texturen unseres Levels werden also jeweils nur einmal in das entsprechende Array der BSP Klasse geladen und jedes Polygon erhält statt des Texturobjektes nur einen Index in dieses Array an dem die passende Textur steckt. Lange Rede kurze Funktion: 

UCHAR XBSP::Textur_Manager(char *achDateiname) {
   HRESULT hr;
   UCHAR   i;

   // Prüfe ob die Textur schon einmal geladen wurde
   for (i=0; i<this->Anz_Texturen; i++) {
      // Ja => also den Index auf Texturarray speichern
      if (lstrcmpi(&this->aTextur[i].achName[0], achDateiname) == 0)
         return i;
      } // for

   // Lade neue Textur in BSP Texturarray
   hr = D3DXCreateTextureFromFileA(g_lpD3DDevice, // D3D Device
                                   achDateiname,  // Grafikdatei
                                   &this->aTextur[i].lpTextur);
   if (FAILED(hr)) {
      fprintf(Protokoll, "Fehler: Textur %s laden\n", achDateiname);
      return 0;
      }

   // Kopiere den BMP Namen in das Texturarray
   lstrcpyn(&this->aTextur[i].achName[0], achDateiname, 128);

   // Zähle Anzahl Texturen mit
   this->Anz_Texturen++;

   // Gib Index der Textur zurück;
   return i;
   } // Textur_Manager
/*------------------------------------------------------*/

Die Funktion durchläuft einfach alle bisher in den BSP Baum geladenen Texturen und vergleicht deren Namen mit dem Namen der Textur die geladen werden möchte. Die Funktion lstrcmpi() liefert den Wert 0 zurück falls die beiden Strings übereinstimmen. Entdecken wir die Textur bereits unter den zuvor geladenen so geben wir den Index in das Array zurück an dem wir die Textur finden können. Diesen Wert merkt sich das Polygon dann ganz einfach. 
Finden wir die Grafikdatei noch nicht unter den Texturen so laden wir sie als neues Element in das Array des BSP Baumes, speichern auch ihren Namen dort, erhöhen den Zähler der geladenen Texturen und geben den entsprechenden Index an das Polygon zurück.

So zurück zum Laden der Leveldaten. Da hatten wir ja noch eine Hilfsfunktion verwendet die wir bisher noch nicht gesehen haben. Zu jedem Polygon welches wir aus der Leveldatei geladen haben und das wir als XPOLY speichern müssen wir auch dessen Ebene berechnen und uns merken. Im vorherigen Kapitel haben wir ja die Ebenenformel kennengelernt und diese müssen wir jetzt einfach für jedes Polygon erzeugen:

XEBENE XBSP::Ebene_von_Poly(XPOLY *pPoly) {
   XEBENE xEbene;

   D3DVECTOR v1, v2;

   v1.x = pPoly->vVerts[1].x-pPoly->vVerts[0].x;
   v1.y = pPoly->vVerts[1].y-pPoly->vVerts[0].y;
   v1.z = pPoly->vVerts[1].z-pPoly->vVerts[0].z;

   v2.x = pPoly->vVerts[2].x-pPoly->vVerts[0].x;
   v2.y = pPoly->vVerts[2].y-pPoly->vVerts[0].y;
   v2.z = pPoly->vVerts[2].z-pPoly->vVerts[0].z;

   xEbene.vNormal = xUtil_Kreuzprodukt(v1, v2);

   xEbene.vNormal = xUtil_Normalisieren(&xEbene.vNormal);

   xEbene.fDistanz = - (
         pPoly->vVerts[2].x*xEbene.vNormal.x +
         pPoly->vVerts[2].y*xEbene.vNormal.y +
         pPoly->vVerts[2].z*xEbene.vNormal.z);

   return xEbene;
   } // Ebene_von_Poly
/*-----------------------------------------*/

Keine Überraschungen hier. Wir nehmen einfach die ersten drei Vertices des Polygons und erzeugen uns daraus zwei Vektoren (Endpunkt minus Startpunkt) die damit logischerweise in der Ebene des Polygons liegen. Diese kreuzen wir dann um einen zu ihnen rechtwinklig gelegenen Vektor zu erhalten. Das ist damit logischerweise der Normalenvektor der Ebene nachdem er Normalisiert wurde. Zu guter Letzt benötigen wir noch einen Wert für -d der die Entfernung der Ebene von Nullpunkt angibt.
Hm...warum nehmen wir diese komische Berechnung da? Die Ebenenformel ist doch n*x+d=0 oder etwas umgeformt n*x=-d. Damit ist die negative Entfernung der Ebene zum Ursprung das Ergebnis einer Multiplikation (Punktprodukt) aus einem beliebigen Punkt in der Ebene mit deren Normalenvektor. Statt v2 hätten wir also auch jeden anderen Punkt aus dem Polygon verwenden können.

Die grosse Schlacht

Und jetzt der Moment den wir alle gefürchtet haben. Nachdem wir das Laden der Leveldaten und das Initialisieren der Polygonliste eben abgehakt haben sind wir nun beim letzten Schritt der Funktion XBSP::Init angekommen. Und dieser ist das Arbeitspferd und der Kern der BSP Klasse. Jetzt implementieren wir die Funktion XBSP::Erstelle_BSP_Baum. Es gilt zu beachten dass die eben besprochene Funktion zum Laden der Leveldaten bereits das Wurzelelement des BSP Objektes initialisiert hat, allem voran mit der Polygonliste. Mit diesem Wurzelelement rufen wir nun das Arbeitspferd auf. Okay, natürlich ist diese Funktion wiederum ein einziges Aufrufen von anderen Hilfsfunktionen aber da müssen wir jetzt durch. So just hang on, ich habe immer kommentiert was die entsprechende Funktion macht und wir nehmen diese hier erst mal als Zerbie-gegeben hin. Erst mal behandeln wir diese Funktion in ihrer Gänze und danach kommen die anderen alle noch dran, versprochen.

// Array für alle Elemente des Baumes unter der Wurzel
XNODE g_aNode_Pool[BSP_NODES_MAX];
// Zähler für die erzeugten Elemente
LONG g_lPool_Index=0;

void XBSP::Erstelle_BSP_Baum(XNODE *pNode) {
   XNODE *pFrontnode, *pBacknode;
   LONG   lAnz_F=0, lAnz_B=0;
   BOOL   blnErgb;
   int    nKlasse;

   // Berechne die Bounding Box um alle Polygone des Nodes
   pNode->xBox = this->Erstelle_BoundingBox(pNode->pPolys,
                                            pNode->lAnz_Polys);
   // Finde die beste Teilungsebene dieses Nodes
   blnErgb = this->Finde_besten_Splitter(pNode->pPolys,
                                         pNode->lAnz_Polys,
                                         &pNode->xEbene);
   // Falls keine Ebene gefunden ist dieser Node ein Leaf
   if (!blnErgb) {
      pNode->blnLeaf = TRUE;
      pNode->pBack   = NULL;
      pNode->pFront  = NULL;
      return;
      }

   // Zu wenig Speicher im Pool für kompletten Baum
   if (g_lPool_Index >= (BSP_NODES_MAX-2)) {
      fprintf(Protokoll, " Fehler: MAX_NODES erreicht \n");
      return;
      }

   pFrontnode = &g_aNode_Pool[g_lPool_Index++];
   pBacknode  = &g_aNode_Pool[g_lPool_Index++];

   pFrontnode->lAnz_Polys = 0;
   pBacknode->lAnz_Polys  = 0;

   // Speicher in ausreichender Menge allokieren
   pFrontnode->pPolys = (XPOLY*)malloc(sizeof(XPOLY)*pNode->lAnz_Polys);
   pBacknode->pPolys  = (XPOLY*)malloc(sizeof(XPOLY)*pNode->lAnz_Polys);
   if (!pFrontnode->pPolys || !pBacknode->pPolys) {
      fprintf(Protokoll, "malloc() Front-/Back failed\n");
      return;
      }
wird fortgesetzt...

Zuerst zu den wichtigen deklarierten Variablen. Wir haben je ein Objekt für einen Front- und einen Backnode des aktuellen Nodes und entsprechende Zähler für die Polygone in den Listen. Als erstes berechnen wir dann die Bounding Box für das übergebene XNODE Objekt. Zu Beginn ist das natürlich die Wurzel des BSP Baumes. Danach suchen wir aus der Menge der Polygone des Baumelementes den besten Splitter heraus. Finden wir diesen nicht, dann handelt es sich bei der Menge der Polygone in diesem Baumelement um eine konvexe Menge und wir definieren dieses Baumelement als Leaf und beenden die Funktion.

Gut, wenn wir aber einen besten Splitter finden dann war die Polygonmenge eben nicht konvex, sondern noch teilbar und wir verwenden dann die globale Variable g_lPool_Index die mitzählt wieviele Elemente unser Baum schon hat und dafür sorgt dass wir nicht mehr als BSP_NODES_MAX Elemente erzeugen. Dazu haben wir das globale Array g_aNode_Pool in dem wir dann die zwei nächsten freien Positionen jeweils der Front- und der Backliste zuweisen. Die beiden Pointer auf den Front- und den Backnode sind damit nichts anderes als Adressen in das statische, globale Array aus XNODE Objekten. Ist auf den ersten Blick vielleicht etwas verwirrend und auf den zweiten Blick etwas unschön, erleichtert hier aber die Arbeit etwas weil wir nicht überall dynamischen Speicher verwenden müssen. Also weiter in der Funktion. Wenn wir kein Leaf haben dann müssen wir logischerweise noch einen ganzen Batzen Arbeit erledigen und dazu kommen wir nun.
Oben ist noch zu sehen dass wir die Polygonzähler der beiden Kinder erst mal auf 0 setzen und dann für die Polygonlisten Speicher allokieren. Dabei erhält jedes Kind des aktuellen Baumelementes genug Platz für so viele Polygone wie im aktuellen Baumelement enthalten sind. Das ist natürlich zu viel Platz, denn im Durchschnitt solte jedes Kind ja nur halb so viel Polygone erhalten. Da wir das aber auf keinen Fall vorher genau bestimmen können (siehe Theorie zur Auswahl des besten Splitters oben) gehen wir erst mal auf Nummer Sicher und passen den Speicher erst später richtig an. Okay, dann machen wir mal weiter mit der Funktion, denn jetzt kommt der spannende Teil :-)

Erstelle_BSP_Baum() Fortsetzung:
   // Durchlaufe alle Polygone und sortiere sie
   for (LONG l=0; l<pNode->lAnz_Polys; l++) {
      // Klassifiziere Polygon auf welcher Seite der Ebene es liegt
      nKlasse = this->Klassifiziere_Poly(pNode->xEbene,
                                         &pNode->pPolys[l]);

      if (nKlasse == BSP_FRONT) {
         pFrontnode->pPolys[pFrontnode->lAnz_Polys] = pNode->pPolys[l];
         pFrontnode->lAnz_Polys++;
         }
      else if (nKlasse == BSP_BACK) {
         pBacknode->pPolys[pBacknode->lAnz_Polys] = pNode->pPolys[l];
         pBacknode->lAnz_Polys++;
         }
      else if (nKlasse == BSP_SPANNING) {
         XPOLY xPolyFRONT, xPolyBACK;
         // Teile das Poly in a und b
         this->Split_Poly(&pNode->pPolys[l], &pNode->xEbene,
                          &xPolyFRONT, &xPolyBACK);
         // Frontliste
         pFrontnode->pPolys[pFrontnode->lAnz_Polys] = xPolyFRONT;
         pFrontnode->lAnz_Polys++;

         // Backliste
         pBacknode->pPolys[pBacknode->lAnz_Polys] = xPolyBACK;
         pBacknode->lAnz_Polys++;
         }
      else if (nKlasse == BSP_PLANAR) {
         // Gleiche Richtung wie die Ebene oder nicht?
         float Pkt_Produkt;
         Pkt_Produkt = pNode->pPolys[l].xEbene.vNormal.x *
                       pNode->xEbene.vNormal.x +
                       pNode->pPolys[l].xEbene.vNormal.y *
                       pNode->xEbene.vNormal.y +
                       pNode->pPolys[l].xEbene.vNormal.y *
                       pNode->xEbene.vNormal.y;
         // Wohin mit dem Polygon?
         if (Pkt_Produkt >= 0) {
            // Frontliste
            pFrontnode->pPolys[pFrontnode->lAnz_Polys] = pNode->pPolys[l];
            pFrontnode->lAnz_Polys++;
            }
         else {
            // Backliste
            pBacknode->pPolys[pBacknode->lAnz_Polys] = pNode->pPolys[l];
            pBacknode->lAnz_Polys++;
            }
         } // BSP_PLANAR
      } // for
wird fortgesetzt...

Wie sagen wir Panzergrenadiere? Dran, drauf, drüber! Dieser Teil der Funktion sollte uns schwer bekannt vorkommen. Wir durchlaufen alle Polygone des Baumelementes und hetzen unsere magische Klassifizierungsfunktion darauf. Diese spuckt dann einen der vier blau markierten Rückgabewerten aus der besagt in welcher Relation zur Teilungsebene des besten Splitters sich das jeweilige Polygon befindet. Am einfachsten sind die Fälle BSP_FRONT und BSP_BACK, hier können wir das Polygon problemlos in die Liste des entsprechenden Kindnodes einsortieren. Im Falle von BSP_SPANNING schneidet das Polygon aber die Ebene und muss fachgerecht in zwei Teile zerlegt werden. Zum einen den Teil der vor und zum anderen den Teil der hinter der Splitterebene liegt. Die beiden entsprechenden Teile die durch unsere magische Teilungsfunktion erzeugt werden, werden dann in die entsprechende Liste einsortiert.
Der letzte mögliche Fall ist BSP_PLANAR bei dem das Polygon direkt in der Teilungsebene liegt. In diesem Fall müssen wir anhand des Normalenvektors entscheiden ob das Polygon in dieselbe Richtung wie die Ebene blickt oder nicht und es dann wie oben in der Theorie besprochen einsortieren. Das Punktprodukt zwischen den beiden Normalenvektoren gibt unter anderem acuh Informationen über den Winkel der beiden Vektoren zueinander preis...ein Hoch auf das Punktprodukt. Ist das Ergebnis grösser als 0 so ist der Winkel zwischen den beiden Vektoren kleiner als 90 Grad. Damit blickt das Polygon in dieselbe Richtung wie die Ebene. Umgekehrt gilt natürlich das Gegenteil. Und nun die gute Nachricht: Das war eigentlich schon die gesamte Funktion zru Erstellung des Baumes. Fehlt nur noch der Abschluss der Funktion und der rekursive Aufruf:

Erstelle_BSP_Baum() Fortsetzung:
   // Speicher genau anpassen:
   pFrontnode->pPolys = (XPOLY*)realloc(pFrontnode->pPolys,
                          sizeof(XPOLY)*pFrontnode->lAnz_Polys);
   pBacknode->pPolys  = (XPOLY*)realloc(pBacknode->pPolys,
                          sizeof(XPOLY)*pBacknode->lAnz_Polys);

   pNode->pFront = pFrontnode;
   pNode->pBack  = pBacknode;

   // Polygonliste des Nodes brauchen wir nicht mehr
   free(pNode->pPolys);
   pNode->pPolys = NULL;

   // Rufe Funktion rekursiv für Kinder auf
   this->Erstelle_BSP_Baum(pNode->pFront);
   this->Erstelle_BSP_Baum(pNode->pBack);

   return;
   } // Erstelle_BSP_Baum
/*-----------------------------------------------*/

Nach dem Lauf der Schleife wissen wir dann auch ganz genau wie viele Polygone in der Front- und wie viele in der Backliste gelandet sind und passen den Speicher entsprechend an. Nun geben wir die Adressen der jeweiligen XNODE Objekte (in dem globalen Array) dem aktuellen Baumelement bekannt, so dass dieses dann Zugriff auf seine Kinder hat. Die Polygonliste eines Nodes der kein Leaf ist wird nie wieder gebraucht, schliesslich ist die Boundig Box alles was wir brauchen. Also blockieren wir keinen überflüssigen Speicher und geben diesen wieder frei. Zu guter Letzt der eigentliche Trick. Für die beiden Kinder des Baumelementes rufen wir dieselbe Funktion auf um die Kinder wiederum in Front und Back Elemente zu teilen, so wie es der BSP Algorithmus halt verlangt. Fertig!

Nebengefechte

So...nun zu den kleinen Nebengefechten. Hier besprechen wir den Pfannkuchenkram, also die Erstellung der Bounding Boxen für eine Menge von Polygonen und die Klassifizierung von Polygonen in Relation zu einer gegebenen Ebene. Fangen wir mit den Boxen an:

#define MAX(a,b) ((a<b) ? (b) : (a))
#define MIN(a,b) ((a<b) ? (a) : (b))

XBOX XBSP::Erstelle_BoundingBox(XPOLY *Polyliste,
                                LONG lAnz_Polys) {
   XBOX xBox;
   XPOLY *pPoly = Polyliste;
   float fMax_x, fMax_y, fMax_z,
         fMin_x, fMin_y, fMin_z;

   // Startwerte beliebig wählen
   fMax_x = fMin_x = pPoly->vVerts[0].x;
   fMax_y = fMin_y = pPoly->vVerts[0].y;
   fMax_z = fMin_z = pPoly->vVerts[0].z;

   for (LONG i=1; i<lAnz_Polys; i++, pPoly++) {
      for (LONG j=0; j<pPoly->lAnz_Verts; j++) {
        // Nach neuem Maximalwert suchen
        fMax_x = MAX(fMax_x, pPoly->vVerts[j].x);
        fMax_y = MAX(fMax_y, pPoly->vVerts[j].y);
        fMax_z = MAX(fMax_z, pPoly->vVerts[j].z);
        // Nach neuem Minimalwert suchen
        fMin_x = MIN(fMin_x, pPoly->vVerts[j].x);
        fMin_y = MIN(fMin_y, pPoly->vVerts[j].y);
        fMin_z = MIN(fMin_z, pPoly->vVerts[j].z);
        } // for [Verts]
     } // for [Polys]

   // Ausdehnung der Box speichern
   xBox.vMax = xUtil_Vector(fMax_x, fMax_y, fMax_z);
   xBox.vMin = xUtil_Vector(fMin_x, fMin_y, fMin_z);

   // Mittelpunkt berechnen
   xBox.vMittelpkt = xUtil_Vector( (fMax_x+fMin_x)/2,
                        (fMax_y+fMin_y)/2,
                        (fMax_z+fMin_z)/2);
   return xBox;
   } // Erstelle_BoundingBox
/*-----------------------------------------------*/

Lächerlich dass man uns mit so etwas überhaupt belästigt. Im letzten Kapitel dieses Tutorials haben wir ja schon eine Funktion für Bounding Boxen gesehen. Diese arbeitete allerdings mit Vertexlisten. Hier haben wir aber eine Liste von Polygonen eines Nodes. Also brauchen wir einfach noch eine Schleife über alle Polygone der Liste und darin die Schleife über alle Vertices eines Polygons. Der Rest der Funktion ist identisch. Also kümmern wir uns nun um das Klassifizieren.

Unser Job ist es eigentlich eine Funktion zu schreiben die ein Polygon in Relation zu einer Ebene klassifiziert. Dieses Problem, ebenso wie einige andere die später noch folgen, lassen sich auf das Problem zur Klassifizierung eines Punktes in Relation zu der Ebene zurückführen, also schreiben wir uns zunächst so eine Funktion:

int XBSP::Klassifiziere_Punkt(XEBENE xEbene,
                              D3DVECTOR vPunkt) {
   float fErgbn;
   D3DVECTOR vAuf_Ebene, vRichtung;

   // Wir brauchen einen Punkt auf der Ebene. Nimm den normalisierten
   // Normalenvektor mal die Entfernung der Ebene zum Ursprung:
   vAuf_Ebene.x = xEbene.vNormal.x * xEbene.fDistanz;
   vAuf_Ebene.y = xEbene.vNormal.y * xEbene.fDistanz;
   vAuf_Ebene.z = xEbene.vNormal.z * xEbene.fDistanz;

   // Endpunkt-Startpunkt=Richtungsvektor zw. beiden
   vRichtung.x = vAuf_Ebene.x - vPunkt.x;
   vRichtung.y = vAuf_Ebene.y - vPunkt.y;
   vRichtung.z = vAuf_Ebene.z - vPunkt.z;

   // Punktprodukt
   fErgbn = vRichtung.x * xEbene.vNormal.x
          + vRichtung.y * xEbene.vNormal.y
          + vRichtung.z * xEbene.vNormal.z;

   if (fErgbn < -BSP_DELTA)
      return BSP_FRONT;
   if (fErgbn > BSP_DELTA)
      return BSP_BACK;
   return BSP_PLANAR;
   } // Klassifiziere_Punkt
/*-------------------------------------*/

Piece of cake, ist alles eine Frage der Kopfarbeit denn der grosse Vorteil bei Vektorrechnung ist, dass man sich alles im Kopf aufmalen kann. Zuerst brauchen wir einen Punkt der auf der Ebene liegt. Einen solchen finden wir ganz einfach. Wir nehmen den Normalenvektor der Ebene und verlängern seine Länge auf die Entfernung die die Ebene vom Ursprung hat. Damit haben wir einen Vektor der vom Ursprung genau bis auf die Ebene (und damit auf einen Punkt auf dieser) zeigt.
Als nächstes berechnen wir einen Richtungsvektor von dem Punkt dessen Relation zur Ebene wir prüfen wollen zu dem Punkt der auf der Ebene liegt. Wir haben also einen Vektor zwischen diesen beiden Punkten. Die gedankliche Höchstleistung kommt aber nun. Wir setzen diesen Vektor in die Ebenegleichung ein und multiplizieren ihn mit dem Normalenvektor der Ebene, daraus erhalten wir den Wert von -d also die Entfernung. Dadurch dass wir aber nicht den Vektor vom Urpsrung zu dem Testpunkt verwenden, sondern den Vektor von der Ebene zum Testpunkt erhalten wir als Ergebnis den Wert 0 falls der Testpunkt in der Ebene liegt.
Ist das Ergebnis kleiner als 0 so liegt der Punkt vor der Ebene und ist das Ergbenis grösser als 0 so liegt der Testpunkt hinter der Ebene. Das klingt zwar erst mal etwas verwirrend, ist aber korrekt. Wir können hier nicht den Vektor vom Ursprung zum Testpunkt verwenden weil wir dann die Ausrichtung des Normalenvektors der Ebene auch noch berücksichtigen müssten, da die Ebene zum Ursprung hin oder von ihm weg blicken kann. Durch unsere Methode erhalten wir gleich das richtige Ergebnis. Aufgrund von Rundungsfehlern können wir aber nie genau auf 0.000000 rechnen, daher verwenden wir in obiger Formel die Konstante BSP_DELTA um ein wenig Ungenauigkeit zuzulassen.

Bewaffnet mit dieser Möglichkeit einen beliebigen Punkt im Raum zu einer gegebenen Ebene zu klassifizieren können wir ganz fix eine Funktion erschaffen die ein Polygon zu einer Ebene klassifiziert. Ein Polygon ist in diesem Sinne schliesslich nicht mehr als eine Ansammlung von Punkten:

int XBSP::Klassifiziere_Poly(XEBENE xEbene, XPOLY *pPoly) {
   D3DVECTOR vPunkt;
   int nAnz_Front=0, nAnz_Back=0, nAnz_Auf=0;
   int nKlasse;

   // Durchlaufe Punkte des Polys und klassifiziere sie
   for (int i=0; i < pPoly->lAnz_Verts; i++) {
      // Mache einen Vektor aus dem Punkt
      vPunkt.x = pPoly->vVerts[i].x;
      vPunkt.y = pPoly->vVerts[i].y;
      vPunkt.z = pPoly->vVerts[i].z;
      // Klassifizieren den Vektor zum Punkt
      nKlasse = this->Klassifiziere_Punkt(xEbene, vPunkt);

      // Vor, hinter oder auf der Ebene
      if (nKlasse == BSP_FRONT)
         nAnz_Front++;
      else if (nKlasse == BSP_BACK)
         nAnz_Back++;
      else {
         nAnz_Front++;
         nAnz_Back++;
         nAnz_Auf++;
         }
      } // for [alle Verts]

   // Alle Verts des Polys sind planar
   if (nAnz_Auf == pPoly->lAnz_Verts)
      return BSP_PLANAR;
   // Alle Verts des Polys liegen vor der Ebene
   else if (nAnz_Front == pPoly->lAnz_Verts)
      return BSP_FRONT;
   // Alle Verts des Polys liegen hinter der Ebene
   else if (nAnz_Back == pPoly->lAnz_Verts)
      return BSP_BACK;
   // Sowohl als auch => Poly spannt über die Ebene
   else
      return BSP_SPANNING;
   } // Klassifiziere_Poly
/*-----------------------------------------*/

Hier sehen wir mal wieder eines ganz klar. Auch 3D Programmierer benutzen Wasser zum Kochen. Wir durchlaufen einfach alle Punkte des Polygons und klassifizieren sie. Dabei zählen wir mit wie viele Punkte als Front, Back und Planar klassifiziert wurden. Nach der Schleife müssen wir dann nur noch prüfen ob alle Punkte Front, oder alle Punkte Back oder alle Punkte planar waren. Trifft keiner der drei Fälle zu dann haben wir ein Poygon welches sich nicht eindeutig auf eine Seite oder in die Ebene zwängen lässt und dieses schneidet dann logischerweise die Ebene. Pfannkuchen.

Wahl der Waffen

Glaubt es oder nicht, unser BSP Baum ist so gut wie fertig. Ein Blick zurück auf die Funktion XBSP::Erstelle_BSP_Baum sagt uns, dass uns nur noch zwei weitere Hilfsfunktionen fehlen die wir dort benötig haben. Hier werden wir eine davon besprechen, nämlich die Auswahl des besten Splitters mit dessen Hilfe wir die Menge der Polygone eines Baumnodes teilen werden.

Glücklicherweise haben wir unse Theoriestunden ja bereits hinter uns. Dort hatten wir gesehen dass wir hauptsächlich zwei Schleifen brauchen. Eine äussere Schleife läuft über alle Polygone in der Liyte des zu prüfenden Nodes und wir wählen je Schleifendurchlauf ein anderes Polygon aus der Liste welches wir als Splitter testen. Für diesen Test brauchen wir die innere Schleife die wiederum über alle Polygone des Nodes läuft. Für jeden potentiellen Splitter klassifizieren wir alle Polygone der Liste und zählen wieder mit wie viele Polygone auf der Front- oder Backseite des Splitters liegen und wie viele Polygonsplits dieser potentielle Splitter verursachen würde. Abschliessend erstellen wir den Punktewert für jeden potentiellen Splitter nach folgender Formel:

   ulScore = abs(lFront - lBack) + (lSplits * 3);

Das haben wir ja oben auch schon besprochen. Die Anzahl der Frontpolygone minus die Anzahl der Backpolygone sorgt für einen ausgewogenen Baum. Jeden Polygonsplit bestrafen wir hier durch den Faktor 3. Je kleiner der Punktewert desto geeigneter ist ein potentieller Splitter, der Idealwert ist 0 denn das bedeutet 0 Splits und die gleiche Anzahl Polygone in Front und Back. Wir speichern dann immer den Splitter mit dem kleinsten Punktwert als bisher besten Splitter und wenn wir mit der Funktion durch sind müssen wir nur noch eines prüfen: Haben wir überhaupt einen Splitter gefunden?
Das ist auch ganz einfach, denn ein potentieller Splitter ist auch wirklich nur ein Splitter wenn die Menge der Polygone nicht konvex ist. Das bekommen wir anhand folgender zwei Kriterien heraus. Nach einem Split muss entweder die Front- und die Backliste des Splitters mehr als 0 Elemente enthalten oder der Splitter muss mindestens einen Polygonsplit verursachen der dann die Front- und Backliste entsprechend füllen wird. So, dann schreiben wir schnell die Funktion:

BOOL XBSP::Finde_besten_Splitter(XPOLY *Polyliste, LONG lAnz_Polys,
                                 XEBENE *BestSplitter) {
   XPOLY *pBest_Splitter = NULL;
   XPOLY *pSplitter = NULL;
   XPOLY *pAkt_Poly = NULL;
   LONG   lFront  = 0, // Wie viele Polys liegen
          lBack   = 0, // bei jedem potentiellen
          lPlanar = 0, // Splitter in Front, Back
          lSplits = 0; // Planar oder spannen?
   int    nKlasse;
   ULONG  ulScore,
          ulBest_Score = 1000000;
   BOOL   blnSplitter_gefunden = FALSE; // mind. einer?

   // Durchlaufe alle Poly in der Liste
   for (int i=0; i<lAnz_Polys; i++) {
      // Nächstes Polygon als Splitter testen
      pSplitter = &Polyliste[i];

      // Zähler zurücksetzen
      lFront = lBack = lPlanar = lSplits = 0;

      // Jedes Poly max einmal als Splitter zulassen
      if (pSplitter->blnWar_schon_Splitter)
         continue;

      // Zurück auf den Start der Polygonliste
      pAkt_Poly = Polyliste;
      // Durchlaufe wieder alle Polys für diesen Splitter
      for (int j=0; j<lAnz_Polys; j++, pAkt_Poly++) {
         // Den Splitter nicht mit sich selbst testen
         if (i==j)
            continue;
         // Klassif. akt. Poly j für akt. Splitter i
         nKlasse = this->Klassifiziere_Poly(pSplitter->xEbene,
                                            pAkt_Poly);
         // Zähle wie viele Polys für Splitter i in die
         // jeweiligen Listen fallen
         if (     nKlasse == BSP_FRONT)
            lFront++;
         else if (nKlasse == BSP_BACK)
            lBack++;
         else if (nKlasse == BSP_PLANAR)
            lPlanar++;
         else
            lSplits++;
         } // for [innen]

      ulScore = abs(lFront-lBack) + (lSplits*3);

      // Haben wir einen neuen besten Score?
      if (ulScore < ulBest_Score) {
         // Ist die Polyliste nicht konvex?
         if ( ((lFront > 0) && (lBack > 0)) ||
              (lSplits > 0) ) {
            ulBest_Score   = ulScore;
            pBest_Splitter = pSplitter;
            // Okay wir haben mind. einen!
            blnSplitter_gefunden = TRUE;
            }
         } // if [ulScore]
      } // for [aussen]

   // Falls KEIN Splitter mehr gefunden abbrechen
   if (!blnSplitter_gefunden)
      return FALSE;

   // Splitter Polygon als benutzt markieren
   pBest_Splitter->blnWar_schon_Splitter = TRUE;

   // Splitter Ebene speichern
   (*BestSplitter) = pBest_Splitter->xEbene;

   return TRUE;
   } // Finde_besten_Splitter
/*------------------------------------------*/

Wir dürfen nur nicht vergessen auch das entsprechende Feld blnWar_schon_Splitter eines Polygones zu setzen wenn dessen Ebene als Splitter verwendet wurde. Weiter oben hatten wir ja besprochen dass es keinen Sinn macht ein Polygon mehr als einmal als Teilungspolygon heranzuziehen.

Einsatz der Special Forces

Nun ist es so weit, die schweren Geschützen haben ihren Job getan und es ist an der Zeit die Spezialeinheiten aufzutauen. Jetzt geht es um die einzige Funktion bei der ganzen BSP Baum Geschichte von der selbst ich zugeben muss dass sie nicht ganz trivial ist. Es geht hier um das Splitten eines Polygons das eine Ebene schneidet in zwei Teile die dann jeweils komplett und ausschliesslich auf je einer Seite der Ebene liegen.

Für diesen Job brauchen wir eine kleine Hilfsfunktion die dazu dient den Schnittpunkt zwischen einer Ebene und einer Linie zu finden falls dieser existiert. Wofür brauchen wir das? Nun, eigentlich ist das Teilen eines Polygons gar nicht so schlimm. Wir nehmen das Polygon und selektieren immer zwei aufeinanderfolgende Punkte von diesem. Damit haben wir eine Linie zwischen zwei Vertices welche auch gleichzeitig eine Kante des Polygons ist. Dann prüfen wir ob dieses Linienstück die Ebene schneidet. Falls neien dann liegt diese Kante des Polygons ausschliesslich auf einer Seite des Polygons und beide Vertices kommen in das entsprechende der beiden neue Teilpolygon (je eines vor bzw. hinter der Ebene) die aus dem Schnitt resultieren. Schauen wir einmal auf die Abbildung 7.

Abbildung 7: Teilung eines Polygons

Ganz oben links sehen wir das zu teilende Polygon aus sechs Vertices. Rechts daneben sehen wir auch schon was passieren muss. Wir haben die Teilungsebene und deren Normalenvektor eingezeichnet. Nun nehmen wir die Vertices v0 und v1 und prüfen diese Kante mit der Ebene: Es gibt keinen Schnittpunkt und beide Vertices liegen auf der Frontseite der Ebene. Dann gehen wir weiter zu v1 und v2 und prüfen diese Kante. Hier gibt es einen Schnitt denn v1 liegt auf der Frontseite und v2 liegt auf der Backseite der Ebene. Die beiden Vertices werden also dann den entsprechenden Polygonteilen zugeordnet, aber nun fehlt unseren beiden neuen Polygonen etwas. Wir müssen den Schnittpunkt der Kante mit der Ebene genau berechnen und diesen als neuen Vertex (hier als v6 rot markiert) in beide Teilpolygone Front und Back einsortieren. Dasselbe passiert dann für die Kante v4v5 in der der neue Vertex v7 entsteht.
Im unteren Teil der Abbildung sehen wir dann die beiden neuen Polygone die nun keinen Schnittpunkt mit der Teilungsebene mehr aufweisen. Das ursprüngliche Polygon ist damit vollkommen verschwunden und wir fügen an dessen Stelle diese beiden neuen Polygone in unsere Polygonlisten ein.

Okay, bevor wir also ein Polygon splitten können brauchen wir die Hilfsfunktion die uns den Schnittpunkt eines Linienstücks zwischen zwei Vertices mit einer Ebene liefert. Und damit beginnen wir nun. Dazu tauchen wir nun erstmalig etwas tiefer in die Gefilde der 3D Mathematik ab, den folgenden Abschnitt könnte man auch mit "Mein Freund das Punktprodukt" betiteln, oder besser "Warum ich das Punktprodukt hassen und lieben gelernt habe."

Was will uns das Punktprodukt V1*V2 zwischen zwei Vektoren sagen? Dazu haben wir ja bereits ein paar Dinge gehört, aber werfen wir mal einen Blick auf Abbildung 8 um uns das noch einmal vor Augen zu führen. Und ab jetzt heisst es erst mal schlucken, schlucken, schlucken...was wir damit anfangen können das sehen wir schon noch früh genug.

Abbildung 8: Das Punktprodukt

Ganz allgemein beschreibt das Punktprodukt zwischen V1 und V2 den Cosinus des Winkels Alpha zwischen den beiden Multipliziert mit den Beträgen der Vektoren. Der Betrag eines Vektors ist nichts anderes als die Länge des Vektors und man schreibt dies in der Mathematik mit den vertikalen Balken rechts und links vom Vektor. |V1| bedeutet also den Betrag/die Länge von V1. In der obigen Abbildung sieht man die Formel etwas umgeform, nämlich durch die beiden Beträge der Vektoren geteilt.
Die Formel für das Punktprodukt wird jedoch wesentlich einfacher wenn wir davon ausgehen, dass die beiden Vektoren V1 und V2 Einheitsvektoren sind. Wieder so ein Fremdwort. Das bedeutet einfach, dass die beiden Vektoren normalisiert sind und damit die Länge 1 haben. Durch 1*1 brauchen wir aber nicht zu teilen und daher fällt dieser Term aus der Formel weg. Das Punktprodukt zwischen zwei Einheitsvektoren liefert also direkt den Cosinus des Winkels zwischen den beiden.

Schlucken, schlucken, schlucken...und weiter gehts. Die Abbildung 9 bringt uns wieder auf Kurs Richtung Schnittpunkt einer Linie mit einer Ebene. Hier sehen wir wie wir die Formel des Punktproduktes geometrisch interpretieren können wenn einer der beiden Vektoren kein Einheitsvektor ist.

Abbildung 9: Das Punktprodukt II

V1 ist hier kein Einheitsvektor während V2 sehr wohl ein Einheitsvektor ist. In einem solchen Fall können wir das Ergebnis des Punktproduktes zwischen V1 und V2 so interpretieren, dass das Ergbenis des Punktproduktes |V3| (der Länge des Vektors V3) entspricht. Dabei ist V3 eine Projektion des Vektors V1 auf den Einheitsvektor V2. Schlucken, schlucken, schlucken...
Nehmen wir einmal an der Punkt A sei die Position der Kamera und Punkt B sei ein Punkt in einer Ebene. Damit wäre der Vektor V1 ein Vektor von der Kameraposition zu einem Punkt in einer Ebene. Cool. Stellen wir uns weiter vor dass der Einheitsvektor V2 der Normalenvektor der Ebene ist...was lernen wir daraus? Wir haben nun eine Möglichkeit gefunden die Entfernung der Kamera (oder eines beliebigen Punktes) zu einer Ebene zu berechnen. Bisher konnten wir immer nur die Entfernung der Ebene vom Ursprung berechnen. Hui...noch cooler. Aber jetzt wird es brutal, also Mund...äh Augen auf.

Jetzt können wir uns daran machen eine Methode zu entwickeln die uns den Schnittpunkt einer Polygonkante mit einer Ebene ermittelt. Definieren wir also folgendes. Punkt A ist der Startpunkt der Polygonkante (z.B. V0 in der Polygonliste), Punkt B ist ein Punkt auf der Ebene an der das Polygon geteilt werden soll und Punkt C ist der Endpunkt der Polygonkante (z.B. V1 in der Polygonliste). Mit Papier und Bleistift kommen wir schnell zu folgender Skizze in der Abbildung 10 die unser Teilungsproblem löst.

Abbildung 10: Punktprodukte

Nun denn meine jungen Jedis. Der linke Teil der Abbildung wiederholt nur noch mal ein wenig. Wir haben eine Ebene mit dem Nromalenvektor N. Erstellen wir das Punktprodukt aus diesem Einheitsvektor N und dem Vektor V1 vom Punkt A zu einem Punkt B auf der Ebene dann erhalten wir als Ergebnis die Entfernung des Punktes A von der Ebene, also mathematisch Formuliert |V3a|.
Auf dem rechten Teil der Abbildung kommen wir dann zur Sache. Wir ziehen nun einen Vektor vRichtung von Punkt A zu Punkt C und nehmen das Punktprodukt von diesem Vektor mit dem Normalenvektor N der Ebene. Das Ergebnis dieser Berechnung ist sozusagen die Entfernung des Punktes A von der Ebene falls diese Ebene parallel verschoben wäre so dass Punkt C in der Ebene liegen würde. In Ermangelung eines besseren Namens haben ich diesem Wert fLaenge genannt. Schlucken, schlucken, schlucken...

Und nun bitte Nachdenken. Wir suchen den Schnittpunkt des Vektors vRichtung zwischen A und C mit der Ebene. Aus der Zeichnung können wir aber eines Ersehen. Den Schnittpunkt des Strahls V3 mit der Ebene könnten wir schon berechnen, aber wir haben hier noch einen interessanten Zusammenhang. Der Prozentsatz bei dem der Vektor V3b von der Ebene geschnitten wird entspricht nämlich genau dem Prozentsatz bei dem auch der Vektor vRichtung von von der Ebene geschnitten wird. In anderen Worten, wenn V3b nach drei Vierteln auf die Ebene trifft, dann trifft auch vRichtung nach drei Vierteln auf die Ebene.
Wir berechnen also den Prozentsatz an dem der Schnitt auftritt mit |V3a|/|V3b| = fEntfernung/fLaenge. Nun müssen wir nur noch den Vektor vRichtung mit diesem Prozentwert multiplizieren und zu dem Vektor zum Punkt A addieren, dann haben wir den Schnittpunkt von vRichtung mit der Ebene genau bestimmt. Und den Prozentwert an dem dieser Schnitt auftritt, denn können wir später auch noch mal verwenden. Wir entwickeln daher jetzt eine Funktion die die Punkte A und C als Start- bzw. Endpunkt einer Linie aus zwei aufeinanderfolgenden Vertices eines Polygons aufnimmt, ebenso wie den Normalenvektor einer Ebene und einen Punkt auf dieser Ebene. Daraus berechnet die Funktion den Schnittpunkt und den Prozentsatz und gibt diese Werte als Call-by-Referenz zurück.

BOOL xUtil_Schnittpunkt(D3DVECTOR *vLinienstart,
                        D3DVECTOR *vLinienende,
                        D3DVECTOR *vAuf_Ebene,
                        D3DVECTOR *vNormal,
                        D3DVECTOR *vSchnittpunkt,
                        float *fProzent) {
   D3DVECTOR vRichtung,// Vektor von vLinstart zu vLinEnde
             V1;       // Vektor von vLinstart zu vAufEbene
   float     fLaenge,
             fEntfernung;

   vRichtung.x = vLinienende->x - vLinienstart->x;
   vRichtung.y = vLinienende->y - vLinienstart->y;
   vRichtung.z = vLinienende->z - vLinienstart->z;

   // Punktprodukt: Wenn v1 NICHT normalisiert und v2 IST
   // normalisiert dann erhalten wir so die Entfernung des
   // Punktes v1 zu der Ebene mit Normalenvektor v2
   // HIER: Entfernung von vLinienstart zur Ebene wenn Ebene
   // so verschoben dass Linienende auf der Ebene liegt.
   fLaenge = vRichtung.x * (*vNormal).x
           + vRichtung.y * (*vNormal).y
           + vRichtung.z * (*vNormal).z;

   if (fabsf(fLaenge)<0.0001) {
      return FALSE;
      }

   V1.x = vAuf_Ebene->x - vLinienstart->x;
   V1.y = vAuf_Ebene->y - vLinienstart->y;
   V1.z = vAuf_Ebene->z - vLinienstart->z;

    //  Punktprodukt:  Wenn  v1  NICHT  normalisiert  und  v2  IST
    //  normalisiert  dann  erhalten  wir  so  die  Entfernung  des
    //  Punktes  v1  zu  der  Ebene  mit  Normalenvektor v2
   // HIER: Entfernung von vAuf_Ebene zu Linienstart
   fEntfernung = V1.x * (*vNormal).x
               + V1.y * (*vNormal).y
               + V1.z * (*vNormal).z;

   // Entfernung durch Laenge gibt an bei wieviel Prozent
   // der Linie der Schnittpunkt mit der Ebene liegt (0-1)
   *fProzent = fEntfernung / fLaenge; 

   if (*fProzent<0.0f) 
      return FALSE;
   else if (*fProzent>1.0f) 
      return FALSE;
   else {
      vSchnittpunkt->x = vLinienstart->x + vRichtung.x*(*fProzent);
      vSchnittpunkt->y = vLinienstart->y + vRichtung.y*(*fProzent);
      vSchnittpunkt->z = vLinienstart->z + vRichtung.z*(*fProzent);
      return TRUE;
      }
   } // xUtil_Schnittpunkt
/*-----------------------------------------------------*/

You still with me? Wer bis hierhin durchgehalten hat der hat es eigentlich schon geschafft. Die eben entwickelte Funktion ist der schlimmste Brocken Mathematik in dem BSP Code und den haben wir jetzt in einer handlichen Funktion versteckt. Machen wir uns also daran den Code zu schreiben mit dessen Hilfe wir ein Polygon an einer Ebene splitten in zwei neue Polygone erzeugen können. Mit der nun geleisteten Vorarbeit ist das im Prinzip nur noch ein wenig Bastelarbeit. Der Code ist zwar extrem lang da es viel zu tun gibt, aber nicht sonderlich kompliziert. Los geht's, fangen wir mit den lokalen Variablen an (diese Funktion basiert auf dem BSP II Tutorial von Gary Simmons, in Perez; Royer "Advanced 3D Game Programming..." [oder wie auch immer es jetzt heisst] findet sich ebenfalls entsprechender Code mit Erläuterung):

void XBSP::Split_Poly(XPOLY *Poly, XEBENE *pEbene,
                      XPOLY *FrontSplit, XPOLY *BackSplit) {
   D3DLVERTEX vFrontList[20],  // Neues Polygon vor Ebene
              vBackList[20];   // Neues Polygon hinter der Ebene
   D3DVECTOR  vSchnittpunkt,   // Schnittpunkt mit der Ebene
              vAuf_Ebene,      // Beliebiger Punkt auf der Ebene
              vPunktA, vPunktB;// Zwei Folgepunkte im Polygon
   WORD       wAnz_Front=0,    // Anzahl Verts im Frontteil
              wAnz_Back=0,     // Anzahl Verts im Backteil
              wLoop=0,         // Schleifenzähler
              wAkt_Vertex=0;   // Aktueller Vertex
   float      fProzent;        // Prozent bis Schnittpkt
wird fortgesetzt...

Eigentlich dürfte hier alles klar sein. Wir brauchen zwei Listen mit Vertices, je eine für eines der beiden neuen Polygone auf der Front- und der Backseite der Ebene. Dann benötigen wir einen Vektor zum Schnittpunkt einer Linie zwischen zwei Vertices des Polys mit der Ebene (siehe allgemeine Splitting-Erklärung bei Abbildung 7 oben). Dazu haben wir zwei Vektoren auf zwei aufeinanderfolgende Vertices im Polygon zwischen denen wir eine Linie aufmachen und einen Vektor zu einem Punkt auf der Ebene, letzteren brauchen wir ja für die eigentliche Schnittpunktfunktion welche wir bereits entwickelt haben. Dann haben wir noch ein paar Zähler und den Prozentwert wo auf der Linie zwischen zwei Vertices des Polys der Schnittpunkt zur Ebene liegt. Diesen Wert gibt uns die Schnittpunktfunktion zurück und wir brauchen ihn zur Berechnung der Texturkoordinaten an neu erzeugten Vertices bei den Schnittpunktkoordinaten.

Der erste Schritt dieser Funktion ist es nun, einen Vektor zu einem Punkt auf der Ebene zu finden. Das klingt vielleicht ungeheuer kompliziert, ist es aber nicht. Schliesslich gibt es unendlich viele davon, das Problem ist nur einen zu finden. Das ist aber lächerlich einfach. Wir nehmen einfach den Normalenvektor der Ebene und laufen diese Richtung vom Ursprung aus so lange ab bis wir die Entfernung der Ebene zum Ursprung gegangen sind. Et voilá, wir sitzen genau auf der Ebene! Diesen Vektor merken wir uns für später und beginnen dann bereits damit, die beiden neuen Polygone zu konstruieren. Wir nehmen den ersten Vertex des Polygons und klassifizieren ihn gegen die Ebene. Entsprechend dieser Klassifizierung sortieren wir den ersten Vertex richtig ein, Front, Back oder in beide Polygone wenn der Vertex planar ist, denn dann muss ein Teil beider neuen Polygone sein weil er genau auf der Ebene liegt.

Split_Poly() Fortsetzung:
   // Wir brauchen einen Punkt auf der Ebene. Nimm normalisierten
   // Normalenvektor mal Entfernung der Ebene zum Ursprung:
   vAuf_Ebene.x = pEbene->vNormal.x * pEbene->fDistanz;
   vAuf_Ebene.y = pEbene->vNormal.y * pEbene->fDistanz;
   vAuf_Ebene.z = pEbene->vNormal.z * pEbene->fDistanz;

   // Klassifiziere den ersten Vertex des Polygons und
   // sortiere ihn in die entsprechende Liste
   D3DVECTOR v1_Vector;
   v1_Vector.x = Poly->vVerts[0].x;
   v1_Vector.y = Poly->vVerts[0].y;
   v1_Vector.z = Poly->vVerts[0].z;

   switch (this->Klassifiziere_Punkt(*pEbene, v1_Vector))
      {
      case BSP_FRONT:
         vFrontList[wAnz_Front++] = Poly->vVerts[0];
         break;
      case BSP_BACK:
         vBackList[wAnz_Back++] = Poly->vVerts[0];
         break;
      case BSP_PLANAR:
         vBackList[wAnz_Back++]   = Poly->vVerts[0];
         vFrontList[wAnz_Front++] = Poly->vVerts[0];
         break;
      default:
         PostQuitMessage(0);
      } // switch
wird fortgesetzt...

Und nun wird es mal wieder haarig denn jetzt kommt ein grosser Code Happen der nur schwer zu trennen ist und eventuell etwas unüberschaubar wirkt. Eigentlich ist das aber gar nicht so schwer. Überlegen wir mal allgemein was wir jetzt machen müssen.
Wir benötigen nun eine Schleife über alle Vertices des Polys beginnend ab dem zweiten Vertex da wir den ersten ja bereits abgehandelt haben. Den jeweils aktuellen Vertex klassifizieren wir dann gegen die Ebene. Ist dieser Vertex planar so kommt er in beide neuen Polygone, so wie im entsprechenden Fall des ersten Vertex. Dann ist die Schleife schon zu Ende. Ist dieser Vertex jedoch nicht planar so wird es komplizierter. Dann nehmen wir den aktuellen Vertex den wir als B bezeichnen und den vorhergehenden Vertex im Polygon den wir als A bezeichnen. Damit haben wir eine Polygonkante zwischen den Punkten A und B und was wir damit machen sehen wir uns gleich an, zuerst aber das neue Code Häppchen. Es sei angemerkt dass der else Fall hier wegen der Übersichtlichkeit noch nicht implementiert ist. Genau dort gehört die Behandlung der Linie AB hin.

Split_Poly() Fortsetzung:
   // Schleife über alle Vertices im Poly
   for (wLoop=1; wLoop < Poly->lAnz_Verts+1; wLoop++) {
      if (wLoop == Poly->lAnz_Verts) 
         wAkt_Vertex = 0;
      else
         wAkt_Vertex = wLoop;

      // Nimm zwei aufeinanderfolgende Vertices des Polys
      vPunktA.x = Poly->vVerts[wLoop-1].x;
      vPunktA.y = Poly->vVerts[wLoop-1].y;
      vPunktA.z = Poly->vVerts[wLoop-1].z;

      vPunktB.x = Poly->vVerts[wAkt_Vertex].x;
      vPunktB.y = Poly->vVerts[wAkt_Vertex].y;
      vPunktB.z = Poly->vVerts[wAkt_Vertex].z;

      // Klassifiziere den Punkt in Bezug zur Ebene
      int nErgbn = this->Klassifiziere_Punkt(*pEbene, vPunktB);

      // Falls Vertex direkt in der Ebene dann kommt eine
      // Kopie in beide neuen Polygone
      if (nErgbn == BSP_PLANAR) {
         vBackList[wAnz_Back++]   = Poly->vVerts[wAkt_Vertex];
         vFrontList[wAnz_Front++] = Poly->vVerts[wAkt_Vertex];
         }
      // Sonst kontrollieren wir ob die beiden zuletzt betrachteten
      // Punkte eine Linie bilden die die Ebene schneidet. Dann
      // müssen wir einen neuen Punkt erzeugen
      else {
         /* HIER FEHLT CODE */
         } // else [!BSP_PLANAR]
      } // for [AnzVerts]
wird fortgesetzt...

Wow, immer noch easy...und es wird auch nicht komplizierter. Denn was müssen wir im else Fall machen? Wir müssen lediglich prüfen ob es einen Schnittpunkt der Line AB mit der Ebene gibt. Ist dies nicht der Fall, so liegen die beiden Punkte A und B auf derselben Seite der Ebene und wir können Punkt B ganz normal klassifizieren und in das richtige Polygon einsortieren.
Im Horrorszenario dass es einen Schnittpunkt gibt haben wir die Situation, dass A und B auf verschiedenen Seiten der Ebene liegen. Wir oben allgemein besprochen müssen wir dann die genauen Koordinaten des Schnittpunktes berechnen und diesen Schnittpunkt in beide neuen Polygone als zusätzlichen Punkt einsortieren. Doch dafür haben wir bereits unsere Schnittpunktfunktion, ist also doch gar nicht so kompliziert. Hier also der Code für den eben ausgelassenen else Fall:

else Fall Fortsetzung:
         // Gibt es einen Schnittpunkt?
         if (xUtil_Schnittpunkt(&vPunktA, // Linienstart
                                &vPunktB, // Linienende
                                &vAuf_Ebene,
                                &pEbene->vNormal,
                                &vSchnittpunkt,
                                &fProzent) == TRUE)
            {
            // Erstelle neuen Vertex mit Texturkoordinaten
            float fDeltaX, fDeltaY, fTexX, fTexY;

            fDeltaX = Poly->vVerts[wAkt_Vertex].tu -
                      Poly->vVerts[wLoop-1].tu;
            fDeltaY = Poly->vVerts[wAkt_Vertex].tv -
                      Poly->vVerts[wLoop-1].tv;
            fTexX = Poly->vVerts[wLoop-1].tu + (fDeltaX * fProzent);
            fTexY = Poly->vVerts[wLoop-1].tv + (fDeltaY * fProzent);

            // Erstelle einen Vertex aus dem Vektor
            D3DLVERTEX vKopie;
            vKopie.x     = vSchnittpunkt.x;
            vKopie.y     = vSchnittpunkt.y;
            vKopie.z     = vSchnittpunkt.z;
            vKopie.color = Poly->vVerts[0].color;
            vKopie.tu    = fTexX;
            vKopie.tv    = fTexY;

            // Neuen Punkt in Front- und Backliste
            vBackList[wAnz_Back++]   = vKopie; 
            vFrontList[wAnz_Front++] = vKopie;

            // Aktuellen Punkt auch noch einsortieren
            if (nErgbn == BSP_FRONT) {
               if (wAkt_Vertex != 0) {
                  vFrontList[wAnz_Front++] = 
                      Poly->vVerts[wAkt_Vertex];
                  }
               } // if [FRONT]
            else if (nErgbn == BSP_BACK) {
               if (wAkt_Vertex != 0) {
                  vBackList[wAnz_Back++] =
                      Poly->vVerts[wAkt_Vertex];
                  }
               } // else [BACK] 
            } // if [Schnittpunkt]

         // Falls kein Schnittpunkt können wir den Punkt
         // gefahrlos in die passende Liste einsortieren
         else {
            if (nErgbn == BSP_FRONT) {
               if (wAkt_Vertex!=0) {
                  vFrontList[wAnz_Front++] =
                      Poly->vVerts[wAkt_Vertex];
                  }
               }
            else if (nErgbn == BSP_BACK) {
               if (wAkt_Vertex!=0) {
                  vBackList[wAnz_Back++] =
                      Poly->vVerts[wAkt_Vertex];
                  }
               }
            } // else [kein Schnittpunkt]
else Fall komplett

Im Falle dass wir einen neuen Vertex erzeugen dürfen wir natürlich nicht vergessen auch den aktuellen Vertex, also Punkt B, zu klassifizieren und einzusortieren. Viel mehr gibt es hier nicht mehr anzumerken. 
So, damit haben wir dann alle Vertices des Polygons durchlaufen und in die entsprechenden Listen einsortiert. Der Rest ist dann wieder reine Pfannkuchenarbeit, denn wir müssen aus den beiden Listen nur noch die beiden Polys erstellen. Wir beginnen diese Arbeit damit, die entsprechenden Attribute des nun gesplitteten Originalpolygons in die beiden neuen Polygone zu kopieren. Insbesondere die verwendete Textur und die Information darüber ob dieses Polygon schon mal ein Splitter war. In diesem Fall dürfen die beiden neuen Polygone auch keine Splitter mehr werden da das geometrisch auch nichts bringen würde.

Split_Poly() Fortsetzung:
   // Attribute des alten Polys übernehmen
   FrontSplit->lAnz_Verts = 
      BackSplit->lAnz_Verts = 0;

   FrontSplit->nTextur_Index = 
      BackSplit->nTextur_Index = 
      Poly->nTextur_Index;

   FrontSplit->blnWar_schon_Splitter = 
      BackSplit->blnWar_schon_Splitter =
      Poly->blnWar_schon_Splitter;

   for (wLoop=0; wLoop < wAnz_Front; wLoop++) {
      FrontSplit->lAnz_Verts++;
      FrontSplit->vVerts[wLoop] = vFrontList[wLoop];
      }
   for (wLoop=0; wLoop < wAnz_Back; wLoop++) {
      BackSplit->lAnz_Verts++;
      BackSplit->vVerts[wLoop] = vBackList[wLoop];
      }

   BackSplit->lAnz_Indices  = (BackSplit->lAnz_Verts -2)*3;
   FrontSplit->lAnz_Indices = (FrontSplit->lAnz_Verts-2)*3;
wird fortgesetzt...

Interessant ist hier noch die Berechnung der Anzahl der Indices der neuen Polygone durch (Anz-2)*3. Unser Problem hier ist doch, dass wir die Polygone als Indexlisten durch DrawIndexedPrimitiveUP() rendern wollen. Damit müssen wir unser Polygon in Indices auf Dreiecke zerlegen. Das hatten wir ja eigentlich schon so weit, denn in unserer Leveldatei finden sich diese Indices. ABER beim Splitten eines Polys haben wir natürlich immer mindestens zwei neue Vertices in das Originalpolygon eingefügt (denn wenigstens ein Vertex des Polys liegt ja auf einer anderen Seite der Ebene und daher gibt es mindestens zwei Schnittpunkte mit der Ebene). Unsere Originalindexlisten stimmen also nicht mehr und wir müssen aus der Liste von Vertices der neuen Polys eine neue Dreickeszerlegung in Indices vornehmen.
Glücklicherweise ist dies einfacher als es klingt...jedenfalls für konvexe Polygone. Merken wir uns also erst mal, dass wir in unserer Leveldatei auch nur konvexe Polygone haben sollten, denn sonst können wir beim Splitten dieser Polygone Probleme bekommen. Die Zerlegung ist denkbar einfach. Wir nehmen die ersten drei Vertices aus der Vertexliste des Polygons. Diese ergeben das erste Dreieck. Den ersten Vertex des Polygons behalten wir bei, den zuletzt verwendeten ebenfalls (in diesem Fall der dritte des Polys). Den zweiten Vertex des Dreiecks ersetzen wir durch den folgenden aus der Vertexliste. Das machen wir so lange bis wir keine Vertices in der Liste mehr haben. Der erste Vertex des Polys ist also immer der erste Vertex eines Dreiecks der Zerlegung. 
Bei einem Poly mit fünf Vertices sieht die Dreieckszerlegung also wie folgt aus:

v0, v1, v2
v0, v2, v3
v0, v3, v4

Und tatsächlich haben wir (Anz-2)*3 = (5-2)*3 = 3*3 = 9 Indices in der Liste, denn wir haben drei Dreicke mit je 3 Indices. Bewaffnet mit diesem Wissen können wir jetzt die letzten Zeilen des Codes zur Erstellung des BSP Baums schreiben:

Split_Poly() Fortsetzung:
   // Berechne die Dreieckszerlegung und speichere sie
   WORD v0,v1,v2;
   for (wLoop=0; wLoop<FrontSplit->lAnz_Indices/3; wLoop++)
      {
      if (wLoop==0) {
         v0=0;
         v1=1;
         v2=2;
         }
      else {
         v1=v2;
         v2++;
         }

      FrontSplit->wIndices[(wLoop*3)+0] = v0;
      FrontSplit->wIndices[(wLoop*3)+1] = v1;
      FrontSplit->wIndices[(wLoop*3)+2] = v2;
      } // for

   //  Backpoly
   for (wLoop=0; wLoop<BackSplit->lAnz_Indices/3; wLoop++)
      {
      if (wLoop==0) {
         v0=0;
         v1=1;
         v2=2;
         }
      else {
         v1=v2;
         v2++;
         }

      BackSplit->wIndices[(wLoop*3)+0] = v0;
      BackSplit->wIndices[(wLoop*3)+1] = v1;
      BackSplit->wIndices[(wLoop*3)+2] = v2;
      } // for

   FrontSplit->xEbene = this->Ebene_von_Poly(&(*FrontSplit));
   BackSplit->xEbene  = this->Ebene_von_Poly(&(*BackSplit));
   } // Split_Poly
/*---------------------------------------------------------*/

Strike!

Propaganda, Rendern des BSP für die Zuschauer am Bildschirm

Es ist vorbei...die Schlacht gegen die bösen Mächte der 3D Mathematik ist ein weiteres Mal erfolgreich von uns geschlagen worden. Nun bleibt uns nur noch eines, wir müssen unseren Sieg so richtig auskosten. Was haben wir von dem besten BSP Baum der Welt wenn wir diesen niemandem zeigen können. Schreiben wir uns also fix ein paar Funktiönchen zum Rendern des Baumes. Beginnen wir mit einer allgemeinen Funktion die der Programmierer aufrufen muss und die dann den Rest erledigt:

void XBSP::Render(void) {
   D3DMATRIX matWelt;

   // Weltverschiebung auf 0 setzen
   xUtil_Einheitsmatrix(&matWelt);
   g_lpD3DDevice->SetTransform(D3DTS_WORLD, &matWelt);

   // Vertex Shader einstellen
   g_lpD3DDevice->SetVertexShader(D3DFVF_LVERTEX);

   // D3D Lichtengine ausschalten da Prelit-Vertices
   g_lpD3DDevice->SetRenderState(D3DRS_LIGHTING, FALSE);

   // Den ganzen BSP Baum durchrendern
   this->Render_rekursiv(&this->xWurzel, xKam.vPos);

   // D3D Lichtengine wieder einschalten
   g_lpD3DDevice->SetRenderState(D3DRS_LIGHTING, TRUE);
   } // Render
/*----------------------------------------------*/

In dieser Mantelfunktion wecken wir das Direct3D Device auf und schieben dann die ganze Arbeit auf die Render_rekursiv Funktion unserer BSP Klasse weiter. Ebenso wie wir den Baum rekursiv erstellen können, können wir ihn natürlich auch rekursiv durchlaufen. Überlegen wir mal was wir eigentlich rendern müssen. Die gesamte Geometri steckt doch in den Leafs des Baumes. Wir müssen also alle Äste des Baumes ablaufen bis wir in einem Leaf landen und dann dessen Geometrie rendern. Dan tun wir das doch einfach:

void XBSP::Render_rekursiv(XNODE *pNode,
                           D3DVECTOR vPosition) {
   int nKlasse;

   // View Frustrum Culling des Nodes
   if (xUtil_Cull_AABB(&pNode->xBox) == BOX_AUSSERHALB)
      return;

   // Falls dieses Element ein Leaf ist dann rendere seine Polys
   if (pNode->blnLeaf) {
      this->Render_Leaf(pNode);
      return;
      }

   // Sonst wandere weiter, je nach Position des Spielers
   nKlasse = this->Klassifiziere_Punkt(pNode->xEbene, vPosition);

   if (nKlasse == BSP_BACK) {
      Render_rekursiv(pNode->pFront, vPosition);
      Render_rekursiv(pNode->pBack, vPosition);
      }
   else {
      Render_rekursiv(pNode->pBack, vPosition);
      Render_rekursiv(pNode->pFront, vPosition);
      }
   } // Render_rekursiv
/*----------------------------------------------*/

In dieser Funktion testen wir dann endlich auch die Bounding Box eines Nodes gegen den View Frustrum. Kommen wir an eine Stelle im Baum wo die Bounding Box ausserhalb des Frustrums liegt so können wir die Arbeit an diesem Ast abbrechen. Treffen wir auf ein Leaf so schieben wir die Arbeit wiederum an eine andere Funktion weiter. Und nun kommt wieder ein kleiner BSP Trick. Wir prüfen jetzt, wenn wir also einen Ast im View Frustrum haben, die Position der Kamera zu der Ebene des Nodes an dem wir uns befinden. Ist die Position der Kamera hinter der Ebene so rendern wir zuerst alle Kindernodes der Frontseite des aktuellen Nodes. Häh?
Okay, das liegt daran dass alle Polygone auf der Frontseite dann weiter von der Kamera entfernt sind als diejenigen auf der Backseite. Und wir wollen die Polygone ja von hinten nach vorne rendern um beispielsweise Transparanzeffekte korrekt darstellen zu können. Umgekehrt rendern wir zuerst die Kindernodes der Backseite wenn die Kamera auf der Frontseite liegt.

Render, render, render. Nun kommt endlich die Funktion die tatsächlich etwas auf den Bildschirm malt:

void XBSP::Render_Leaf(XNODE *pNode) {
   XPOLY *pPoly = pNode->pPolys;

   // Durchlaufe alle Polys im Leaf und rendere sie
   for (int i=0; i<pNode->lAnz_Polys; i++, pPoly++) {
      // Textur des Polys einstellen
      #define n pPoly->nTextur_Index
      g_lpD3DDevice->SetTexture(0, this->aTextur[n].lpTextur);

      g_lpD3DDevice->BeginScene();
      g_lpD3DDevice->DrawIndexedPrimitiveUP(
               D3DPT_TRIANGLELIST,    // echte Dreiecke
               0,                     // Min Index
               pPoly->lAnz_Verts,     // Anz Vertices
               pPoly->lAnz_Indices/3, // Anz Primitive
               pPoly->wIndices,       // Indexliste
               D3DFMT_INDEX16,        // 16 Bit Indices
               pPoly->vVerts,         // Vertexliste
               sizeof(D3DLVERTEX));   // Vertexgrösse
               g_lpD3DDevice->EndScene();
      } // for
   } // Render_Leaf
/*------------------------------------*/

Boah...langweilig oder? Wir müssen einfach nur alle Polygone in der Liste des Leafs durchlaufen. Für jedes Polygon setzen wir dann die entsprechende Textur und rendern es als indizierte Primitive. Bitte mal die Hand heben wer jetzt enttäuscht ist dass ein BSP Baum eigentlich so einfach ist :-)

Beseitigung der Trümmer

So, nachdem wir dann die Schlacht geschlagen haben müssen wir nachher auch die Trümmer aufräumen, sprich den allokierten Speicher wieder freigeben. Das ist hier natürlich denkbar einfach. Alle Texturen des BSP Baums müssen gekilled werden und alle Polygonlisten in den Leafs müssen ihres Speichers beraubt werden. Das machen wir mit den folgenden beiden Funktionen.

void XBSP::Kill(void) {
   // Texturen freigeben
   for (int i=0; i<this->Anz_Texturen; i++) {
      this->aTextur[i].lpTextur->Release();
      this->aTextur[i].lpTextur = NULL;
      } // for

   // Speicher der Polygonlisten freigeben
   this->Kill_rekursiv(&this->xWurzel);
   } // Kill
/*----------------------------------*/

void XBSP::Kill_rekursiv(XNODE *pNode) {
   // Falls Element ein Leaf Speicher freigebn
   if (pNode->blnLeaf) {
      free(pNode->pPolys);
      pNode->pPolys = NULL;
      }

   // Falls Kinder dann diese auch killen
   if (pNode->pBack)
      this->Kill_rekursiv(pNode->pBack);
   if (pNode->pFront)
      this->Kill_rekursiv(pNode->pFront);
   } // Kill_rekursiv
/*----------------------------------*/

Der BSP Baum in unserem Code

Let's rock! Jetzt haben wir den BSP Baum sauber gekapselt und können ihn wunderbar einfach in unserem Code verwenden. Dazu brauchen wir lediglich ein Objekt der Klasse zu deklarieren:

XBSP BSP_Baum;

Dieses werden wir dann in Phase 1, also bei der Initialisierung des Programms, mit den Daten füllen bzw. den BSP Baum berechnen lassen:

// Initialisiere den BSP Baum
blnErg = BSP_Baum.Init("testlevel.zfx");
if (blnErg == FALSE) {
   fprintf(Protokoll,"SpielInit: BSP failed \n");
   g_blnBeenden = TRUE;
   return FALSE;
   }

In der zweiten Phase, also dem Laufen des Programms, können wir den Baum dann ganz einfach in den BackBuffer rendern:

// Indoorlevel rendern
BSP_Baum.Render();

Zu guter Letzt müssen wir dann in der Phase 3, also dem Beenden des Programms, auch brav alles aufräumen und geordneten Speichern hinterlassen:

// BSP Baum Speicher freigeben
BSP_Baum.Kill();

Pfannkuchen.

Was kommt denn jetzt noch?

Keine Panik, jetzt haben wir wirklich alles komplett was wir an Quellcode brauchen und unser Demo ist damit wirklich fertig. Bevor ich Euch aber den Code downloaden lassen will ich noch einen Ausblick geben wie wir den Code verbessern können um die Technik des BSP Baumes noch schneller zu machen als sie jetzt schon ist.

Noch schneller rendern durch zwei BSP Bäume...

Eines der Probleme unseres aktuellen BSP Baums ist der Overdraw der Trotz des Bounding Box Tests auftritt. Befindet sich die Kamera etwa in einem sehr kleinen Raum und dahinter befindet sich ein sehr grosser konvexer Raum der ein einzelnes Leaf des Baumes ist, so liegt die Bounding Box dieses Leafs eventuell nur um wenige Millimeter im View Frustrum, wir zeichnen dann aber blind alle Polygone des Raums. Dabei senden wir auch viele Triangle an das Device die eh bereits ausserhalb des View Frustrums liegen.
Diesem Problem widmet sich der Ansatz der View Space Method. (siehe Eberly, 2000)

Nach der Erstellung des BSP Baumes unserer Welt, genannt Welt-Baum, erzeugen wir in jedem Frame einen zweiten BSP Baum, genannt Sichtbarkeits-Baum. Dieser Baum enthält bei seiner Erstellung zunächst nur sechs Partioning Planes, nämlich genau die sechs Ebenen des View Frustrums. Dann beginnen wir damit unsere Welt-Baum zu durchlaufen. Alle Polygone die wir in den Welt-Baum Leafs finden (idealerweise kombiniert mit dem Bounding Box Test) senden wir dann an die Wurzel des Sichtbarkeits-Baums und lassen sie durch diesen Baum wandern. Alle Polygone werden nun durch die View Frustrum Ebenen klassifiziert und in der Frontliste der sechsten View Frustrum Ebene landen dann tatsächlich nur genau die Polygone (oder Teilpolygone nach entsprechenden Splits) die wirklich im View Frustrum liegen. Das gute an dieser Methode ist, dass wir die Funktionen für die Berechnung des BSP Baumes bereits zur Verfügung haben, ebenso wie die Ebenen des View Frustrums. Die Nachteile dieser Methode sind, dass wir den Sichtbarkeits-Baum wirklich in jedem Frame erstellen müssen was bei modernen Grafikkarten nicht unbedingt schneller ist als das blinde Rendern aller Polys aller Bounding Boxen die wenigstens teilweise im View Frustrum liegen.

Da muss es doch noch eine bessere Methode geben? Und die gibt es auch. Man kann nämlich tatsächlich vorherberechnen, welche anderen Leafs von dem Leaf aus gesehen werden können in dem sich die Kamera befindet. Und das nennt sich PVS.

...oder durch Vorberechnung des PVS

Ein kommerzielles Spiel in der Qualität von Quake braucht natürlich mehr. In diesem Tutorial werden wir dieses mehr aus Platzgründen nicht behandeln, aber ich möchte wenigstens erklären was genau dieses mehr macht.

Das Zauberwort heisst PVS, oder auch Potential Visibility Set. Unser BSP Baum beruht bisher auf der fundamentalen Basis, dass wir den Baum mehr oder weniger vollständig durchlaufen. Wir besuchen wenigstens alle Äste die im Sichtbereich des Spielers liegen wobei sich auch von diesen wieder sehr viele gegenseitig verdecken werden und zu Overdraw führen. An genau diesem Problem setzt das PVS System an, und es funktioniert wie folgt. Zuerst berechnen wir den vollständigen BSP Baum für unsere Leveldaten. Danach durchläuft das PVS System den Baum und stoppt an jedem Leaf, also an jenen Baumelement die eine Teilmenge von Polygonen konvexer Anordnung enthalten. Nun berechnet das PVS System für jedes einzelne Leaf exakt welche anderen Leafs von einem Leaf aus gesehen werden können.

Gehen wir einmal davon aus, dass wir unsere Leafs durchnummeriert haben. Dann berechnet das PVS beispielsweise: Wenn der Spieler sich in Leaf Nummer 234 befinden, dann kann er von dort aus maximal Leaf Nummer 433, 235, 654, 123 und 456 sehen. Egal an welcher Stelle im Leaf 234 sich der Spieler befindet und wie er sich auch dreht und wendet. Um uns das besser vorzustellen nehmen wir einmal an das Leaf 234 sei ein ganzes Zimmer mit einer offenen Tür. Egal wie der Spieler sich dreht und wendet er kann auf alle Fälle nur die Leafs sehen die man auch in der realen Welt physisch durch die Tür sehen könnte, keine anderen, selbst wenn diese im View Frustrum des Spielers liegen, denn sie werden durch die Wände des Raumes verdeckt. 
Das PVS System berechnet also für jedes Leaf ganz exakt welche anderen Leafs ein Leaf potentiell sehen kann und speichert in jedem Leaf eine entsprechende Liste von sichtbaren Leafs. Wenn wir den BSP Baum nun rendern wollen, oder Kollisionsabfragen o.a. durchführen, so laufen wir den Baum nur einmal, einen Ast herunter bis wir das Leaf finden in dem der Spieler sich befindet. Dann nehmen wir die dort gespeicherte Liste und wissen sofort ohne einen einzigen Test durchzuführen welche anderen Leafs wir rendern müssen. Selbst bei einem Level in Quake Grösse mit 10'000 oder mehr Polygonen erhalten wir so in rasender Geschwindigkeit eine Menge von sagen wir mal 800 Polygonen (bei sehr offener Geometrie, sonst wesentlich weniger) die potentiell sichtbar sind. Was aber viel wichtiger ist: Alle anderen 9'200 Polygone des gesamten Levels sind auf alle Fälle nicht sichtbar und müssen nicht transformiert, gerendert oder sonst irgendwie beachtet werden.
Für die potentiell sichtbaren Leafs führen wir dann auch noch die Bounding Box Tests durch. Der Raum in dem der Spieler sich befindet kann beispielsweise an zwei gegenüberliegenden Wänden je eine Türöffnung haben. Das PVS System speichert dann in der Liste der sichtbaren Leafs für diesen Raum alle Leafs die man durch beide Türöffnungen sehen kann. Physisch kann sich der Spieler aber nie so positionieren, dass er gleichzeitig durch beide Türen blicken kann. Daher enthält die vom PVS generierte Liste eventuell auch Leafs, die nicht sichtbar sind, daher die Bezeichnung Potential Visibility und die Notwendigkeit des Bounding Box Tests. Wir müssen aber nun nicht mehr alle Nodes des gesamten Baumes testen, sondern nur noch die paar Leafs die in der PVS Liste gespeichert sind. Damit sparen wir enorm viel an Berechnungen und unsere Level können theoretisch unendlich gross sein ohne dass die Framerate kleiner wird.

So, das war ein kleiner Theoriekurs in Sachen PVS. Sowohl die Erstellung des BSP Baumes als auch die PVS Berechnung (für die man Portale verwendet) finden natürlich normalerweise vor dem Start unseres Programms statt, da die entsprechenden Berechnungen sehr zeitaufwendig sind. Wenn wir also unser Quake starten, so wird der vorher berechnete und gespeicherte, fertig kompilierte BSP Baum mit PVS Liste in den einzelnen Leafs von der Festplatte als solcher einfach geladen und dann verwendet. Das ist auch der Grund, warum sich die Architektur während des Spiels nicht ändern darf. Zum einen geht dabei die Übereinstimmung des BSP Baumes mit der Levelgeometrie verloren und zum anderen stimmen natürlich die PVS Daten nicht mehr, wenn sich die Leafs (oder schlimmer noch Polygone verschiedener Leafs) bewegen.

Und wie geht es jetzt weiter?

Okay...wow, Zeit sich etwas abzukühlen bevor wir diese Frage klären. Wir haben nun eine stabile 3D Engine mit der wir unsere 3D Indoor Level am Screen in sinnvoller Geschwindigkeit rendern können, selbst ohne fancy 3D Beschleuniger. Es gibt allerdings noch eine Anmerkung zum Rendern. Wir rufen die Renderfunktion DrawIndexedPrimitiveUP() für jedes Leaf des Baumes einzeln auf. Das ist nicht sehr schnell, eher im Gegenteil. Idealerweise würden wir die Indizes auf die Vertices aller sichtbaren Leafs in einer grossen Liste speichern und dann noch nach Texturkoordinaten ordnen. Dann könnten wir alle Indizes in einem Frame die dieselbe Textur verwenden durch einen einzigen Funktionsaufruf rendern und hätten nur so viele Aufrufe der Renderfunktion wie wir verschiedene Texturen haben. Das würde die Geschwindigkeit unserer Engine noch einmal beträchtlich erhöhen.

Zusammen mit dem Kamerasystem des vorletzten Artikels kann der Betrachter auch in dem Level manövrieren und sich alles betrachten. Man wird jedoch schnell feststellen, dass man durch die Wände gehen kann und dass auch die Höhe des Spielers über dem Boden nicht angepasst wird. Beides sind Probleme der sogenannten Kollisionsabfrage. Unsere Polygone am Bildschirm sind natürlich nur bunte 2D Grafiken und keine wirklich soliden Wände durch die man nicht hindurch gehen kann. Der Computer tut schliesslich nur was man ihm sagt und wenn wir ihm sagen bewegen die Kamera nach vorne so tut er das. Ob da eine Grafik ist oder nicht. Wir müssen dem Computer also extra testen lassen ob das eine Wand ist oder nicht.

Denken wir erst mal an die automatische Anpassung der Höhe des Spielers über dem Boden. Alles was man dazu tun muss ist folgendes: In jedem Leaf welches gerendert wird prüft man noch, ob sich die Kameraposition innerhalb der Bounding Box dieses Leafs befindet. Dabei prüft man aber lediglich die x und z Werte voll und prüfen bei dem y Wert lediglich ob die Kamera in oder über der Box ist. Schliesslich kann der Spieler sich ja auch über der Box befinden, sollte aber direkt auf einem Polygon in der Box stehen. Also müssen wir auch alle Boxen testen die unter der Kamera liegen. Haben wir es mit einer solchen Box zu tun, in oder über der sich die Kamera befindet, dann durchlaufen wir die Liste der Polygone dieses Leafs. Von der Position der Kamera aus starten wir eine Linie über eine genügend grosse Distanz nach unten und prüfen welches der Polygone (nicht die Ebenen) diese Linie schneidet. Von allen Polygonen die diese Linie schneiden wählen wir dasjenige aus welches am nähesten unter der Kamera liegt und legen die y Position der Kamera auf den y Wert des Schnittpunktes fest, plus einem Wert von 1.7f für die Augenhöhe über dem Boden. Ich gebe zu dass das mit etwas Mathematik verbunden ist...
Die Kollision mit Wände ist ebenfalls leicht :-) in den Leafs in den die Kamera sich befinden könnte klassifiziert man die Position der Kamera (nachdem die Kamera nach der Neuberechnung der Höhe immer noch in diesem Leaf ist) gegen alle Ebenen der Polys in dem Leaf. Die Kamera darf nie auf eine Backseite eines Polys kommen, sonst hat der Spieler gerade eine Wand durchlaufen. Ist dies der Fall so muss die Kamera zurück auf die Frontseite des Polys gesetzt werden (Position der Kamera plus Normalenvektor der Ebene). Fertig!

Als nächstes fehlt es der Engine an der Möglichkeit, statische Objekte einzubinden, beispielsweise Tische, Schränke, Lampen, usw. Hierbei gilt es anzumerken, dass das Beispiellevel NICHT sehr gut durchdacht ist. In dem Beispiellevel habe ich bereits zu viele detaillierte Objekte eingebaut, die den BSP Baum unnötig vergrössern und die man besser nach der Erstellung des Baumes als statische Objekte eingefügt hätte (z.B. die Säulen in dem Startraum, Holzstützen im Kellergeschoss, Computerkonsolen im Hangarkontrollzentrum). Alle diese Objekte unterteilen das Level nicht kritisch, denn sie sind nur Objekte in einem Raum und verdecken andere Geometrie in diesem Raum nur minimal, so dass sich das Einbinden der Objekte in den BSP im Vergleich zur Alternative des Overdraws nicht lohnt. Wie machen wir das also besser?
Die Leveldatei sollte wirklich nur die Architektur aus Wänden, Decken, Böden und Treppen enthalten. Danach erstellen wir den BSP Baum und speichern ihn auf Diskette. Als nächstes haben wir ein Programm mit welchem wir den fertigen BSP Baum laden können. In diesem Programm erstellen wir dann die Objekte wie Tische, Lampen, Computerkonsolen und speichern in dem BSP Baum dann Informationen über die Objekte. Beispielsweise kann man ein Objekt und dessen Bounding Box von der Wurzel ab durch den BSP Baum jagen. Wir prüfen an jedem Node ob die Bounding Box noch komplett in die Bounding Box eines der beiden Kinder passt. Ist dies der Fall so schicken wir das Objekt an diesen Kind-Node. Passt die Box irgendwann nicht mehr in ein Kind-Node so speichern wir das Objekt an dem Node wo es zuletzt in die Bounding Box gepasst hat. Beim Durchlaufen des BSP Baumes für das Rendern prüfen wir dann zusätzlich jeden Node des Baumes auf eine Liste mit Objekten. Finden wir dort welche rendern wir sie einfach, der Z Buffer wird's schon richten :-)

Dieselbe Methode verwendet man übrigens auch für bewegte Objekte in einem BSP Level. Türen oder Fahrstühle könnte man beispielsweise in denjenigen Node des Baums einsortieren in dessen Bounding Box das Objekt mitsamt seines gesamten möglichen Bewegungspfades passt. Also eine Tür gehört in den Node in dessen Bounding Box sie sowohl offen als auch geschlossen ganz hineinpasst. 
Bei echten animierten Objekten die sich uneingeschränkt bewegen können, wie beispielsweise Gegner, gibt es auch wieder viele Alternativen. Für unseren BSP Baum wäre es vielleicht am sinnvollsten diese Objekte nicht unbedingt in den Baum einzusortieren, sondern eine getrennte Liste für diese zu haben. Vor oder nach dem Rendern des BSP Baums komen dann diese Objekte an die Reihe und werden mit ihren eigenen Bounding Volumes gegen den Viewport getesten und bei potentieller sichtbarkeit gerendert. Erst bei einem PVS macht es Sinn diese Objekte in jedem Frame neu in den BSP Baum einzusortieren und nur diejenigen in den sichtbaren Leafs zu rendern.

Ja...das war eigentlich auch schon das Wichtigste was dem Programm noch fehlt um 3D Indoorlevel von hoher Detailstufe mit vielen Objekten zu bauen und zu verwenden. Ein PVS System zu integrieren wäre natürlich auch eine feine Sache, aber das ist eine Übung für später. Im dritten Band meiner Bücherreihe über 3D Spieleprogrammierung werde ich dann das Beispiel-Spiel Pandoras Box entwickeln und erläutern in dem natürlich auch statische und animierte Objekte vorkommen und der Spieler sich durch seine Waffen gegen die hartnäckigen Angriffe von Gegnern verteidigen darf. Dazu werden die notwendigen Tools wie beispielsweise ein Leveleditor entwickelt und erläutert und es gibt natürlich die Möglichkeit, den kompilierten BSP Baum mit den Objektlisten auf Festplatte zu speichern und in das Spiel zu laden. 

Level mit AC3D bauen

Nun auf ein Wort zum Download: Darin enthalten ist auch ein AC3D Plugin zfxexport.p für das Exportieren von Leveldaten aus AC3D in das richtige Format für dieses Tutorial. Kopiert die Datei einfach in das PLUGINS Verzeichnis von AC3D. Es gilt hierbei dass AC3D Level wegen des potentiellen Polygonsplittings nur aus konvexen Polygonen gebaut werden sollten und alle Polygone einzelne Objekte sind (keine Gruppen oder Objekte mit mehreren Polys). Die Farben die man für die Polys festlegt bestimmen dann die endgültigen Farben im gerenderten BSP. Ein weisses Poly hat also helles weisses Licht, ein schwarzes Poly hat kein Licht, ein rotes Poly wird von rotem Licht angestrahlt, usw. Ach ja, nach dem Export muss man sich die Leveldatei mit der Endung *.zfx noch einmal ansehen und die Pfadangaben bei den Texturen korrigieren. AC3D exportiert hier meistens den kompletten Pfad c:\programme\ac3d usw. Dann kann man in jedem einfachen Texteditor die Funktion Ersetzen wählen und diesen Pfad durch nichts ersetzen lassen.
Im Download gibt es auch das Beispiellevel das ich erstellt habe. Das ist zwar nicht besonders gross, aber ich dachte mir bevor ich nach tagelang daran baue bringe ich die Sachen lieber online. Ein Raum (sollte mal eine Kirche werden) ist auch noch nicht ordentlich textuiert und schattiert, aber dann könnt Ihr auch gleich ein wenig mit AC3D das Levelbauen über. Der Beweis für die Lauffähigkeit des Codes ist also erbracht und das Level bietet auch komplexe 3D Geometrie um zu zeigen dass das hier kein Fake mit 2,5D statt 3D ist :-)

ACHTUNG: Leider gab es bei AC3D ein paar Probleme mit der Beleuchtung, daher mag der Level nicht sehr schön beleuchtet erscheinen. In AC3D wird eine Punktlichtquelle verwendet die alle Geometrie abhängig von der Rotation der Objekte in der Welt berechnet. Daher kann man den korrekten Farbwert der Polxgone nie so erkennen wie er später in diesem Code hier erscheinen wird.

Und hier gibt es den Code des gesamten Tutorials zum Download: Projektdateien