Ray Tracing
Ray Tracing ist das Verfolgen eines beim Ray Casting erstellten Strahls in der Szene. Ziel der Verfolgung des Strahls ist es das erste Hindernis zu finden auf welches der Strahl auftrifft. Je nachdem für welchen Zweck der Strahl ausgesendet wurde, müssen unter Umständen nur bestimmte Objekte der Szene berücksichtigt werden oder für die Genauigkeit der Schnittprüfung können manchmal die umgebenden Bounding Volumes ausreichen während manchmal genau der getroffene Teil eines Objekts benötigt wird.
Das Finden von Schnitten eines Strahls mit Bounding Volumes kann anhand der Ray und Bounding Volume Structs sehr einfach implementiert werden. Wenn man die genauen Schnittpunkte eines Strahls mit den Triangles eines Modells berechnen möchte muss man dies manuell implementieren da dies von XNA standardmäßig nicht unterstützt wird. Der Triangle Intersection Artikel zeigt wie dies bei XNA implementiert werden kann.
Die Schwierigkeit beim Ray Tracing ist es den nahsten Schnittpunkt des Strahls effizient, also zum einen möglichst schnell und zum anderen mit einem möglichst geringen zusätzlichen Speicherplatzaufwand für Beschleunigungsstrukturen zu finden.
Naives Ray Tracing
Die einfachste Art Ray Tracing zu implementieren wird auch als Naives Ray Tracing bezeichnet. Hierfür werden keinerlei Beschleunigungsstrukturen verwendet. Der Strahl dessen Schnittpunkt man finden will wird einfach mit allen Objekten der Spielwelt geschnitten wobei man sich jedes mal wenn ein Schnitt stattfindet das Objekt mit dem nahsten Schnittpunkt merkt. Es werden also einfach alle Objekte der Spielwelt auf naive Weise durchprobiert. Ist man durch alle Objekte der Spielwelt durchiteriert ist das gemerkte Objekte das getroffene.
Dieser Ansatz funktioniert allerdings nur für sehr kleine Welten mit wenigen Objekten, sobald man eine größere Spielwelt hat dauert das Berechnen der Schnittpunkte mit allen Objekten zu lange um für ein Echtzeitspiel verwendet werden zu können. Um trotzdem mit Raytracing arbeiten zu können müssen also entsprechende Optimierungen zur Beschleunigung umgesetzt werden.
Ray Tracing mit Beschleunigungsstrukturen
Der zeitaufwändigste Teil beim Ray Tracing ist die Berechnung der Schnittpunkte des Strahls mit den Spielobjekten. Um Ray Tracing effizient umsetzen zu können ist es daher das Ziel die Anzahl an Schnittpunktberechnungen auf ein Minimum zu reduzieren. Im groben gibt es hierfür zwei Kategorien für Optimierungen. Zum einen die Verwendung eines Spatial Partitionings und zum anderen die Verwendung eines Object Partitionings.
Ray Tracing mit Spatial Partitioning
Eine Aufteilung des Raums hilft beim Ray Tracing sicherzustellen dass nur Objekte auf Schnittpunkte geprüft werden die sich in unmittelbarer Nähe zum Strahl befinden und damit überhaupt für einen Schnitt in Frage kommen. Dadurch kann man bei größeren Spielwelten von vornherein die meißten Objekte direkt ignorieren und spart sich damit die Berechnung einer Vielzahl von Schnittpunkten.
Ray Tracing mit Object Partitioning
Um die Schnittpunkte von Strahlen und Objekten zu berechnen werden in XNA standardmäßig lediglich Bounding Volumes verwendet. Zur Annäherung komplexerer Objekte kann es dabei notwendig werden die Form eines Objekts über mehrere Bounding Volumes zu definieren. Damit zur Berechnung des Schnitts mit einem solchen Objekt nicht immer direkt alle Teilvolumes auf einen Schnittpunkt getestet werden müssen kann man eine Bounding Volume Hierarchie als Object Partitioning verwenden. Dabei wird zunächst ein Bounding Volume welches das Modell komplett umfasst auf einen Schnittpunkt geprüft und nur wenn der Strahl dieses Volume schneidet werden alle Teilvolumes in der nächsten Hierarchie-Ebene auf einen Schnitt getestet um die Schnittberechnung genauer zu machen. Wenn der Strahl das umgebende Volume nicht schneidet kann man sich dagegen die Berechnung der Schnittpunkte aller Volumes in der nächsten Hierarchie sparen und man kann das Objekt direkt mit nur einem Schnittpunkttest ausschließen.
Wie bereits erwähnt wurde ist es auch möglich in XNA ein Ray Tracing auf Genauigkeit der Triangles der Modelle zu implementieren. Da der Schnittpunkt Test eines Strahls mit einem Dreieck relativ langsam ist und ein Modell für gewöhnlich aus relativ vielen Triangles besteht ist hierbei die Verwendung eines Object Partitionings in Form einer Bounding Volume Hierarchie, bei der sich die Triangles der Modelle erst auf der untersten Hierarchiestufe befinden, zwingend erforderlich.
Wichtige Hinweise zum Umgang mit Beschleunigungsstrukturen
Weiterhin nützlich ist, dass sich die beschriebenen Optimierungen mittels Spatial und Object Partitioning auch miteinander kombinieren lassen. Man kann seine Objekte also problemlos z.B. mittels eines OcTrees räumlich unterteilen um nur relevante Objekte beim Ray Tracing überprüfen zu müssen und gleichzeitig können die Objekte selbst über Bounding Volume Hierarchien verfügen um den getroffenen Teil eines Modells sehr genau mit möglichst wenigen Schnittpunkttests bestimmen zu können.
Trotzdem sollte man sich genau überlegen welche Arten von Optimierungen und welcher Detailgrad für die Partitionierungen im eigenen Spiel überhaupt sinnvoll sind. Die Datenstrukturen für die Partitionierungen benötigen schließlich zusätzlichen Speicherplatz und bedeuten auch einen gewissen Overhead an Schnitttests die allein zum Traversieren der Beschleunigungsstrukturen benötigt werden. Die Kunst besteht hierbei also den optimalen Kompromiss zu finden um das Raytracing bei möglichst geringem Speicheraufwand möglichst schnell und vor allem schnell genug für eine Echtzeitanwendung zu machen.
