TUTORIAL: WIE FUNKTIONIERT EIN BSP-TREE UND WIE MANN MAN IHN GRAFISCH BEI DER 3D-PROGRAMMIERUNG EINSETZEN? (TEIL 1) Ich habe das ganze Ding in Kapitel unterteilt: INHALTSVERZEICHNIS KAPITEL 1: ERKLÄRUNG DES FUNKTIONSPRINZIPS KAPITEL 2: WIE MAN ES PROGRAMMIERT (SO SIEHT EIN "NODE" AUS) KAPITEL 3: BEISPIELE FÜR VERSCHIEDENE MÖGLICHKEITEN KAPITEL 4: DIE SONDERFÄLLE BEIM EINORDNEN DER LINIEN KAPITEL 5: WIE BENUTZT MAN BINÄRE BÄUME ZUR 3D-DARSTELLUNG? KAPITEL 6: SCHWÄCHEN DES VERFAHRENS MIT BINÄREM BAUM (BSP-TREE) KAPITEL 7: DIE MATHEMATISCHE LÖSUNG FÜR DIE PRÜFUNG, OB PUNKTE "VOR" ODER "HINTER" DER LINIE SIND KAPITEL 8: WIE ERMITTELT MAN, WO MAN SELBST SICH IM LEVEL BEFINDET? KAPITEL 9: WIE VERMEIDET MAN ES, DURCH WÄNDE ZU LAUFEN (CLIPPING) ? KAPITEL 10: WIE KANN MAN DAS ALLES AUF "ECHTES" 3D ANWENDEN? KAPITEL 11: DIE "ANDERE" METHODE, UM 3D FIGUREN IM RAUM ZU ORDNEN KAPITEL 12: BEWEGLICHE FIGUREN ("SPRITES") IM LEVEL KAPITEL 13: SO MACHT ES DIE GRAFIKKARTE KAPITEL 14: SCHLUßWORTE DES VERFASSERS - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - KAPITEL 1: ERKLÄRUNG DES FUNKTIONSPRINZIPS BSP bedeutet Binary Space Partitioning - also Binäre Raum-Aufteilung. Und genau dieses ist damit gemeint. Das Prinzip erklärt sich so: Wenn man auf eine Gegenstand sieht, sieht man zuerst alle Gegenstände, die DAVOR stehen, dann (wenn man Glück hat) den Gegenstand SELBST und danach (wenn man noch mehr Glück hat) die Gegenstände, die sich dahinter befinden. Ich erkläre das jetzt zunächst erst einmal für das "zweieinhalb-D" (also Pseudo-3D), wie es in DOOM und anderen frühen Shootern benutzt wird. (Weil es anschaulicher ist.) Ich komme dann später noch auf "richtiges" 3D. Achja: Die in Kapitel 11 beschriebene Methode ist in der Ausführung wahrscheinlich schneller als der "reine BSP" und ein wenig flexibler. (Man sollte sich aber evtl. DOCH das andere auch durchlesen, um hinter das Prinzip des ganzen zu kommen.) Dazu stellt man sich einfach vor, man würde das ganze 3D-Level von oben sehen, die Wände sind also alle nur Linien - denn sie können in DOOM & Co nur senkrecht stehen. Nun führt man für jede Linie genau das aus, was ich oben gesagt habe. Man verlängert in Gedanken die Linie so, daß sie eine Gerade ist, die den gesamten Raum in zwei Teile teilt und dann sortiert man die restlichen Linien je nachdem, wo sie sich befinden, in den "linken" oder "rechten" Raum davon. Allerdings muß man das für jede neue Linie machen, den jede weitere Linie teilt den "Rest-Raum" WIEDER in 2 Teile - bis zum Schluß keine Linien mehr vorhanden sind. KAPITEL 2: WIE MAN ES PROGRAMMIERT (SO SIEHT EIN "NODE" AUS) Für einen Programmierer klingt das möglicherweise zu abstrakt, daher werde ich das jetzt für Programmierer erklären. Dazu führe ich den Begriff Node (Knoten) ein. Solche Nodes sind immer eine "Astgabel" des Baums. Jeder Node enthält 3 Daten: Einen Zeiger auf eine Linie (die man dann "verlängern" kann), und zwei Zeiger auf einen "Folge-Node", einen für die "linke Seite" und einen für die "rechte Seite" der Linie. (Das ist so, weil ich davon ausgehe, daß die beiden Punktkoordinaten ja schon bei der Linie SELBST definiert wurden, so daß es Blödsinn ist, diese NOCH EINMAL irgendwo zu nennen.) Die erste Linie trägt man einfach so ein. Die beiden Folge-Nodes setzt man auf $FFFF (oder sonst irgendwas ungültiges - d.h. man definiert einfach eine Zahl, die bedeutet: KEIN NODE). So ein "kein Node"-Wert bedeutet: Offenes Ende. Dann kommt die nächste Linie. Und für alle Linien außer der ersten macht man die folgende Prüfung: Man "verlängert" die Linie des schon vorhandenen Nodes (lineare Algebra und prüft, auf welcher Seite sich der Anfangs- und Endpunkt der neu einzusortierenden Linie befinden. (Dazu muß man darauf achten, daß es NICHT egal ist, welcher Punkt der "Node-Linie" (also der ERSTEN die man verlängert hat) der ANFANGS- und welcher der ENDPUNKT ist. (Denn nur auf die Art gibts ja wirklich ein eindeutiges "Links" und "Rechts" der Linie - egal, wie diese im Raum gedreht ist!!!) Ich erkläre später noch, wie man sowas rein programmtechnisch macht. Nehmen wir an, im Koordinatensystem wäre A "unterhalb" (also südlich) von B und man definiert diesen Zustand so, daß links der Linie der ERSTE Folgenode und rechts der linie der ZWEITE Folgenode folgt. Dann würde, wenn A und B genau vertauscht wären, sich auch "links" und "rechts" vertauschen (weil man sich vorstellen muß, man sähe die Linie IMMER so, daß A senkrecht unter B steht - d.h. "rechts" wäre in dem Fall das, was (optisch gesehen) auf der "Karte" links wäre. Wenn man's bis hierhin verstanden hat, ist es schonmal gut. So. Und nun prüft man also BEIDE Punkte der neuen Linie, wo sie sich im Bezug zur Geraden durch A und B befinden. (Wie gesagt: Ich erkläre weiter unten nochmal, wie man sowas macht - das gehört erstmal nicht zum BSP selbst.) Sind beide "LINKS" der Linie, sortiert man sie als ERSTEN Node ein, sind beide RECHTS der Linie, dann als ZWEITEN. Nehmen wir einmal an, beide Punkte lägen links der Linie, dann würde man zum ersten Folge-Node gehen. Ist dieser $FFFF - also ungültig - trägt man den Node für die neue Linie einfach dort ein. Ist dieser NICHT $FFFF, dann muß man auch für DIESEN Node wieder prüfen, wo sich beide Punkte der Linie im Verhältnis zur verlängerten Linie befinden. D.h. man definiert für jede Linie (mindestens) einen neuen "Node" und diesen läßt man quasi "durch die Nodes durchrieseln", bis man an ein "offenes Ende" kommt - und dort trägt man den neuen Node ein. KAPITEL 3: BEISPIELE FÜR VERSCHIEDENE MÖGLICHKEITEN Nehmen wir an, die Linien wären durchnumeriert 0 bis x, und man würde bei den Nodes auch mit 0 beginnen zu zählen. Linie 1 wäre "links" von Linie 0. Dann sähen die ersten beiden Nodes so aus: Node 0: - Zeiger auf Nummer der Linie: 0 - Zeiger auf ersten FolgeNode: 1 - Zeiger auf zweiten FolgeNode: $FFFF Node 1: - Zeiger auf Nummer der Linie: 1 - Zeiger auf ersten FolgeNode: $FFFF - Zeiger auf zweiten FolgeNode: $FFFF Nehmen wir nun an, Linie Nummer 2 befände sich jetzt "rechts" von Linie 0 - dann würde Node 0 geändert und Node 2 hinzugefügt. Node 0: - Zeiger auf Nummer der Linie: 0 - Zeiger auf ersten FolgeNode: 1 - Zeiger auf zweiten FolgeNode: 2 (Hier Node 2 eingetragen) Node 1 wäre unverändert. Node 2: - Zeiger auf Nummer der Linie: 2 - Zeiger auf ersten FolgeNode: $FFFF - Zeiger auf zweiten FolgeNode: $FFFF Nehmen wir nun einmal an, das wäre NICHT so, sondern Linie 2 wäre auch "links" von Linie 0, aber "rechts" von Linie 1. Dann würden sich folgende Nodes ergeben (Node 1 geändert und Node 2 hinzugefügt) : Node 0 bliebe unverändert (weil weitergegangen zu Node 1) Node 1: - Zeiger auf Nummer der Linie: 1 - Zeiger auf ersten FolgeNode: $FFFF - Zeiger auf zweiten FolgeNode: 2 (Node 2 würde HIER eingetragen) Node 2 wäre wie oben. So etwas kann man am besten mit rekursiver Programmierung machen - müßte man aber nicht - wenn es nicht die SONDERFÄLLE gäbe. KAPITEL 4: DIE SONDERFÄLLE BEIM EINORDNEN DER LINIEN Es gibt noch drei Sonderfälle, die eine gesonderte Behandlung brauchen: 1. Sonderfall: Was macht man, wenn ein Punkt sich LINKS, der andere RECHTS der Linie befindet? In diesem Fall sortiert man die Linie links UND rechts ein! So komisch das klingt, aber GENAU SO wird es gemacht. Das passiert folgendermaßen: Man ermittelt den Schnittpunkt der beiden Linien. (wieder: lineare Algebra, Gleichungssystem mit zwei Gleichungen und zwei Unbekannten. Die Gleichungen sind die linearen Gleichungen für die Linien. Die Unbekannten sind die beiden Koordinaten des Schnittpunkts.) Und diesen Schnittpunkt definiert man als NEUEN PUNKT. Und dann definiert man zwei NEUE LINIEN. Nehmen wir an, die Punkte der zu prüfenden neuen Linie wären C und D. Dann würde man einen neuen Punkt E definieren und zwei neue Linien C->E und E->D. (Btw: EIGENTLICH sind so Linien ja keine Strecken, sondern eher "Vektoren", denn sie haben ja eine Richtung! - Deswegen nennt man diesen 3D-Kram auch Vektorgrafik...) Ob man nun die ursprüngliche Linine C->D löscht, bleibt einem selbst überlassen. Man kann natürlich auch C->D gleich mit C->E überschreiben und nur E->D neu anlegen. Man "zerschneidet" also die Wand (=Linie) komplett und sortiert die beiden Hälften getrennt weiter ein. (Und sollte damit rechnen, daß die noch ein paarmal mehr zerschnitten werden kann!) Hierbei ergibt sich für 3D-Coder noch ein weiteres interessantes Problem: Damit man diese "Schnitte" später nicht sieht, muß man die Textur der ZWEITEN Wand (also der, wo E der neue Anfangspunkt ist) um den Abstand C->E nach verschieben ("Vorderseite" der Wand, die von C nach D geht). Und auf der "Rückseite" muß man die Textur auf der ERSTEN Wand um den Abstand D->E verschieben. Ich gehe mal einfach davon aus, daß ohnehin jeder zu jeder Wand so einen Textur-Offset für beide Richtungen speichert - um die Texturen auf der Wand beliebig hin- und herschieben zu können - um z.B. Wand-Übergänge darstellen zu können - oder z.B. Säulen, die eine durchgehende Textur "drumherum" haben, obwohl sie aus kleinen Teilstücken bestehen und eigentlich "N-Ecke" sind. Achja: Abstand zwischen zwei Punkten natürlich mit dem Satz des Phytagoras. (c²=a²+b²), also Wurzel aus (x2-x1)²+(y2-y1)². Btw: Wer Interesse an nem Verfahren hat, wie man im Binärsystem eine Wurzel zieht (weil er z.B. alles in Assembler machen will), kann sich ja mal melden - habe dergleichen mal auf C64 entwickelt (dessen CPU übrigens nichtmal Multiplikation/Division hat!) und kanns auch gerne mal für PC erklären. Wem das aber nicht genau genug ist (meistens wird so ein Textur-Offset höchstens pixelgenau gespeichert), der kann bei so Nodes gerne noch einen VIERTEN Wert speichern - nämlich die Nummer der "Ursprungslinie" - die gleich der Nummer der Linie ist, wenn die Linie NICHT geteilt wird und ansonsten halt auf die Nummer der EIGENTLICHEN Linie zeigt. (In dem Fall darf man natürlich die Urspungslinie NICHT löschen!) 2. Sonderfall: Was macht man, wenn sich EINER der Punkte genau AUF der Linie befindet? Nun, das ist viel einfacher zu behandeln - wer logisch nachvollziehen kann, was wir hier machen, wird vielleicht schon von alleine drauf gekommen sein: In dem Fall wird NUR DER ANDERE Punkt zum Prüfen benutzt. Denn die Linie befindet sich dann dort im Bezug zur "verlängerten Linie", wo dieser eine Punkt ist. Denn die Punkte SELBST haben ja keine "Räumliche Ausdehnung" - d.h. die Linien sind ja nicht die Punkte SELBST, sondern der PLATZ DAZWISCHEN - klar? Daß sich der eine Punkt genau auf der Linie befindet, macht also GAR NICHTS! 3. Sonderfall: Was macht man, wenn sich BEIDE Punkte genau AUF der Linie befinden? Das ist NOCH EINFACHER zu behandeln: Es ist EGAL, ob man die Linie dann "vor" oder "hinter" die andere Linie sortiert, weil diese ja dann offensichtlich "nebeneinander" stehen. Man kann es sich in diesem Fall also AUSSUCHEN. OK, das war das Verfahren - wie BENUTZT man nun binäre Bäume? KAPITEL 5: WIE BENUTZT MAN BINÄRE BÄUME ZUR 3D-DARSTELLUNG? Es gibt zwei Möglichkeiten, wie man sich verdeckende Wände darstellen kann. Die erste ist lame: Man zeichnet einfach alle Wände von hinten nach vorn, dabei überdecken sich die Wände. Lame ist es deswegen, weil man 90% (wenn das mal reicht!) der Grafik völlig umsonst zeichnen läßt, weil die ja dann wieder "übermalt" wird. Kostet tierisch Performance - vor allem, weil ja jeder weiß, daß der Bus zur Grafikkarte das Nadelöhr im ganzen System ist. (Also: So wenig Daten wie möglich zur Grafikkarte schicken!) Die zweite ist viel besser: Man zeichnet von vorn nach hinten - zeichnet aber "hinten" nur an den Stellen, wo "vorn" noch nichts gezeichnet wurde. Hier führt man einfach die folgende rekursive Routine EINMAL aus: Zeichne_Node(N): - Zeichne_Node(vorderer Node) - Zeichne aktuelle Linie=Wand - Zeichne_Node(hinterer Node) Das heißt, man führt einfach aus: Zeichne_Node(0) Und fertig. Auf diese Art werden ALLE Linien gezeichnet - denn so wird der "allererste Node" auch ganz zuerst gezeichnet. Achja: Welcher der "vordere" und welcher der "hintere" Node ist, ermittelt man, indem man rausfindet, ob man die "aktuelle Linie" von VORN oder von HINTEN sieht. Und DAS findet man so raus: Wenn die Punkte, nachdem man sie auf 3D umgerechnet hat so liegen, daß Punkt 1 LINKS von Punkt 2 liegt, ist das die Vorderseite - anderenfalls die Rückseite! - Klar? Und: Der "mittlere" Befehl (also "Zeichne aktuelle Linie=Wand") wird natürlich NUR DANN ausgeführt, wenn sich mindestens einer der beiden Punkte der Wand VOR dem "Spieler" (bzw dem "Blickpunkt") befindet. Falls Interesse daran, wie man es machen kann, daß man von VORN nach HINTEN zeichnet und nur da, wo VORN noch nichts gezeichnet wurde, weiterzeichnet - kann ich dieses Verfahren auch noch gerne posten. (Ist mir mal irgendwann auf der Toilette eingefallen.) Nur soviel: Man denke sich einfach oben und unten am Bildschirm einen Haufen Punkte, die die die vertikale Grenze für das zu zeichnende Bild angeben. Und jedesmal, wenn man etwas zeichnet, gehen diese Punkte weiter zusammen (zur Bildmitte hin). Ist es eine Stufe, die von oben oder unten ins Bild kommt, dann nur bis zu dieser Stufe. Ist es eine WAND, dann schließen sie sich ganz. Achja: Wenn geschlossen, dann kann man auch die Anzahl noch zu zeichnender senkrechter Linien um 1 verringern. Wenn diese =0 wird, braucht man die restlichen Nodes nicht mehr zu prüfen, sondern kann die "Node-Zeichne-Routine" komplett verlassen. Falls jemand keine Idee hat, wie das bei ner rekursiven Routine gehen soll: Man speichere vorher den Wert des Stackpointers... KAPITEL 6: SCHWÄCHEN DES VERFAHRENS MIT BINÄREM BAUM (BSP-TREE) 1.) Jeder wirds gemerkt haben: Es kann eventuell einen Moment dauern, bis er alle Nodes berechnet hat (allerdings selbst für das größte DOOM1-Level (E2M7) braucht er bei mir (486er, BSP-Tree-Routine 100% Pascal!) nur knapp 2 Sekunden. Das gilt aber nur für die BERECHNUNG, die nur EINMAL gemacht werden muß für jedes Level. 2.) Das funktioniert nur für "starre" Levels - ändern sich die Levels, würde sich auch die Lage der Linien zueinander ändern, und die Nodes müßten neu berechnet werden. Btw: Diese "starren" Levels sind auch der Grund, wieso sich Plattformen, Türen und so weiter in DOOM nur nach oben/unten bewegen können. 3.) Man weiß nie vorher, wieviele Nodes man bekommt, da man die Anzahl Teilungen nicht kennen kann. 4.) Linien (also Wände) dürfen sich nicht kreuzen, da dies bei manchen Blickwinkeln definitiv zu Darstellungsfehlern führen wird. 5.) Sogenanntes "Totlaufen". Ist das Level zu "fitzelig", d.h. besteht aus zu kleinen Elementen, so kann das dazu führen, daß unzählige Teilungen vorgenommen werden und ein riesiger Baum entsteht. Eine Linie, die man ganz knapp an einem der Endpunkte teilt, würde nicht mehr wirklich geteilt, weil der Teilungspunkt gleichzeitig der Endpunkt wäre. Das würde dazu führen, daß dieselbe Linie wieder und wieder versucht wird, zu teilen, ohne je ein Ergebnis zu haben (und dazu, daß "leere Linien" einsortiert würden). Abhilfen für die Schwächen: 1.) In DOOM werden diese Nodes mitgespeichert. (Hatte sie allerdings nicht entschlüsselt. Ich bilde die Nodes immer selbst - auch wenn ich DOOM Levels lade.) Man könnte das Level auch in einige Quadrate (bzw Würfel) zerlegen und für jeden Würfel einzeln einen Baum bilden. (Man braucht ja nur die Nummer des ERSTEN Nodes für jeden Würfel speichern!) Achja: Sollten bei der Würfelbildung Wände zerschnitten werden müssen, dann eben wieder zerschneiden. Selbes Verfahren wie oben. Achja: Diese Würfelbildung kann man auch nutzen, wenn man RIESENGROßE Levels haben will, die man teilweise nachlädt. (Lädt man eben immer nur in "Teilwürfel"-Einheiten nach.) Wie man angrenzende Würfel richtig verdeckt/darstellt, sollte jedem klar sein. Wenn nicht: Für jede der 8 möglichen "Haupt-Blickrichtungen" die Reihenfolge der Würfel ändern. Kann das bei Bedarf genauer erläutern. Für "Wolfenstein"-artige Levels bräuchte man btw garkeine solchen Nodes, da reicht das "Würfelverfahren" nämlich aus. 2.) Sollte man bewegliche Teile einbauen wollen, dann einfach das ganze Level normal in den Baum einsortieren - aber ohne die Teile, die sich bewegen sollen. Dann einen Marker setzen, also welches der letzte "feste" Punkt, "feste" Linie und "feste" Node ist. Und DANN ERST die beweglichen Teile einsortieren. Und NUR DIESE kann man dann nämlich JEDESMAL, wenn sich eins der Teile bewegt hat, WIEDER einsortieren - vorher halt immer wieder auf die "festen" Werte "resetten". Zweite Möglichkeit ist ein Verfahren, in dem man einen ganzen "Kasten", innerhalb dessen sich etwas bewegen kann, als einen "Sonder-Node" betrachtet, um den "herum" alles fest ist und INNERHALB dessen sich etwas bewegen kann. An diesen "Sonder-Node" bindet man einen NEUEN BSP-Tree, den man nur innerhalb dieses kleinen Bereichs benutzt. Kann das bei Wunsch gern noch genauer erklären. 3.) Es gibt keine "Musterlösung", um die Anzahl Teilungen zu minimieren. Aber ich habe mir etwas ausgedacht, womit man im allgemeinen bessere Ergebnisse (d.h. möglichst wenige Teilungen) erhält: Man sortiert vorher die Linien nach Länge und zwar von der längsten zur kürzesten. Erklärung: Die Wahrscheinlichkeit, daß eine lange Linie geteilt wird ist höher als die, daß eine kurze geteilt wird. Und eine Linie kann umso häufiger geteilt werden, je größer der Node-Tree schon ist. Das heißt, daß es besser ist, die langen Linien zuerst einzusortieren, wenn es noch nicht so viele Nodes gibt. Eine bessere Möglichkeit zur Lösung dieses Problems fällt mir nicht ein. (Es gibt eine IDEAL-Lösung. Diese ist, alle Reihenfolgen durchzuprobieren und am Ende die mit den wenigsten Teilungen zu benutzen. Allerdings würde dies bedeuten, den ganzen Baum z.B. für 1000 Linien 1000! (Tausend-Fakultät) mal testweise bilden zu müssen - es sei denn, man erhält vorher schon einen Baum, der nur 1000 Nodes (kleiner wirds nicht bei 1000 Linien!) hat. Die Zahl 1000-Fakultät (also 1x2x3x4x5....x998x999x1000) kann ich nichtmal ansatzweise berechnen, kann also auch nicht sagen, wieviele Möglichkeiten man da hätte. Zum Vergleich: Fakultät 69 kann ein Taschenrechner afaicr als letzte anzeigen, Fakultät 70 nicht mehr. Und damit meine ich Taschenrechner, die Zahlen in wissenschaftlicher Schreibweise (also 100 Ziffern!) unterstützen... Ich schätze mal, angesichts dessen wird wohl jeder mit der "nach Länge sortieren"-Methode leben können. Anmerkung: Ich habe das auch nachgeprüft: Anzahl Nodes ohne Sortierung wurde halt mittelgroß. Bei Sortierung von längster zur kürzesten Linie hatte ich die wenigsten Nodes, bei Sortierung von kürzester zur längsten Linie viel mehr als ohne Sortierung. Daher ist anzunehmen, daß Sortieren wirklich hilft. 4.) Die Abhilfe ist ganz einfach. Man kreuzt keine Linien! Sollten sich Linien kreuzen, so macht man aus den 2 Linien 4 Teil-Linien. Nehmen wir an, zwei Linien A->B und C->D würden sich kreuzen. Der Node-Builder würde nur EINE davon teilen. Aber man selbst teilt BEIDE (am besten schon im Editor - kann man aber auch im Builder machen - wenn Schnittpunkt für neue Linie halt ZWISCHEN den Punkten der "verlängerten Linie", wird auch DIESE geteilt...) So. Dieser Schnittpunkt wäre also E, und die vier neuen Linien wären A->E, E->B, C->E und E->D. Alles klar? 5.) Es gibt hier mehrere Möglichkeiten. Die erste ist, die Genauigkeit des Node-Builders auf einen sinnvollen Wert zu stellen. Oder anders ausgedrückt: Wenn der Abstand einer Punkt-Koordinate zur Linie kleiner ist als dieser Wert (z.B. 8), dann wird der Punkt als "auf der Linie liegend" angenommen. Wählt man 2er Potenzen, kann man es sich auch noch leichter machen, indem man einfach die unteren Bits der Werte (im Falle 8 z.B. die unteren 3 Bits) auf 0 setzt. KAPITEL 7: DIE MATHEMATISCHE LÖSUNG FÜR DIE PRÜFUNG, OB PUNKTE "VOR" ODER "HINTER" DER LINIE SIND Nun noch die Erklärung, wie man prüft, wo sich ein Punkt im Verhältnis zu einer Linie befindet. Man ermittelt zunächst die Abstände AX und AY, indem man AX=X2-X1 und AY=Y2-Y1 rechnet (wobei X1;Y1 = Koordinaten des ERSTEN Linienpunkts und X2;Y2 = Koordinaten des ZWEITEN Linienpunkts. (Ich gehe jetzt erstmal davon aus, daß weder AX noch AY gleich Null sind - das erkläre ich nachher noch gesondert!) Daraus kann man dann eine Gleichung ableiten der Form y=mx+n. Y=(X-X1)*(AY/AX)+Y1 m (der "Anstieg") wäre in diesem Fall AY/AX. n wäre Y1. Vorher muß man aber noch vom Argument (also X) X1 abziehen. Was das soll, erklärt sich am besten, wenn man X1 und Y1 mal auf Null setzt. Dann wäre die Gleichung nämlich Y=(X-0)*(AY/AX)+0 oder auch (weil man -0 oder +0 ja weglassen kann) Y=X*(AY/AX) Klar? D.h. man reduziert es auf eine Gleichung für eine Gerade, die durch 0;0 (Koordinatenursprung) geht. Und weil sie das aber nicht tut, sondern in Wirklichkeit ja durch X1;Y1, nimmt man eben diesen. Anmerkung: Man kann auch von X2;Y2 ausgehen, nur kehren sich dann die Vorzeichen um. Dann setzt man in die Gleichung für X die X-Koordinate des zu prüfenden Punktes ein und erhält einen Wert Y. Diesen vergleicht man mit der Y-Koordinate des Punktes. Ist sie KLEINER als der erhaltene Wert, liegt der Punkt "vor" der Linie - wenn sie GRÖßER ist, "hinter" der Linie - aber NUR DANN, wenn X1X2, kehrt sich alles um. Also: Punkt_Davor=(YpunktX2) (wie gesagt: X1=X2 noch nicht behandelt, weil ja dann AX=0 wäre) So! Und nun noch zwei Möglichkeiten, wie man dem AX=0 entgehen kann. Für AX=0 ergäbe sich keine Gleichung, denn AY/AX wäre nicht lösbar. Aber: (logisch Nachdenken!) so eine Linie wäre genau SENKRECHT - und was wissen wir darüber? Da wäre es noch viel einfacher zu prüfen, wo im Verhältnis zur Linie sich der Punkt befindet - nämlich wenn Xpunkt>X1 (dran denken X2=X1, daher egal, ob X1 oder X2!), dann wäre er DAVOR, wenn Y10 sein. Und für den umgekehrten Fall gilt dasselbe, da wäre dann AX IMMER <>0, außer wenn AX und AY BEIDE =0 sind. Nochmal nachdenken: Was wäre, wenn AX und AY beide =0 wären? Richtig: Anfangs- und Endpunkt der Linie wären ein- und derselbe, d.h. es wäre also eine Linie der Länge 0, die unsichtbar ist. Welches Interesse sollte also jemand haben, die in einen BSP-Tree einzusortieren? (Wo man sie doch sowieso nicht sieht...) Die zweite Methode gefällt mir viel besser, denn statt Dingen wie Y=(X-X1)*(AY/AX)+Y1 kann man ja auch schreiben; Y=((X-X1)*AY) div AX + Y1 Und erhielte halt den ganzzahligen Wert, der genau genug wäre. Und schon braucht man keinen lästigen Fließkomma-Kram mehr... Und, wie bereits im vorigen Kapitel erwähnt: Wenn man den ermittelten X-Wert mit Xpunkt oder den Y-Wert mit Ypunkt vergleicht, darauf achten, daß man bei einem Abstand kleiner als der "Node-Builder-Genauigkeit (z.B. 8) annimmt, daß X=Xpunkt oder Y=Ypunkt (d.h. daß dieser Punkt auf der Linie liegt). Liegen BEIDE Punkte auf der Linie, kann man ja dann immer noch prüfen, ob sie es WIRKLICH tun oder welcher der beiden Abstände zur Linie "größer" ist, um die Linie dann auf die entsprechende Seite zu sortieren. Grund für diese Ungenauigkeit: Erstens: Bei zu großer Genauigkeit wird das Level in tausende Schnipsel zerschnitten, ohne daß dies für die Darstellung wirklich sinnvoll wäre. Zweitens: Man prüft ja nicht wirklich Schnittpunkte mit den Wänden SELBST, sondern nur mit deren VERLÄNGERUNGEN - d.h. selbst wenn man z.B. mit 2048 Winkeln arbeitet (Duke Nukem 3D) statt 360 (DOOM), würde sich durch die optische perspektivische Verzerrung kein Unterschied in der Darstellung ergeben. Der BSP-Tree wird ja nicht zur Berechnung der Wandkoordinaten benutzt - sondern lediglich zur Festlegung, in welcher REIHENFOLGE die Wände gezeichnet werden. Achja, ich höre schon manchen fragen: Aber man berechnet das ja nur für ein Level, das NICHT GEDREHT ist - wenn man es dreht, ändert sich doch der Blickwinkel? Ja, das ist richtig. Aber die Grundlage für den BSP-Tree bildet ja nur die Lage der Punkte ZUEINANDER - und die ändert sich ja nicht, auch wenn man das ganze Level dreht! KAPITEL 8: WIE ERMITTELT MAN, WO MAN SELBST SICH IM LEVEL BEFINDET? Nun - wie ermittelt man nun, wo man sich im Bezug zu den Wänden befindet? Ganz einfach: Man testet einen einzelnen Punkt für alle Nodes durch, wo im Verhältnis zum jeweiligen Node er sich befindet und geht dann immer weiter durch, bis man an ein "offenes Ende" kommt. Und dieser "letzte" Node gibt genau das an, was man wissen will. Zum Beispiel: Wand 67, Rückseite. Damit weiß man, daß sich zwischen diesem Blickpunkt und der Rückseite von Wand 67 definitiv nichts mehr befindet! Von jeder Wand ist ja bekannt, bzw läßt sich durch den Levelaufbau hundertprozentig ermitteln (wenn nicht, ist der Levelaufbau Mist, denn dann läßt es sich auch nicht ZEICHNEN!), welcher "Sektor" daran angrenzt - also welcher Boden/Decke usw. Und diese haben ja auch eine bestimmte Höhe bzw Eigenschaften. An der Höhe kann man z.B. ermitteln, wo sich der Fußboden im Verhältnis zur Figur befindet... KAPITEL 9: WIE VERMEIDET MAN ES, DURCH WÄNDE ZU LAUFEN (CLIPPING) ? So - und nun noch, wie man sich durchs Level "bewegen" kann ohne durch Wände zu laufen (sogenanntes "Clipping") : Also, dazu prüft man nicht EINEN, sondern ZWEI Punkte, wo sie sich befinden. (D.h. man tut so, als würde man eine neue Linie/Wand einsortieren wollen. Anfangspunkt ist der Punkt, wo man sich befindet - Endpunkt der, wo man hinwill. Man kann sogar dieselbe Routine wie die das Node-Builders benutzen.) Sobald diese Linie "zerschnitten" werden soll, weiß man, daß ein "Node" überschritten wird - also eine verlängerte Linie. Dann prüft man, ob sich der Schnittpunkt wirklich zwischen beiden Punkten der Linie befindet. Wenn NEIN, "zerschneidet" man die zu prüfende Linie (die die "Bewegung" simuliert) und prüft weiter. Wenn JA, dann weiß man, daß man eine Linie durchschreiten will, die halt einer "Wand" entspricht. Diese kann man dann prüfen, ob sie "durchlässig" ist oder nicht, d.h. ob es wirklich eine Wand ist oder etwas, wo man durchlaufen kann. Bei dieser Prüfung kommt man also entweder an ein loses Ende und dann kann die "Figur" bedenkenlos weiterlaufen oder man kommt an eine undurchlässige Wand. Dann kann man das halt nicht. Man kann auch z.B. einfach prüfen, ob der neue Sektor, den man betreten will, im Vergleich zur eigenen Höhe der Figur (wenn man also nicht gerade springt, dann ist das gleich der Höhe des aktuellen Sektors) nur einen gewissen maximalen Abstand hat oder geringer ist. Wenn geringer, fällt man normal runter. Wenn höher, ist es eine "Stufe" und hier kann man ja irgendwo definieren, wie hoch eine Stufe maximal sein kann, auf die man steigen/springen kann und wann man einfach gegen die Wand rennt... Nun stellt sich nur noch die Frage, wie man das Problem löst, daß eine Figur wie irgendein Typ im Schutzanzug mit ner BFG-9000 (wie komm ich jetzt nur darauf...?), der ein ziemlich breites Kreuz hat, sich nicht zwischen zwei dicht nebeneinanderstehenden Säulen oder zwischen zwei Gitterstreben durchquetschen kann. Nun - ganz einfach. Man läßt nicht einen PUNKT sich bewegen, sondern eine "Figur", also einen "Zylinder". Normalerweise reicht hier schon ein gleichseitiges Dreieck. Spitze ist vor, zwei Punkte sind hinten. Und man kann nur weiter, wenn alle drei Punkte sich zum "Zielpunkt" bewegen können, ohne durch eine Wand zu laufen. Achja: In DOOM gibt es auch "unsichtbare" Wände, die teilweise nur als Teil eines Schattenwurfs benutzt werden. Diese kann man natürlich normal durchlaufen. Ebenfalls sind manche solcher Linien einfach "Ereignis-Trigger", d.h. sobald man die Linie überschreitet, löst man eine bestimmte Aktion aus. (Die Linien, die um einen Teleporter herum angeordnet sind, triggern halt z.B. den Teleporter. Hätte man natürlich auch mit "Betreten des Sektors" lösen können... Es gibt auch solche Trigger, die feststellen, ob man ein "Secret" (=Geheimraum" gefunden hat. Ob das dann mit "sehen eines Sektors" oder "Überschreiten einer Linie" getriggert wird, weiß ich grad nicht. Anmerkung: In DOOM wird trotz dieser Möglichkeit, die "Kollision" mit Wänden abzufragen, scheinbar trotzdem eine sogenannte BLOCKMAP eingesetzt. Deren Format habe ich damals nicht 100% gehackt - aber es sieht so aus, als würde diese BITWEISE für fast jeden Punkt des Levels eine rechteckige "Bitmap" enthalten, die angibt, ob man diesen Punkt betreten kann (0) oder nicht (1). Beweis für diese These: Man gehe mal an einer "geraden" Wand schräg vorwärts entlang. Dabei "gleitet" man halt so an der Wand lang. Macht man dasselbe bei einer schrägstehenden Wand (also einer, die in der Karte keinen 0,90,180,270°-Winkel hat), dann merkt man die "Treppenstufen" dieser Block-Map. (Block wohl nicht gemeint im Sinne von Blöcke, sondern von blocken, also blockieren.) KAPITEL 10: WIE KANN MAN DAS ALLES AUF "ECHTES" 3D ANWENDEN? So, ich hatte ja noch versprochen, zu erklären, wie das alles bei ECHTEM 3D funktioniert - d.h. für Levels mit beliebiger Form, wo die Wände auch "schiefstehen" können. Nun - hier taugt dieses Modell mit einer von oben betrachteten Karte nicht mehr - denn die Wände wären keine Linien mehr. Es gibt bei "echtem" 3D keine Wände, Fußböden und Decken mehr, sondern nur noch "Flächen", die alle "gleichberechtigt" sind. (Ob man auf einer Wand stehen kann oder nicht, entscheidet lediglich ihr Winkel zur X/Y Ebene. Wenn man davon ausgeht, daß X/Y der theoretische Fußboden und Z die Höhe ist.) Also - aufgrund dessen, daß viele Grafikroutinen mit Dreiecken arbeiten, erkläre ich das GANZE für Dreiecke. Wieso man Dreiecke benutzt? Dreiecke sind die kleinstmögliche Fläche, die man bilden kann. (Mit noch weniger Ecken wirds keine Fläche mehr.) Bei Dreiecken ist garantiert, daß sie immer "eben" sind, sich also alle Punkte in derselben Ebene befinden. Dreiecke sind immer konvex - da es hier natürlich keine "nach innen zeigenden" Punkte geben kann. Und: Man kann jede andere Flächenfigur in Dreiecke zerlegen, so daß man z.B. ein Rechteck durch zwei Dreiecke darstellen kann. Man zieht einfach eine Diagonale durch und erhält zwei Dreiecke... So, nun zur Prüfung des ganzen: Auch eine FLÄCHE kann man durch eine Formel darstellen, allerdings hat man hier zwei Argumente, weil die Formel ja "3-dimensional" ist. Die Form ist (hoffe, ich erzähl keinen Schmarrn, schon ne Weile her) : z=mx+ny+p Wobei m und n zwei Anstiege sind und p eine Konstante, die addiert wird. Man setzt hier auch wieder Punktkoordinaten ein. Jeder Punkt eines solchen Polygons hat jedoch DREI Koordinaten (also Raum-Koordinaten), d.h. man setzt ZWEI davon in die Gleichung ein und prüft, wie sich die DRITTE zum Ergebnis verhält. Wie genau man die Werte für m, n und p erhält (also mathematisch - mit genau solchen Formeln wie ich das für die "2D"-Variante erklärt habe) erkläre ich im zweiten Teil des BSP-Tutorials, wenn ich mal einen mache. (Setzt halt das Interesse der Leute voraus.) Wo sich hier übrigens die "Vorderseite" und "Rückseite" befindet, wird ebenfalls wieder per Definition festgelegt. Die gängige Methode, um dies für ein Polygon zu definieren, ist die Reihenfolge der Punkte des Polygons. Zum Beispiel: Ist es im Uhrzeigersinn beschriftet, ist dies die Vorderseite, anderenfalls die Rückseite. (Halt, welche Seite der "Punkt sehen würde", wenn er von seiner Position aus auf das Polygon "draufguckt". Von "hinten" ist die "Beschriftung" nämlich genau "linksrum" zur Vorderseite.) Dabei ist natürlich völlig klar, was passiert: Die Flächenformel ist halt eine ganze Ebene, die "den Raum durchschneidet" und quasi eine "Verlängerung" des Dreiecks/Polygons. Das neue Dreieck/Polygon, das man prüft, wird halt so geprüft: Man prüft alle Eckpunkte, wo sie sich im Verhältnis zu dieser Schnittebene befinden und sortiert es entweder "davor" oder "dahinter". Sollte ein oder zwei Punkte genau IN der Ebene liegen, entscheiden die restlichen Punkte. Wenn jedoch ein Punkt auf der einen und ein oder zwei auf der anderen Seite liegen, muß das Dreieck geteilt werden. Man bildet die beiden Punkte, an denen die Seitenkanten des Dreiecks die Ebene durchstoßen und verbindet diese zu einer Linie. An dieser Schnittlinie wird das Dreieck geteilt. Dabei entsteht ein Dreieck und ein Viereck. (Außer wenn der dritte Punkt genau AUF der Ebene lag, dann entstehen zwei Dreiecke.) Und das ist dann halt weiter einzusortieren. Bei Vierecken und Mehr-Ecken hat man (wenn man nur eine Dreiecks-fähige Routine hat) die Wahl, es entweder so zu lassen und immer mehr Ecken zu erzeugen, bis das Polygon dann seine Endposition erreicht. Oder man zerlegt das Viereck gleich wieder in zwei Dreiecke (es ist auf jeden Fall konvex, daher egal, wo man die Diagonale setzt!) und sortiert diese weiter ein. Ich PERSÖNLICH wäre ja dafür, rechteckige Flächen gleich als solche zu speichern und dafür entweder eine gesonderte optimierte Routine für Rechtecke zu benutzen - oder eben, wenigstens 3- und 4-Ecke zuzulassen (aber am besten beliebige konvexe N-Ecke) damit man erst am Ende bei der Darstellung halt in Dreiecke zerlegt. (ist ja dann nicht schwer, wenn die N-Ecke konvex sind.) Nehmen wir an, das neue Dreieck wäre D-E-F und D läge auf einer Seite der Ebene, E und F auf der anderen Seite. Dann würde man den Schnittpunkt zwischen der Ebene und der Geraden durch D->E, sowie den Schnittpunkt zwischen der Ebene und der Geraden durch F->F ermitteln müssen. (Indem man die Ebenengleichung mit den Geradengleichungen wieder gleichsetzt.) Man sieht schon, das artet langsam in Arbeit aus, deswegen würd ich das auch bei "echtem" 3D so NIEMALS machen, sondern die "andere" Methode benutzen... (Falls dennoch Interesse an den genauen Formeln, mach ich mich nochmal ne Runde schlau.) KAPITEL 11: DIE "ANDERE" METHODE, UM 3D FIGUREN IM RAUM ZU ORDNEN Und dann noch ein Hinweis: Ich schätze, einige der Konstrukte, die in der DOOM.WAD drin sind, die ich noch nicht entschlüsselt, da nicht gebraucht habe, enthalten genau dieses was ich JETZT GLEICH sage. (Diese Dinge sind offensichtlich in den als SSEG und SSECTOR bezeichneten Unter-Konstrukten der Levels abgelegt - könnte jedenfalls sein, hab es nicht vollständig gehackt - ist aber wohl auch nicht nötig.) Also: Bekanntermaßen kann man jede konvexe Figur einfach so darstellen, ohne ihre Flächen sortieren zu müssen, wenn man NUR die äußeren Flächen oder NUR die inneren Flächen darstellen will. (Das ist halt eine physikalische Tatsache - findet Euch damit ab...) Diesen Umstand kann man auch benutzen, um jede 3D-Figur einfach so lange in Teilfiguren zu zerlegen, bis nur noch konvexe Figuren übrig sind. (Erklärung: Konvex ist eine Figur genau dann, wenn keine einzige Ecke nach "innen" geht.) Doch obengenannte Eigenschaft - nämlich, daß man bei einer konvexen Figur die Wände nicht mehr sortieren muß, bevor man sie zeichnet, kann man folgendes tun: Erstmal: Ein Computerlevel ist auch nichts anderes als "die größte 3D-Figur der Welt" - also gilt für ein Computerlevel genau das gleiche wie für ein "Player-Model" (nich Playboy-Models! - PLAYER!) - also die im Level rumhüpfenden 3D-Figuren, die sich immer Schüsse in den Schädel einfangen... So. Also teilt man das ganze Level in so konvexe Teile. Ein so konvexes Teil ist eine Zusammenfassung von Wänden, die alle zusammen eine konvexe Figur ergeben. Diese muß nicht "geschlossen" sein - Hauptsache ist, daß kein Eckpunkt nach "innen" zeigt. Jede dieser "Zusammenfassungen" bildet also eine konvexe Figur. Das heißt, man muß nur noch die Lage zweier konvexer Figuren zueinander testen - nicht mehr die Lage aller Wände zueinander. (Dazu muß man aber erstmal die konvexen Figuren ermitteln!) Um konvexe Figuren zueinander zu sortieren, reicht es, einfach die Lage ihrer Mittelpunkte zueinander zu prüfen. Dann sortiert man die Figur mit dem "weiter vorn" liegenden Mittelpunkt in den "vorn"-Node und die mit dem "weiter hinten" liegenden Mittelpunkt in den "hinten"-Node. EIGENTLICH ist es ja egal, welchen Punkt man nimmt - es kann auch einer der Eckpunkte der Figuren sein - sollte eben nur nicht gerade derselbe sein. Um die Berechnung für die Darstellung zu beschleunigen, kann man hier auch 3 Punkte für eine "Ebene" definieren, die genau zwischen den beiden Figuren durchgeht - und abhängig davon, ob man die "Vorderseite" oder die "Rückseite" des Dreiecks sieht, das zwischen den Figuren verläuft, stellt man eben die eine oder die andere Figur zuerst dar. (Man braucht schon ein dreidimensionales Vorstellungsvermögen, um zu wissen, was ich meine. Also wohl nichts für Frauen, soweit ich weiß.) Es gibt allerdings noch eine DRITTE Möglichkeit, wie zwei so Figuren zueinander liegen können: Nämlich INEINANDER. Das ermittelt man, indem man prüft, ob der Mittelpunkt einer Figur innerhalb der anderen liegt. (Relativ einfach - kann gern im "nächsten Teil" des Tutorials ein Verfahren vorstellen, wie man das macht...) Das heißt: Man speichert entweder so eine "Unterscheidungsfläche" ab oder den Vermerk: "Innerhalb" bzw "drumherum" als eine Art "Flag" oder so - je nachdem, wie die Figuren zueinander liegen. Anmerkung: Man kann "ineinander" liegende Figuren auch vollständig vermeiden, indem man dann einfach weiterteilt. Wie gesagt: Auch HIER werden "Nodes" gebildet, allerdings gehört zu einem solchen "Node" dann gleich eine Zusammenfassung mehrerer Wände. Diese kann man halt miteinander "verketten". (Wie man sowas speichern kann - auch siehe nächster Teil, wenn einer kommt.) Und gezeichnet werden solche Nodes so (angenommen, man würde vordere Wände zuerst zeichnen) : Zeichne_Node(N): - Zeichne_Node(vorderer Node) - Zeichne_aeussere_Waende(aktueller Node N) - Zeichne_Node(innerer Node) - Zeichne_innere_Waende(aktueller Node N) - Zeichne_Node(hinterer Node) Dran denken: Man teilt in diesem Fall eigentlich in DREI Teile, nämlich vorn, innen und hinten. Man kann es aber so lösen, daß man z.B. bei der Node-Nummer (16Bit) das oberste Bit setzt, wenn ein Node statt HINTEN halt INNEN ist oder so - damit hat man nur noch 32767 mögliche Nodes ($FFFF ist ja "loses Ende"), aber man spart eine weitere Angabe ("innen" halt), die sehr oft unbenutzt bliebe. Bei DIESER METHODE entfällt übrigens komplett das Zerschneiden der Wände - dafür ist das Verfahren, konvexe Figuren aus dem Level zu extrahieren, etwas aufwendiger. Ach ja: Dem aufmerksamen Leser wird nicht entgangen sein, daß es auf diese Art natürlich möglich ist, gewisse statische Objekte innerhalb des Levels zu bewegen - und daß man, wenn man erst das Level in konvexe Figuren geteilt hat, viel leichter die "Nodes" bauen kann, weil es ja auch viel weniger sind. Auf diese Art kann man eben auch - solange sich die Figuren nicht gegenseitig "durchdringen" - während des Spiels noch "on the fly" immer wieder neu die Lage der konvexen Figuren zueinander berechnen und Levels etwas dynamischer gestalten. Wenn man gleich beim BAUEN eines "echten 3D" Levels dieses in konvexe Figuren teilt, entfällt natürlich das komplexe "Finden" dieser Figuren. Diese Methode finde ich viel empfehlenswerter für "echtes 3D" als das nachträgliche "Punkte-Prüfen"... KAPITEL 12: BEWEGLICHE FIGUREN ("SPRITES") IM LEVEL Die in DOOM verwendeten "Sprites" sind ja meist beweglich - außerdem haben sie nur EINEN statt ZWEI Punkte. Da sie auch stellenweise "durchsichtig" sind, ist aber hier die beste Methode, sie "von hinten nach vorn" zu zeichnen, damit sie sich auch gegenseitig überdecken können. (Viel schneller als entsprechende "Auslaß-Routinen", imo.) Diese muß man natürlich nachträglich getrennt in das Level einfügen - auch dafür habe ich ein Verfahren entwickelt, das ich "Back-Tracing" genannt habe. (Bei Interesse erläutere ich dieses ebenfalls.) Hier gibt es aber auch der Möglichkeiten viele. KAPITEL 13: SO MACHT ES DIE GRAFIKKARTE Falls es jemanden interessiert: Es gibt noch eine Möglichkeit, 3D-Objekte aus Polygonen darzustellen: Man definiert für JEDEN Punkt des gesamten Bildes einen "Entfernungs-Wert", den man zu Anfang auf die maximal mögliche Entfernung (vom Blickpunkt aus) setzt, also $FFFF oder $FFFFFFFF. Das heißt, für 320x200 bräuchte man bei 16Bit-Werten (also bis 65535) 128000 Bytes, für 32Bit-Werte (also bis 4294967295) bräuchte man 256000 Bytes. (Wie gesagt, 320x200 - NIEDRIGSTE AUFLÖSUNG!) Wenn man ein Polygon zeichnet, rechnet man für jeden Pixel die Entfernung zum Blickpunkt des "Spielers" aus - also man geht von den Eckpunkten des Polygons aus und kann das natürlich dann anhand von Formeln berechnen. Dann prüft man, ob der Punkt, den man zeichnen will, eine kleinere Entfernung als der hat, der schon an der Stelle im Bild steht. Wenn NEIN, zeichnet man den Punkt NICHT. Wenn JA, dann zeichnet man den Punkt über den anderen drüber und setzt den 16- oder 32-bit-Wert auf den neuen Entfernungs-Wert. Das macht man für jeden Punkt des Polygons. Dieses Verfahren wird Z-Puffer ("Z-Buffering") genannt. Mit Z ist dabei die Entfernung - also die dritte Koordinate (ausgehend davon, daß X und Y die zwei der "Bildfläche" sind) gemeint. Vorteil ist natürlich, daß sich hier auch alles gegenseitig "durchdringen" kann. Auf diese Art braucht man KEINE BSP-Trees und KEINE Sortierung. Allerdings braucht man mörderisch viel Speicher und Rechenpower dafür, - weil man das für jeden Punkt einzeln testen muß - weil man viele Polygone völlig umsonst zeichnet, da sie danach von anderen überlagert werden - weil man alleine für 640x480 für 32bit-Puffer 1228800 Bytes (also ca. 1,2 MB) und für 16-bit-Puffer 614400 Bytes (also 0,6 MB) braucht - weil man den Puffer vorher auch "löschen" muß Deswegen wurde diese Methode früher nur in kleinen Demos benutzt, wo man vielleicht ein paar 3D-Figuren einander durchdringen ließ - (obwohl ich auch schon Demos gesehen habe, die wirklich die Schnittlinien der Flächen berechnet haben und ohne Z-Puffer auskamen!) Ansonsten wurde diese Methode nicht eingesetzt, weil sie gegenüber allen anderen Methoden die meiste Performance UND Speicher kostet und daher als die LAMEste Methode angesehen wird, 3D darzustellen. Heutzutage ist das allerdings die Methode, die alle 3D-fähigen Grafikkarten hardwaremäßig einsetzen, um sich verdeckende Polygone darzustellen. (D.h. man gleicht Idiotie mit 'nem schnellem Prozessor aus, wie so oft...) - Naja. Ist ja nicht das erste Mal, daß sich die lameste Methode am Ende durchsetzt. (siehe Windows) Daher braucht auch niemand, der heutzutage Hardware-3D benutzt, sich mehr Gedanken darüber zu machen, in welcher Reihenfolge er seine Polygone an die Grafikkarte zum Zeichnen schickt. Das ist nur nötig, wenn man Software-Rendering benutzen will. Und das bedeutet auch: Wer Hardware-3D benutzen will, muß sich um diesen ganzen Kram mit BSP-Tree eigentlich gar keine Gedanken machen. (Er kann es natürlich trotzdem, aber ob das dann noch die Performance steigert, kann ich nicht sagen.) Für Hardware-3D ist es wohl eher sinnvoll, ein Verfahren zu haben, mit dem man möglichst schnell prüfen kann, ob sich ein Polygon innerhalb des "Pyramiden-Stumpfs" befindet, dessen eine Grundfläche der Bildschirm ist und das nach "hinten" hin perpektivisch größer wird bis hin zur maximalen Entfernung, an der man etwas darstellen will. Falls sich jemand DAFÜR interessiert - auch da habe ich Gleichungen dafür da, um dies zu prüfen. KAPITEL 14: SCHLUßWORTE DES VERFASSERS Ich weiß, die Erklärung ist nicht perfekt. Man hätte hier und da noch ein paar mehr Anmerkungen machen können. Aber ich bin schließlich kein Gelehrter - ich habe nichtmal studiert. Das Grundprinzip des BSP (aber nicht, wie man's berechnet) habe ich mal irgendwo in einem englischen Text gelesen - und es hat ne Weile gedauert, bis ich dahintergekommen war, wie der das meinte. Alles, was ich hier vorstelle, habe ich mir selbst mit Hilfe dessen, was ich noch aus dem Mathe-Unterricht aus der Schule wußte und mit meinem gesunden Menschenverstand und meinem 486er angeeignet. Will sagen: Das hier erhebt keinen Anspruch auf Vollständigkeit, Richtigkeit oder darauf, "der Weisheit letzter Schluß" zu sein. Es ist einfach so: Bei MIR funktionierts erfolgreich. Also muß es ja gehen. Wenn es noch Fragen dazu gibt oder Interesse an einer Weiterführung dieses Tutorials besteht, laßt es mich wissen. (Weitere Teile folgen also nur dann, wenn auch Interesse besteht. Wenn nicht, muß ich nicht Eure - und meine - Zeit verschwenden.) Ich kann auch z.B. gerne ein "Gesamt 3D" Tutorial machen - zum Beispiel: Wie bringe ich eine Textur korrekt perspektivisch verzerrt auf eine Wand-Fläche oder Fußboden/Decke im 3D-Level? Wie "drehe" ich überhaupt die Punkte? Und ähnliche Dinge. Ich hoffe, ich konnte damit einigen Leuten weiterhelfen. Man möge mir meine furchtbare Ausdrucksweise verzeihen. Ich kann nicht anders. Ich rede auch so. Xpyder (Imperial Games)