Aktuelle Version vom 15. September 2007, 00:18 Uhr

Was ist das?

Frustum Culling ist eine Optimierungsmethode, bei der all die Objekte vom Zeichnen ausgeschlossen werden, die außerhalb des Sichtbereichs (des Frustums) liegen.

Wozu brauch ich es?

Frustum Culling sorgt dafür, dass akzeptable Frameraten auch bei großen Szenen möglich sind. Denn durch Frustum Culling werden viele der Teile der Szene nicht gezeichnet, die man ohnehin nicht sehen kann.

Wie funktioniert es?

Anwendungsspezifisches

Für eine Anwendung kann Frustum Culling sehr ähnlich wie eine Kollisionsabfrage behandelt werden. Meist wird hier keine exakte Kollisionsabfrage durchgeführt (wie es beispielsweise mit dem Seperation Axis - Algorithmus gemacht werden könnte), sondern es wird lediglich eine eher pessimistische Variante verwendet.

Frustum von oben

Links: Eine Kugel die bei der pessimistischen Variante als teilweise innerhalb erkannt wird tatsächlich jedoch ausserhalb liegt.

Rechts: Vergleich pessimistische und exakte Kollisionsabfrage mit einer Kugel.

Für die pessimistische Variante benötigen wir lediglich die 6 Ebenengleichungen des Frustums. Danach prüfen wir, ob ein Objekt komplett oder teilweise ausserhalb eines der 6 Halbräume ist, also ob sich das Objekt hinter der entsprechenden Ebene befindet. Nun gibt es 3 Möglichkeiten:

1. Objekt komplett hinter mindestens einer Ebene => Objekt überhaupt nicht sichtbar.
2. Objekt vor allen 6 Ebenen => Objekt komplett sichtbar
3. Objekt mindestens durch eine Ebene teilweise "abgeschnitten", also weder davor noch dahinter.

Im 3. Fall hängt es nun davon ab ob wir eine hierarchische Abfrage durchführen wollen. Also beispielsweise:

• Ein Octree wo jeder Würfel in bis zu 8 kleinere unterteilt werden kann.
• Gruppen von Objekten (beispielsweise ein Sonnensystem bildet eine Gruppe), wo die einzelnen Objekte noch getrennt abgefragt werden können.
• Der Extremfall wäre das man jedes Dreieck eines Objektes untersucht (was beispielsweise für Raytracer sinnvoll sein könnte).

Wenn wir nun einen hierarchischen Aufbau besitzen, so bedeutet der 3. Fall, dass wir eine Hierarchiestufe weiter nach unten gehen müssen um die Objekte oder Volumen dieser Stufe zu testen.

Wenn wir keinen hierarchischen Aufbau (oder keine weitere Hierarchiestufe mehr) besitzen, so muss natürlich das gesamte Objekt - bzw. alle Dreiecke die sich innerhalb des geprüften Volumen befinden - gezeichnet werden.

Angemerkt sei noch, dass "vor" und "hinter" der Ebene natürlich vom Normalvektor (der für die Ebenengleichung verwendet wird) abhängig ist. Hier wird davon ausgegangen, dass die Normalvektoren in das innere des Frustums zeigen.

Je nach Objekttyp lässt sich verhältnismäßig einfach Prüfen ob das Objekt hinter oder vor einer Ebene ist:

• Punkt: prüfen ob die Ebenengleichung ein positives oder negatives Ergebnis liefert.
• Kugel: liefert die Ebenengleichung (mit einem normierten Normalvektor) für das Zentrum der Kugel einen absoluten Wert (Vorzeichen weg lassen) der kleiner als der Radius der Kugel ist, so schneidet die Kugel die Ebene. Ansonnsten wird gleich wie bei einem Punkt verfahren.
• Quader: liefern manche Eckpunte ein positives Ergebnis und andere ein Negatives wenn man sie in die Ebenengleichung einsetzt, so schneidet der Quader die Ebene. Liefern alle Punkte ein positives, oder alle Punkte ein negatives Ergebnis, so liegt der Quader gänzlich vor bzw. hinter der Ebene.
• Dreieck: gleich wie bei einem Quader werden einfach alle Eckpunkte betrachtet, hier natürlich nur 3 statt 8 Eckpunkte.

Hardwareunterstützung

Standard

OpenGL teilt automatisch alle Dreiecke welche nicht oder nur teilweise sichtbar sind in einen sichtbaren und eine nicht sichtbaren Bereich ein. Es wird dann nur noch der sichtbare Bereich gezeichnet, oder ggf. natürlich auch gar nichts gezeichnet wenn das Dreieck komplett ausserhalb des Frustums liegt. Siehe auch: Clipping Plane.

Occlusion Query Extension

Die Extension GL ARB occlusion query bietet die Möglichkeit abzufragen wieviele Pixel gezeichnet wurden. Diese Extension wird häufig für Sichtbarkeitsabfragen verwendet, indem man bevor man ein komplexeres Objekt zeichnet nur dessen Bounding Volumen (meist einen Quader) zeichnet und prüft ob davon ein Pixel auf den Bildschirm landen würde. Ein netter Nebeneffekt an diesen Sichtbarkeitsabfragen ist natürlich, dass auch alle Dreiecke die ausserhalb des Frustums liegen keine Pixel auf den Bildschirm bringen, somit kann man beide Test vereinen. Es kann aber natürlich dennoch hilfreich sein wenn man selbst diese einfacheren Tests etwas gruppiert, um so größere Bereiche die weg fallen gleich von der CPU erkennen zu lassen. Vor allem sehr große Bereiche werden von diesem Test auch nicht erkannt. Man stelle sich hierfür einen Quader vor, der den gesamte Frustum beinhaltet. Dieser würde ebenfalls kein einziges Pixel auf dem Bildschirm "wert" sein.

Siehe auch

Frustum, Clipping Plane, Frustum Culling Tutorial