Culling
# Culling

Der Begriff Culling (englisch cull: Auslese, Wegschneiden, Abfall) bezeichnet ein Prinzip aus der 3D-Computergrafik, bei welchem getestet wird, ob ein betrachtetes Objekt aktuell sichtbar ist, um nicht sichtbare Objekte möglichst früh zu verwerfen und dadurch einen Performance-Gewinn bei der Darstellung zu erreichen, siehe Sichtbarkeitsproblem.

Je nach angewendeter Methode wird unterschieden in Backface Culling, Frontface Culling, Frustum Culling und Occlusion Culling.

## Backface Culling

Das Backface Culling ist eine Technik der 3D-Computergrafik, mit der ein Großteil der nicht sichtbaren Dreiecke (oder allgemeiner: von Polygonen) von Objekten in einer Szene entfernt wird. Die geringere Anzahl zu zeichnender Flächen erhöht die Darstellungsgeschwindigkeit.

Bei einer Dreiecksfläche ist eine ihrer beiden Seiten durch den Normalenvektor $N_{P}$ als Vorderseite definiert. Gibt es in der Szene nur geschlossene, massive Objekte, so blickt der Betrachter immer auf solche Vorderseiten.

Bei einem Kubus sind beispielsweise maximal 3 Seiten gleichzeitig sichtbar, die anderen Seiten sind vom Betrachter abgewandt. Es ist somit überflüssig, die Rückseiten (englisch backfaces) zu zeichnen, da diese von anderen Dreiecken verdeckt werden.

Geht man also von undurchsichtigen, geschlossenen Objekten aus, so ist ein einfacher Test, um festzustellen ob eine Seite des Objektes gesehen werden kann oder nicht, die Richtung des Normalenvektors $N_{P}$ des Dreiecks mit der Blickrichtung $N$ zu vergleichen.

Normale des Dreiecks (Kreuzprodukt von $V_{1}$ und $V_{2}$):

$N_{p}=V_{1}\times V_{2}$

Prüfung, ob Normale in Blickrichtung (Skalarprodukt von $N_{p}$ und $N$):

$N_{p}\cdot N$

wobei $V_{1}$ und $V_{2}$ orientierte Dreieckskanten sind und $N$ der Blickrichtungsvektor.

Ist das Ergebnis $\leq 0$, so ist die Fläche (von vorne) zu sehen, bei einem Ergebnis $>0$ nicht (bzw. nur von hinten). Das setzt voraus, dass die Flächennormalen bei einem Körper vom Körper weg zeigen. Ist eine Fläche sichtbar, werden anschließend die weiteren Schritte der Grafikpipeline durchlaufen. Ist die Fläche nicht zu sehen, durchläuft sie keine weiteren Schritte, wird also verworfen.

Das Backface Culling sollte, um den Gesamtprozess möglichst effizient zu gestalten, möglichst früh angewendet werden. Oftmals ist es der erste Schritt einer Grafikpipeline.

## Frontface Culling

Eng verwandt mit dem Backface Culling ist das Frontface Culling, bei dem die eigentlich sichtbaren Vorderseiten verworfen werden und nur die Rückseiten eines Objektes gezeichnet werden. Diese Technik wird für besondere Effekte (zum Beispiel den Shadow Volumes) benötigt.

## Frustum Culling

Beim Frustum Culling (Frustum, deutsch: Pyramidenstumpf) wird getestet, ob ein betrachtetes Objekt im Sichtbereich liegt. Frustum Culling bedeutet so viel wie Kegelstumpf-Auslese.

Das Frustum ist eine abgeschnittene Pyramide, deren Basis die hintere Clippingebene ist, also der Bereich, hinter dem nichts mehr gezeichnet werden soll. Die Schnittebene der Pyramide, die vordere Clippingebene, entspricht der Position des Betrachters (der in Richtung der Pyramidenbasis schaut). Alles, was in der Pyramide zwischen der Schnittebene und der Spitze liegt, liegt quasi hinter dem Betrachter. Die Seitenwände der Pyramide sind die Ebenen, die den Bildschirmrand bilden.

Um im Sichtbereich zu liegen, muss ein Punkt innerhalb des so genannten Frustums liegen. Um nicht jeden Punkt eines Objekts einzeln berechnen zu müssen, werden zur schnelleren Berechnung einfache Hüllobjekte (engl. „bounding volume“) wie Quader oder Kugeln um die Objekte gelegt und ein Schnitttest zwischen dem Hüllobjekt und dem Sichtvolumen (Frustum) durchgeführt. Ist die Schnittmenge aus dem Volumen des Frustums und dem Volumen des Hüllobjekts leer, so ist das Objekt nicht auf dem Bildschirm sichtbar. Liegt das Volumen des Hüllobjekts vollständig im Frustum, so ist das Objekt vollständig sichtbar. Existiert eine andere Schnittmenge, so ist das Objekt unter Umständen nur teilweise sichtbar.

## Occlusion Culling

Occlusion Culling (englisch occlusion = Verdeckung) ist ein Verfahren, um verdeckte (Teil-)Objekte einer Szene zu bestimmen. Die von anderen Objekten verdeckten Polygone müssen im Weiteren nicht weiter behandelt und gezeichnet werden, was die Schnelligkeit von Berechnungen für die gesamte Szene erhöht. Daher wird dieses Verfahren bei sehr polygonreichen Szenen angewendet.

Occlusion Culling wird nativ von NVIDIA ab der GeForce 3 unterstützt.

