Nach dem letzten Artikel standen zwei Leserwunschthemen im Raum, die beantwortet werden wollten. Die Fragen waren, wie sich zum einen feststellen lässt, wann sich ein Dreieck eines zu zeichnenden Objektes (komplett) hinter einem anderen befindet und daher nicht gezeichnet werden muss, und wie zum anderen sich überlappende Dreiecke (ich vermute, mit “Flächen” waren Dreiecke gemeint) effizient gezeichnet werden können. In dem heutigen Artikel soll es um die erste Frage gehen, angereichert um einige zusätzliche Informationen.
Beim Zeichnen von Dreiecken (Polygonen – wir erinnern uns) in Echtzeit (das heißt in einer Geschwindigkeit, die genügend Bilder pro Sekunde erlaubt, um dem Betrachter ein flüssiges Bild zu suggerieren, etwa in Computerspielen) kommt es natürlich vor allem auf die Geschwindigkeit an, mit der eine Szene gezeichnet werden soll; dies geht umso schneller, je weniger Dreiecke gezeichnet werden müssen, insbesondere, da die Dreiecke ja mit Farbinformationen gefüllt werden müssen, um einen hohen Detailgrad bei der Darstellung zu simulieren. Das kollidiert allerdings mit der Anforderung, möglichst viele Details in der Szene unterzubringen, um ein realistischeres Bild zu erzeugen; mehr Details erfordern im Allgemeinen auch mehr Dreiecke. Um diese beiden Anforderungen wenigstens halbwegs vereinen zu können, ist es wichtig, die weniger bis nicht relevanten Dreiecke zu identifizieren und zu entfernen (wobei die Identifizierung natürlich nicht mehr Zeit beanspruchen darf als das eigentliche Zeichnen). Hier kommen mehrere Verfahren zum Einsatz; die beiden wichtigsten dürften das LOD-Verfahren und das Culling sein.
Beim LOD-Verfahren – LOD steht für Level Of Detail – werden Objekte in verschiedenen Auflösungen (das heißt, mit einer unterschiedlichen Anzahl an Dreiecken) erstellt; je weiter sich ein Objekt vom Punkt des Betrachters (der Kamera) entfernt befindet, desto weniger Details sind sichtbar und desto weniger Dreiecke sind benötigt, um das Objekt noch realistisch darzustellen. Weiter entfernte Objekte werden demzufolge mit einem Modell einer niedrigeren Auflösung gezeichnet; so kann die Anzahl der zu zeichnenden Polygone in der Szene schon drastisch reduziert werden.
Für die eigentliche Frage nach der Verdeckung von Dreiecken ist jedoch das zweite Verfahren, das Culling, interessant. Der Name des Verfahrens leitet sich vom englischen Begriff cull ab, was so viel wie aussondern bedeutet – und genau darum geht es bei dem Verfahren. Konkret hat das Culling zum Ziel, diejenigen Dreiecke in der zu zeichnenden Szene, die nicht sichtbar sind und daher nicht gezeichnet werden müssen, zu identifizieren und auszusondern. Eigentlich wird mit Culling auch nicht ein einzelnes Verfahren beschrieben, sondern eine ganze Sammlung von Methoden zur Reduzierung der Anzahl zu zeichnender Objekte in der Szene. Im Folgenden wollen wir einige der Verfahren durchgehen und dabei (hoffentlich) auch die Leserfrage beantworten.
Das zweifellos wichtigste Culling-Verfahren ist das Frustum-Culling. Beim Zeichnen einer Szene ist die meiste Zeit über nur eine kleine Menge an Objekten sichtbar; die restlichen befinden sich entweder hinter dem Betrachter, seitlich außerhalb seines Blinkwinkels oder so weit entfernt, dass sie ohnehin nicht sichtbar sind. Diese Grenzen des Sichtfeldes bilden einen Pyramidenstumpf, englisch Frustum – daher der Name. Das kleine Ende des Pyramidenstumpfes, die Near Clipping Plane, ist gewissermaßen die Ebene des Betrachters; alles dahinter befindet sich hinter dem Betrachter. Das große Ende des Pyramidenstumpfes, die Far Clipping Plane, ist die Ebene, hinter welcher Objekte so weit entfernt sind, dass sie nicht mehr gezeichnet werden müssen. Die Seiten des Pyramidenstumpfes repräsentieren die Grenzen des Sichtfeldes (da wir alle keinen Tunnelblick haben, sondern unser Gesichtsfeld in einem bestimmten Winkel nach außen geht, werden auch Bilder am Computer entsprechend gezeichnet). In der 3D-Grafik wird die Near Clipping Plane in der Regel nicht direkt auf die Position des Betrachters gesetzt, sondern ein wenig davor, um unschöne Effekte (etwa, dass die Spielfigur in einem Computerspiel in anderen Objekte hineinschauen kann) zu vermeiden; das sieht dann ungefähr so aus (der Stern ist der Betrachter):
Alle Dreiecke, die sich außerhalb des Frustums befinden, müssen nicht gezeichnet werden, da sie ohnehin nicht sichtbar sind. Damit nicht für sämtliche Polygone einer Szene einzeln geprüft werden muss, ob sie sich innerhalb des Sichtfeldes befinden, werden nach Möglichkeit gleich ganze Objekte ausgefiltert. Sind die Objekte einfache geometrische Figuren wie etwa Quader oder Kugeln, ist der Test auch schnell gemacht (die mathematischen Details erspare ich den Lesern an dieser Stelle einmal). Um aber auch für komplexe Objekte schnell prüfen zu können, ob sie innerhalb des Frustums liegen, wird ein weiteres Verfahren, die Verwendung sog. Hüllobjekte oder Bounding Volumes, eingesetzt. Ein Bounding Volume ist eine einfache geometrische Figur (meist ein Quader oder eine Kugel), deren Ausmaße und Ausrichtung so gewählt wird, dass sie das zu untersuchende Objekt möglichst eng umschließt. Am Beispiel der weit verbreiteten Utah-Teekanne sieht ein Hüllobjekt (in diesem Fall eine Bounding Box) folgendermaßen aus:
Diese geometrische Repräsentation des Objektes kann nun einfach gegen das Frustum geprüft werden; liegt das Hüllobjekt komplett außerhalb oder innerhalb des Sichtfeldes, gilt dies auch für das eigentliche Objekt. Ein Sonderfall tritt ein, wenn ein Objekt auf einer der Kanten des Frustums liegt, also nur teilweise sichtbar ist. Dieser Fall kann auf drei Arten berücksichtigt werden; entweder wird ein derartiges Objekt als “außerhalb” klassifiziert und verworfen – was aber zu dem unschönen Effekt führt, dass Objekte am Rand des Sichtfeldes plötzlich auftauchen und verschwinden (diese Art der Behandlung ist heutzutage nicht mehr üblich, kann aber teilweise bei einigen Spielen der frühen 3D-Ära beobachtet werden). Alternativ kann ein derartiges Objekt auch als “sichtbar” eingestuft und komplett gezeichnet werden, wobei die überstehenden Dreiecke zwar berechnet, die Farbinformationen durch die Grafikkarte aber verworfen werden; bei kleinen Objekten ist das auch kein Problem, bei sehr großen Objekten führt das aber dazu, dass sehr viele Dreiecke umsonst bearbeitet werden müssen. Aus diesem Grund wird heutzutage in der Regel Methode 3 angewandt: hierbei wird bestimmt, welche Polygone des Objektes innerhalb und welche außerhalb des Frustums liegen; die außerhalb liegenden werden verworfen, die innerhalb liegenden gezeichnet (wobei Dreiecke, die eine der Frustum-Ebenen schneiden, ebenso wiederum verworfen, immer gezeichnet oder beschnitten werden können). Dieser Vorgang wird als Clipping bezeichnet, daher auch die Bezeichnungen Near Clipping Plane und Far Clipping Plane. Schauen wir von oben auf eine (aus Sicht der Kamera) zu zeichnende Szene, so könnte sich etwa das folgende Bild ergeben (oben die Szene vor dem Clipping, unten danach; nur die übrigbleibenden farbigen Teile werden gezeichnet):
Durch das Frustum Culling und Clipping wurde die Anzahl der zu zeichnenden Polygone schon massiv reduziert; dennoch reicht das nicht, um selbst auf moderner Hardware Szenen mit einem hohen Detaillierungsgrad zu zeichnen; wir brauchen also Verfahren, um noch mehr Dreiecke zu zeichnen.
Eine Beobachtung aus der realen Welt hilft hier, weitere Polygone auszufiltern: normalerweise sieht man von Objekten nur die Vorderseiten; die Rückseiten sind nicht sichtbar (abgesehen von transparenten Objekten; die lassen wir hier einmal außen vor). Da ein Mesh, also eine Sammlung von Polygonen, in der Regel ein geschlossenes Objekt ist (das heißt, jedes Dreieck an allen drei Kanten ein weiteres Dreieck berührt), wissen wir, dass auch in der Szene die Dreiecke der Rückseite eines Objektes niemals sichtbar sind (mit Rückseite ist die vom Betrachter abgewandte Seite eines Objektes gemeint). Wenn wir diese ausfiltern könnten, hätten wir wieder eine große Menge an Polygonen zum Zeichnen (im Schnitt wohl die Hälfte) eingespart.
An dieser Stelle greift das Verfahren des Backface Culling. Wie es der Name schon andeutet, werden hierbei sämtliche Dreiecke entfernt, die auf der Rückseite eines Objektes liegen. Ein einfacher mathematischer Kniff hilft, diese Polygone zu identifizieren. Jedes Dreieck besitzt einen Normalenvektor, also einen Vektor, der genau senkrecht zur Dreiecksfläche orientiert ist und, entsprechend der Konvention, in die gleiche Richtung wie die Vorderseite zeigt (der Normalenvektor lässt sich übrigens durch die Reihenfolge der Dreieckspunkte bestimmen, da die drei Punkte eines Polygons reichen, um den Normalenvektor zu beschreiben). Zusätzlich ist ja die Blickrichtung des Betrachters, ebenfalls ein Vektor, bekannt. Nun der Kniff: zeigen Normalenvektor und Blickrichtung grob in die gleiche Richtung (sprich, ist der Winkel zwischen den beiden Vektoren nicht größer als 90°), so schauen wir auf die Rückseite des entsprechenden Dreiecks und es kann verworfen werden; ist der Winkel zwischen Dreiecksnormale und Blickrichtung dagegen größer als 90°, sehen wir die Vorderseite. Es muss also nur für jedes Dreieck bestimmt werden, wohin sein Normalenvektor zeigt, damit bestimmt werden kann, ob es relevant ist oder nicht (wer an den mathematischen Details des Verfahrens interessiert ist, kann sie hier nachlesen). Von oben betrachtet könnte das so aussehen (die dickeren Striche repräsentieren von oben gesehene Dreiecke, die beiden grünen sind sichtbar, die beiden roten nicht):
Aber selbst das Backface Culling ist noch nicht ausreichend, um in wirklich komplexen Szenen genügend Polygone auszufiltern, um eine flüssige Darstellung zu erlauben. Zum Glück gibt es noch ein paar weitere Dreiecke, die ausgefiltert werden können. Rekapitulieren wir: bisher haben wir alle Objekte außerhalb des Sichtfeldes aussortiert, sowie die Dreiecke der Rückseiten von Objekten. In einer komplexen Szene passiert es aber auch, dass Objekte auch durch andere Objekte verdeckt werden und daher nicht gezeichnet werden müssen. Die Identifizierung und Aussortierung derartiger Objekte wird als Occlusion Culling (von engl. “occlusion”, Verdeckung) bezeichnet.
Hier gibt es nun viele verschiedene Ansätze, die alle ihre ganz eigenen Vor- und Nachteile haben. Grundsätzlich unterschieden werden muss dabei zwischen Verfahren, die auf statischen Informationen beruhen, also aus den unbeweglichen Objekte einer Szene vor der eigentlichen Verdeckungsberechnung ein Sichtbarkeitsmodell erstellen, und Verfahren, die den Verdeckungstest mit Hilfe dynamischer Informationen durchführen. Erstere benötigen mehr Speicherplatz und benötigen statische, also unbewegliche Objekte, benötigen dafür zur Laufzeit weniger Rechenzeit; letztere kommen ohne die Anforderungen aus, benötigen dafür aber in der Regel auch etwas mehr Rechenzeit.
Ein weit verbreitetes statisches Occlusion Culling-Verfahren ist das Portal Rendering. Dieses Verfahren ist vor allem in Szenen mit vielen statischen, großen Objekten (z.B. Wände) geeignet, die große Teile der Szene verdecken, also insbesondere Szenen im Inneren von Gebäuden o.ä. (sog. Indoor Scenes). Beim Portal Rendering wird die Szene in Räume (oder Zellen) unterteilt, die durch Portale (zum Beispiel Türen oder Fenster) miteinander verbunden sind (die Definition der Räume und Portale erfolgt hierbei durch den Modellierer der Szene). Der Gedanke ist nun, dass für einen Betrachter in einem Raum zuerst einmal der Raum selber mit all seinen Objekten gezeichnet wird. Anschließend kann geprüft werden, ob sich im Sichtfeld des Betrachters ein Portal befindet; ist das der Fall, so muss auch der Raum hinter dem Portal gezeichnet werden. Der Clou dabei ist, dass natürlich nicht der gesamte Raum gezeichnet werden muss, sondern nur der Abschnitt, der durch das Portal sichtbar ist; das wird nun aber in der Regel ein Pyramidenstumpf sein (siehe Abbildung unten), und richtig: den Begriff kennen wir schon vom Frustum Culling. Dieses Verfahren erlaubt uns, die relevanten Objekte innerhalb des Frustums zu identifizieren; befindet sich hier ein weiteres Portal, so wird auch der Raum dahinter gezeichnet und so weiter. Bildlich lässt sich das sehr schön darstellen (die grünen Objekte sind vollständig sichtbar, die blauen zum Teil, die roten nicht; die grauen Bereiche stellen die Sichtfelder ausgehend von den Portalen dar):
Das Problem der statischen Verfahren ist, dass sie für Szenen außerhalb von Gebäuden (sog. Outdoor Scenes) nicht geeignet angewendet werden können; zudem können sie dynamische, also bewegliche Objekte zwar ausfiltern, wenn sie durch Wände o.ä. verdeckt werden, aber die Verfahren beachten nicht den Fall, dass ein bewegliches Objekt selber große Teiler einer Szene verdecken kann. An dieser Stelle greifen dann die dynamischen Verfahren, die dieses Problem behandeln; relativ bekannt sind hier etwa die Hierarchical Occlusion Maps (ich hoffe, jeder kommt an diesen Link) und die Hierarchical Z-Buffers (ebenso; man möge mir verzeihen, dass ich diese Verfahren nicht im Detail beschreibe).
Eine weitere Möglichkeit für dynamisches Occlusion Culling ist das Shadow Frustum Culling. Dieses Verfahren kombiniert Techniken, die zur Berechnung von Schatten verwendet werden, mit denen des Frustum Cullings, daher der Name. Das Prinzip dieses Verfahrens ist relativ einfach (ich hoffe, es hier richtig wiederzugeben): für die Objekte, die sich am nächsten zum Beobachter befinden, wird der sogenannte Occluder bestimmt; der Occluder ist eine Fläche, die dem Umriss des Objektes entspricht. Aus diesem Occluder wird, ähnlich wie beim Frustum Culling, ein Frustum mit Grundfläche (entspricht der Near Clipping Plane) und Seitenflächen erstellt (die Entsprechung zur Far Clipping Plane wird dabei nicht benötigt), das Shadow Frustum (Shadow daher, weil es dem Bereich entspricht, der im Schatten liegen würde, wenn der Betrachter eine Lichtquelle wäre); je nach Form des Occluders kann das wieder der bereits bekannte Pyramidenstumpf mit 4 Seiten sein, oder eine Pyramide mit mehr oder weniger Seiten. Alle Objekte, die sich nun innerhalb dieses Shadow Frustums befinden, werden durch das initiale Objekt verdeckt und können also verworfen werden (nicht verdeckte Objekte sind Ausgangspunkt weiterer Shadow Frusta). Falls es zu kompliziert klingt: hier ist eine kleine Abbildung.
Gehen wir von folgender Szene aus (der Pfeil markiert die Blickrichtung, beide Quader sollen sich auf der gleichen Höhe befinden):
Der dem Betrachter näherstehende Quader besitzt den folgenden Umriss (dick eingezeichnet):
Aus diesem Umriss lässt sich nun das Shadow Frustum bilden:
Es ist zu sehen, dass sich der zweite Quader vollständig innerhalb des Frustums befindet. Er kann daher bedenkenlos ignoriert werden.
Damit haben wir nun die wichtigsten Techniken beisammen, um zu bestimmen, ob ein Objekt oder Dreieck sichtbar ist oder ignoriert werden kann. Noch eine Anmerkung zur ursprünglichen Leserfrage: die Frage war auch, ob bei sich bewegenden Objekten die Bewegungsinformation in die Verdeckungstests mit einbezogen werden kann, etwa, indem anhand der Bewegungsinformationen abgeleitet wird, dass sich ein Objekt längere Zeit hinter einem anderen befinden wird und daher für die nächsten Bilder gar nicht mehr berücksichtigt werden muss. Ich könnte mir vorstellen, dass es möglich wäre, diese Information zu erfassen und zu berücksichtigen; ich vermute aber, dass der Aufwand hierfür nicht im Verhältnis zum Geschwindigkeitsgewinn steht. Das Prüfen etwa, ob sich ein Objekt innerhalb eines Shadow Frustums befindet, ist relativ einfach machbar; der eigentlich teure Schritt ist die Erstellung des Frustums. Da dieses aber vermutlich ohnehin für jedes Bild berechnet werden muss, ist der Geschwindigkeitsgewinn hier einfach zu niedrig, als dass es sich lohnen würde.
Der nächste Artikel zu diesem Thema wird sich um ein ähnliches Thema drehen und sich mit der Frage beschäftigen, wie man mit Dreiecken umgeht, die sich (teilweise) verdecken, aber von denen nicht eins eindeutig aussortiert werden kann, so dass beide gezeichnet werden müssen. Außerdem wird das in diesem Artikel unterschlagene Thema der Transparenz eine Rolle spielen. Seid gespannt!
Kommentare (2)