In dem folgenden Artikel möchten wir ein wenig näher auf das sogenannte „Quake Hidden Surface Removal“ eingehen.

Einstieg Quake Hidden Surface Removal

Bewegen von Objekten und Z-Buffer.

Wir beginnen zunächst mit ein paar Bemerkungen zu den Problemen beim Umgang mit beweglichen Objekten (Billboards/Sprites, BSP-Modelle wie Türen, Items, Polygonmodelle) mit einem BSP. Das BSP stellt alle Polygone der statitischen Welt in einer perfekt sortierten Reihenfolge zur Verfügung. Diese könnten verwendet werden, um den Z-Buffer zu füllen (Speichern eines separaten Z-Buffers löschen). Die Leistungsauswirkungen für diesen Durchgang können etwa 10 Prozent betragen. Beachten Sie, dass dieser Durchgang getrennt von der eigentlichen Texturabbildung der betreffenden Polygone durchgeführt werden muss (was auch eine Z-Berechnung pro Pixel für eine perspektivisch korrekte Texturabbildung beinhaltet), da es bei i586-Prozessoren keine Register gibt.

Der Z-Buffer wird tatsächlich für Billboards (Sprites), Polygonmodelle (deren Dreiecke sich möglicherweise schneiden könnten) und Spezialeffekte verwendet, die später (sobald der Z-Buffer bereits drin war) wie Partikel eingeführt wurden. BSP-Modelle werden unterschiedlich beghandelt. Die Auswirkungen auf die Z-Lese-, Vergleichs- und Schreibleistung variieren stark und liegen im Durchschnitt bei etwa 10 Prozent.

Schließlich ist der Speicherbedarf etwa 128K für 320×200. Dementsprechend verwendet die gleiche 16bit Z-Buffer-Tiefe 1,3 Mb mit den 960×720 Modi, die wir gelegentlich mit Linux/Xfree86 verwenden. Das klingt nach viel, aber das Spiel benötigt ohnehin 8 Mb und der Oberflächen-Cache wird wahrscheinlich viel mehr verwenden, wenn dieser nur verfügbar ist.

Level-Performance und sortierte Spans.

Der Back-to-Front-Ansatz zur Darstellung der statischen Welt, den John Cormack mit dem PVS ausprobierte, lieferte aufgrund der unterschiedlichen Überziehung keine gleichwertige Leistung. Es wird zum größten Teil davon ausgegangen, dass Back-to-Front-Rendering mit dem Painter`s Algorithmus ohnehin kein nützlicher Ansatz für skalierbare, dicht verschlossene Umgebungen ist. So wurde z.B. auch ein beam-tree ähnlicher Ansatz in Betracht gezogen, aber auch schnell wieder verworfen, weil dieser bereits zur Bestimmung der sichtbaren Fläche ausprobiert wurde. Die Performance war insgesamt gesehen nicht zuverlässig und zudem gab es ein Overhead-Problem.

In der Folge unterschieden sie sich, die HSR-Aufgabe auf Span- statt auf Polygonebene zu lösen. Dieser skizziert die bsische Idee von sortierten Spans und diskutiert zwei Alternativen:

  • Edge-Sortierung,
  • Span-Sortierung.

Von Letzteren ist eher wenig im Gedächtnis geblieben und deshalb verzichten wir hier darauf, eine Erklärung dafür zu liefern.

Es gibt keine schlüssige Antwort darauf, welche Technik bevorzugt werden sollte. Bei Quake entschied man sich für die Edge-sortierenden Rasterizer mit einigen Vorteilen:

  • horizontale Kohärenz für eine schnelle Sortierung,
  • Edges (Kanten) können zwischen benachbarten Polygonen geteilt werden,
  • konkave Polygone sind möglich.

Grundlagen zur Edge-Sortierung.

Der Rest des Artikels behandelt einige Details. Es wird erklärt, dass die Verwendung von 1/z statt z als Sorting Key verschiedene Vorteile hat:

  • 1/z ist linear im Screen Space,
  • Erhöhung der Auflösung bei abnehmenden Abstand.

Wir verweisen Sie auf Chris Heckers Serie über Texture-Mapping im Game Developer`s Magazine in Bezug auf das Verhalten von Z-Gradienten in verschiedenen Räumen. Die Alternative, auf die Hecker eingeht, besteht darin, die Reihenfolge der BSP-Traversal zur Schlüsselvergabe zu verwenden. Sie taten dies tatsächlich mit Quake, benutzten aber zum Zeitpunkt des Artikels 1/z Schlüssel. Die Entscheidung ist durchaus in den letzten Tagen vor dem Versand getroffen worden. Der Nachteil von BSP-basierten Schlüsseln besteht darin, dass bewegliche BSP-Objekte durch World-BSP-Ebenen aufgeteilt werden müssen, was die Anzahl der Polygone erhöht. Bei der 1/z-Sortierung ist es nicht notwendig, BSP-Modellpolygone zu splitten. Darüber hinaus löst die 1/z-Taste das Zusammenführen der BSP-Modellzeichnungsreihenfolge in der weltweiten BSP-Zeichnungsreihenfolge (die sich idealerweise in das Zusammenführen zweier bereits sortierter Listen, Methinks, aufgliedert).

Abschließend wird erklärt, wie man auf effiziente Weise einen 1/z-Wert und einen beliebigen Punkt auf dem Polygon erhält, indem dieser eine Ebenengleichung in Bezug auf den View Space z und den Screen Space x,y verwendet und gibt die ungefähren Kosten auf einem Pentium als etwa sechs Zyklen an.

Das Handling von BSP-Modellen.

Wie bereits erwähnt, werden die BSP-Modelle nicht mit einem Z-Buffer read/compare gerendert. BSP-Objekte bieten daher eine Überziehungsreduktion – Türen blockieren vor allem jede Oberfläche dahinter um Edge-sortierten Raster. Folglich müssen BSP-Modelle gegen World-Polygone abgeschnitten werden, um Interpenetrationen zu vermeiden.

Dies ist für Polygon-Modelle, Billboards und Partikel nicht erforderlich, da z-compares Schnittmengen berücksichtigen. Dies wird an befahrbaren Laya-/Wasseroberflächen deutlich.

Wir hoffen, dass wir Ihnen einen ersten kleinen Überblick über die Thematik bieten konnten. Wenn Sie noch Fragen oder Anregungen haben sollten, hinterlassen Sie uns unten einen Kommentar.

Vielen Dank für Ihren Besuch.