HSR: Hidden Surface Removal

14. November 2002 / von aths / Seite 1 von 5

   Einleitung

Der Begriff "Hidden Surface Removal" (im Kontext sinngemäß "verdeckte Flächen unsichtbar halten"), abgekürzt mit HSR, wird für vielfältige Methoden gebraucht. Jede 3D-Grafikkarte und so gut wie jede 3D-Engine hat HSR-Mechanismen. Diese unterscheiden sich jedoch erheblich. Wir möchten in diesem Artikel wesentliche HSR-Techniken vorstellen.

Zunächst sollen die Hardware-Methoden beleuchtet werden, und dann hinterfragen wir, was die Software tun kann. In beiden Fällen werden auch gängige Optimierungs-Möglichkeiten besprochen, denn natürlich wird die 3D-Grafik schneller, wenn die ohnehin nicht sichtbaren Flächen gar nicht erst bearbeitet werden müssen, so dass bislang eine Menge "Forschung und Entwicklung" in dieser Richtung betrieben wurde. Uns geht es in diesem Artikel nicht um die graue Theorie, was man alles machen könnte, sondern um konkrete Realisierungen, wie man sie heute vorfindet.

   HSR in Hardware

Man stelle sich folgendes 3D-Szenario vor: In einem Raum befindet sich ein Gummibaum. Es muss gewährleistet sein, dass der Gummibaum an den entsprechenden Stellen die Raumwand überdeckt, und zwar unabhängig von der Renderreihenfolge. Jede 3D-Hardware hat das HSR-Feature, denn ansonsten könnten eigentlich verdeckte Flächen ja sichtbar sein. Das Problem besteht darin, dass man Kenntnis von allen Dreiecken braucht, bevor man weiß, welche Stellen von welchen Objekten im Bild verdeckt sind.

Fast alle Grafikkarten rendern aber einfach Dreieck für Dreieck. Von den bereits gerenderten Dreiecken ist die Lage unbekannt, und über zukünftige Dreiecke kann natürlich erst recht keine Aussage getroffen werden. Die Lösung besteht darin, neben dem Backbuffer (in dem das Bild während des Aufbaus gespeichert wird) noch einen Z-Buffer zu nutzen. Hier wird für jedes Pixel gespeichert, wie weit es von der Bildschirm-Projektionsfläche bzw. vom Betrachter entfernt ist (bei letzterem spricht man auch vom W-Buffer). Der Z-Wert gibt also an, wie "tief" der Pixel sich "hinter" dem Bildschirm befindet.

Wird das Dreieck in Zeilen zerlegt und dann Zeile für Zeile pixelweise gerendert, findet für jedes Dreiecks-Pixel ein Z-Test statt. Liegt auf aktueller Position schon ein Pixel "näher" am Bildschirm als das neue, wird das gerenderte Dreiecks-Pixel nicht in den Backbuffer geschrieben, sondern verworfen. Ansonsten wird es in den Backbuffer "gemalt", und der für dieses Pixel gültige Z-Wert in den Z-Buffer geschrieben, womit dann das vorherige Pixel überdeckt wird.

Diese Technik war jahrelang üblich. 3dfx adaptierte dieses von SGI-Renderen bekannte Prinzip für die ersten weit verbreiteten 3D-Zusatzkarten. Seit einiger Zeit gibt es aber Verfahren, die effizienter arbeiten. Die originale Radeon führte "HyperZ" ein. Darunter ist zu verstehen, dass der Z-Buffer in kleine Kacheln zerlegt wird. Für die Speicherzugriffe eine "Kachelung" des Bildes vorzunehmen ist seit der Voodoo1 ein gängiges Prinzip, da Blockzugriffe wesentlich effizienter als die Übertragung einzelner Werte ist. Wenn in diesem Artikel von Kacheln gesprochen wird, sind damit aber ausgefeiltere Techniken gemeint.

Bei der Radeon wird für jede Kachel der größte und der kleinste darin vorkommende Z-Wert in einem extra Buffer gespeichert. Damit lässt sich in jeder Kachel sehr schnell entscheiden, ob ein Pixel "garantiert sichtbar", "garantiert nicht sichtbar" oder "vielleicht sichtbar" ist. Denn wenn der Z-Wert des aktuellen Pixels vor dem kleinsten Z-Wert der Gesamt-Kachel liegt, ist der Pixel auf den Fall sichtbar, wenn er größer als der größte Wert der Kachel ist, garantiert verdeckt.

Er kann natürlich auch irgendwo dazwischen liegen. Nur für den diesen Fall muss dann noch ein "richtiger" Z-Test gemacht werden. Bei garantierter Sichtbarkeit ist natürlich weiterhin ein abschließender Z-Buffer-Schreibzugriff nötig, um die Position des neuen Pixels zu vermerken. Mit HyperZ benötigt die HSR-Technik "Z-Buffering" aber weniger Bandbreite - kritische Größe aller gängigen 3D-Karten - als ohne, was dieses Standard-Feature beschleunigt. Natürlich sind dafür zusätzliche Logikgatter im Chip erforderlich, doch der Performance-Gewinn rechtfertigt den höheren Aufwand allemal. Zusätzlich findet eine Komprimierung des Z-Wertes statt, was wiederum Bandbreiten-freundlich ist.

Ein kurzes Abschweifen zur Z-Komprimierung: Statt 24 Bit Z einen 16 Bit Z-Wert zu nehmen, könnte auch als verlustbehaftete Komprimierung angesehen werden. Doch damit ist letztlich nichts gewonnen, da die eingesparte Bandbreite mit erhöhter Ungenauigkeit erkauft wurde. Die Komprimierung muss also verlustfrei stattfinden.

Alle verlustfreien Komprimierungs-Algorithmen beruhen darauf, dass sich im Datenstrom bestimmte Muster wiederholen. Ein so genanntes "weißes Bitrauschen", was bedeutet, dass 0 und 1 völlig zufällig auftreten, ist prinzipiell nicht komprimierbar. Zwar sorgt der Zufall dafür, dass sich dann noch mal kleine Muster wiederholen, doch um das zu vermerken, wird mehr Speicherplatz benötigt, als man durch die Komprimierung gewinnt. Z-Komprimierung ist also darauf angewiesen, dass die Bitfolgen möglichst wenig zufällig sind, mehr dazu gleich.

Ein zusätzliches Problem besteht darin, dass ein einzelner Z-Wert relativ wenig Bits umfasst, was das Auftreten gleicher Muster nicht gerade wahrscheinlicher macht. Oftmal ist von einer 4:1-Komprimierung die Rede. Inklusive Stencil ist der Z-Wert üblicherweise 32 Bit lang und wäre 4:1-komrimiert auf nur 8 Bit geschrumpft. Natürlich lassen sich 2^32 Werte nicht eindeutig auf 2^8 Werte abbilden.

Deshalb werden nicht einzelne Z-Werte komprimiert, sondern praktischerweise immer gleich ganze Kacheln. Ein Problem bleibt aber - es ist keineswegs zu garantieren, dass sich genügend Muster im Bitstrom wiederholen, dass eine verlustfreie 4:1-Komprimierung immer möglich ist. Da Verluste auszuschließen sind, muss man die Kompressionsrate anpassen, weshalb höchstens von einer Komprimierung von bis zu 4:1 gesprochen werden kann.