Geekly articles weekly

Inside Quake: Immer Alternativen in Betracht ziehen

Bild

Der Programmierer Michael Abrash, der Mitte der 90er Jahre von John Carmack eingeladen wurde, am Motor des ersten Bebens zu arbeiten, schrieb während des Entwicklungsprozesses eine Reihe von Artikeln. Dies ist die zweite Spalte in dieser Reihe. Die Übersetzung des ersten ist hier .

Ich muss zugeben: Ich habe den klassischen Rock satt. Das letzte Mal vor ungefähr 20 Jahren war ich glücklich, etwas von Cars oder Boston zu hören. Außerdem hat mich Bob Seager und Queen, ganz zu schweigen von Elvis, nie besonders angezogen, so wenig hat sich geändert. Aber ich erkannte, dass sich etwas änderte, als ich das Radio umschalten wollte, als ich Allman Brothers oder Steely Dan oder Pink Floyd oder, Gott, vergib mir, die Beatles hörte (aber nur bei Dingen wie „Hallo Auf Wiedersehen“ und „Ich werde Weinen Sie stattdessen, nicht Ticket to Ride oder Ein Tag im Leben; so weit bin ich noch nicht gegangen). Es dauerte nicht lange, die Gründe dafür zu finden; Ich habe ein Vierteljahrhundert lang dieselben Songs gehört und bin einfach müde geworden.

Ich erzähle es so, denn als meine Tochter und ich eines Abends aus dem Café fuhren, wurde der Radiosender „Es gibt keine Alternative“ zum ersten Mal im Auto eingeschaltet.

Wir sprechen von einem zehnjährigen Mädchen, das mit einer ständigen Diät alter Hits aufgewachsen ist. Sie mag Melodien, eingängige Lieder und gute Sänger. Sie werden nichts davon finden, wenn Sie eine alternative Rockstation hören. Daher ist es nicht verwunderlich, dass sie beim Einschalten des Radios zuerst sagte: "Fu!"

Aber Folgendes hat mich überrascht: Nachdem sie eine Weile zugehört hatte, sagte sie: "Weißt du, Papa, aber das ist wirklich interessant."

Dies deutete mich nicht nur darauf hin, welche Art von Musik im ganzen Haus rumpeln würde, wenn sie ein Teenager wurde. Ihre schnelle Übernahme von Alternative Rock (verglichen mit meiner Faszination für die Musik meiner eigenen Jugend seit zehn Jahren) erinnerte mich an etwas, das leicht vergessen wird, wenn man älter wird und sich der Lebensstil festsetzt. Dies erinnerte mich daran, dass es notwendig war, offen zu bleiben und darauf vorbereitet zu sein, neue Dinge auszuprobieren. Programmierer neigen dazu, an vertraute Ansätze gebunden zu sein, und neigen dazu, sie zu verwenden, wenn sie die Aufgaben angemessen bewältigen. Aber es gibt immer Alternativen zur Programmierung, und ich finde, dass es sich oft lohnt, sie zu erkunden.

Aber angesichts der sich ständig ändernden Natur von Quake sollte ich eine solche Erinnerung wirklich nicht brauchen.

Kreativer Stream


Im Januar habe ich einen kreativen Stream beschrieben, der John Carmack dazu veranlasste, vorberechnete PVS-Polygone (Potential Visible Set) für jeden möglichen Standpunkt in Quake (einem Spiel, das wir gemeinsam in id Software entwickeln) zu verwenden. Vorläufige Berechnung von PVS bedeutet, dass wir nicht viel Zeit damit verbringen müssen, die Datenbank der Polygone zu durchsuchen, die aus der aktuellen Sicht in der Weltdatenbank sichtbar ist, sondern einfach alle Polygone in der PVS von hinten nach vorne zeichnen können (die Reihenfolge aus dem BSP-Baum der Welt übernehmen; Diskussion über BSP- Sehen Sie sich die Bäume in unseren Spalten für Mai, Juli und November 1995 an und lassen Sie die Szene vollständig korrekt rendern, ohne zu suchen. Dadurch kann der letzte Schritt der Entfernung versteckter Oberflächen (HSR) rückwärts gerendert werden. Es war eine großartige Idee, aber für die Quake-Architektur ist der Pfad noch nicht abgeschlossen.

Bewegte Objekte zeichnen


Zum Beispiel gab es immer noch eine Frage, wie sich bewegende Objekte richtig sortiert und gezeichnet werden können. Tatsächlich wurde diese Frage nach der Januar-Kolumne am meisten gestellt, also werde ich ihr Zeit geben. Das Hauptproblem besteht darin, dass ein sich bewegendes Modell in mehrere BSP-Blätter fallen kann. Wenn sich das Modell bewegt, ändern sich diese Blätter. Zusammen mit der Möglichkeit, mehrere Modelle in einem Blatt zu finden, bedeutet dies, dass es keine einfache Möglichkeit gibt, die BSP-Reihenfolge zu verwenden, um Modelle in einer korrekt sortierten Reihenfolge zu zeichnen. Als ich die Januar-Kolumne schrieb, zeichneten wir Sprites (wie Explosionen), bewegliche BSP-Modelle (wie Türen) und polygonale Modelle (wie Monster), schnitten sie mit den Blättern ab, die sie berührten, und zeichneten dann die entsprechenden Teile, wenn jedes BSP-Blatt erreicht war Sie sind dran, wenn Sie von hinten nach vorne gehen. Dies löste jedoch nicht das Problem, mehrere sich bewegende Modelle in einem Blatt relativ zueinander zu sortieren, und hinterließ auch unangenehme Probleme bei komplexen polygonalen Modellen.

John hat das Sortierproblem für Sprites und Polygonmodelle auf überraschend einfache Weise gelöst: Jetzt schreiben wir sie in den Z-Puffer. (Das heißt, bevor wir jedes Pixel zeichnen, vergleichen wir den Abstand oder z mit dem z-Wert des bereits auf dem Bildschirm angezeigten Pixels. Ein neues Pixel wird nur gezeichnet, wenn es näher als das vorhandene Pixel ist.) Zuerst zeichnen wir die Hauptwelt - Wände, Decken usw. so. Zu diesem Zeitpunkt wird kein Test des Z-Puffers verwendet (wie wir bald sehen werden, wird die Definition der sichtbaren Oberflächen der Welt auf andere Weise durchgeführt); Wir füllen den Z-Puffer jedoch mit Z-Werten (tatsächlich 1 / Z-Werte, wie unten beschrieben) für alle Pixel auf der Welt. Das Füllen eines Z-Puffers ist ein viel schnellerer Prozess als das Z-Puffern der ganzen Welt, da es kein Lesen, keine Vergleiche, nur das Schreiben von Z-Werten gibt. Nachdem wir das Zeichnen abgeschlossen und den Z-Puffer der Welt ausgefüllt haben, können wir einfach Sprites und polygonale Modelle mit Z-Puffer zeichnen und die perfekte Sortierung erhalten.

Bei Verwendung des Z-Puffers stellen sich zwangsläufig Fragen: Wie wirkt sich dies auf den belegten Speicher und die Leistung aus? Bei einer Auflösung von 320 x 200 werden 128 KB Speicher benötigt, was nicht trivial ist, aber nicht so sehr für ein Spiel, für dessen Funktion 8 MB erforderlich sind. Auswirkungen auf die Leistung: ca. 10% beim Füllen des Z-Puffers der Welt und ca. 20% (Indikatoren variieren stark) beim Rendern von Sprites und polygonalen Modellen. Im Gegenzug erhalten wir eine perfekt sortierte Welt sowie die Möglichkeit, zusätzliche Effekte zu erzielen, z. B. Explosionen und Rauch von Partikeln, da Sie mit dem Z-Puffer diese Effekte einfach in der Welt sortieren können. Im Allgemeinen hat die Verwendung von Z-Buffer die visuelle Qualität und Flexibilität der Quake-Engine erheblich verbessert und den Code auf Kosten angemessener Speicherkosten und Leistung erheblich vereinfacht.

Nivellierung und Steigerung der Produktivität


Wie ich oben sagte, zeichnet die Quake- Architektur zuerst die Welt selbst, ohne den Z-Puffer zu lesen oder zu vergleichen, und füllt den Z-Puffer nur mit den Werten der Polygone der Welt in z. Danach werden sich bewegende Objekte mit vollständiger Z-Pufferung über die Welt gezeichnet. Bisher habe ich nur darüber gesprochen, wie man sich bewegende Objekte zeichnet. Im Rest der Spalte werde ich über einen anderen Teil der Rendering-Gleichung sprechen - das Zeichnen der Welt selbst, wenn die ganze Welt als ein BSP-Baum gespeichert ist und sich nie bewegt.

Wie Sie sich aus der Januar-Kolumne erinnern können, waren wir sowohl über die Rohleistung als auch über die Mittelung besorgt. Das heißt, wir wollten, dass der Rendering-Code so schnell wie möglich und gleichzeitig ausgeführt wird, damit der Unterschied zwischen der Rendergeschwindigkeit der mittleren Szene und der langsamsten beim Rendern der Szene so gering wie möglich ist. Es gibt nichts Gutes in den durchschnittlichen 30 Bildern pro Sekunde, wenn 10% der Szenen mit 5 fps gezeichnet werden, da das Ruckeln in solchen Szenen im Vergleich zur durchschnittlichen Szene extrem auffällig ist. In 100% der Fälle ist es besser, die Frequenz mit 15 Bildern pro Sekunde zu mitteln, obwohl die durchschnittliche Rendergeschwindigkeit halb so hoch ist.

Vorberechnete PVS waren ein wichtiger Schritt in Richtung einer höheren und ausgewogeneren Leistung, da keine sichtbaren Polygone mehr bestimmt werden mussten - eine eher langsame Phase, die sich in den komplexesten Szenen am schlechtesten zeigte. Trotzdem enthalten vorberechnete PVS an einigen Orten mit realen Spielstufen fünfmal mehr Polygone als tatsächlich gesehen wird. In Verbindung mit der Entfernung von rückwärts versteckten Oberflächen (HSR) wurden „heiße Zonen“ geschaffen, in denen die Bildrate spürbar reduziert wurde. Hunderte von Polygonen wurden von hinten nach vorne gezogen, und die meisten von ihnen wurden sofort von engeren Polygonen neu gezeichnet. Die Rohleistung insgesamt verringerte sich ebenfalls um durchschnittlich 50% der Neuzeichnung, die durch das Rendern aller Elemente im PVS verursacht wurde. Obwohl das Rendern von Rückwärts-PVS-Sets als letzte Stufe des HSR fungierte und eine Verbesserung gegenüber der vorherigen Architektur darstellte, war es daher nicht ideal. John dachte, es gäbe wahrscheinlich einen besseren Weg, PVS zu verwenden, als von vorne nach hinten zu zeichnen.

Und er wurde tatsächlich gefunden.

Sortierte Intervalle


Die ideale letzte HSR-Stufe für Quake bestand darin, alle Polygone im PVS zu verwerfen, die sich tatsächlich als unsichtbar herausstellten, und nur die sichtbaren Pixel der verbleibenden Polygone zu zeichnen, ohne sie neu zu zeichnen. Das heißt, jedes Pixel würde natürlich genau einmal und ohne Leistungsverlust gezeichnet. Eine Lösung (die jedoch Kosten erfordert) besteht darin, von vorne nach hinten zu zeichnen, den Bereich zu speichern, der die aktuell überlappenden Teile des Bildschirms beschreibt, und jedes Polygon vor dem Rendern mit den Rändern dieses Bereichs abzuschneiden. Es klingt vielversprechend, erinnert aber in etwa an die Bündelbaumlösung, die ich in der Januar-Kolumne beschrieben habe. Wie wir herausgefunden haben, erfordert dieser Ansatz eine Verschwendung zusätzlicher Ressourcen und hat ernsthafte Probleme mit dem Lastausgleich.

Sie können es viel besser machen, wenn Sie den letzten HSR-Schritt von der Polygonebene auf die Intervallebene verschieben und die Lösung mit sortierten Intervallen verwenden. Im Wesentlichen besteht dieser Ansatz darin, jedes Polygon in eine Reihe von Intervallen umzuwandeln, wie in Abbildung 1 gezeigt, und anschließend die Intervalle relativ zueinander zu sortieren und abzuschneiden, bis nur noch sichtbare Teile der sichtbaren Intervalle zum Rendern übrig bleiben, wie in Abbildung 2 dargestellt Sehr ähnlich der Z-Pufferung (die, wie oben erwähnt, zu langsam ist, um beim Rendern der Welt verwendet zu werden, obwohl sie für kleinere sich bewegende Objekte geeignet ist), aber es gibt wichtige Unterschiede. Im Gegensatz zur Z-Pufferung werden nur die sichtbaren Teile der sichtbaren Intervalle Pixel für Pixel gescannt (obwohl alle Kanten der Polygone noch gerastert werden müssen). Noch besser ist, dass die durch Z-Pufferung für jedes Pixel durchgeführte Sortierung zu einer Intervalloperation mit sortierten Intervallen wird, und da eine integrale Eigenschaft der Intervallliste die Verbundenheit ist, wird jede Kante nur relativ zu einigen Intervallen in derselben Zeile sortiert und nur um einige Intervalle abgeschnitten, wenn horizontale Überlagerung. Obwohl die Verarbeitung komplexer Szenen immer noch länger dauerte als einfache, waren die schlimmsten Fälle nicht so schlimm wie bei der Verwendung von Beam-Bäumen oder beim Sortieren von hinten nach vorne, da keine Neuzeichnung und Suche nach versteckten Pixeln erfolgt, die Komplexität durch die Pixelauflösung begrenzt ist und die Intervallkonnektivität die Sortierung der schlimmsten begrenzt Fälle in einem beliebigen Bereich des Bildschirms. Als Bonus erfolgt die Ausgabe sortierter Intervalle in der Form, die ein Rasterizer auf niedriger Ebene benötigt: im Format einer Reihe von Intervalldeskriptoren, von denen jede aus einer Koordinate des Anfangs und der Länge besteht.



Intervallgenerierung

Kurz gesagt, die Lösung mit sortierten Intervallen liegt ziemlich nahe an unseren ursprünglichen Kriterien. Obwohl es keine Kosten spart, sind sie immer noch nicht ganz schrecklich. Das Neuzeichnen und Scannen von Pixeln der überlappenden Teile der Polygone wird vollständig eliminiert, und im schlimmsten Fall kann die Leistung ausgeglichen werden. Wir würden uns nicht nur auf sortierte Intervalle als Mechanismus zur Beseitigung verborgener Oberflächen verlassen, sondern vorberechnete PVS reduzieren die Anzahl der Polygone auf ein Niveau, das sortierte Intervalle gut genug handhaben.

Wir haben also den Ansatz gefunden, den wir brauchen. es bleibt nur der Code zu schreiben und das ist vorbei, oder? Ja und nein. Der konzeptionelle Ansatz mit sortierten Intervallen ist einfach, aber überraschend schwer zu implementieren: Sie müssen einige wichtige Entwurfsentscheidungen treffen, es erfordert ein wenig Mathematik und es gibt listige Fallstricke. Schauen wir uns zuerst die Designlösungen an.

Rippen gegen Intervalle


Die erste Entscheidung besteht darin, auszuwählen, was sortiert werden soll: Intervalle oder Kanten (beide Konzepte gehören zur allgemeinen Kategorie der „sortierten Intervalle“). Obwohl die Ergebnisse in beiden Fällen gleich sind (eine Liste von Intervallen, die ohne erneutes Zeichnen gezeichnet werden müssen), sind Implementierungen und Auswirkungen auf die Leistung sehr unterschiedlich, da Sortieren und Abschneiden durch sehr unterschiedliche Datenstrukturen durchgeführt werden.

Beim Sortieren von Intervallen werden diese Intervalle in Speichersegmenten gespeichert, die nach x verknüpften Listen sortiert sind, normalerweise ein Segment pro Rasterzeile. Jedes Polygon wird wiederum in Intervalle gerastert, wie in Abbildung 1 gezeigt. Jedes Intervall wird sortiert und in das Speichersegment der Rasterzeile abgeschnitten, in der sich das Intervall befindet, wie in Abbildung 2 dargestellt, sodass zu jedem Zeitpunkt jedes Segment die nächsten angetroffenen Intervalle enthält , immer ohne Überlagerungen. Bei diesem Ansatz müssen nacheinander alle Intervalle für jedes Polygon generiert werden, und jedes Intervall wird sofort sortiert, abgeschnitten und dem entsprechenden Speichersegment hinzugefügt.



Abbildung 2: Die Intervalle von Polygon A aus Abbildung 1 werden in Intervallen von Polygon B sortiert und abgeschnitten, während sich Polygon A entlang der Z-Achse in einem konstanten Abstand von 100 und Polygon B entlang der Z-Achse in einem konstanten Abstand von 50 befindet (Polygon B befindet sich näher an der Kamera )

Beim Sortieren von Kanten werden diese Kanten in Speichersegmenten gespeichert, die nach x verknüpften Listen entsprechend ihrer anfänglichen Rasterzeile sortiert sind. Jedes Polygon ist wiederum in Kanten unterteilt, wodurch zusammen eine Liste aller Kanten in der Szene erstellt wird. Wenn alle Kanten aller Polygone in der Sichtbarkeitspyramide zur Kantenliste hinzugefügt werden, wird die gesamte Liste in einem Durchgang von oben nach unten von links nach rechts gescannt. Eine Liste der aktiven Kantenlisten (AEL) wird gespeichert. Bei jedem Schritt zu einer neuen Rasterlinie werden die Kanten, die auf dieser Rasterlinie angezeigt werden, aus dem AEL entfernt, die aktiven Kanten werden zu ihren neuen x-Koordinaten verschoben, die Kanten ab der neuen Rasterlinie werden zum AEL hinzugefügt und die Kanten werden nach der aktuellen x-Koordinate sortiert.

Für jede Rasterzeile wird eine nach z sortierte aktive Polygonliste (APL) gespeichert. Es geht in der Reihenfolge sortiert nach x AEL. Beim Treffen mit jeder neuen Kante (dh wenn jedes Polygon beginnt oder endet, wenn es sich von links nach rechts bewegt) wird das ihm zugeordnete Polygon aktiviert und in APL sortiert (im Fall einer Startkante), wie in Abbildung 3 gezeigt, oder deaktiviert und aus APL gelöscht ( im Fall einer Hinterkante), wie in Abbildung 4 gezeigt. Wenn sich das nächstgelegene Polygon geändert hat (dh das nächste ist ein neues Polygon oder das nächstgelegene Polygon ist zu Ende), wird für das gerade nicht mehr am nächsten liegende Polygon ein Intervall ab dem Punkt erstellt, an dem sich das Polygon befindet vym, weil es die am nächsten und enden x-Koordinate der aktuellen Kanten und die aktuellen x-Koordinate in der Deponie aufgenommen, die jetzt in der Nähe. Diese gespeicherte Koordinate wird später als Beginn des Intervalls verwendet, das erstellt wird, wenn das neue nächste Polygon nicht mehr vorne liegt.



Abbildung 3: Polygonaktivierung, wenn eine Startkante in AEL erkannt wird.



Abbildung 4: Deaktivierung des Polygons, wenn in AEL eine Hinterkante erkannt wird.

Machen Sie sich keine Sorgen, wenn Sie die oben genannten Punkte nicht vollständig verstehen. Dies ist nur eine kurze Übersicht über das Sortieren von Kanten, damit der Rest der Spalte klarer wird. Eine ausführliche Erklärung finden Sie in der nächsten Spalte.

Die durch Sortieren von Kanten erzeugten Intervalle scheinen genau die gleichen Intervalle zu sein, die sich aus dem Sortieren der Intervalle ergeben würden. Der Unterschied liegt in den Zwischendatenstrukturen, die zum Sortieren der Intervalle in der Szene verwendet werden. Beim Sortieren von Kanten werden die Intervalle innerhalb der Kanten gespeichert, bis der endgültige Satz sichtbarer Intervalle generiert wird. Daher wird das Sortieren, Trimmen und Erstellen von Intervallen durchgeführt, wenn jede Kante ein Polygon hinzufügt oder entfernt, basierend auf dem Status des durch die Kante definierten Intervalls und des Satzes aktiver Polygone. Beim Sortieren von Intervallen werden die Intervalle sofort sichtbar, wenn jedes Polygon gerastert wird, und diese Zwischenintervalle werden dann sortiert und relativ zu den Intervallen in der Rasterlinie abgeschnitten, um die endgültigen Intervalle zu erstellen. Daher werden die Zustände der Intervalle ständig explizit festgelegt, und alle Arbeiten werden direkt in Intervallen ausgeführt.

Sowohl die Intervallsortierung als auch die Kantensortierung funktionieren gut und wurden erfolgreich in kommerziellen Projekten eingesetzt. Für Quake haben wir uns für die Kantensortierung entschieden, auch weil sie effizienter zu sein scheint und eine hervorragende horizontale Konnektivität aufweist, die die minimale Sortierzeit bietet, im Gegensatz zu der möglicherweise kostspieligen Sortierung in verknüpfte Listen, die beim Sortieren von Intervallen erforderlich sein kann.Ein wichtigerer Grund war jedoch, dass wir beim Sortieren von Kanten die Kanten zwischen benachbarten Polygonen aufteilen können. Dies reduziert das Sortieren, Trimmen und Rastern von Kanten um etwa die Hälfte und reduziert auch die Weltdatenbank erheblich, da die Kanten häufig werden.

Der letzte Vorteil beim Sortieren von Kanten besteht darin, dass nicht zwischen konvexen und konkaven Polygonen unterschieden wird. Für die meisten Grafik-Engines ist dies kein sehr wichtiger Aspekt, aber bei Quake ist das Trimmen, Transformieren, Projizieren und Sortieren von Kanten zum Hauptengpass geworden. Daher tun wir alles, um die Anzahl der Polygone und Kanten zu verringern, und konkave Polygone sind in dieser Hinsicht sehr hilfreich. Konkave Polygone können zwar auch durch Sortierintervalle verarbeitet werden, dies führt jedoch zu einer erheblichen Leistungsminderung.

Es gibt jedoch keine endgültige Antwort auf den besten Ansatz. Am Ende erfüllen Sortierintervalle und Sortierkanten eine Funktion, und die Auswahl zwischen ihnen ist eine Frage der Benutzerfreundlichkeit. In der nächsten Spalte werde ich mehr über das Sortieren von Kanten mit ihrer vollständigen Implementierung sprechen. Im Rest dieser Spalte werde ich den Grundstein für die nächste legen, indem ich über die Sortierschlüssel und die Berechnung von 1 / z spreche. Dabei werde ich einige Verweise auf die Aspekte des Sortierens von Kanten machen, die noch nicht im Detail besprochen wurden. Ich entschuldige mich, aber das ist unvermeidlich und alles wird erst am Ende der nächsten Spalte klar.

Rippensortiertasten


Nachdem wir nun wissen, dass wir die Sortierung der Kanten auswählen und daraus die Intervalle der Polygone erstellen, die dem Betrachter am nächsten liegen, stellt sich die Frage: Woher wissen Sie, ob diese Polygone am nächsten sind? Im Idealfall speichern wir einfach den Sortierschlüssel jedes Polygons. Wenn eine neue Kante angezeigt wird, vergleichen wir den Schlüssel seiner Oberfläche mit den Schlüsseln anderer aktiver aktiver Polygone, um leicht zu bestimmen, welches der Polygone am nächsten liegt.

Das klingt zu gut, ist aber möglich. Wenn Ihre Weltdatenbank beispielsweise als BSP-Baum gespeichert ist und alle Polygone in BSP-Blätter abgeschnitten sind, ist die BSP-Durchquerungsreihenfolge die richtige Renderreihenfolge. Wenn Sie beispielsweise BSP von vorne nach hinten umgehen und jedem Polygon bei Erreichen einen inkrementell größeren Schlüsselwert zuweisen, werden Polygone mit höheren Schlüsselwerten garantiert vor Polygonen mit kleineren Schlüsseln angezeigt. Dieser Ansatz wird in Quake seit einiger Zeit verwendet, aber jetzt wird aus Gründen, die ich kurz erläutern werde, eine andere Lösung angewendet.

Wenn Sie kein BSP oder eine ähnliche Datenstruktur haben oder wenn Sie viele sich bewegende Polygone haben (BSP verarbeitet sich bewegende Polygone nicht sehr effizient), besteht eine andere Möglichkeit, Ziele zu erreichen, darin, alle Polygone relativ zueinander zu sortieren, bevor Sie die Szene rendern und die entsprechenden Schlüssel entsprechend ihrer räumlichen Zuordnung zuweisen Beziehungen im Ansichtsfenster. Leider ist dies im allgemeinen Fall eine extrem langsame Aufgabe, da jedes Polygon miteinander verglichen werden muss. Es gibt Techniken zur Verbesserung der Leistung beim Sortieren von Polygonen, aber ich kenne niemanden, der das allgemeine Sortieren von Polygonen auf einem PC in Echtzeit durchführen würde.

Eine Alternative besteht darin, im Bildschirmbereich nach dem Abstand z vom Betrachter zu sortieren. Diese Lösung passt gut zur überlegenen räumlichen Konnektivität von Sortierkanten. Wenn Sie sich mit jeder neuen Kante auf der Rasterlinie treffen, können Sie den Abstand z des entsprechenden Polygons berechnen und mit den Abständen anderer Polygone vergleichen. Danach kann das Polygon in APL gespeichert werden.

Das Erhalten von Abständen entlang z kann jedoch eine schwierige Aufgabe sein. Vergessen Sie nicht, dass wir in der Lage sein müssen, z an einem beliebigen Punkt des Polygons zu berechnen, da eine Kante auftreten und das Polygon in der APL an einer beliebigen Stelle auf dem Bildschirm sortieren kann. Wir können z direkt aus den Bildschirmkoordinaten x und y und den Gleichungen der Ebene des Polygons berechnen, aber dies kann leider nicht sehr schnell erfolgen, da sich z für die Ebene im Bildschirmraum nicht linear ändert. 1 / z variiert jedoch linear, daher verwenden wir diesen Wert. (Eine Diskussion der Linearität im Bildschirmbereich und der Verläufe für 1 / z finden Sie in Chris Heckers Serie über Textur-Mapping im Game Developer- Magazin des letzten Jahres.) Ein weiterer Vorteil der Verwendung von 1 / z besteht darin, dass die Auflösung mit abnehmendem Abstand zunimmt, dh mit 1 / z haben wir immer die beste Tiefenauflösung für nahe Objekte, die am wichtigsten sind.

Der naheliegende Weg, um den 1 / z-Wert an einem beliebigen Punkt im Polygon zu erhalten, besteht darin, 1 / z an den Eckpunkten zu berechnen, sie über beide Kanten des Polygons zu interpolieren und zwischen den Kanten zu interpolieren, um den Wert am gewünschten Punkt zu erhalten. Leider erfordert dies viel Arbeit entlang jeder Rippe; Schlimmer noch, dies erfordert eine Division, um den 1 / z-Schritt pro Pixel in jedem Intervall zu berechnen.

Es wäre besser, 1 / z direkt aus der Gleichung der Ebene und dem Bildschirm x und y des für uns interessanten Pixels zu berechnen. Die Gleichung hat die folgende Form:

1/z=(a/d)x′−(b/d)y′+c/d


Dabei ist z die Koordinate im Ansichtsfenster z des Punkts auf der Ebene, der in die Bildschirmkoordinaten (x ', y') projiziert wird (der Ursprung der Koordinaten für diese Berechnungen ist das Projektionszentrum, der Punkt auf dem Bildschirm direkt vor dem Ansichtspunkt), [abc] normal zur Ebene im Ansichtsfenster, und d ist der Abstand vom Ursprung des Ansichtsfensters zur Ebene entlang der Normalen. Die Division wird für jede Ebene nur einmal durchgeführt, da a, b, c und d Konstanten für Ebenen sind.

Eine vollständige 1 / z-Berechnung erfordert zwei Multiplikationen und zwei Additionen, und jede Operation muss mit einem Gleitkomma ausgeführt werden, um Bereichsfehler zu vermeiden. Ein solches Volumen an Gleitkommaberechnungen scheint teuer zu sein, aber tatsächlich ist es insbesondere bei Pentium-Prozessoren nicht so, dass der Wert der 1 / z-Ebene an jedem Punkt in Assemblersprache in nur sechs Zyklen berechnet werden kann.

Wenn Sie interessiert sind, finden Sie hier eine schnelle Ableitung der 1 / z-Gleichung. Die Ebenengleichung für die Ebene hat die folgende Form:

ax+by+cz−d=0


wobei x und y die Koordinaten des Ansichtsraums sind, sind a, b, c, d und z oben definiert. Wenn wir die Substitution machen

Source: https://habr.com/ru/post/de439830/

More articles:


All Articles