Advanced Game Physics - Exam

Aufgabe 1)

Betrachten Sie ein physikalisches System, das durch zwei Massenpunkte beschrieben wird, die durch eine Feder verbunden sind. Beide Massenpunkte bewegen sich in einer Ebene und unterliegen keinem Luftwiderstand. Die Massepunkte haben die Massen m_1 und m_2 und die Feder hat eine Federkonstante k und eine Ruhelänge l_0. Die Positionen der Massenpunkte zu einem Zeitpunkt t sind durch die Vektoren \(\textbf{r}_1(t)\) und \(\textbf{r}_2(t)\) gegeben. Entwickeln Sie ein numerisches Simulationsmodul zur Berechnung der Bewegung dieser Massenpunkte unter Verwendung der Methode von Euler und der Methode von Runge-Kutta 4. Ordnung.

a)

• Implementiere die Bewegungsgleichungen für die beiden Massenpunkte unter Berücksichtigung der Federkraft. Gehe dabei von den Newton'schen Bewegungsgleichungen aus und schreibe die entsprechenden Differentialgleichungen auf. Beachte dabei, dass die Federkraft \( \textbf{F}_\text{feder} = -k(\textbf{r} - l_0)\) ist.
• Implementiere sowohl das Euler-Verfahren als auch das Runge-Kutta 4. Ordnung Verfahren in Python zur numerischen Lösung der Bewegungsgleichungen. Veranschauliche die Bewegung der Massenpunkte über die Zeit durch Plots ihrer Bahnen.

Lösung:

Um die Bewegung der beiden Massenpunkte, die durch eine Feder verbunden sind, zu simulieren, müssen wir die Newton'schen Bewegungsgleichungen aufstellen und darauf basierende Differentialgleichungen formulieren. Anschließend implementieren wir die numerische Lösung dieser Gleichungen sowohl mit dem Euler-Verfahren als auch dem Runge-Kutta-Verfahren 4. Ordnung und visualisieren die Bewegung der Massenpunkte.

Bewegungsgleichungen:

Betrachte folgendes System:

• Massenpunkte mit Massen: \(m_1\) und \(m_2\)
• Feder mit Federkonstante: \(k\)
• Ruhelänge der Feder: \(l_0\)
• Positionen der Massenpunkte: \(\textbf{r}_1(t)\) und \(\textbf{r}_2(t)\)

Diese Kräfte resultieren in folgenden Newton'schen Bewegungsgleichungen:

• Für den ersten Massenpunkt:

 m_1 \frac{d^2 \textbf{r}_1}{dt^2} = \textbf{F}_\text{feder} 

m_2 \frac{d^2 \textbf{r}_2}{dt^2} = -\textbf{F}_\text{feder} 

Die Federkraft \(\textbf{F}_\text{feder}\) ist gegeben durch:

\textbf{F}_\text{feder} = k \frac{\textbf{r}_2 - \textbf{r}_1}{|\textbf{r}_2 - \textbf{r}_1|} (|\textbf{r}_2 - \textbf{r}_1| - l_0) 

Numerische Lösung:

Implementierung der Euler-Methode und Runge-Kutta-Methode 4. Ordnung in Python:

Euler-Verfahren:

import numpy as npimport matplotlib.pyplot as pltdef euler_integration(f, y0, t0, tf, dt):    t = np.arange(t0, tf, dt)    n = len(t)    y = np.zeros((n, len(y0)))    y[0] = y0    for i in range(1, n):        y[i] = y[i-1] + dt * f(y[i-1], t[i-1])    return t, ydef equations(y, t):    m1, m2 = 1.0, 1.0  # Massen    k = 1.0  # Federkonstante    l0 = 1.0  # Ruhelänge    r1, v1, r2, v2 = y[0:2], y[2:4], y[4:6], y[6:8]    r12 = r2 - r1    dist = np.linalg.norm(r12)    F_feder = k * (dist - l0) * (r12 / dist)    dr1_dt = v1    dv1_dt = F_feder / m1    dr2_dt = v2    dv2_dt = -F_feder / m2    return np.hstack([dr1_dt, dv1_dt, dr2_dt, dv2_dt])y0 = np.array([0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0])  # Anfangswertet, y = euler_integration(equations, y0, 0, 10, 0.01)plt.plot(y[:, 0], y[:, 1], label='Masse 1')plt.plot(y[:, 4], y[:, 5], label='Masse 2')plt.legend()plt.show()

Runge-Kutta 4. Ordnung:

def runge_kutta_integration(f, y0, t0, tf, dt):    t = np.arange(t0, tf, dt)    n = len(t)    y = np.zeros((n, len(y0)))    y[0] = y0    for i in range(1, n):        k1 = f(y[i-1], t[i-1])        k2 = f(y[i-1] + 0.5 * dt * k1, t[i-1] + 0.5 * dt)        k3 = f(y[i-1] + 0.5 * dt * k2, t[i-1] + 0.5 * dt)        k4 = f(y[i-1] + dt * k3, t[i-1] + dt)        y[i] = y[i-1] + dt/6 * (k1 + 2*k2 + 2*k3 + k4)    return t, yy0 = np.array([0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0])  # Anfangswertet, y = runge_kutta_integration(equations, y0, 0, 10, 0.01)plt.plot(y[:, 0], y[:, 1], label='Masse 1')plt.plot(y[:, 4], y[:, 5], label='Masse 2')plt.legend()plt.show()

b)

• Implementiere eine Kollisionsdetektion für die beiden Massenpunkte. Verwende dafür das Separating Axis Theorem (SAT) und berechne, wann die Massenpunkte kollidieren. Zeige, wie man durch Implementierung einer Bounding Volume Hierarchy (BVH) die Effizienz des Kollisionsdetektionsalgorithmus verbessern kann.
• Erkläre, wie du die numerische Integration über die Zeit stabilisierst und wie du Optimierungsmethoden einsetzt, um die Simulationseffizienz zu maximieren. Diskutiere die Vor- und Nachteile der verschiedenen numerischen Methoden, die du verwendet hast.

Lösung:

Um eine Kollisionsdetektion für die beiden Massenpunkte zu implementieren, verwenden wir das Separating Axis Theorem (SAT) und die Bounding Volume Hierarchy (BVH) zur Effizienzsteigerung. Wir stabilisieren die numerische Integration über die Zeit und diskutieren Optimierungsmethoden, um die Simulationseffizienz zu maximieren.

Kollisionsdetektion mit dem Separating Axis Theorem (SAT):

Das Separating Axis Theorem ermöglicht die Feststellung von Kollisionen zwischen konvexen Körpern, indem überprüft wird, ob eine trennende Achse existiert. Für zwei Massenpunkte können wir dies vereinfachen, da Massenpunkte als kleine sphärische Körper betrachtet werden können.

import numpy as npdef detect_collision(r1, r2, radius1, radius2):    distance = np.linalg.norm(r2 - r1)    return distance < (radius1 + radius2)# Beispielpositionen und Radienr1 = np.array([1.0, 1.0])r2 = np.array([2.0, 2.0])radius1 = 0.5radius2 = 0.5collision = detect_collision(r1, r2, radius1, radius2)print(f'Kollision: {collision}')

Bounding Volume Hierarchy (BVH):

Die Verwendung einer Bounding Volume Hierarchy (BVH) verbessert die Effizienz der Kollisionsdetektion, indem die Anzahl der zu prüfenden Kollisionspaare reduziert wird. Ein BVH strukturiert die Objekte in einer hierarchischen Weise und verwendet einfache Hüllkörper (Bounding Volumes) zur schnellen Vorauswahl potenzieller Kollisionen.

Implementierung einer einfachen BVH:

class BVHNode:    def __init__(self, objects):        self.objects = objects        self.left = None        self.right = None        self.bounding_volume = self.compute_bounding_volume(objects)    def compute_bounding_volume(self, objects):        # Berechne das Bounding Volume für die aktuellen Objekte        pass    def build(self):        if len(self.objects) > 1:            # Teile die Objekte in zwei Gruppen und erstelle Kinderknoten            middle = len(self.objects) // 2            self.left = BVHNode(self.objects[:middle])            self.right = BVHNode(self.objects[middle:])            self.left.build()            self.right.build()    def traverse_and_detect_collisions(self, r1, radius1):        # Prüfe Bounding Volume        if not self.bounding_volume.collides_with(r1, radius1):            return False        # Falls keine Kinderknoten, überprüfe tatsächliche Kollisionen        if self.left is None and self.right is None:            for obj in self.objects:                if detect_collision(r1, obj.position, radius1, obj.radius):                    return True            return False        # Falls Kinderknoten, traverse in die Knoten        return (self.left and self.left.traverse_and_detect_collisions(r1, radius1)) or (self.right and self.right.traverse_and_detect_collisions(r1, radius1))# Beispielnutzungobjects = [...]  # Liste der Objekte mit Positionen und Radienroot = BVHNode(objects)root.build()collision = root.traverse_and_detect_collisions(r1, radius1)print(f'Kollision: {collision}')

Stabilisierung der numerischen Integration:

Stabilisierungstechniken helfen dabei, die Genauigkeit der numerischen Integration zu gewährleisten:

• Zeitschrittwahl: Wähle den Zeitschritt klein genug, um die Dynamik des Systems korrekt abzubilden. Beachte, dass ein zu großer Zeitschritt zu Instabilitäten führen kann.
• Verlustfreie Energie: Reduziere Energieverluste und andere Fehlerquellen durch genaue Berechnung der Feder- und Bewegungsgleichungen.
• Verwendung des Runge-Kutta-Verfahrens: Das Runge-Kutta-Verfahren 4. Ordnung bietet höhere Genauigkeit und Stabilität im Vergleich zum einfachen Euler-Verfahren.

Optimierungsmethoden:

Um die Effizienz der Simulation zu maximieren:

• Verwendung von vektorisierter Berechnung: Nutze numpy für vektorisierte Operationen, um die Rechenzeit zu reduzieren.
• Zwischenwerte speichern: Speichere häufig benötigte Werte (z.B. normierte Vektoren), um Berechnungen zu vermeiden.
• Adaptive Zeitschritte: Erhöhe die Zeitauflösung dynamisch, wenn schnelle Änderungen auftreten, und verringere sie, wenn das System stabil ist.

Vor- und Nachteile der numerischen Methoden:

• Euler-Verfahren:
  • Vorteile: Einfach zu implementieren, geringe Rechenkosten.
  • Nachteile: Geringe Genauigkeit, instabil für große Zeitschritte.
• Runge-Kutta-Verfahren 4. Ordnung:
  • Vorteile: Hohe Genauigkeit, stabiler für größere Zeitschritte.
  • Nachteile: Höhere Rechenkosten, komplexere Implementierung.

Aufgabe 2)

In einem 3D-Simulationsspiel müssen Kollisionen zwischen den Charakteren erfasst werden. Zwei Arten von Kollisionsdetektionen kommen zum Einsatz: AABB (Axis-Aligned Bounding Box) und OBB (Oriented Bounding Box). AABBs sind Boxen, die an den Achsen des Koordinatensystems ausgerichtet sind. Sie werden durch ihre minimalen und maximalen Koordinaten entlang der Achsen definiert. OBBs hingegen sind frei ausgerichtete Boxen, die durch ihre Mittelpunkte, Halbachsen und die Orientierungen der Boxen definiert werden. Ein grundlegender Ansatz zur Kollisionsprüfung besteht darin, die Projektionen der Boxen entlang der Achsen zu überprüfen. Speziell für OBBs wird der Separating Axis Theorem (SAT) angewandt, um zu überprüfen, ob Trennungsebenen existieren, die eine Kollision verhindern. Beachte, dass AABB-Kollisionsprüfungen schneller sind, aber weniger genau, während OBB-Kollisionsprüfungen präziser, aber rechnerisch intensiver sind.

a)

Implementiere in Python eine Funktion, die prüft, ob zwei AABB-Boxen kollidieren. Der Funktion sollen die minimalen und maximalen Koordinaten der beiden Boxen übergeben werden. Eine Kollision liegt vor, wenn sich die Projektionen der Boxen entlang aller Achsen überschneiden. So könnte der Anfang der Funktion aussehen:

def aabb_collision(min_a, max_a, min_b, max_b):    # Deine Implementierung hier    pass

Lösung:

• Der Kern der Kollisionsprüfung für AABB-Boxen (Axis-Aligned Bounding Box) besteht darin, entlang jeder Achse (x, y, und z) zu überprüfen, ob sich die Projektionen der Boxen überschneiden.

def aabb_collision(min_a, max_a, min_b, max_b):    # Prüfen auf Überschneidung entlang der x-Achse    if max_a[0] < min_b[0] or min_a[0] > max_b[0]:        return False    # Prüfen auf Überschneidung entlang der y-Achse    if max_a[1] < min_b[1] or min_a[1] > max_b[1]:        return False    # Prüfen auf Überschneidung entlang der z-Achse    if max_a[2] < min_b[2] or min_a[2] > max_b[2]:        return False    # Wenn keine Trennung entlang der Achsen gefunden, liegt eine Kollision vor    return True

• Erklärung:
• Die Funktion aabb_collision bekommt vier Parameter: min_a und max_a sind die minimalen und maximalen Koordinaten der ersten AABB-Box, und min_b und max_b sind die entsprechenden Koordinaten der zweiten AABB-Box.
• Jeder dieser Parameter ist eine Liste oder ein Tupel mit drei Elementen, die die Koordinaten in den x-, y- und z-Richtungen repräsentieren.
• Die Funktion prüft entlang jeder Achse, ob eine Trennung existiert. Wenn mindestens eine Trennung existiert, gibt es keine Kollision und die Funktion gibt False zurück.
• Wenn keine Trennung entlang aller drei Achsen gefunden wird, liegt eine Kollision vor und die Funktion gibt True zurück.

c)

Angenommen, du hast die Koordinaten zweier OBB-Boxen gegeben: Die OBB A mit Mittelpunkt (\textbf{c_a}) = (1, 2, 3), Halbachsen (\textbf{u_a1}, \textbf{u_a2}, \textbf{u_a3}) = ((1, 0, 0), (0, 1, 0), (0, 0, 1)) und Längen (l_a1, l_a2, l_a3) = (2, 2, 2), sowie die OBB B mit Mittelpunkt (\textbf{c_b}) = (5, 2, 3), Halbachsen (\textbf{u_b1}, \textbf{u_b2}, \textbf{u_b3}) = ((0.707, 0.707, 0), (-0.707, 0.707, 0), (0, 0, 1)) und Längen (l_b1, l_b2, l_b3) = (3, 1, 1). Berechne, ob diese OBBs sich überschneiden oder nicht, indem du die Begrifflichkeiten und Formeln des Separating Axis Theorems verwendest.

Lösung:

Um zu bestimmen, ob sich die beiden OBBs überschneiden, verwenden wir das Separating Axis Theorem (SAT). Hier sind die detaillierten Schritte zu dieser Kollisionsprüfung:

1. Definiton der OBB-Parameter

• OBB_A:
  • Mittelpunkt \( \textbf{{c_a}} \): (1, 2, 3)
  • Halbachsen \( (\textbf{{u_a1}}, \textbf{{u_a2}}, \textbf{{u_a3}}) \): ((1, 0, 0), (0, 1, 0), (0, 0, 1))
  • Längen \( (l_a1, l_a2, l_a3) \): (2, 2, 2)
• OBB_B:
  • Mittelpunkt \( \textbf{{c_b}} \): (5, 2, 3)
  • Halbachsen \( (\textbf{{u_b1}}, \textbf{{u_b2}}, \textbf{{u_b3}}) \): ((0.707, 0.707, 0), (-0.707, 0.707, 0), (0, 0, 1))
  • Längen \( (l_b1, l_b2, l_b3) \): (3, 1, 1)

2. Bestimmung der potenziellen Trennachsen

• Diese werden durch die Orientierungsvektoren der OBBs und ihre Kreuzprodukte definiert:
• Achsen der OBB_A:
  • \( \textbf{{u_a1}}, \textbf{{u_a2}}, \textbf{{u_a3}} \)
• Achsen der OBB_B:
  • \( \textbf{{u_b1}}, \textbf{{u_b2}}, \textbf{{u_b3}} \)
• Kreuzprodukte von Achsen der OBB_A und OBB_B:
  • \( \textbf{{u_a1}} \times \textbf{{u_b1}}, \textbf{{u_a1}} \times \textbf{{u_b2}}, \textbf{{u_a1}} \times \textbf{{u_b3}}, \textbf{{u_a2}} \times \textbf{{u_b1}}, \textbf{{u_a2}} \times \textbf{{u_b2}}, \textbf{{u_a2}} \times \textbf{{u_b3}}, \textbf{{u_a3}} \times \textbf{{u_b1}}, \textbf{{u_a3}} \times \textbf{{u_b2}}, \textbf{{u_a3}} \times \textbf{{u_b3}} \)

3. Projektion der OBBs auf die Trennachsen

• Für jede Achse berechne die Projektionen der Mittelpunkte und Halbachsen der beiden OBBs.

Beispiel für die Trennachse \( \textbf{{u_a1}} \)

• Projektion des Mittelpunkts und der Halbachse:
• Position der OBB-A:
• \( \text{proj}_{u_a1}(c_a) = (1 \times 1) + (2 \times 0) + (3 \times 0) = 1 \)
• Position der OBB-B:
• \( \text{proj}_{u_a1}(c_b) = (5 \times 1) + (2 \times 0) + (3 \times 0) = 5 \)

Projektion der Halbachsen:

• Projizierte Länge der Halbachse von OBB_A:
• \( l_a1 \times |u_a1 \cdot u_a1| = 2 \times |1 \times 1| = 2 \)
• Projizierte Länge der Halbachse von OBB_B:
• \( l_b1 \times |u_b1 \cdot u_a1| = 3 \times |0.707 \times 1| = 2.121 \)

Überprüfung der Überlappung:

• Projizierte Intervalle:
• OBB_A: \( [ 1 - 2, 1 + 2 ] = [-1, 3] \)
• OBB_B: \( [ 5 - 2.121, 5 + 2.121 ] = [2.879, 7.121] \)

Weil \([ -1, 3 ] \) und \([2.879, 7.121] \) nicht überlappen, gibt es entlang der Achse \( \textbf{{u_a1}} \) keine Kollision.

Wir müssten die gleiche Berechnung für jede der 15 Trennachsen anstellen. Wenn keine Trennachse gefunden wird, auf der sich die Projektionen nicht überschneiden, gibt es keine Kollision.

Aufgabe 3)

Du arbeitest an einem Echtzeit-Physiksimulator, der die Bewegung und Kollision von Objekten in einer 3D-Umgebung simuliert. Zur Optimierung der Kollisionserkennung soll ein mehrstufiger Ansatz verwendet werden, der effiziente Methoden zur Erkennung und Behandlung von Kollisionen zwischen Objekten integriert.

• Verwendung von Bounding Volumes: AABB, OBB, Sphären
• Schrittweise Verfeinerung: Stack-basierte Kollisionsprüfung
• Breitphasen- und Engphasen-Kollisionserkennung
• Algorithmus von Gilbert-Johnson-Keerthi (GJK) zur minimalen Distanz
• Konvexe Hülle und Minkowski-Differenz
• Simulationsauflösung und Taktung vs. Performance
• Vermeidungsstrategien: Pseudokräfte und Trennvektoren
• Fixpunktarithmetik zur Vermeidung numerischer Instabilitäten
• Optimierung durch Spatial Partitioning: Quadtrees, Octrees, BSP-Trees

a)

(a) Beschreibe den Unterschied und die Vor- und Nachteile der Verwendung von Axis-Aligned Bounding Boxes (AABB), Oriented Bounding Boxes (OBB) und Bounding Spheres für die Kollisionserkennung in Echtzeitanwendungen.

Lösung:

(a) Die Kollisionserkennung in Echtzeitanwendungen kann durch verschiedene Methoden der Bounding Volumes optimiert werden. Im Folgenden werden die Unterschiede, Vor- und Nachteile von Axis-Aligned Bounding Boxes (AABB), Oriented Bounding Boxes (OBB) und Bounding Spheres beschrieben.

• Axis-Aligned Bounding Boxes (AABB):
  • Unterschied: AABBs sind rechteckige Boxen, deren Kanten parallel zu den Koordinatenachsen ausgerichtet sind.
  • Vorteile:
    • Sehr einfache und schnelle Berechnung und Prüfung von Kollisionen, da nur minimale/maximale Werte entlang der Achsen verglichen werden.
    • Effizient in der Breitphasen-Kollisionserkennung.
  • Nachteile:
    • Bieten keine ideale Anpassung an die Form von Objekten, insbesondere bei stark rotierenden Objekten.
    • Können größere Volumina einnehmen als nötig, was zu unnötiger Prüfung führen kann.
• Oriented Bounding Boxes (OBB):
  • Unterschied: OBBs sind rechteckige Boxen, deren Kanten nicht notwendigerweise mit den Koordinatenachsen ausgerichtet sind und beliebige Orientierungen annehmen können.
  • Vorteile:
    • Bessere Anpassung an die tatsächliche Form des Objekts, besonders wenn das Objekt rotiert.
    • Können kleinere Volumina um das Objekt umfassen, was die Präzision der Kollisionserkennung erhöht.
  • Nachteile:
    • Kollisionsprüfung ist rechnerisch komplexer und zeitaufwendiger als bei AABBs.
    • Erfordert zusätzliche Berechnungen zur Bestimmung der OBB und deren Transformationen.
• Bounding Spheres:
  • Unterschied: Bounding Spheres sind kugelförmige Begrenzungen, die durch ihren Mittelpunkt und Radius definiert werden.
  • Vorteile:
    • Sehr einfache und schnelle Berechnung und Prüfung von Kollisionen, da nur der Abstand zwischen Mittelpunkten überprüft werden muss.
    • Unabhängig von der Ausrichtung des Objekts.
  • Nachteile:
    • Bieten keine ideale Anpassung an die Form von länglichen oder asymmetrischen Objekten.
    • Können größere Volumina einnehmen als nötig, was zu unnötigen Kollisionsprüfungen führt.

b)

(b) Erläutere den mehrstufigen Ansatz der Kollisionserkennung mit Breitphasen- und Engphasen-Kollisionserkennung. Gib Beispiele für algorithmische Techniken, die in jeder Phase verwendet werden.

Lösung:

(b) Der mehrstufige Ansatz der Kollisionserkennung in Echtzeitanwendungen besteht typischerweise aus zwei Hauptphasen: der Breitphasen- und der Engphasen-Kollisionserkennung. Diese zwei Ebenen sorgen dafür, dass Kollisionen effizient und genau erkannt werden.

• Breitphasen-Kollisionserkennung:
  • Ziel: In dieser Phase werden potenzielle Kollisionen schnell identifiziert, indem große Gruppen von Objekten auf offensichtliche Kollisionen überprüft werden. Es sollen unnötige Berechnungen durch die spätere Engphasenprüfung vermieden werden.
  • Algorithmische Techniken:
    • Sort & Sweep: Objekte werden entlang einer Achse sortiert und ihre Intervalle (z.B. Bounding Volumes) werden auf Überschneidungen überprüft.
    • Spatial Partitioning: Die Umgebung wird in Zellen oder Regionen unterteilt, wie Quadtrees (2D) oder Octrees (3D), um nur nahegelegene Objekte miteinander zu vergleichen.
    • Bounding Volume Hierarchies (BVH): Hierarchien von Bounding Volumes wie AABBs oder OBBs werden erstellt, um schnell potenzielle Kollisionen zu finden.
• Engphasen-Kollisionserkennung:
  • Ziel: In dieser Phase werden die potenziell kollidierenden Objekte, die in der Breitphase identifiziert wurden, genauer untersucht. Es wird mit präziseren Methoden überprüft, ob tatsächlich eine Kollision vorliegt.
  • Algorithmische Techniken:
    • Gilbert-Johnson-Keerthi (GJK) Algorithmus: Dieser Algorithmus wird verwendet, um die minimale Distanz zwischen konvexen Polyedern zu berechnen und Kollisionen festzustellen.
    • Separating Axis Theorem (SAT): Diese Methode prüft, ob es eine Trennungsebene (Separating Axis) zwischen zwei konvexen Körpern gibt. Wenn keine solche Ebene existiert, liegt eine Kollision vor.
    • Continuous Collision Detection (CCD): Diese Technik berücksichtigt die Bewegungsgeschwindigkeit und Bahn der Objekte, um Tunnel-Effekte zu vermeiden und genaueres Timing der Kollisionen zu bestimmen.

Durch die Kombination dieser beiden Ebenen wird die Kollisionserkennung sowohl effizient als auch präzise.

c)

(c) Implementiere den Algorithmus von Gilbert-Johnson-Keerthi (GJK) zur Bestimmung der minimalen Distanz zwischen zwei konvexen Polyedern. Zeige anhand eines Beispiels, wie die Konvexe Hülle und die Minkowski-Differenz in diesem Kontext verwendet werden.

'pythondef gjk_algorithm(shape1, shape2):    # Grundlegende GJK-Algorithmus-Implementierungdefined by algorithm {'implement_basic_algorithm_here'}

Lösung:

(c) Der Algorithmus von Gilbert-Johnson-Keerthi (GJK) ist eine effiziente Methode zur Bestimmung der minimalen Distanz zwischen zwei konvexen Polyedern. Der Algorithmus nutzt das Konzept der Minkowski-Differenz und der konvexen Hülle, um festzustellen, ob zwei konvexe Polyeder kollidieren. Hier ist eine grundlegende Implementierung des GJK-Algorithmus in Python und ein Beispiel, wie die konvexe Hülle und Minkowski-Differenz in diesem Kontext verwendet werden.

• Grundlegende Konzepte:
  • Konvexe Hülle: Die konvexe Hülle eines Satzes von Punkten ist der kleinste konvexe Polyeder, der alle Punkte enthält.
  • Minkowski-Differenz: Die Minkowski-Differenz zweier Mengen A und B ist die Menge aller Vektoren, die man erhält, indem man einen Punkt aus A von einem Punkt aus B subtrahiert.

Hier ist die Implementierung des GJK-Algorithmus:

'pythonimport numpy as npdef support(shape, direction):    # Find the point in the shape that is farthest in the given direction    return max(shape, key=lambda point: np.dot(point, direction))def gjk_algorithm(shape1, shape2):    # Initial direction    direction = np.array([1, 0, 0])    # Create the initial simplex    simplex = [support(shape1, direction) - support(shape2, -direction)]    # Reverse the direction    direction = -simplex[0]        while True:        # Add a new point to the simplex        new_point = support(shape1, direction) - support(shape2, -direction)        if np.dot(new_point, direction) <= 0:            return False # No collision        simplex.append(new_point)        if check_simplex(simplex, direction):            return True # Collision detecteddef check_simplex(simplex, direction):    # Check if the simplex contains the origin    # Handle different simplex configurations (line, triangle, tetrahedron)    if len(simplex) == 2:        # Line segment case        return line_case(simplex, direction)    elif len(simplex) == 3:        # Triangle case        return triangle_case(simplex, direction)    elif len(simplex) == 4:        # Tetrahedron case        return tetrahedron_case(simplex, direction)    return Falsedef line_case(simplex, direction):    # Implement line case handling    passdef triangle_case(simplex, direction):    # Implement triangle case handling    passdef tetrahedron_case(simplex, direction):    # Implement tetrahedron case handling    passdef example_usage():    # Example shapes (convex polyhedra)    shape1 = [np.array([1, 1, 1]), np.array([-1, 1, 1]), np.array([1, -1, 1]), np.array([1, 1, -1])]    shape2 = [np.array([2, 2, 2]), np.array([0, 2, 2]), np.array([2, 0, 2]), np.array([2, 2, 0])]    print(gjk_algorithm(shape1, shape2)) # Outputs True or False

In diesem Beispiel wird die `support`-Funktion verwendet, um die Punkte in den Formen in die angegebene Richtung zu finden, die am weitesten entfernt sind. Der `gjk_algorithm` baut schrittweise ein Simplex auf und überprüft, ob das Simplex den Ursprung enthält, was auf eine Kollision hinweist.

Die `check_simplex`, `line_case`, `triangle_case` und `tetrahedron_case` Funktionen müssen noch implementiert werden, um alle Fälle korrekt zu behandeln. Dies ist ein Beispiel für eine vereinfachte Version des GJK-Algorithmus.

d)

(d) Diskutiere die Vor- und Nachteile der Verwendung von Spatial Partitioning Techniken wie Quadtrees, Octrees und BSP-Trees zur Optimierung der Kollisionserkennung. Wann würde man welche Technik bevorzugen?

Lösung:

(d) Spatial Partitioning Techniken wie Quadtrees, Octrees und BSP-Trees spielen eine wichtige Rolle bei der Optimierung der Kollisionserkennung in Echtzeitanwendungen. Im Folgenden werden die Vor- und Nachteile dieser Techniken sowie mögliche Anwendungsszenarien diskutiert:

• Quadtrees:
  • Vorteile:
    • Quadtrees sind gut geeignet für 2D-Räume und bieten eine effiziente Raumeinteilung.
    • Sie ermöglichen schnelle Kollisionsprüfungen, da nur Objekte innerhalb des gleichen oder benachbarten Quadrants überprüft werden müssen.
    • Einfach zu implementieren und zu debuggen.
  • Nachteile:
    • Bei sehr ungleich verteilten Objekten können Quadtrees unausgeglichen werden, was die Effizienz verringert.
    • Nicht direkt auf 3D-Räume anwendbar.
  • Wann bevorzugen: Quadtrees sind ideal für 2D-Simulationen oder wenn die Umgebung relativ flach ist (z.B. bei Strategiespielkarten).
• Octrees:
  • Vorteile:
    • Octrees sind gut geeignet für 3D-Räume und bieten eine effiziente Möglichkeit, den Raum hierarchisch zu unterteilen.
    • Sie ermöglichen schnelle Kollisionsprüfungen in dreidimensionalen Umgebungen.
    • Gut skalierbar bei großen und komplexen Szenen.
  • Nachteile:
    • Komplexer zu implementieren und zu debuggen im Vergleich zu Quadtrees.
    • Bei sehr ungleich verteilten Objekten können Octrees unausgeglichen werden, was die Effizienz verringert.
  • Wann bevorzugen: Octrees sind die Methode der Wahl für 3D-Simulationen wie Echtzeit-3D-Rendering, physikalische Simulationen und dynamische Szenen mit komplexen Interaktionen.
• Binary Space Partitioning (BSP) Trees:
  • Vorteile:
    • BSP-Trees ermöglichen eine präzise Unterteilung des Raums durch die Verwendung von beliebigen Trennungsebenen anstelle von festen Achsen.
    • Sind besonders effizient bei der Sichtlinienprüfung und in Szenen mit vielen statischen Objekten.
    • Eignen sich gut für die statische Szenenanalyse und die Berechnung von Sichtbarkeits- und Kollisionsdaten im Voraus.
  • Nachteile:
    • Komplexer und rechenintensiver zu berechnen und zu aktualisieren, vor allem bei dynamischen Szenen.
    • Vorausberechnete BSP-Trees sind weniger flexibel gegenüber Veränderungen in der Szene.
  • Wann bevorzugen: BSP-Trees sind ideal für statische Szenen, wie Level-Geometrien in Computerspielen, bei denen die Sichtbarkeitsprüfung wichtig ist und die Szenengeometrie vorwiegend statisch bleibt.

Zusammenfassung:

• Quadtrees werden in 2D-Szenen bevorzugt.
• Octrees sind die beste Wahl für dynamische 3D-Umgebungen.
• BSP-Trees eignen sich hervorragend für statische Szenen und Sichtbarkeitsprüfungen.

Aufgabe 4)

Du entwickelst eine Echtzeitsimulation für physikalische Effekte in einem Computerspiel. Während der Testphase stellst Du fest, dass die Simulation nicht flüssig läuft und dass es gelegentlich zu erheblichen Verzögerungen kommt. Deine Aufgabe ist es, die Leistungsengpässe durch Optimierungstechniken zu identifizieren und zu beseitigen. Verwende Profiling-Tools, um herauszufinden, welche Teile des Codes verlangsamt werden und wende Techniken an, um die Performance der Simulation zu verbessern.

a)

Führe eine Profiling-Analyse der Echtzeitsimulation durch, um die Bottlenecks in deinem Code zu identifizieren. Beschreibe die genauen Schritte, die du unternommen hast, um diese Engpässe zu ermitteln, und welche Tools du verwendet hast (z.B. Valgrind, gprof). Erläutere deine Ergebnisse mit besonderem Fokus auf die Teile des Codes, die die meiste Laufzeit in Anspruch nehmen.

Lösung:

Durchführung einer Profiling-Analyse der Echtzeitsimulation

Um die Leistungsengpässe in Deiner Echtzeitsimulation zu identifizieren, sind detaillierte Schritte nötig. Hier ist die Vorgehensweise:

• Vorbereitung: Stelle sicher, dass Dein Projekt im Debug-Modus kompiliert ist, um Symbolinformationen zu erhalten. Dies erleichtert das Debugging und das Profiling.
• Wahl eines Profiling-Tools: Wähle ein geeignetes Profiling-Tool. In unserem Fall verwenden wir Valgrind und gprof, die weitverbreitet und leistungsfähig sind.

Schritte zur Durchführung der Profiling-Analyse:

• Schritt 1: Valgrind installieren

  sudo apt-get install valgrind

• Schritt 2: Simulation mit Valgrind ausführenFühre Deine Anwendung mit Valgrind aus, um eine ausführliche Profiling-Analyse zu erhalten:

  valgrind --tool=callgrind ./deine_anwendung

  Dadurch wird eine Datei callgrind.out.<pid> erstellt, die detaillierte Informationen über die Funktionsaufrufe und deren Laufzeit enthält.
• Schritt 3: Analyse der ErgebnisseUm die Ergebnisse besser sichtbar zu machen, verwende KCachegrind, ein GUI-Tool zur Visualisierung und Analyse der von Callgrind generierten Daten:

  sudo apt-get install kcachegrindkcachegrind callgrind.out.<pid>

  Du kannst nun die Ausführungszeiten der einzelnen Funktionen und deren Aufrufhierarchien analysieren. Insbesondere suchst Du nach Funktionen, die einen hohen Anteil an der Gesamtlaufzeit beanspruchen.
• Schritt 4: gprof verwendenErstelle Dein Projekt neu mit der Option für Profiling:

  g++ -pg -o deine_anwendung deine_quellen.cpp

  Führe die Anwendung aus, um die Profiling-Daten zu sammeln:

  ./deine_anwendung

  Dies erzeugt eine Datei namens gmon.out. Analysiere diese Datei mit gprof:

  gprof deine_anwendung gmon.out > analysis.txt

  Öffne die analysis.txt Datei, um die detaillierten Profiling-Ergebnisse zu betrachten.
• Ergebnisse und Engpässe:
  • CPU-Intensive Funktionen: Identifiziere Funktionen, die viel CPU-Zeit verbrauchen. In der Regel sind dies Teile des Codes, die komplexe Berechnungen ausführen.
  • Häufig aufgerufene Funktionen: Einige Funktionen könnten sehr oft aufgerufen werden und summieren so ihre Laufzeit.
  • Unnötige Berechnungen: Überprüfe, ob einige Berechnungen unnötig oft durchgeführt werden und ob sie optimiert oder außerhalb der Schleifen verschoben werden können.
  • Speicherzugriffsprobleme: Speicherzugriffszeiten können Engpässe verursachen, insbesondere bei Cache-Misses. Tools wie Valgrind helfen auch hier, ineffiziente Speicherzugriffe zu identifizieren.

Zusammenfassung:

Durch die detaillierte Profiling-Analyse mit Tools wie Valgrind und gprof konntest Du die Engpässe in Deiner Echtzeitsimulation identifizieren. Insbesondere hast Du Funktionen entdeckt, die die meiste Laufzeit in Anspruch nehmen, und Bereiche aufgedeckt, die optimiert werden können, um die Leistung zu verbessern. Deine nächsten Schritte umfassen die Optimierung dieser Codebereiche, um die Performance der Simulation zu erhöhen und Verzögerungen zu minimieren.

b)

Wende \textbf{Amdahls Gesetz} an, um die maximale Beschleunigung deiner Simulation durch Parallelisierung zu bewerten. Angenommen, 70% deines Programms können parallelisiert werden und du hast Zugang zu einem 8-Kern-Prozessor. Berechne die erwartete Beschleunigung (Speedup) und diskutiere, welche weiteren Optimierungsmöglichkeiten du in Betracht ziehen könntest, um die Performance zu verbessern. Zeige alle Berechnungen detailliert und in korrekter Latex-Notation.

Lösung:

Anwendung von Amdahls Gesetz auf die Parallelisierung der Simulation

Um die mögliche Beschleunigung (Speedup) Deiner Simulation durch Parallelisierung zu bewerten, verwenden wir Amdahls Gesetz. Laut Amdahls Gesetz ist die maximale Beschleunigung, die durch Parallelisierung erreicht werden kann, gegeben durch:

\begin{equation}S = \frac{1}{(1-P) + \frac{P}{N}}\end{equation}

wobei:P der parallelisierbare Anteil des Programms und N die Anzahl der Prozessoren ist.

Angenommen, 70% des Programms können parallelisiert werden (P = 0.7) und Du verwendest einen 8-Kern-Prozessor (N = 8), dann können wir die erwartete Beschleunigung wie folgt berechnen:

\begin{equation}S = \frac{1}{(1-0.7) + \frac{0.7}{8}}\end{equation}

Nun berechnen wir den Nenner:

\begin{equation}(1-0.7) + \frac{0.7}{8} = 0.3 + 0.0875 = 0.3875\end{equation}

Daher ist die maximale Beschleunigung (Speedup):

\begin{equation}S = \frac{1}{0.3875} \approx 2.58\end{equation}

Die maximale Beschleunigung beträgt also etwa 2.58.

Diskussion möglicher weiterer Optimierungen:

• Speichermanagement verbessern: Ineffizientes Speichermanagement kann die Leistung erheblich beeinträchtigen. Durch die Optimierung des Cachings, die Minimierung von Speicherzugriffen oder die Verwendung schnellerer Speicherpools kannst Du die Gesamtperformance verbessern.
• Algorithmische Optimierungen: Untersuche, ob effizientere Algorithmen eingesetzt werden können. Dies könnte bedeuten, dass weniger rechenaufwendige Algorithmen verwendet oder komplexe Berechnungen durch Näherungsverfahren ersetzt werden.
• Parallelisierungsstrategie überprüfen: Obwohl 70% des Programms parallelisiert werden können, ist es wichtig sicherzustellen, dass die Parallelisierung effizient umgesetzt wird. Tools und Bibliotheken wie CUDA, OpenMP oder TBB helfen dabei, die Parallelisierungsstrategie zu optimieren.
• Asynchrone Programmierung und Multi-Threading: Verwende asynchrone Programmierung oder Multi-Threading, um die Nutzung mehrerer Kerne zu maximieren. Dies kann dazu beitragen, die verbleibenden Engpässe im seriellen Teil des Programms zu reduzieren.
• Profiling und iterative Optimierung: Setze Profiling-Tools kontinuierlich ein, um Engpässe zu identifizieren und den Code iterativ weiter zu optimieren. Dadurch kannst Du weitere, bislang unerkannte Optimierungsmöglichkeiten entdecken.

Zusammenfassung: Durch Anwendung von Amdahls Gesetz haben wir festgestellt, dass der maximale Speedup bei etwa 2.58 liegt, wenn 70% der Simulation parallelisiert werden. Weitere Optimierungen können Speicherverwaltungsstrategien, algorithmische Verbesserungen, eine Überprüfung der Parallelisierungsstrategie und die kontinuierliche Nutzung von Profiling-Tools umfassen.