Advanced Game Physics - Cheatsheet

Mathematische Werkzeuge und Algorithmen für physikalische Simulationen

Definition:

Verwendung mathematischer Methoden und Algorithmen zur Berechnung und Darstellung physikalischer Phänomene in Simulationen.

Details:

• Differentialgleichungen: Lösen von Bewegungsgleichungen mittels Methoden wie Euler, Runge-Kutta.
• Lineare Algebra: Matrizen und Vektoren für Transformationen und Kollisionsberechnungen.
• Partikelsysteme: Simulation von Flüssigkeiten, Rauch, und anderen Systemen mithilfe von Kraftfeldern und Integrationsmethoden.
• Kollisionsdetection: Algorithmen wie Sweep and Prune, Bounding Volume Hierarchies (BVH), und Separating Axis Theorem (SAT).
• Numerische Integration: Diskretisierung zeitabhängiger Phänomene.
• Optimierung: Methoden zur Minimierung von Rechenaufwand und Maximierung der Simulationseffizienz.

Kollisionserkennung: AABB und OBB Algorithmen

Definition:

Kollisionserkennung mit AABB (Axis-Aligned Bounding Box) und OBB (Oriented Bounding Box) dient zur Überprüfung, ob sich zwei Objekte im 3D-Raum überlappen. AABBs sind an den Achsen ausgerichtete Boxen, OBBs sind beliebig orientierte Boxen.

Details:

• AABB: Berechnet durch min. und max. Koordinaten entlang der Achsen.
• OBB: Berechnet durch die Mittelpunkte, Halbachsen und Orientierungen der Box.
• Kollisionsvergleich AABB: Prüfe, ob sich Projektionen entlang der Achsen überschneiden.
• Kollisionsvergleich OBB: Separating Axis Theorem (SAT) verwenden, um Trennungsebenen zu finden.
• Effizienz: AABB schneller, aber weniger genau; OBB genauer, aber rechenintensiver.

Behandlung und Optimierung von Kollisionen in Echtzeitanwendungen

Definition:

Effiziente Methoden zur Erkennung und Behandlung von Kollisionen zwischen Objekten in Echtzeit.

Details:

• 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

Optimierungstechniken und Bottleneck-Analyse für Echtzeitsimulationen

Definition:

Optimierung von Echtzeitsimulationen durch Identifikation und Beseitigung von Leistungsengpässen.

Details:

• Profiling zur Identifikation von Bottlenecks
• Verwendung von \textbf{Amdahls Gesetz} zur Bewertung der maximalen Parallelisierung:

• Optimierungstechniken:
• Code-Aufteilung und Parallelisierung
• Optimierung von Speicherzugriffen
• Algorithmische Verbesserungen
• Verwendung von Profiling Tools (z.B. Valgrind, gprof)
• Leistungsmetriken wie Frame Time, CPU/GPU-Auslastung

Numerische Integration bei starren Körpern

Definition:

Integration von Bewegungsgleichungen für starre Körper zur Simulation in Computergrafik und Spielen.

Details:

• Verwendung von Näherungsverfahren zur Lösung der Newtonschen Bewegungsgleichungen.
• Verfahren wie Explizites Euler-Verfahren, Implizites Euler-Verfahren oder das Runge-Kutta-Verfahren werden benutzt.
• Sicherstellen der Stabilität und Genauigkeit der Simulation durch Wahl der Zeitschritte (\textit{Timestep}).
• Standardform der Bewegungsgleichungen: \(\textbf{F} = m \textbf{a}\) und \(\textbf{τ} = I \boldsymbol{\theta}\).
• Typische Schritte: Berechnung der Kräfte und Momente, Aktualisierung der Geschwindigkeit und Beschleunigung, Positions- und Orientierungsintegration.

Navier-Stokes-Gleichungen für Flüssigkeitssimulationen

Definition:

Navier-Stokes-Gleichungen beschreiben die Bewegung von Flüssigkeiten und Gasen, essentiell für realistische Flüssigkeitssimulationen in der Spielphysik.

Details:

• Grundlage für Strömungsmechanik
• Eindimensionale Form: \[ \rho ( \frac{\partial u}{\partial t} + u \frac{\partial u}{\partial x}) = -\frac{\partial p}{\partial x} + \mu \frac{\partial^2 u}{\partial x^2} + f_x \]
• Berechnung der Geschwindigkeit u und Druck p
• Übliche Vereinfachungen: inkompressible und nicht-viskose Strömungen
• Implementierung oft durch Diskretisierungsmethoden wie Finite-Differenzen oder Finite-Elemente

Particle-based Simulation (SPH) und Gitter-basierte Simulation

Definition:

Partikelbasierte Simulation (SPH) und Gitter-basierte Simulation sind Methoden zur Modellierung physikalischer Systeme in der fortgeschrittenen Spielphysik.

Details:

• SPH (Smoothed Particle Hydrodynamics): Simulation von Flüssigkeiten und Gasen durch Partikel.
• Gitter-basierte Simulation: Verwendung eines festen Rasters zur Berechnung physikalischer Eigenschaften.
• SPH-Formel: Dichteschätzung durch \( \rho_i = \sum_j m_j W(r_i - r_j, h) \)
• Gitter-basierte Formel: Diskretisierung von partiellen Differentialgleichungen, z.B. Navier-Stokes-Gleichungen, auf einem Gitter.
• Vorteile SPH: Flexibilität bei komplexen Geometrien und Grenzbedingungen.
• Vorteile Gitter-basiert: Effizienz und einfache Implementierung.
• Anwendungsbereiche SPH: Realistische Flüssigkeits-und Rauchsimulation.
• Anwendungsbereiche Gitter-basiert: Luftströmungen, Wärmeübertragung, Festkörperdynamik.