» News | » My 3d Dev | » Papers | » Downloads | » Contact
Chemnitz, den 24. April 2002

Echtzeit Culling Algorithmen

- Eine Übersicht -

Einleitung

Trotz immer leistungsstärker werdenden Hardware ist es längst noch nicht möglich alle Polygone komplexerer Szenen mit korrekter Echtzeitlichtberechnung und Texturierung in Sekundenschnelle auf dem Bildschirm darzustellen. Als einziger Ausweg bleibt also nur das Aussortieren (to "cull") von nicht sichtbarer Geometrie. Im Laufe der Jahre sind dabei verschiedene Algorithmen entstanden, auf welche hier kurz eingegangen werden soll. Es geht hier nicht um die Frage, welcher Algorithmus nun am effektivsten bzw. schnellsten ist, da alle ihre Vor- und Nachteile bezüglich der Verwendung haben. Vielmehr soll ein Überblick über die Eigenschaften und Funktionsweise dieser gegeben werden. Es wird auch keinerlei Quell- oder Pseudo Code vorgestellt werden, da man mit etwas Matheverständnis und den Grundlagen der Prinzipien in der Lage sein sollte, diese Algorithmen in einer Programmiersprache umzusetzen.

Render Pipeline

Bevor wir jedoch auf die Algorithmen eingehen wollen, ist es sinnvoll einen groben Überblick zu haben, welche Operationen ein Vertex (3D Punkt) durchlaufen muss um seinen Weg als Pixel (2D Punkt) auf dem Bildschirm zu finden. Diese Operationen werden unter dem Begriff Render Pipeline zusammen gefasst.

grober Aufbau einer Renderpipeline

Zuerst werden die Positionen der Vertices im Transform Modul berechnet und auf 2D projiziert. Mit anderen Worten „Monitor“ gerecht berechnet. Steht fest, dass ein Vertex zu sehen ist, wird dieser im Lighting Modul schattiert und beleuchtet. Das Zeichnen der Polygone erfolgt letztendlich im Rasterizer. Wird diese Rasterisation nicht vom Prozessor sondern von der Grafikkarte vorgenommen, spricht man von einer 3D Beschleuniger Karte. Unterstützt die Grafikkarte dabei die Transformation und Beleuchtung, spricht man von einer T&L (Transform and Lighting) Karte. Letztendlich wird ersichtlich, dass diese Render Pipeline eine zeitaufwendige Angelegenheit ist und das Aussortieren von Vertices bzw. Polygonen erfolgen sollte bevor ein Vertex auf diese Reise geschickt wird.

Backface Culling

Einer der am häufigsten benutzen und effektivsten Algorithmen ist das BackFace Culling (Rückseitenentfernung). Es ist meist der letzte Culling Algorithmus welcher durchgeführt wird, bevor ein Pixel durch die Renderpipeline geschickt wird. Das Prinzip ist recht simpel. Man berechnet den Vektorwinkel zwischen dem Normalenvektor der Ebene und dem Richtungsvektor der Kamera bzw. des Betrachters. Ist dieser Wert größer als 90°, so ist das Polygon vom Betrachter nicht sichtbar und braucht nicht dargestellt werden.


In der obigen Abbildung hat dieser Schnittwinkel einen Wert kleiner als 90°. Demzufolge ist diese Fläche vom Betrachter sichtbar. Würde man diese Fläche aber Rotieren bis der Winkel größer oder gleich 90° ist, so würde der Betrachter nur die Rückseite des Polygons sehen welche man normalerweise als unsichtbar deklariert. Ein Beispiel dafür ist die Betrachtung eines Würfels. Einen Würfel kann man drehen wie man will. Es ist dabei unmöglich jemals mehr als drei Seiten zu sehen. Die restlichen Flächen zeigen immer vom Betrachter weg und können somit ignoriert werden. Die Einsparung liegt hier also bei 50%, was auch ein Näherungswert für komplexere Szenen ist.

View Frustum Culling

Bevor hier näher auf das Prinzip des View Frustum Culling eingegangen werden soll, ist es nützlich vorher den Begriff “View Frustum“ selbst zu klären. View Frustum ist die Bezeichnung für das Sichtfeld der Kamera, beziehungsweise des Betrachters. Folgende Abbildung soll dies verdeutlichen:


Wie zu sehen ist, wird das Sichtfeld durch 6 Ebenen begrenzt. Zum einen wären da die vier Pyramidenwände, welche durch die Eckpunkte des Bildschirms und der Betrachterposition definiert sind, sowie die Bildschirmfläche selbst. Die 6. Ebene befindet sich parallel zum Bildschirm in einer festgelegten Entfernung und wird als Far Clipping Plane bezeichnet. Sie dient dazu, dass Objekte ab einer gewissen Entfernung nicht mehr auf dem Bildschirm sichtbar sind.

Das View Frustum Culling verfährt nun nach folgendem Schema. Es wird getestet, ob die Punkte eines Polygons alle hinter einer der 6 Ebenen liegen (Hinter bedeutet hier Backface, falls die Normalenvektoren der Ebenen alle nach innen zeigen). Dabei Können folgende 3 Ergebnisse auftreten:
  1. Alle Punkte liegen hinter einer Ebene → Das Polygon ist nicht zu sehen
  2. Alle Punkte liegen vor jeder Ebene → Das Polygon ist komplett zu sehen
  3. Nur einige Punkte liegen vor jeder Ebene → Das Polygon ist teilweise zu sehen
Tritt Fall 3 ein gibt es zwei Möglichkeiten. Entweder das Polygon wird gerendert oder an der Ebenen geclippt. Der meist verwendete Algorithmus zum Clippen von Polygonen ist das Sutherland-Hodgman Clipping auf was hier jedoch nicht weiter eingegangen werden soll.

Wie sicherlich auffällt ist bei diesem Verfahren der Rechenaufwand so groß, dass es keinen nennenswerten Geschwindigkeitsvorteil bringen würde. Aus diesem Grund bedient man sich sogenannten Bounding Boxen, welche um eine lokale Ansammlungen von Polygonen (Objekte) gespannt wird. Eine Bounding Box ist dabei nichts anderes wie ein unsichtbarer Quader, welcher in Bezug auf Breite, Höhe und Tiefe an das Objekt angepasst wird. Jetzt testet man nicht mehr die Polygone selber, sondern nur noch die Flächen dieses Quaders. Ist der Quader nicht zu sehen, ist folglich auch das Objekt nicht sichtbar. Geht man von einer Gleichverteilung der Geometrie aus, erhält man dadurch eine Ersparnis von etwa 70%.

Quadtrees

Quadtrees finden ihre Verwendung vor allem in Outdoor-Szenen wo große Teile der Geometrie mit wenigen Tests “eliminiert“ werden müssen. Der erste Schritt besteht darin beim Einladen der Szene alle Polygone in eine Baumstruktur zu bringen. Dazu stelle man sich seine Szene aus der Vogelperspektive vor und zieht einen Rahmen um diese. Dieses entstandene Quadrat ist die Wurzel unseres Quadtrees. Jetzt definieren wir einen Wert von maximalen Polygonen welcher pro Quadrat nicht überschritten werden soll. Dieses Quadrat wird also wiederum in 4 gleichgroße Quadrate unterteilt. Besitzt einer dieser 4 Quadrate immer noch eine Polygonzahl größer unserer Maximalzahl, so wird dieses Quadrat wiederum in 4 kleiner Quadrate unterteilt. Diesen Vorgang wiederholen wir so lange, bis es nur noch Quadrate gibt, deren Polygonanzahl kleiner der gewählten Maximalzahl ist. Hier ein Beispiel, bei dem die Maximalzahl der Polygone bei 10 liegt.

Die Zahlen geben die Anzahl der Polygone an

Durch diese Baumstruktur ist es jetzt möglich eine große Anzahl an Polygonen mit wenigen Tests auszusortieren. Wir beginnen dabei mit der Wurzel (81) und testen alle Äste ( 36, 9, 9 und 27) mittels View Frustum Culling auf die Sichtbarkeit in Bezug auf den Betrachter.


Anhand dieses Beispiels wird ersichtlich, dass bereits nach dem ersten Test 54 der 81 Polygone "herausfallen" (~ 67%).

Als eine erweiterte Form des Quadtrees sei hier der Begriff Octree zu erwähnen, wobei die Szene nicht in Quadrate sondern Würfel geteilt wird. Das Prinzip ist dabei das gleiche, wobei es jedoch nicht 4, sondern 8 Äste gibt, da ein Würfel in 8 kleinere Würfel geteilt wird.

Portalisierung

Um in einer Szene den Algorithmus der Portalisierung anwenden zu können, muss diese in Sektoren aufgeteilt werden. Diese Sektoren werden dabei durch unsichtbare Portale miteinander verbunden, wobei ein Portal einen Ursprung (Quellsektor) und ein Ziel (Zielsektor) hat.

Sektoren sollten dabei idealerweise in sich abgeschlossene Räume sein und die Portale zum Beispiel Türen, Fenster, Tore, usw. Das Prinzip des Algorithmus ist dabei folgender: Es wird zuerst der Sektor gezeichnet in dem sich der Betrachter befindet. Danach werden alle Portale dieses Sektors auf ihre Sichtbarkeit im View Frustum getestet. Befindet sich so ein Portal im Sichtfeld des Betrachters, so wird das Sichtfeld durch dieses Portal neu berechnet und der Zielsektor dieses Portals mit dem neuen Sichtfeld ebenfalls gezeichnet. Ist von diesem Zielsektor wiederum ein Portal im Sichtfeld des Spieler, wird dessen Zielsektor ebenfalls gezeichnet. Das geschieht so lange, bis alle vom Betrachter sichtbaren Portale berücksichtigt wurden. Aus diesem Grund ist dieser Algorithmus auch rekursiv. Der Vorteil dabei ist, dass man die Portalisierung auch in dynamischen Szenen verwenden kann. Entsteht zum Beispiel ein Loch in einer Wand, muss an dieser Stelle nur ein neues Portal gesetzt werden. Da die Anzahl der Geometrie in einem Sektor gering gehalten werden sollte, ist dieser Algorithmus nur für Indoor (Räume) verwendbar. Jedoch ist es möglich den Zielsektor eines Portals als Outdoor (Landschaft) zu beschreiben, wobei dieser Zielsektor dann jedoch mit einem anderen Algorithmus dargestellt werden muss. Ein Mix aus Indoor und Outdoor ist somit leicht zu realisieren. Ein weiterer großer Vorteil ist, das man mittels Portale auf einfache Art und Weise Spezialeffekte wie zum Beispiel Spiegelungen hervorrufen kann. Dabei ist der Quell- und Zielsektor eines Portals ein und der Selbe. Die Kameraposition wird dann an diesem Portal gespiegelt und der Algorithmus erneut aufgerufen. Die Effizienz dieses Algorithmus liegt darin, dass nicht sichtbare Sektoren in keiner Weise berücksichtigt werden müssen. Es finden somit keine unnötigen Tests auf Sichtbarkeit statt.

BSP Bäume

Die genaue Erklärung der BSP – Technik würde hier den Rahmen dieser Ausarbeitung sprengen, soll aber aufgrund seiner weiten Verbreitung kurz in seiner Wirkungsweise beschrieben werden. BSP bedeutet so viel wie Binary Space Partitioning und hat die Aufgabe Polygone nach ihrer Entfernung zur Kamera zu ordnen. Den Algorithmus zum erstellen eines BSP Baumes nennt man BSP Compiler, welcher die Aufgabe hat alle Polygone in konvexe Partitionen aufzuteilen und diese in einem binären Baum zu speichern. Da dieser Baum nur einmal beim Laden der Szene erstellt wird, können hier ebenfalls nur statische Polygone verwendet werden. Das erstellen der konvexen Partitionen erfolgt auf folgende Art und Weise: Man wählt ein Polygon als Teilungspolygon, erstellt an dessen Position eine Ebene und "schneidet" damit die Szene in 2 Hälften. Dabei sollte beachtet werden, dass die Teilungsebene die Szene in zwei ausgeglichene Hälfte teilt und bei dem "zerschneiden" so wenig wie möglich Polygone geteilt werden müssen. Mit jeder Hälfte geht man dann nach dem gleichen Schema vor, bis man nur noch konvexe Partitionen übrig hat. Als Resultat erhält man einen binären Baum, welcher mit Hilfe von erstellten Bounding Boxen ebenfalls beim Durchgang eine Menge an Geometrie "eliminiert". Trotz der vielen Vorteile beim Rendern der Geometrie gibt es auch hier Nachteile. Es entstehen viele zusätzliche Polygone, da bei der Erstellung des Baumes Polygone durch das Teilungspolygon zweigeteilt werden. Des weiteren kann ein BSP Baum schnell eine enorme Größe (Je nach Architektur der Szene) aufnehmen und ist ausschließlich für Indoor Szenen geeignet.

Schlusswort

Ich hoffe, dass ich mit diesem Dokument einen Einblick zum Thema Culling geben konnte. Es wurden hier jedoch nur die wichtigsten Algorithmen angeschnitten, wobei der Vollständigkeit halber noch der Begriff Occlusion Culling zu erwähnen ist. Natürlich muss man nicht unbedingt alle dieser Algorithmen in seiner Applikation unterbringen, jedoch sollte man versuchen einen guten, Problembezogenen Mix zu finden. Gerade das Backface- und das View Frustum Culling sind Grundalgorithmen, welche heutzutage schon allein durch ihre Effizienz in Echtzeitanwendungen nicht fehlen sollten. Neben den Culling Algorithmen sollte man sich ebenfalls mit dem Begriff LOD (Level Of Detail) befassen, da diese ebenso effizient den Renderprozess beschleunigen können. Gerade bei Outdoor – Szenen ist es schwierig akzeptable Frameraten zu erzielen. Ebenso ist abzusehen, dass die vorgestellten Algorithmen nicht so schnell ihre Gültigkeit verlieren werden, da man bedenken muss, dass nicht nur die Hardware sich weiter entwickelt, sondern gleichzeitig der Anspruch an realistisch wirkender Grafik steigt und je effektiver die Algorithmen zum Culling implementiert werden, desto weniger Zeit wird für die Render-Phase benötigt und umso mehr Polygone können in einer Szene dargestellt werden

Weiterführende Literatur

Samuel Ranta Eskola:
Binary Space Partioning Trees and Polygon Removal in Real Time 3D Rendering
http://www.flipcode.com/misc/SamuelRanta-Eskola_BSPTrees.pdf

Pietari Laurila
Geometry Culling in 3D Engines
http://www.gamedev.net/reference/programming/features/culling

Jacco Bikker
Building a 3D Portal Engine
http://www.flipcode.com/portal/

Gerald Filimonov
Binary Space Partitioning Trees
http://www.3dtechdev.com/tutorials/leafbsp/3dbsptrees.html

Kenneth E. Hoff III
Faster 3D Game Graphics by Not Drawing What Is Not Seen
http://www.cs.unc.edu/~hoff/papers/vfc/vfc.htm

Bryan Turner
Real-Time Dynamic Level of Detail Terrain Rendering with ROAM
http://www.gamasutra.com/features/20000403/turner_01.htm