Beschleunigungsstrukturen für echtzeitfähiges Ray-Tracing auf aktueller Hardware-Infrastruktur

Raytracing ist eine Methode um realistische aussehende Bilder zu erzeugen, indem man den Transport des Lichtes nachahmt. Dies wird mit Hilfe von Strahlen (Rays) erreicht, die man mit der Geometrie der vorliegenden Szene schneidet. Dabei ermittelt man den von der Kamera aus nächstliegenden Schnittpunkt. Dazu wird für jeden Pixel der Bildfläche ein Strahl erzeugt. Ein naiver Algorithmus iteriert pro Strahl über alle Dreiecke der Geometrie, um den nächstliegenden Schnittpunkt für einen bestimmten Strahl zu ermitteln. Diese Methode (Brute-Force) ist vergleichsweise langsam. Mit Hilfe einer Beschleunigungsstruktur, kann die Schnittberechnung beschleunigt werden. Diese unterteilt die Geometrie räumlich und strukturiert die entstehenden Teilbereiche hierarchisch in einer Baumstruktur. Dabei verringert sich die Suche nach dem nächstliegenden Schnittpunkt im besten Fall von O(n) auf O(log n). Dennoch benötigt der Bau dieser Datenstruktur Zeit und zusätzlichen Speicher. Es gibt verschiedene Arten von Beschleunigungsstrukturen, welche sich in der Aufbauzeit, dem Speicherbedarf und der Renderzeit unterscheiden.

Mithilfe von Beschleunigungsstrukturen ist es möglich die Anzahl der nötigen Schnitte mit der Geometrie im Vergleich zu einer Brute-Force-Methode drastisch zu reduzieren. Dazu wird die Geometrie so aufgeteilt, dass nicht geschnittener Raum garnicht erst betrachtet wird (Space Partitioning). Eine einfache Methode ist die Einteilung der Szene in ein einheitliches Gitter (Uniform Grid). Die Geometrie wird anhand des Gitters aufgeteilt, dadurch referenziert jede Zelle des Gitters die darin liegende Geometrie der Szene. Diese kann auch leer sein. Während dem Rendern schneidet man erst mit den Zellen des Gitters und danach mit der dahinter liegenden Gemoterie.

Eine andere Variante, die auch in diesem Projekt Anwendung fand, ist die Verwendung von Baumstrukturen (Spatial Hierachies). Dabei wird die Geometrie in einem Baum so sortiert, dass der Strahl später nur einen Pfad im Baum abarbeiten muss um zum nächesten Schnittpunkt zu kommen. Die Knotenpunkte des Baumes bestehen dabei meist aus kostengünstig zu schneidenden Primitiven (Planes, Cubes, Spheres). Im besten Fall kann die komplette Geometrie eines der Kinder verworfen werden, sollte ein Knoten nicht geschnitten werden. Die Laufzeit wäre dann n*log(n) wobei n die Anzahl der Dreiecke darstellt.

In der Arbeit wurden die folgenden drei Strukturen auf ihre Vor- und Nachteile untersucht:

• BVH
• k-d Baum
• BIH

Zur Wahl der Splitting-Plane

Für die Konstruktion einer räumlichen Beschleunigungsstruktur benötigt man eine Ebene an der die Geometrie der Szene geteilt wird. Das Volumen welches geteilt wird, ist durch die Bounding Box der Sezene gegeben. Die Ebene/Splittinplane, welche die Szene unterteilt, ist meist achsenparallel. Es gibt verschiedene Methoden zur bestimmung der Splitting-Plane, in diesem Projekt wurden die folgenden Heuristiken implementiert.

Median-Cut: Beim Median Cut wird die Splitting-Plane so gewählt, dass sie den Raum entlang einer Achse in zwei gleichgroße Volumen teilt. Es ist die trivialste Methode Geometrie aufzuteilen und resultiert in sehr schnellen Bauzeiten von Bechleunigungstrukturen. Die Aufteilung nimmt aber keine Rücksicht auf die Verteilung der Dreiecke im Raum und verursacht selten gute Ergebnisse in den Renderzeiten, da zum Beispiel sehr große überschneidungen beim BVH oder leerer Raum beim BIH nicht beachtet wird.

Surface Area Heuristic: Bei der Surface Area Heuristic (SAH) kann durch die Anwendung einer Funktion die Wahl der Splitting-Plane optimiert werden. Die Funtkion berechnet die Traversierungskosten für einen Split mit einer definierten Canidateplane. Die Canidateplane wird dabei an alle Vertices einer Szene angelegt (Exact SAH). Der Aufwand kann dabei sehr hoch sein, da für eine exakte Bestimmung sämtliche Vertices betrachtet werden müssen. Um die Berechnung zu beschleunigen, wird der Raum diskretisiert (Binned SAH). Für eine optimierte Struktur sollen diese Kosten minimiert werden. Die Kosten sind niedriger je mehr Dreiecke ein geringes Volumen in einer Teilszene einnehmen, denn so ist die Wahrscheinlichkeit am geringsten, dass eine Teilszene geschnitten wird.

Ein k-d Baum ist ein binärer Baum, der einen k-dimensionalen Raum hierarchisch mit Hilfe von Schnittebenen (Splitting-Planes) unterteilt.
Dabei speichern Blattknoten die Referenzen der Dreiecke, die sich im jeweilig repräsentierten Unterraum befinden und innere Knoten verwalten die Schnittebenen. Schneidet man nun die Struktur mit einem Strahl, so kann man den Baum traversieren und an Hand der Ebenen bestimmen, ob die von den entsprechenden Kindknoten aufgespannten Teilbäume traversiert werden müssen oder nicht. Dadurch kann die Anzahl der Dreiecksschnitte stark reduziert werden, allerdings müssen dafür Schnitte mit den Ebenen berechnet werden.
Ein k-d Baum lässt sich relativ einfach konstruieren, indem man den Raum und seine Unterräume mittels Median-Cut teilt. Allerdings ist diese Herangehensweise unter Umständen wenig effizient, da die Form der zu unterteilenden Struktur, beziehungsweise die Lage der Dreiecke zueinander, nicht berücksichtigt wird. So ist es in diesem Fall möglich, dass Knoten mit sehr vielen und Knoten mit sehr wenig Referenzen existieren (man stelle sich eine Szene vor, in der ein oder mehrere Anhäufungen von Dreiecken in Randbereich existieren). Beim Traversieren eines solchen Baumes kann es aus bestimmten Blickwinkeln zu starken Performanceeinbrüchen kommen.

Konstruktion

Um einen k-d Baum zu konstruieren muss man den Raum möglichst so aufteilen, dass die Kindknoten ein bestimmtes Volumen unterschreiten oder eine bestimmte Anzahl an Dreiecksreferenzen enthalten. Dazu nimmt man den obersten Knoten vom Stack und prüft, ob alle in ihm gespeicherten Dreiecke auch wirklich in seinem Volumen liegen (in wenigen Fällen kann es durch Bereichsvergleiche vorkommen, dass dies nicht der Fall ist). Nun versucht man die optimale Schnittebene zu finden oder das Volumen des Knotens zu verkleinern, indem man leeren Raum "abschneidet". Dabei wird ein leerer Kindknoten erzeugt und einer dessen Dreiecksliste mit der des aktuellen Knotens identisch ist. Dieser Vorgang wird als "Empty Space Clipping" bezeichnet. Auf diese Art unterteilt man den Raum nun so lange, bis jeder Kindknoten eine bestimmte Anzahl von Dreiecksreferenzen unterschreitet oder bis die über die SAH berechneten Traverierungskosten die Kosten des aktuellen Knotens nicht mehr unterschreiten (denn dann wäre es sinnlos, weiter zu unterteilen). Für den Aufbau des Baumes sind viele Daten notwendig, die bei der Traversierung irrelevant sind. Um die Datenstruktur möglichst klein zu halten und im Speicher zu ordnen ist es sinnvoll sie in eine kleinere, serialisierte Form zu überführen.
Das Finden von geeigneten Schnittebenen gestaltet sich oftmals als schwierig. Deswegen kam die SAH zur Anwendung.

Schnitt/Traversierung

Um herauszufinden, ob, beziehungsweise welche Dreiecke ein Strahl schneidet, traversiert man den k-d Baum. Ist der aktuelle Knoten ein innerer, so berechnet man den Schnittpunkt mit dem Strahl. Mit near wird der Schnittpunkt des Strahls mit der vorherigen Schnittebene bezeichnet, welcher dem Betrachter am nächsten ist. far bezeichnet den entsprechenden weiter entfernteren Schnittpunkt. Ist d größer far so schneidet der Strahl das vordere Kind, ist d kleiner near so wird das hintere Kind geschnitten. Liegt d zwischen near und far, so müssen beide Kinder traversiert werden. Hierbei wird das vordere zuerst untersucht und das hintere im Stack gespeichert. Trifft man auf einen Kindknoten so berechnet man für jedes Dreieck in seiner Liste den Schnittpunkt und fährt fort.

Die Bounding Interval Hierarchy (BIH) ist eine hybride Beschleunigungsstruktur. Die Konstruktion der Struktur richtet sich nach der Aufteilung einer Objektliste, die Traversierung nutzt die Effizients räumlicher Aufteilung. Es ist möglich den Speicherbedarf im Voraus zu bestimmen.
Die Datenstruktur besteht aus zwei Arten von Knoten. Zum einen innere Knoten, welche zwei Referenzen auf deren Kindknoten enthalten, und zum anderen Blattknoten, welche eine Referenz auf den Anfang einer Dreiecksliste halten. Jeder innere Knoten besitzt zwei parallele Ebenen die zu einer der drei Koordinatenachsen orthogonal sind, dies ist die dominante Achse. Diese zwei Ebenen teilen den Knoten in einen rechten und einen linken Kindknoten auf. Die Kindknoten repräsentieren einen Unterraum des Vaterknoten, sind aber nicht zwangsläufig disjunkt (vgl. k-d Baum). Um die Kindknoten zu erzeugen wird die Bounding Box des Vaterknotens mit Hilfe der zwei Ebenen unterteilt. Dadurch entsteht ein linker und ein rechter Bereich die wiederum die Bounding Box der Kindknoten ergeben. Diese Bereiche können sich sowohl überlappen, ähnlich bei der BVH, sie können aber auch einen leeren Bereich zwischen den beiden Kindknoten erzeugen.
Ein innerer Knoten wird beschrieben durch die Position der beiden Ebenen und ein Index auf den ersten Kindknoten. Ein Blattknoten wird beschrieben durch einen Dreiecksindex und die Anzahl an Dreiecken, welche von diesem Knoten gehalten werden.

Konstruktion

Der Bau der BIH ist vergleichsweise simpel. Angenommen für den Wurzelknoten wurde ein optimaler Schnittkandidat mit Hilfe der SAH berechnet. Dieser Schnittkandidat teilt den Knoten orthogonal zu der gewählten Schnittachse. Als nächstes wird für jedes Dreieck innerhalb dieses Knotens bestimmt auf welcher Seite des Schnittkandidat es sich befindet. Danach werden die beiden Schnittebenen des Knotens bestimmt, indem entlang der Achse das Maximum und Minimum der linken und rechten Dreiecksmenge ermittelt wird. Daraufhin werden die Dreiecke im Speicher neusortiert, damit die Dreiecke eines Knotens immer ein kontinuierliches Stück Speicher belegen.
Dieser Algorithmus wird rekursiv auf die Kindknoten angewendet, bis ein bestimmtes Abbruchkriterium erreicht wurde.
Vor jeder Teilung eines Knotens wird überprüft, ob an den Grenzen des Volumes ein leerer Raum besteht. Anhand eines Schwellwertes wird definiert, ab wann dieser leere Raum abgetrennt wird und daraus ein leerer Knoten ensteht oder ob der Knoten normal weiter geteilt wird. Dieser Test ist notwendig, damit die Bounding Boxen der Knoten an die darin enthaltene Geometrie angepasst werden.

Schnitt/Traversierung

Das Traversieren der BIH ist ähnlich zu dem Traversieren der BVH, da es möglich ist leeren Raum zwischen zwei nicht überlappenden Kindknoten zu schneiden. Dennoch profitiert die BIH auch von der räumlichen Aufteilung, da es mit Hilfe der Strahlrichtung möglich ist, direkt das Kind zu traversieren, welches näher am Strahlursprung liegt. Dadurch ähnelt das Traversieren wiederum einem k-d Baum. Da die Knoten der BIH sich überlappen können, ist es nicht möglich sofort bei einem Schnitt mit der Szenengeometrie die Traversierung zu stoppen. Es ist notwendig die restlichen Elemente auf dem Traversierungsstack zu testen, um auszuschließen, dass ein Schnittpunkt existiert, welcher näher am Kameraursprung liegt. Dennoch kann die zu traversierende Struktur reduziert werden, sobald ein Schnittpunkt gefunden wurden, da alle Knoten, welche sich weiter entfernt zur Kamera befinden, als der derzeitige Schnittpunkt, verworfen werden können.