Ist die Verwendung von BSP in Doom wirklich ein genialer Schritt?

Der Gipfel der Technologie der Zeit.

1993 veröffentlichte id Software Doom , einen Ego-Shooter, der sich schnell zu einem Phänomen entwickelte. Heute wird angenommen, dass dies eines der Spiele ist, die den größten Einfluss in der Geschichte hatten.

Zehn Jahre nach der Veröffentlichung von Doom veröffentlichte der Journalist David Kouchner 2003 ein id-Software-Buch mit dem Titel Masters of Doom , das seitdem eine kanonische Beschreibung des Doom- Erstellungsprozesses darstellt. Ich habe Masters of Doom vor ein paar Jahren gelesen und erinnere mich fast an nichts, aber eine Geschichte aus einem Buch über den Hauptprogrammierer John Carmack ist mir in Erinnerung geblieben. Meine Beschreibung wird nicht ganz zutreffend sein (siehe unten für weitere Details), aber kurz gesagt, in der frühen Phase der Doom- Entwicklung stellte Carmack fest, dass der 3D-Renderer, den er für das Spiel geschrieben hatte, beim Rendern bestimmter Ebenen langsamer wurde. Dies war inakzeptabel, da Doom ein aktives und sogar hektisches Spiel werden musste. Carmack erkannte, dass das Renderer-Problem so grundlegend war, dass er nach einem optimaleren Rendering-Algorithmus suchen musste, und begann, Forschungsartikel zu lesen. Infolgedessen implementierte er eine Technik namens BSP (Binary Space Partitioning), die zuvor noch nie in Videospielen verwendet wurde, und beschleunigte damit die Doom- Engine erheblich.

Diese Geschichte, wie Carmack die neuesten wissenschaftlichen Erkenntnisse auf Videospiele übertragen hat, hat mich immer beeindruckt. Meiner Meinung nach wurde Carmack so zu einer legendären Figur. Er verdient es aus vielen Gründen, als archetypischer brillanter Videospiel-Programmierer bekannt zu sein, aber als wichtigster erinnere ich mich immer an die Episode mit dem Lesen von wissenschaftlichen Artikeln und der binären Aufteilung des Raums.

Offensichtlich ist diese Geschichte beeindruckend, denn der Begriff „binäre Raumteilung“ scheint nicht nur für die Implementierung, sondern auch für das Verständnis etwas kompliziert zu sein. Lange Zeit ging ich davon aus, dass Carmack einen intellektuellen Sprung nach vorne gemacht hatte, aber da ich nicht wusste, was eine binäre Raumaufteilung ist und wie neu diese Technik war, als Carmack sich entschied, sie zu verwenden, war ich mir nicht ganz sicher. Wie genial war das Hinzufügen einer binären Raumpartition zu Doom auf einer Skala von Homer Simpson bis Albert Einstein?

Ich fragte mich auch, woher die BSP kam und wie die Idee zu Carmack kam. Daher wird dieser Beitrag nicht nur John Carmack und Doom gewidmet , sondern auch der Geschichte der Datenstruktur des "Binary Space Partition Tree" (oder BSP-Baums). Es stellte sich heraus, dass der BSP-Baum, wie viele andere Aspekte der Computerwissenschaften, aus Forschungen für das Militär stammt.

Ja, das stimmt: E1M1, das erste Doom- Level, ist dank der US Air Force erschienen.

VSD-Aufgabe

Der BSP-Baum ist eine Lösung für eine der schwierigsten Aufgaben in der Computergrafik. Um eine dreidimensionale Szene zu rendern, muss der Renderer bestimmen, was vom aktuellen Punkt aus sichtbar und was nicht sichtbar ist. Dies ist nicht besonders schwierig, wenn Sie viel Zeit haben. Eine sich selbst respektierende Echtzeit-Game-Engine sollte jedoch mindestens 30 Mal pro Sekunde die sichtbaren und unsichtbaren Teile der Welt bestimmen.

Diese Aufgabe wird häufig als VSD-Aufgabe (Visible Surface Determination) bezeichnet. Der Programmierer Michael Abrash, der mit Carmack on Quake (dem nächsten id-Software-Spiel nach Doom ) zusammengearbeitet hat, schrieb in seinem berühmten Buch Graphics Programming Black Book über die VSD-Aufgabe:

Ich möchte über die meiner Meinung nach schwierigste Aufgabe der 3D-Grafik sprechen: das Bestimmen der sichtbaren Flächen (Zeichnen der gewünschten Fläche in jedem Pixel) und deren enger Verwandter - die Aufgabe des Keulens (so schnell wie möglich unsichtbare Polygone werfen, um die Bestimmung der sichtbaren Flächen zu beschleunigen). Der Kürze halber bezeichne ich mit der Abkürzung VSD sowohl die Definition von sichtbaren Oberflächen als auch das Beschneiden.

Warum halte ich VSD für die schwierigste 3D-Aufgabe? Obwohl Rasterungsprobleme wie die Texturabbildung ebenfalls erstaunliche und wichtige Aufgaben sind, handelt es sich hierbei um Aufgaben von relativ begrenztem Umfang, deren Lösung sich auf das Auftreten von 3D-Beschleunigern auf Geräten verlagert. Außerdem skalieren sie nur, wenn die Bildschirmauflösung erhöht wird, was durchaus erträglich ist.

Im Gegensatz dazu ist VSD eine unbegrenzte Aufgabe, und jetzt werden Dutzende von Lösungen verwendet, um sie zu lösen. Noch wichtiger ist, dass die naive Leistung von VSD direkt mit der Komplexität der Szene skaliert, die normalerweise als quadratische oder kubische Funktion zunimmt, sodass sie schnell zum begrenzenden Faktor für die Wiedergabe realistischer Welten wird.

Abrash schrieb über die Komplexität des VSD-Problems in den späten 90ern, ein paar Jahre nachdem Doom bewiesen hatte, dass normale Leute in der Lage sein möchten, grafisch anspruchsvolle Spiele auf ihren Heimcomputern zu spielen. In den frühen 90er Jahren, als id Software gerade mit der Veröffentlichung von Spielen begann, mussten sie effektiv auf ungeeigneten Computern arbeiten: Heimcomputer wurden für die Arbeit mit Text, Tabellenkalkulationen und ähnlichen Anwendungen entwickelt. Um dieses Ziel zu erreichen, musste sich das Unternehmen der Fiktion nähern, insbesondere im Fall mehrerer 3D-Spiele, die von id Software vor Doom veröffentlicht wurden . In diesen Spielen wurde das Design aller Level so eingeschränkt, dass die Lösung des VSD-Problems vereinfacht wurde.

Zum Beispiel bestand in Wolfenstein 3D , dem Spiel, das id Software kurz vor Doom herausbrachte , jede Ebene aus Wänden, die entlang der Achsen ausgerichtet waren. Mit anderen Worten, im Wolfenstein-Universum könnte es Nord- / Südwände oder Ost- / Westwände geben, und keine anderen. Darüber hinaus können Wände in festen Abständen im Raster platziert werden. Alle Korridore haben eine Breite von entweder einer oder zwei Rasterzellen usw., jedoch niemals von 2,5 Zellen. Obwohl dies bedeutete, dass das Team von id Software nahezu gleich aussehende Ebenen erstellen konnte, machte es diese Einschränkung Carmack sehr leicht, einen Renderer für Wolfenstein zu schreiben.

Der Wolfenstein- Renderer löste das Problem der VSD, indem er Strahlen (Ray Marching) vom Bildschirm in die virtuelle Welt bewegte. Ray-Renderer sind in der Regel Raycasting-Renderer - sie sind häufig langsam, da zur Lösung des VSD-Problems in Raycaster der erste Schnittpunkt zwischen dem Strahl und einem Objekt auf der Welt gesucht werden muss, der viel Rechenaufwand erfordert. Da jedoch alle Wände in Wolfenstein mit einem Gitter ausgekleidet sind, sind die Gitterlinien die einzigen Stellen, an denen ein Balken die Wand überqueren kann. Daher reicht es aus, wenn der Renderer jeden dieser Schnittpunkte überprüft. Wenn der Renderer zunächst den Schnittpunkt überprüft, der dem Ansichtspunkt des Players am nächsten liegt, dann den zweiten in der Nähe usw. und endet, wenn er auf die erste Wand trifft, ist das VSD-Problem auf die trivialste Weise gelöst. Der Strahl bewegte sich einfach von jedem Pixel vorwärts, bis er auf etwas stieß, was in Bezug auf die Prozessortaktraten sehr kostengünstig ist. Und da alle Wände die gleiche Höhe haben, reicht es aus, dass wir für jede Pixelspalte Strahlen aussenden.

Diese Vereinfachung des Renderns machte Wolfenstein schnell genug, um auf schwachen Heim-PCs jener Zeit zu arbeiten, als es noch keine speziellen Grafikkarten gab. Ein solcher Ansatz würde in Doom jedoch nicht funktionieren, da das ID-Team beschlossen hat, dass es in seinem neuen Spiel so neue Elemente wie diagonale Wände, Treppen und Decken mit unterschiedlichen Höhen geben wird. Ray Marschieren war nicht mehr geeignet, also schrieb Carmack eine andere Art von Renderer. Der Wolfenstein- Renderer, bei dem der Strahl für jede Pixelspalte verwendet wurde, wurde vom Bild abgestoßen, und der Doom- Renderer sollte von Objekten abgestoßen werden. Dies bedeutete, dass der Doom- Renderer, anstatt die Bildschirmpixel zu durchlaufen und ihre Farbe zu bestimmen, über Objekte in der Szene iterieren und diese nacheinander auf den Bildschirm projizieren musste.

In einem solchen Renderer besteht eine einfache Möglichkeit, das VSD-Problem zu lösen, in der Verwendung eines Z-Puffers. Jedes Mal, wenn wir ein Objekt auf den Bildschirm projizieren, wird für jedes Pixel, das wir zeichnen möchten, eine Überprüfung durchgeführt. Befindet sich der zu zeichnende Teil des Objekts näher am Player als das bereits im Pixel gezeichnete Objekt, können wir seine Informationen umschreiben. Andernfalls müssen Sie das Pixel unverändert lassen. Dieser Ansatz ist einfach, aber der Z-Buffer benötigt viel Speicher und der Renderer kann immer noch eine Reihe von Prozessortakten für die Projektion von Ebenengeometrien ausgeben, die der Player nicht sieht.

Anfang der neunziger Jahre hatte die Z-Buffer-Lösung einen weiteren Nachteil: Auf IBM-kompatiblen PCs mit einem Videoadaptersystem namens VGA war das Schreiben in den Ausgabebildpuffer ein kostspieliger Vorgang. Die für das Rendern von Pixeln aufgewendete Zeit, die dann einfach überschrieben wird, hat die Leistung des Renderers erheblich verringert.

Da das Schreiben in den Einzelbildpuffer so teuer war, bestand der ideale Renderer darin, zunächst die Objekte zu zeichnen, die dem Player am nächsten lagen, dann die Objekte unmittelbar dahinter usw., bis das Schreiben in jedes Pixel des Bildschirms abgeschlossen war. Zu diesem Zeitpunkt hätte der Renderer verstehen müssen, dass es Zeit zum Anhalten war, und so die Zeit sparen müssen, die er zum Erkunden entfernter Objekte aufwenden konnte, die der Player nicht sah. Die Anordnung von Szenenobjekten auf diese Weise, von der nächstgelegenen bis zur am weitesten entfernten, ist jedoch gleichbedeutend mit der Lösung des VSD-Problems. Die Frage stellt sich erneut vor uns: Was kann ein Spieler sehen?


Zunächst versuchte Carmack, dieses Problem zu lösen, indem er sich auf das Doom- Level-Schema stützte. Sein Renderer zeichnete zunächst die Wände des Raums, in dem sich der Player befindet, und ging dann in benachbarte Räume über, um Wände in diesen Räumen zu zeichnen, die vom aktuellen Raum aus sichtbar sein könnten. Wenn jeder Raum konvex wäre, würde dies das VSD-Problem lösen. Nicht konvexe Räume könnten in konvexe „Sektoren“ unterteilt werden. Wie diese Rendering-Technik wie eine starke Verlangsamung ausgesehen haben könnte, zeigt das oben gezeigte Video , in dem ein YouTuber-Benutzer mit dem Spitznamen Bisqwit seinen eigenen Renderer demonstriert, der nach demselben allgemeinen Algorithmus arbeitet. Dieser Algorithmus wurde erfolgreich im Duke Nukem 3D-Spiel verwendet, das drei Jahre nach Doom veröffentlicht wurde , als die Prozessoren leistungsfähiger wurden. Zu dieser Zeit hatte der Doom- Renderer, der diesen Algorithmus verwendete, 1993 Probleme mit komplexen Ebenen. Dies war besonders offensichtlich, als die Sektoren ineinander gebaut wurden, und dies war die einzige Möglichkeit, zum Beispiel eine Wendeltreppe zu schaffen. Wendeltreppen erforderten mehrere rekursive Abfahrten in den bereits eingezeichneten Bereich, was die Motordrehzahl drastisch verringerte.

Etwa zur gleichen Zeit, als das ID-Team feststellte, dass die Doom- Engine möglicherweise zu langsam ist, wurde ID-Software aufgefordert, Wolfenstein 3D auf Super Nintendo zu portieren. SNES war sogar noch leistungsschwächer als die IBM-kompatiblen PCs der damaligen Zeit, und es stellte sich heraus, dass der Wolfenstein- Renderer mit Ray-Marching-Technologie trotz seiner Einfachheit nicht mit Super-Nintendo-Geräten mit ausreichender Geschwindigkeit lief. Aus diesem Grund suchte Carmack nach einem besseren Algorithmus. Tatsächlich untersuchte und implementierte Carmack für Wolfensteins Super-Nintendo-Port zunächst die Partitionierung des binären Raums. In Wolfenstein war es ziemlich einfach, weil alle Wände parallel zu den Achsen waren; Untergang macht es schwerer. Aber Carmack erkannte, dass BSP-Bäume auch in Doom Geschwindigkeitsprobleme lösen würden.

Binäre Raumaufteilung

Die Binärraumpartitionierung vereinfacht die Lösung des VSD-Problems, indem die 3D-Szene vorab aufgeteilt wird. Im Moment reicht es für Sie, um zu verstehen, warum Partitionierung nützlich ist: Wenn Sie eine Linie (die eigentlich eine Ebene in 3D ist) durch die gesamte Szene ziehen und wissen, auf welcher Seite der Linie sich der Player oder die Kamera befindet, wissen wir auch, dass nichts ist Die andere Seite der Linie kann keine Objekte von der Seite der Linie abhalten, an der sich die Kamera befindet. Wenn Sie den Vorgang mehrmals wiederholen, erhalten Sie eine 3D-Szene, die in viele Abschnitte unterteilt ist. Dies ist keine Verbesserung gegenüber der ursprünglichen Szene, außer dass wir jetzt mehr darüber wissen, wie sich verschiedene Teile der Szene überlappen können.

Die ersten, die über diese Einteilung der 3D-Szene berichteten, waren Forscher, die für die US Air Force herausfinden wollten, ob Computergrafiken für den Einsatz in Flugsimulatoren progressiv genug sind. Ihre Ergebnisse veröffentlichten sie 1969 in einem Bericht mit dem Titel "Forschung zur Verwendung computergenerierter Bilder in der visuellen Simulation". Der Bericht kam zu dem Schluss, dass Computergrafiken zur Ausbildung von Piloten verwendet werden können. Gleichzeitig warnten die Forscher, dass die Implementierung des Systems durch die Aufgabe des VSD erschwert würde:

Eine der wichtigsten Aufgaben, die bei der Berechnung von Bildern in Echtzeit gelöst werden muss, ist die Prioritätsaufgabe oder versteckte Linien. In unserer alltäglichen visuellen Wahrnehmung der Welt um uns herum löst die Natur dieses Problem mit trivialer Einfachheit. Der Punkt eines undurchsichtigen Objekts überlappt alle anderen Punkte, die entlang derselben Sichtlinie liegen und weiter entfernt sind. Im Falle eines Computers ist diese Aufgabe sehr schwierig. Der zur Bestimmung der Priorität erforderliche Rechenaufwand nimmt im Allgemeinen mit zunehmender Komplexität der Umgebung exponentiell zu und übersteigt bald den Rechenaufwand, der mit der Suche nach Bildern von Objekten unter Berücksichtigung der Perspektive verbunden ist.

Eine von diesen Forschern erwähnte Lösung, von der sie sagten, dass sie zuvor in einem NASA-Projekt verwendet wurde, basiert auf der Schaffung einer sogenannten „Überlappungsmatrix“. Die Forscher weisen darauf hin, dass eine Ebene, die eine Szene in zwei Teile unterteilt, verwendet werden kann, um "etwaige Prioritätenkonflikte" zwischen Objekten auf gegenüberliegenden Seiten der Ebene aufzulösen. Im Allgemeinen müssen Sie diese Ebenen möglicherweise explizit zur Szene hinzufügen. Bei einer bestimmten Struktur der Geometrie können Sie sich jedoch auf die vorhandenen Flächen der Objekte verlassen. Die Forscher demonstrieren das folgende Beispiel, in dem p1 , p2 und p3 Oberflächen teilen. Befindet sich der Blickpunkt der Kamera auf der Vorderseite oder der „wahren“ Seite einer dieser Ebenen, ist pi 1. Die Matrix zeigt die Beziehung zwischen den drei Objekten in Abhängigkeit von den drei Trennebenen und der Position des Blickpunkts der Kamera. Wenn Objekt ai Objekt aj überlappt, dann Das Element aij der Matrix ist gleich 1.


Forscher haben vorgeschlagen, diese Matrix in Hardware zu implementieren und sie in jedem Frame neu zu berechnen. Tatsächlich sollte die Matrix als großer Schalter oder als eine Art eingebauter Z-Puffer fungieren. Beim Rendern des aktuellen Objekts wird das Video nicht für Teile des Objekts ausgegeben, wenn sich 1 in der Objektspalte befindet, sondern das entsprechende Zeilenobjekt wird gezeichnet.

Ein schwerwiegender Nachteil dieses Ansatzes besteht darin, dass eine Matrix der Größe n ² benötigt wird, um eine Szene mit n Objekten zu beschreiben. Die Forscher beschlossen daher zu prüfen, ob es möglich ist, die Überlappungsmatrix in Form einer „Prioritätenliste“ darzustellen, die nur eine Größe von n hat, und die Reihenfolge anzugeben, in der Objekte gezeichnet werden sollen. Sie stellten sofort fest, dass in bestimmten Szenen, beispielsweise in der oben gezeigten, die Reihenfolge nicht vollständig festgelegt werden kann (da es einen Überlappungszyklus gibt), weshalb sie der mathematischen Definition von „richtigen“ und „falschen“ Szenen viel Zeit widmeten. Am Ende kamen sie zu dem Schluss, dass zumindest für die „richtigen“ Szenen (und der Szenendesigner kann leicht die „falschen“ Fälle vermeiden) eine Prioritätenliste erstellt werden kann. Sie überließen die Listenerstellung jedoch dem Leser als Übung. Es scheint, dass der Hauptbeitrag dieser Arbeit von 1969 darin besteht, zumindest theoretisch die Möglichkeit aufzuzeigen, Teilungsebenen zu verwenden, um Objekte in der Szene anzuordnen.

Und nur in einem Artikel von 1980 mit dem Titel „Über die Erzeugung sichtbarer Oberflächen durch A-Priori-Baumstrukturen“ wurde ein spezifischer Algorithmus dafür demonstriert. In diesem Artikel, der von Henry Fuchs, Zvi Kedem und Bruce Naylor verfasst wurde, wurde der BSP-Baum erstmals beschrieben. Die Autoren sagen, ihre neue Datenstruktur sei "eine Lösung, ein alternativer Ansatz, der erstmals vor zehn Jahren verwendet wurde, aber aufgrund einiger weniger verbreiteter Schwierigkeiten" - und reagieren auf die Entscheidung, die sie 1969 in der Arbeit für die US-Luftwaffe getroffen haben. Nachdem Sie einen BSP-Baum erstellt haben, können Sie auf einfache Weise Objekte mit Priorität in der Szene organisieren.

Fuchs, Kedem und Naylor lieferten eine ziemlich klare Beschreibung der Funktionsweise des BSP-Baums, aber ich werde versuchen, eine weniger formelle, aber kurze Beschreibung zu geben.

Wir beginnen mit der Auswahl eines Polygons in der Szene und machen die Ebene, in der das Polygon liegt, zu einer Teilungsebene. Dieses einzelne Polygon wird auch zum Wurzelknoten des Baums. Die verbleibenden Polygone der Szene befinden sich auf der einen oder anderen Seite der Wurzelteilungsebene. Polygone auf der "vorderen" Seite oder im "vorderen" Halbraum der Ebene erscheinen im linken Teilbaum des Wurzelknotens und Polygone auf der "hinteren" Seite oder im "hinteren" Halbraum der Ebene erscheinen im rechten Teilbaum. Anschließend wiederholen wir diesen Vorgang rekursiv und wählen Polygone aus den linken und rechten Teilbäumen als neue Trennflächen für ihre eigenen Halbräume aus, die weitere Halbräume und Teilbäume erzeugen. Der Prozess endet, wenn die Polygone enden.

Nehmen wir an, wir möchten die Geometrie der Szene von hinten nach vorne rendern. ( « », , , , .) , BSP-; , , , — . «» , , «» . «» «» . VSD, , , .

BSP-, 2D-. 2D , .




BSP-, , — , . , BSP- . BSP- , . BSP- — , .

, , «» BSP-. BSP- , . , , , BSP , , , — . , BSP- .

, 1980 , 1993 «Constructing Good Partitioning Trees». id Software , , , BSP- Doom .

BSP- Doom

, Doom , , , . BSP- , ( ), .

« BSP- Doom » BSP- Doom . Doom BSP-. , 11 Doom . - , BSP «» BSP-. , , , BSP- . BSP- , .

BSP-, 1980 : Doom BSP- , . 1980 , , BSP- , , IBM- PC. Doom , . BSP-, . , Doom z-, z-, . , , , . Doom z-, Doom , , . , Doom : , , , , , , .


Doom II , , .


.


Quake

— Doom , BSP-. Doom BSP-, ; BSP- . Doom , ( ) , . , . , BSP-, , , .

BSP- Doom . , , , BSP-. ?

Doom , , «Constructing Good Partitioning Trees» BSP- 3D-. , , Doom , . , , BSP- , - . Masters of Doom : , : « BSP- 3D-, ?»

BSP-. , , , . 1980 . , , BSP- , . , BSP- . , . 1/30 .

BSP- . , , BSP- , — . , . BSP- , 1991 , 1990 Computer Graphics: Principles and Practice . , . 1991 BSP-, , Doom , « z-», . BSP-, . ( 1990 .) Computer Graphics: Principles and Practice , .


E1M1: Hangar.

, — « , , ?» — , , BSP- — . , , , BSP- , , . , , , Doom , . , , Doom ( Game Engine Black Book: DOOM ) — . , VSD , Doom . , , , , . .