Inside Quake: Sichtbare Oberflächen definieren

Der Veteran der dreidimensionalen Grafikprogrammierung, Michael Abrash, spricht am Beispiel der Entwicklung des ersten Quake über die Notwendigkeit kreativen Denkens bei der Programmierung.

Vor vielen Jahren arbeitete ich für die inzwischen aufgelöste Videoadapterfirma Video Seven. Dort half ich bei der Entwicklung eines VGA-Klons. Mein Kollege Tom Wilson, der viele Monate rund um die Uhr an der Entwicklung des Video Seven VGA-Chips arbeitete, versuchte, VGA so schnell wie möglich zu machen, und war sich sicher, dass seine Leistung fast maximal optimiert wurde. Als Tom jedoch bereits den letzten Schliff für das Chipdesign gab, hörten wir Gerüchte, dass unser Konkurrent Paradise in seinem Entwicklungsklon durch Hinzufügen von FIFO eine noch höhere Leistung erzielt hatte.

Dies war das Ende der Gerüchte - wir wussten nicht, was FIFO war oder wie sehr er half, sonst nichts. Tom, normalerweise eine freundliche und entspannte Person, wurde jedoch zu einem aktiven, besessenen Fanatiker mit zu viel Koffein im Blut. Anhand dieser Informationen versuchte er herauszufinden, was das Paradies konnte. Am Ende kam er zu dem Schluss, dass Paradise wahrscheinlich einen FIFO-Schreibpuffer zwischen dem Systembus und VGA eingefügt hat, sodass die zu schreibenden Daten beim Aufzeichnen der CPU in den Videospeicher sofort in den FIFO gelangen und die CPU die Verarbeitung fortsetzen kann, anstatt jedes Mal im Leerlauf zu stehen als er in den Anzeigespeicher schrieb.

Tom hatte weder logische Elemente noch genügend Zeit, um einen vollständigen FIFO zu implementieren, aber er schaffte es, FIFO mit einer einzigen Operationstiefe zu implementieren, wodurch der Prozessor den VGA-Chip durch eine Schreiboperation überholen konnte. Tom war sich nicht sicher, ob dies zu guten Ergebnissen führen würde, aber das war das einzige, was er tun konnte. Deshalb implementierte er dieses System und übertrug den Chip in die Produktion.

Es stellte sich heraus, dass FIFO für eine Operation unglaublich cool funktioniert: Zu dieser Zeit waren Video Seven VGA-Chips die schnellsten auf dem Markt; Sie wurden zu Beweisen für Toms Genie und zu Beweisen dafür, wozu der Schöpfer unter dem Druck der Umstände fähig ist. Das Tolle an dieser Geschichte ist jedoch, dass das Paradise FIFO-Design nichts mit dem Tom-Design zu tun hatte und überhaupt nicht funktionierte . Paradise fügte einen Lese- FIFO-Puffer zwischen dem Anzeigespeicher und der Videoausgangsstufe des VGA-Chips ein, der es ermöglichte, die Videoausgabe im Voraus zu lesen, so dass die Pixel aus dem FIFO entnommen werden konnten, wenn die CPU auf den Anzeigespeicher zugreifen musste, und der CPU-Befehl sofort ausgeführt wurde. Dies verbesserte tatsächlich die Leistung, jedoch nicht so stark wie Toms FIFO-Schreibpuffer.

Und dieser Fall kann als eine gute Parabel über die Natur des kreativen Prozesses angesehen werden, den eine Person erreichen kann. Nachrichtenfetzen über den Paradise-Chip enthielten fast keine sachlichen Informationen, aber sie zwangen Tom, über die Grenzen hinauszugehen, die er unbewusst gesetzt hatte, und das ursprüngliche Design des Chips zu entwickeln. Ich glaube, dass dies das wichtigste Element eines genialen Designs ist, sei es auf dem Gebiet der Hardware, Software oder einer anderen kreativen Sphäre, und er war es, der in den Tom-Nachrichten über das Paradies geboren wurde: die Fähigkeit, die Grenzen zu erkennen, die Sie bei der Arbeit an dem Projekt aufgebaut haben, und diese zu überwinden Grenzen.

Das Problem ist natürlich, wie man die Grenzen überwindet, deren Existenz man nicht einmal kennt. Es gibt keine Erfolgsformel, aber zwei Prinzipien können diesem Zweck gut dienen: erstens vereinfachen, zweitens ständig etwas Neues ausprobieren.

Wenn Sie das Gefühl haben, dass der Code kompliziert wird, nehmen Sie normalerweise geringfügige Änderungen an der eingefrorenen Struktur vor. Es besteht eine hohe Wahrscheinlichkeit, dass Sie die Produktivität steigern und die Codemenge reduzieren können, indem Sie das Design erneut erfinden. Eine wirklich gute Struktur sollte einen Moment tiefer Zufriedenheit bringen, wenn alles zusammenpasst, und Sie sind überrascht, wie wenig Code benötigt wird und wie gut alle Grenzfälle funktionieren.

Bei der Überprüfung der Struktur ist es wichtig, alle Ideen zu untersuchen, die mir in den Sinn kommen, egal wie verrückt sie erscheinen mögen. Viele der wirklich großartigen Ideen, die ich zuerst hörte, schienen Unsinn zu sein, weil sie nicht in mein bestehendes Bild der Welt passten. Oft sind diese Ideen wirklich verrückt, aber genau wie die Paradise-Chip-Nachrichten Toms Fantasie anregten, kann die aggressive Erforschung scheinbar wahnhafter Ideen neue Möglichkeiten für Sie eröffnen.

Gute Illustration: Die Entwicklung der Quake 3D-Grafik-Engine.

Die komplexeste 3D-Grafikaufgabe der Welt

Ich habe die letzten sieben Monate an Quake gearbeitet, dem Erben von DOOM von id Software, und ich gehe davon aus, dass Quake drei weitere Monate später, wenn Sie diesen Artikel lesen, als Shareware veröffentlicht wird.

In Bezug auf die Grafik wird Quake für DOOM das sein, was DOOM für seinen Vorgänger Wolfenstein 3D war. Quake fügt echte willkürliche 3D-Bilder (der Spieler kann nach oben und unten schauen, sich zur Seite lehnen und sogar zur Seite fallen), detaillierte Beleuchtung und Schatten, 3D-Monster und Charaktere anstelle von DOOM-Sprites hinzu. Bald werde ich ausführlicher darüber sprechen, aber diesen Monat möchte ich über das Problem sprechen, das ich in meinem Buch als das schwierigste in dreidimensionalen Grafiken bezeichne: das Bestimmen sichtbarer Oberflächen (Zeichnen der entsprechenden Oberfläche für jedes Pixel) und über eine Aufgabe, die sehr nahe daran liegt - ungefähr Clipping (so schnell wie möglich unsichtbare Polygone verwerfen, um die Bestimmung sichtbarer Oberflächen zu beschleunigen). Der Kürze halber werde ich die Abkürzung VSD verwenden, um die Definition der Bestimmung und Keulung der sichtbaren Oberfläche zu bezeichnen.

Warum halte ich VSD für die schwierigste Aufgabe von 3D-Grafiken? Obwohl die Aufgaben der Rasterung, beispielsweise das Textur-Mapping, ebenso erstaunlich und wichtig sind, sind sie in ihrem Umfang recht begrenzt, und nach dem Aufkommen von 3D-Beschleunigern wird ihre Lösung auf die Hardware übertragen. Außerdem hängt ihr Maßstab nur von der Bildschirmauflösung ab, das heißt, sie sind recht bescheiden.

Im Gegensatz dazu ist VSD eine unbegrenzte Aufgabe, und Dutzende von Ansätzen werden verwendet, um sie zu lösen. Noch wichtiger ist jedoch, dass die VSD-Leistung in einer naiven Lösung von der Komplexität der Szene abhängt, die normalerweise als quadratische oder kubische Funktion zunimmt und daher schnell zum begrenzenden Faktor bei der Erstellung realistischer Welten wird. Ich glaube, dass VSD in den nächsten Jahren ein zunehmend dominantes Problem bei 3D-Echtzeitgrafiken für PCs sein wird, da die Details von 3D-Welten ständig zunehmen werden. Bereits heute kann ein Quake-Level mit fester Größe etwa 10.000 Polygone enthalten, dh fast dreimal so viel wie ein vergleichbares DOOM-Level.

Struktur auf Bebenebene

Bevor ich mich mit dem VSD befasse, möchte ich erwähnen, dass jede Ebene von Quake als ein riesiger dreidimensionaler BSP-Baum gespeichert ist. Dieser BSP-Baum teilt wie jeder andere BSP den Raum in diesem Fall entlang der Ebenen der Polygone. Im Gegensatz zum BSP-Baum, den ich zuvor demonstriert habe, speichert der Quake-BSP-Baum jedoch keine Polygone in den Baumknoten als Teil der Teilungsebenen, sondern in leeren (ungefüllten) Blättern, wie in Abbildung 1 in der Draufsicht dargestellt.


Abbildung 1. In Quake werden Polygone in leeren Blättern gespeichert. Dunkle Bereiche sind gefüllte Blätter (gefüllte Volumen, z. B. die Innenseiten von Wänden).

Die richtige Renderreihenfolge erhalten Sie, indem Sie die Blätter in der BSP-Reihenfolge „von vorne nach hinten“ oder „von hinten nach vorne“ rendern. Da BSP-Blätter immer konvex sind und Polygone die Grenzen von BSP-Blättern sind, die nach innen schauen, können sich die Polygone eines Blattes niemals überlappen und in beliebiger Reihenfolge gezeichnet werden. (Dies ist eine allgemeine Eigenschaft von konvexen Polyedern.)

Beschneiden und Definieren sichtbarer Flächen

Im Idealfall sollte der VSD-Prozess wie folgt funktionieren: Zunächst müssen Sie alle Polygone verwerfen, die sich außerhalb der Sichtbarkeitspyramide befinden, und alle unsichtbaren Teile der Polygone abschneiden, die teilweise sichtbar sind. Dann müssen Sie nur die Pixel jedes Polygons zeichnen, die vom aktuellen Standpunkt aus tatsächlich sichtbar sind, wie in Abbildung 2 in der Draufsicht dargestellt, ohne Zeit damit zu verschwenden, die Pixel wiederholt neu zu zeichnen. Beachten Sie, wie wenige Polygone in Abbildung 2 Sie zeichnen müssen. Und schließlich sollte in einer idealen Welt die Überprüfung der Sichtbarkeit von Teilen von Polygonen kostengünstig sein und die Verarbeitungszeit für alle möglichen Gesichtspunkte gleich sein, damit das Spiel reibungslos funktioniert.


Abbildung 2. Die ideale VSD-Architektur rendert nur die sichtbaren Teile der sichtbaren Polygone.

Bei der Ausführung dieser Aufgabe ist es einfach zu bestimmen, welche der Polygone vollständig außerhalb des Bereichs der Sichtbarkeitspyramide liegen oder teilweise abgeschnitten sind, und es ist vollständig möglich, genau herauszufinden, welche Pixel gezeichnet werden sollen. Leider ist die Welt alles andere als ideal, und all diese Überprüfungen sind kostspielig. Der Trick besteht also darin, verschiedene Überprüfungen zu beschleunigen oder zu überspringen, um das notwendige Ergebnis zu erzielen.

Wie ich in früheren Artikeln ausführlich erklärt habe, können Sie mit einem BSP einfach und kostengünstig in der Reihenfolge von vorne nach hinten oder von hinten nach vorne um die Welt gehen. Die einfachste VSD-Lösung besteht darin, den Baum einfach von hinten nach vorne zu durchlaufen, jedes Polygon mit einer Sichtbarkeitspyramide abzuschneiden und es zu zeichnen, wenn sein Gesicht in die Kamera gerichtet und nicht vollständig abgeschnitten ist (Künstleralgorithmus). Aber ist das eine adäquate Lösung?

Für relativ einfache Welten ist es durchaus anwendbar. Es skaliert jedoch nicht gut. Eines der Probleme besteht darin, dass immer mehr Transformationen und Überprüfungen erforderlich sind, wenn der Welt neue Polygone hinzugefügt werden, um unsichtbare Polygone abzuschneiden. Ab einem bestimmten Schwellenwert wird dies die Leistung erheblich verlangsamen.

Glücklicherweise hat dieses spezielle Problem eine gute Problemumgehung. Wie oben erwähnt, beschreibt jedes Blatt im BSP-Baum einen konvexen Unterraum, und die mit dem Blatt verbundenen Knoten begrenzen den Raum. Weniger offensichtlich ist, dass jeder Knoten im BSP-Baum auch einen Unterraum beschreibt - einen Unterraum, der aus allen untergeordneten Knoten des Knotens besteht (siehe Abbildung 3). Sie können dies folgendermaßen tun: Jeder Knoten teilt den Unterraum, der von den oben in Baum und die untergeordneten Elemente des Knotens rahmen diesen Unterraum weiter in alle vom Knoten kommenden Blätter ein.


Abbildung 3: Knoten E beschreibt einen abgedunkelten Unterraum, der die Blätter 5, 6, 7 und den Knoten F enthält.

Da der Unterraum des Knotens begrenzt und konvex ist, können wir prüfen, ob er vollständig außerhalb der Sichtbarkeitspyramide liegt. Wenn ja, werden alle untergeordneten Knoten des Knotens definitiv vollständig abgeschnitten und können ohne zusätzliche Verarbeitung verworfen werden. Da sich der Hauptteil der Welt normalerweise außerhalb der Sichtbarkeitspyramide befindet, können viele Polygone der Welt durch riesige Fragmente von Teilräumen von Knoten fast kostenlos abgeschnitten werden. Das Durchführen einer idealen Prüfung zum Abschneiden von Teilräumen ist ziemlich kostspielig, daher werden normalerweise für jeden Knoten einschränkende Parallelogramme oder Kugeln zum Beschneiden von Prüfungen verwendet.

Das heißt, das Abschneiden entlang der Sichtbarkeitspyramide ist kein Problem, und Sie können BSP verwenden, um rückwärts zu zeichnen. Was ist das Problem?

Neu zeichnen

Das Problem, mit dem der Hauptautor der DOOM- und Quake-Technologien John Carmack bei der Entwicklung von Quake konfrontiert war, bestand darin, dass in einer komplexen Welt viele Szenen in der Pyramide der Sichtbarkeit eine große Anzahl von Polygonen aufweisen. Die meisten dieser Polygone werden teilweise oder vollständig von anderen Polygonen überlappt. Der oben beschriebene Algorithmus des Künstlers erfordert jedoch das Zeichnen jedes Pixels jedes Polygons in der Sichtbarkeitspyramide. Sie werden jedoch oft nur gerendert, um von anderen neu gezeichnet zu werden. Bei einem Quake-Level von 10.000 Polygonen ist es leicht, den schlimmsten Fall des Neuzeichnens zu erhalten, wenn Pixel zehnmal oder öfter gezeichnet werden. Das heißt, in einigen Frames wird jedes Pixel im Durchschnitt zehnmal oder öfter gezeichnet. Kein Raster ist schnell genug, um die Größenordnung zu kompensieren, die zum Rendern einer Szene erforderlich ist. Schlimmer noch, der Algorithmus des Künstlers erzeugt große Leistungsunterschiede zwischen dem besten und dem schlechtesten Fall, was zu einer signifikanten Änderung der Bildrate beim Bewegen des Betrachters führt.

John stand also vor dem Problem, die Anzahl der Neuzeichnungen auf ein akzeptables Maß zu reduzieren. Im Idealfall sollte jedes Pixel nur einmal gezeichnet werden, im schlimmsten Fall jedoch nicht mehr als zwei- oder dreimal. Für das Durchschneiden der Sichtbarkeitspyramide war es idealerweise erforderlich, dass alle in der Pyramide unsichtbaren Polygone fast ohne zusätzliche Kosten abgeschnitten wurden. Ein Plus wäre auch, dass es möglich wäre, nur die sichtbaren Teile von teilweise sichtbaren Polygonen zu zeichnen, gleichzeitig aber ein Gleichgewicht aufrechtzuerhalten: Die Operation sollte weniger als das Neuzeichnen ausgeben.

Als ich Anfang März zu id kam, hatte John bereits einen Prototyp des Motors und einen Umrissplan, daher ging ich davon aus, dass unsere Arbeit einfach darin bestehen würde, diesen Motor fertigzustellen und zu optimieren. Wenn ich jedoch die Geschichte von id kennen würde, könnte ich herausfinden, was was ist. John hat nicht nur DOOM erstellt, sondern auch Engines für Wolf 3D und mehrere andere frühere Spiele. Während des Entwicklungsprozesses hat er mehrere verschiedene Versionen jeder Engine erstellt (nachdem er in vier Wochen vier Engines erstellt hat), dh in vier Jahren hat er ungefähr 20 Engines geschrieben . Johns unermüdlicher Wunsch nach immer mehr neuen und hochwertigen Technologien der Quake-Engine wird erst nach der Veröffentlichung des Spiels enden.

Drei Monate nach meiner Ankunft blieb nur ein Element der ursprünglichen VSD-Struktur im Motor, und Johns Wunsch, „neue Dinge auszuprobieren“, ging so weit, dass ich so etwas noch nie zuvor gesehen hatte.

Bündelbaum

In Johns ursprünglichem Quake-Projekt wurde das Rendern von vorne nach hinten mithilfe eines zweiten BSP-Baums durchgeführt, der bereits gezeichnete und noch leere Teile des Bildschirms verfolgt, die mit den verbleibenden Polygonen gefüllt werden mussten. Logischerweise kann dieser BSP-Baum als zweidimensionaler Bereich betrachtet werden, der die gefüllten und leeren Teile des Bildschirms beschreibt, wie in Abbildung 4 dargestellt. Tatsächlich handelt es sich jedoch um einen dreidimensionalen Baum, der als „Strahlbaum“ bezeichnet wird. Ein Strahlbaum ist eine Reihe von 3D-Sektoren (Bündeln), die durch Ebenen begrenzt sind, die von einem zentralen Punkt (in unserem Fall dem Ansichtspunkt) projiziert werden (siehe Abbildung 5).


Abbildung 4. Der Quake Beam-Baum teilt den Bildschirm effektiv in einen 2D-Bereich auf


Abbildung 5. Der Bebenstrahlbaum besteht aus 3D-Sektoren oder Strahlen, die vom Ansichtspunkt zu den Kanten der Polygone projiziert werden.

In Johns Projekt besteht ein Garbenbaum zunächst aus einer einzelnen Garbe, die die Pyramide der Sichtbarkeit beschreibt. Alles außerhalb dieses Bündels wird als gefüllt betrachtet (dh es muss dort nichts gezeichnet werden), und alles innerhalb des Bündels wird als leer betrachtet. Wenn ein neues Polygon erreicht wurde, indem der BSP-Baum der Welt von vorne nach hinten umrundet wurde, wurde dieses Polygon in einen Strahl umgewandelt, indem Ebenen von seinen Kanten durch den Blickpunkt gezogen wurden, und alle Teile des Strahls, die leere Strahlen im Strahlbaum kreuzten, wurden als gezeichnet betrachtet und dem Strahlbaum als gefüllter Strahl hinzugefügt. Dies ging weiter, entweder bis die Polygone endeten oder bis der Garbenbaum vollständig voll wurde. Nachdem der Balkenbaum fertiggestellt war, wurden die sichtbaren Teile der im Balkenbaum eingeschlossenen Polygone gezeichnet.

Der Vorteil der Arbeit mit einem dreidimensionalen Bündelbaum anstelle des 2D-Bereichs bestand darin, dass zur Bestimmung der Seite der Bündelebene, auf der sich der Scheitelpunkt des Polygons befindet, das Vorzeichen des Vektorprodukts des Strahls zum Scheitelpunkt und die Normale zur Ebene überprüft werden muss, da alle Bündelebenen durch den Anfang verlaufen Koordinaten (Standpunkt). Da die Strahlenebene vollständig durch eine einzelne Normale beschrieben ist, reicht außerdem aus, um einen Strahl von der Kante des Polygons zu erzeugen, nur das Skalarprodukt der Kante und der Strahl von dieser Kante zum Gesichtspunkt. Schließlich kann man für das Gruppenbeschneiden durch die oben beschriebene Sichtbarkeitspyramide die Begrenzungskugeln von BSP-Knoten verwenden.

Zunächst schien die Bundle-Tree-Eigenschaft (die endet, wenn der Bundle-Tree voll wird) attraktiv, da sie die Leistung im schlimmsten Fall einschränken würde. Leider waren immer noch Szenen möglich, in denen man alles bis zum Himmel oder zur Rückwand der Welt sehen konnte. Im schlimmsten Fall mussten Sie immer noch alle Polygone in der Sichtbarkeitspyramide in Bezug auf den Haufenbaum überprüfen. Ähnliche Probleme können auch bei kleinen Rissen aufgrund von Einschränkungen der numerischen Genauigkeit auftreten. Es wird ziemlich viel Zeit für das Durchschneiden des Strahlbaums aufgewendet, und in Szenen mit einem hohen Sichtbereich, z. B. von oben gesehen, reduzierten die Gesamtkosten für die Verarbeitung der Strahlen die Bildrate von Quake auf Schildkrötengeschwindigkeit. Das heißt, am Ende stellte sich heraus, dass die Lösung mit Bündelbäumen an fast denselben Krankheiten leidet wie der Algorithmus des Künstlers: Der schlimmste Fall ist viel schlimmer als der Durchschnittsfall und lässt sich mit zunehmender Komplexität des Levels nicht gut skalieren.

Täglich neue 3D-Engine

Nachdem der Beam Tree seine Arbeit aufgenommen hatte, arbeitete John unermüdlich daran, die 3D-Engine zu beschleunigen, und versuchte ständig, ihre Struktur zu verbessern, anstatt Änderungen an der Implementierung vorzunehmen. , , : « , ...», , . , , , . , . , . . , , , FIFO- Paradise .

raycast : , 8x8, ; , , BSP-, , . , , , , ; , , . , , . : , .

: . . ( ), .

: z-, , , . , , , , . : , 256 0-8 ; x86 8 .

: , , . , . , ; , .

: , , . , , , . , .

, — , , BSP- , BSP- . , DOOM (2D), BSP- DOOM 2D- . 3D , . BSP , , . , , BSP.

, , , - . BSP, , , . 3:30 , , , , , , , .

: (potentially visible set, PVS) . PVS 1 . . BSP , . , , , , . , BSP , , PVS 20 .

20 ( PVS), (PVS , , , 50%, 150%). , PVS ; , VSD, . , — , , , .

, PVS , , «» . , , , , , «» , .

-

Was bedeutet das? , : - . PVS , ( PVS — , ). , PVS — . , ?

Überhaupt nicht. , , . , , .

, , . : — , . , , «» . , « »; . VSD, , . , « » , ( , ) PVS .

— , , . , , . , 3D- , ; , , .

.

,

, . , Dr. Dobb's Journal , — . , Tiny C , D-Flat , - DDJ . ( , .) — , DDJ .

id Software , Quake . id Wolfenstein 3D ftp.idsoftware.com/idstuff/source [. .: github ] ; , , ; wolfsrc.txt , , .

: , . , , , , , . ; — , . , !

Referenzen

Foley, James D., et al. , Computer Graphics: Principles and Practice , Addison Wesley, 1990, ISBN 0-201-12110-7 (, BSP-, VSD).

Teller, Seth, Visibility Computations in Densely Occluded Polyhedral Environments (), http://theory.lcs.mit.edu/~seth/ .

Teller, Seth, Visibility Preprocessing for Interactive Walkthroughs , SIGGRAPH 91 proceedings, pp. 61-69.