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):

1 / 2 / 3 / 4 / Auf einer Seite lesen

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.