Einsatz von verketteten Listen bei der Kollisionserkennung

Im letzten Artikel haben wir die Vorteile der Sektorisierung im Rahmen der Kollisionserkennung besprochen. Heute befassen wir uns mit dem Handling der in den Sektoren befindlichen Kollisionsobjekte und werden die Frage beantworten, wie man schnell und unkompliziert Zugriff auf diese erhält, um sie paarweise auf eine mögliche Kollision hin testen zu können.
Zur Lösung des Problems bieten sich unterschiedliche Vorgehensweisen an. Der in der nachfolgenden Abbildung skizzierte Ansatz behandelt den Einsatz von verketteten Listen. Diese Listen lassen sich problemlos in Echtzeit generieren. Zu diesem Zweck muss zunächst ermittelt werden, in welchem Sektor sich ein Kollisionsobjekt aktuell befindet. Ist der Sektor gefunden, wird die Liste mit den sich ebenfalls im Sektor befindlichen Kollisionsobjekten einfach um ein zusätzliches Element verlängert.

Sektorisierung der Spielewelt: Camera Aligned Collision Grid (an der Kamera ausgerichtete Kollisionsbereiche)

Mit zunehmender Anzahl der Spieleobjekte wirkt sich die für die Durchführung der Kollisionstests benötigte Rechenzeit zunehmend negativ auf die Performance eines Spiels aus. Ohne weitere Optimierungen müssten alle Objekte paarweise auf eine mögliche Kollision hin getestet werden, was die Anzahl der benötigten Prüfläufe schnell in die Höhe treibt:

• 2 Objekte: 1 Kollisionstest
• 3 Objekte: 3 Kollisionstests
• 4 Objekte: 6 Kollisionstests
• 16 Objekte: 120 Kollisionstests
• 100 Objekte: 4950 Kollisionstests
• N Objekte: 0.5*N*(N-1) Kollisionstests

Das Ziel aller Optimierungstechniken muss es sein, die Anzahl der zu testenden Objektpaarungen so klein wie möglich zu halten. Eine Möglichkeit, dies zu erreichen, besteht darin, bestimmte Paarungen (Bsp. Waffenprojektil – Waffenprojektil) von vorneherein auszuschließen.
Die mit Abstand wichtigste Technik zur Vermeidung unnötiger Kollisionstests besteht jedoch in der Sektorisierung der Spielewelt. Hierbei wird die Anzahl der möglichen Objektpaarungen dadurch reduziert, dass nur diejenigen Objekte auf eine Kollision hin überprüft werden, die sich im selben Sektor befinden.

Schnittpunktberechnung: Strahl schneidet Dreieck (bzw. Polygon)

Im heutigen Artikel werden wir darüber sprechen, wie sich der Schnittpunkt eines Strahls mit einem Dreieck (bzw. Polygon) berechnen oder aber frühzeitig ausschließen lässt – ein unverzichtbares mathematisches Verfahren, wenn wir bei einem Treffer- bzw. Kollisionstest die einzelnen Dreiecke des Render- oder Kollisionsmeshes berücksichtigen wollen.

Portale (Indoor-Szenen-Management)

Vernünftiges Szenen-Management ist eines der Schlüsselelemente für die Performance eines Spiels, da sich auf diese Weise eine Vielzahl unnötiger Berechnungen vermeiden lassen. Dies betrifft nicht nur die grafische Darstellung sondern auch Kollisionsprüfungen, KI (künstliche Intelligenz) und Spielephysik.

Für das Handling von Indoor-Szenen bietet sich der Einsatz von Portalen an. Vereinfacht kann man sich Portale wie Türöffnungen vorstellen, die einzelne Räume (bzw. Sektoren) miteinander verbinden. Im Unterschied zu Türöffnungen funktionieren Portale jedoch nur in eine Richtung – für gewöhnlich wird ein Portal stets dem Raum zugeordnet, der durch das Portal verlassen werden kann.
Betritt nun eine Spielfigur einen neuen Raum, dann müssen etwaige Kollisionsprüfungen nur mit den Elementen des neu betretenden Raumes durchgeführt werden. Physische Interaktionen sind natürlich auch nur mit Objekten möglich, die sich im selben Raum befinden. Des Weiteren bietet der Einsatz von Portalen eine elegante Möglichkeit für die Bestimmung der sichtbaren Räume bzw. Sektoren und der darin befindlichen Objekte – ein Raum oder Sektor ist immer dann sichtbar, wenn mindestens eines der in den Raum führenden Portale für den Spieler einsehbar ist (darüber hinaus ist natürlich auch derjenige Raum sichtbar, in dem sich der Spieler augenblicklich befindet).

Schnittpunktberechnung: Strahl schneidet Ebene

Bei der Durchführung von Kollisions- und Treffertests gilt es abzuwiegen zwischen der Genauigkeit und dem damit verbundenen Rechenaufwand. Größte Genauigkeit erreicht man, indem man die Tests mit den einzelnen Dreiecksflächen des 3D-Rendermodells oder mit denjenigen des 3D-Kollisionsmodells (Mesh mit kleinerem Polygon Count; es wird weniger Rechenzeit für die Durchführung der Kollisions- und Treffertests benötigt) durchführt. Bevor wir uns jedoch mit diesen Tests befassen können, müssen wir uns zunächst einige mathematische Grundlagen erarbeiten.

Orientierte Bounding-Boxen (OBB), OBB-OBB-Kollisionstest

Spieleobjekte unterliegen beständigen Transformationen. Ändert sich beispielsweise ihre Orientierung, dann betrifft diese Änderung nicht allein das 3D-Modell; auch das verwendete Kollisionsmodell muss entsprechend transformiert werden.
Verwendet man ein Kollisionsmodell auf Basis von Bounding-Sphären, dann ändern sich dabei lediglich die Positionen der einzelnen Bounding-Sphären. Komplizierter ist die Situation bei einem Kollisionsmodell auf Basis von Bounding-Boxen, denn hier ändern sich zusätzlich dazu auch die Orientierungen der einzelnen Boxen. In diesem Zusammenhang spricht man von sogenannten orientierten Bounding-Boxen (OBB).

Kollisionen an beliebig orientierten Flächen

Bei der Verwendung von achsenausgerichteten Bounding-Boxen (AABB) werden im Zuge des Kollisions-Handlings nur die sechs achsenparallelen Kollisionsflächen der Boxen bei der Berechnung der Bewegungsrichtungen nach einer Kollision berücksichtigt. Dies führt zu teils starken Abweichungen vom realen Verhalten der Kollisionspartner, was den meisten Spielern natürlich nicht verborgen bleibt – kurzum, man bemerkt schnell, dass hier irgendetwas nicht stimmt, dass getrickst wurde.
Mithilfe von Bounding-Sphären ist hingegen eine deutlich realistischere Kollisionsbeschreibung möglich, da es keinerlei Beschränkungen bei der Anzahl der möglichen Kollisionsflächen gibt. Bei einer Kollision zweier Sphären lässt sich jedem denkbaren Kontaktpunkt eine separate Kollisionsfläche zuordnen.

Kollisionen an achsenparallelen Flächen

Der heutige Artikel widmet sich der Beschreibung von Kollisionen an achsenparallelen Flächen – also Flächen in der xy-, in der xz- oder in der yz-Ebene. Diese sind am einfachsten zu beschreiben und daher ein guter Einstieg in die Materie.
Ausgangspunkt für unsere Überlegungen ist das Reflektionsgesetz, welches Ihnen vielleicht noch aus der Schulzeit vertraut ist:

Einfallswinkel = Ausfallswinkel

Schnittpunktberechnung: Strahl schneidet Kugel/Ellipsoid

Gleißende Phasersalven und glühende Schutzschilde; vom mathematischen Standpunkt aus betrachtet sind Phasersalven Strahlen und glühende Schutzschilde Kugelschalen bzw. Ellipsoide, die von den Strahlen geschnitten werden.

Achsenausgerichtete Bounding-Boxen (AABB)

Im Rahmen von Kollisionsberechnungen finden neben Bounding-Sphären auch Bounding-Boxen Verwendung. An dieser Stelle werden wir uns lediglich mit achsenausgerichteten Boxen befassen, die eine genau definierte Höhe, Breite und Länge (Ausdehnung in x-, y- und z-Richtung) unabhängig von der momentanen Orientierung der umschlossenen Spieleobjekte besitzen. Wird hingegen die Ausrichtung einer Bounding-Box an die Orientierung des zugehörigen Spieleobjekts angepasst (kurz: Dreht sich das Objekt, dann wird die Box mitgedreht), spricht man von einer orientierten Bounding-Box (OBB).
Für die Beschreibung einer AABB kann die folgende Struktur verwendet werden:

Der Bounding-Sphären-Test

Der Bounding-Sphären-Test stellt eine sehr einfache Methode zum Ausschluss unnötiger Treffer- und Kollisionsberechnungen dar. Eine Bounding-Sphäre (bounding sphere) ist schnell erzeugt, man definiert einen entsprechend großen Kollisionsradius, so dass das zugehörige Spieleobjekt vollständig von der Sphäre eingeschlossen ist.
Bei einem Trefferausschluss-Test kann die Bounding-Sphäre des Projektils vernachlässigt werden, da diese normalerweise deutlich kleiner ist als die des möglicherweise getroffenen Objekts. Ist nun der quadratische Abstand zwischen Projektil und Sphärenmittelpunkt kleiner als der quadratische Radius der Sphäre, dann liegt ein Treffer im Bereich des Möglichen (Hinweis: Man betrachtet den quadratischen Abstand, da dessen Bestimmung weniger aufwändiger ist und ohne Wurzelberechnungen auskommt).