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.

1 / 2 / 3 / 4

Kommentare (2)

  1. #1 camil7
    Oktober 20, 2012

    Danke für den ausführlichen Artikel und die Mühe der vielen Illustrationen, die alles sehr schön veranschaulichen!
    Seit ich das letzte Mal in die Thematik geschaut habe, hat sich doch einiges getan.
    Die Idee mit dem “Backface Culling” finde ich besonders elegant, weil einfach, aber effizient.
    Die “Level of Detail” methode konnte ich bei einigen älteren Animationen noch gut nachvollziehen, da haben sich die Objekte beim Annähern regelrecht “entfaltet”. Inzwischen ist das so weit entwickelt, dass der Effekt nicht mehr sichtbar ist.
    Die Links zu den PDFs funktionieren auch für mich (nur beim zweiten Artikel fehlen zwei Abbildungen, die vermutlich wegen der hohen Auflösung aus dem PDF entfernt wurden) – und ich kann voll verstehen, dass Du das nicht auch noch in einen Blog-artikel klemmen wolltest. Das gibt noch reichlich weiteren Lesestoff …
    Nochmals Danke!

  2. #2 McNeal
    Januar 20, 2013

    Hi Marcus,

    schoener Artikel! Gibt einen soliden Einblick und du hast dir auch viel Muehe gegeben mit den Illustratione, find ich gut! Zwar ein wenig veraltet, so auf dem Stand 2000 wuerd ich sagen, aber der ganze neue Kram sprengt eh den Rahmen eines Blogartikels.

    Nur ein paar kleine Anmerkungen:
    LOD ist so ziemlich das wichtigste Cullingverfahren, da es die Komplexitaetsklasse aendern kann. Idealerweise aendert sich der Aufwand von O(n) auf O(log n). Andere Cullingverfahren aendern nur eine Konstante, wenn ueberhaupt.
    Achja, und kam der Z-Buffer eigentlich schon vor?

    Occlussion-Culling hat sich, bis auf Portalrendering, uebrigens nie so grossflaechig durchgesetzt. Das war mehr ne nette Forschungsarbeit als es praxistaglich ist.

    Zu der Frage mit dem Occlusion-Culling von bewegten Objekten koennte man z.B. groessere Huellenkoerper verwenden. Bewegt sich das Objekt aus diesem erweiterten Huellenkoerper heraus, muss ein neuer Verdeckungstest durchgefuehrt werden, ebenfalls mit groesserem Huellenkoerper. Dasselbe kann man mit dem Shadow Frustum machen, nur in die andere Richtung, also das Frustum kleiner machen um den Test noch konservativer zu gestalten. Sozusagen ein lazy-update, falls es das Wort gibt 🙂 Das duerfte aber nur ganz speziellen Faellen lohnenswert sein.