Physically-based Simulation in Computer Graphics - Exam

Aufgabe 1)

Gesetze der klassischen Mechanik und deren Anwendung in der Computergrafik

Die Gesetze der klassischen Mechanik beschreiben die Bewegung von Objekten unter dem Einfluss von Kräften und finden Anwendung in der Computergrafik zur realistischen Darstellung von Bewegung und Kollisionsdynamik. Wesentliche Gesetze sind die Newton'schen Gesetze, das Energieerhaltungsprinzip und die Impulserhaltung. Zu den Anwendungen zählen unter anderem Rigid Body Simulationen, Partikelsysteme und die Kollisionserkennung und -behandlung. Zudem werden Differentialgleichungen und Integrationsmethoden wie Euler und Runge-Kutta verwendet, um physikalisch basierte Animationen zu erstellen.

a)

(a) Newton'sche Gesetze: Erkläre die drei Newton'schen Gesetze der Bewegung und diskutiere, wie jedes dieser Gesetze in der Simulation einer starren Körperdynamik (Rigid Body Simulation) verwendet wird. Ergänze Deine Antwort durch mathematische Formeln und Beispiele.

Lösung:

Newton'sche Gesetze der Bewegung

• Erstes Gesetz (Trägheitsgesetz): Ein Körper bleibt in Ruhe oder in gleichmäßiger geradliniger Bewegung, sofern keine resultierende Kraft auf ihn wirkt.

Mathematisch ausgedrückt als:

 \( \textbf{F} = 0 \rightarrow \textbf{v} = \text{konstant} \) 

Beispiel in der Rigid Body Simulation: Ein starrer Körper, der sich ohne äußere Einwirkung bewegt, behält seine Geschwindigkeit und Richtung bei. Wenn ein Würfel ohne äußere Kräfte auf einer flachen Oberfläche gleitet, bewegt er sich geradlinig weiter, bis eine Kraft (wie Reibung) ihn abbremst.

• Zweites Gesetz (Aktionsprinzip): Die Beschleunigung eines Körpers ist proportional zur auf ihn wirkenden Kraft und erfolgt in Richtung dieser Kraft.

Mathematisch ausgedrückt als:

 \( \textbf{F} = m \textbf{a} \) 

Beispiel in der Rigid Body Simulation: Wenn eine bestimmte Kraft auf einen starren Körper ausgeübt wird, kann die Beschleunigung des Körpers unter Verwendung seiner Masse berechnet werden. In einem Ballwurf-Szenario bedeutet eine größere Kraft beim Werfen des Balls eine höhere Beschleunigung und damit eine schnellere Bewegung des Balls.

• Drittes Gesetz (Wechselwirkungsprinzip): Zu jeder Kraft gibt es eine gleich große, aber entgegengesetzt gerichtete Gegenkraft.

Mathematisch ausgedrückt als:

 \( \textbf{F}_{AB} = - \textbf{F}_{BA} \) 

Beispiel in der Rigid Body Simulation: Bei einer Kollision zweier starrer Körper übt der erste Körper eine Kraft auf den zweiten Körper aus, die zweite Körper übt aber gleichzeitig eine gleich große und entgegengesetzte Kraft auf den ersten Körper aus. Dies bedeutet, dass bei einer Billardkugel-Kollision, die eine Kugel auf die andere trifft, beide Kugeln entsprechende Kräfte und Gegenkräfte erfahren und daher ihre Bewegungen entsprechend ändern.

Anwendung in der Simulation einer starren Körperdynamik (Rigid Body Simulation):

• Im ersten Gesetz wird sichergestellt, dass Objekte in einer Simulation ohne äußere Kräfte keine Änderungen in ihrer Bewegung erfahren.
• Das zweite Gesetz ermöglicht die Berechnung der Beschleunigung und daraus der neuen Position und Geschwindigkeit der Objekte, basierend auf den auf sie wirkenden Kräften.
• Das dritte Gesetz stellt sicher, dass die Wechselwirkungen zwischen Objekten korrekt dargestellt werden, insbesondere bei Kollisionen, um realistische physikalische Reaktionen zu erzeugen.

b)

(b) Energieerhaltung und Impulserhaltung: Zeige anhand eines Beispiels, wie das Prinzip der Energieerhaltung und der Impulserhaltung in einer physikalisch basierten Animation von Partikelsystemen angewendet wird. Erläutere die Schritte und die Berechnungen, die durchgeführt werden müssen.

Lösung:

Energieerhaltung und Impulserhaltung in der Animation von Partikelsystemen

Um die Prinzipien der Energieerhaltung und Impulserhaltung in der physikalisch basierten Animation von Partikelsystemen zu zeigen, verwenden wir ein Beispiel mit zwei Partikeln, die miteinander kollidieren.

Beispiel: Betrachte zwei Partikel A und B mit Massen \(m_A\) und \(m_B\), Geschwindigkeiten \(\textbf{v}_A\) und \(\textbf{v}_B\), die elastisch kollidieren.

1. Schritt: Vor der Kollision

• Berechne den Gesamtimpuls vor der Kollision:

 \( \textbf{p}_{\text{vorher}} = m_A \textbf{v}_A + m_B \textbf{v}_B \) 

• Berechne die Gesamtenergie vor der Kollision:

 \( E_{\text{kin, vorher}} = \frac{1}{2} m_A \textbf{v}_A^2 + \frac{1}{2} m_B \textbf{v}_B^2 \) 

2. Schritt: Kollisionsbehandlung

Bei einer elastischen Kollision gelten sowohl die Impuls- als auch die Energieerhaltung.

• Der Gesamtimpuls muss erhalten bleiben:

 \( \textbf{p}_{\text{nachher}} = m_A \textbf{v}_A' + m_B \textbf{v}_B' = \textbf{p}_{\text{vorher}} \) 

• Die Gesamtenergie muss erhalten bleiben:

 \( E_{\text{kin, nachher}} = \frac{1}{2} m_A \textbf{v}_A'^2 + \frac{1}{2} m_B \textbf{v}_B'^2 = E_{\text{kin, vorher}} \) 

3. Schritt: Nach der Kollision

Um die neuen Geschwindigkeiten \(\textbf{v}_A'\) und \(\textbf{v}_B'\) nach der Kollision zu berechnen, verwendet man die Impuls- und Energieerhaltungsgleichungen. Für eine zweidimensionale Kollision können diese Gleichungen lauten:

 \( \textbf{v}_A' = \frac{ (m_A - m_B) \textbf{v}_A + 2 m_B \textbf{v}_B }{ m_A + m_B } \)  \( \textbf{v}_B' = \frac{ 2 m_A \textbf{v}_A + (m_B - m_A) \textbf{v}_B }{ m_A + m_B } \) 

4. Schritt: Validierung der Erhaltung

• Berechne den Gesamtimpuls und die Gesamtenergie nach der Kollision:

 \( \textbf{p}_{\text{nachher}} = m_A \textbf{v}_A' + m_B \textbf{v}_B' \)  \( E_{\text{kin, nachher}} = \frac{1}{2} m_A \textbf{v}_A'^2 + \frac{1}{2} m_B \textbf{v}_B'^2 \) 

• Stelle sicher, dass die Werte denjenigen vor der Kollision entsprechen:

 \( \textbf{p}_{\text{nachher}} = \textbf{p}_{\text{vorher}} \)  \( E_{\text{kin, nachher}} = E_{\text{kin, vorher}} \) 

Durch diese Schritte wird sichergestellt, dass die physikalisch basierte Animation der Partikelsysteme den Prinzipien der Energieerhaltung und Impulserhaltung entspricht.

c)

(c) Differentialgleichungen und Integrationsmethoden: Erkläre die Rolle von Differentialgleichungen in der Simulation physikalischer Systeme. Beschreibe die Euler- und die Runge-Kutta-Integrationsmethoden. Vergleiche die beiden Methoden und diskutiere deren Vor- und Nachteile.

Lösung:

Differentialgleichungen und Integrationsmethoden in der Simulation physikalischer Systeme

In der Simulation physikalischer Systeme spielen Differentialgleichungen eine zentrale Rolle, da sie die grundlegenden Gesetze der Physik in mathematischer Form ausdrücken. Zum Beispiel beschreibt Newtons zweites Gesetz der Bewegung die Änderung der Geschwindigkeit eines Körpers als Reaktion auf eine wirkende Kraft:

 \( \textbf{F} = m \textbf{a} \)  \( \textbf{a} = \dot{\textbf{v}} \) 

Hierbei ist \( \dot{\textbf{v}} \) die erste Ableitung der Geschwindigkeit \( \textbf{v} \) nach der Zeit. Solche Gleichungen, die die Rate der Änderung einer Variablen beschreiben, sind Differentialgleichungen.

Um physikalische Systeme auf einem Computer zu simulieren, müssen diese Differentialgleichungen numerisch integriert werden. Zwei der am häufigsten verwendeten Integrationsmethoden sind die Euler-Methode und die Runge-Kutta-Methode.

Euler-Integration

• Die Euler-Methode ist eine einfache, aber weniger präzise Methode zur numerischen Integration. Sie berechnet die neue Position und Geschwindigkeit eines Objekts basierend auf der aktuellen Geschwindigkeit und Beschleunigung.

 \( \textbf{v}_{t+\Delta t} = \textbf{v}_t + \Delta t \cdot \textbf{a}_t \)  \( \textbf{x}_{t+\Delta t} = \textbf{x}_t + \Delta t \cdot \textbf{v}_t \) 

Hierbei ist \( \Delta t \) der Zeitschritt.

• Vorteile: Einfach zu implementieren, rechenzeit- und speichereffizient.
• Nachteile: Kann instabil sein und große Fehler bei größeren Zeitschritten aufweisen.

Runge-Kutta-Integration

• Die Runge-Kutta-Methode (insbesondere die vierte Ordnung, bekannt als RK4) ist eine sehr gebräuchliche und genauere Methode. Sie berechnet den Wert der Variablen unter Berücksichtigung mehrerer Zwischenschritte innerhalb eines Zeitschritts.

 \begin{align*} k_1 &= f(t, y_t) \cdot \Delta t \ k_2 &= f(t + \frac{\Delta t}{2}, y_t + \frac{k_1}{2}) \cdot \Delta t \ k_3 &= f(t + \frac{\Delta t}{2}, y_t + \frac{k_2}{2}) \cdot \Delta t \ k_4 &= f(t + \Delta t, y_t + k_3) \cdot \Delta t \ y_{t+\Delta t} &= y_t + \frac{k_1 + 2k_2 + 2k_3 + k_4}{6} \end{align*} 

• Vorteile: Deutlich genauer und stabiler als die Euler-Methode, selbst bei größeren Zeitschritten.
• Nachteile: Komplexer zu implementieren und benötigt mehr Rechenzeit und Speicher.

Vergleich der Methoden

• Die Euler-Methode ist einfach und schnell, aber weniger präzise und anfällig für Fehler und Instabilitäten, besonders bei größeren Zeitschritten.
• Die Runge-Kutta-Methode bietet eine höhere Genauigkeit und Stabilität, eignet sich besser für präzise Simulationen, erfordert jedoch mehr Rechenressourcen und ist komplexer zu implementieren.

In der Praxis werden häufig höhere Integrationsmethoden wie Runge-Kutta verwendet, insbesondere wenn Genauigkeit und Stabilität wichtig sind. Die Euler-Methode kann jedoch für einfache und weniger kritische Anwendungen oder als erster Ansatz zum Testen und Verstehen des Simulationsmodells nützlich sein.

d)

(d) Kollisionsdynamik: Wie wird die Kollisionsdynamik zwischen Objekten in einer Simulation behandelt? Erläutere die Schritte der Kollisionserkennung und -behandlung. Verwende Mathematik und physikalische Gesetze, um Deine Erklärung zu untermauern.

Lösung:

Kollisionsdynamik in Simulationen

In der Simulation physikalischer Systeme ist die Behandlung von Kollisionen zwischen Objekten entscheidend für die realistische Darstellung der Dynamik. Die Kollisionsdynamik umfasst zwei Hauptschritte: Kollisionserkennung und Kollisionsbehandlung.

1. Kollisionserkennung

Der erste Schritt in der Kollisionsdynamik besteht darin, festzustellen, ob zwei oder mehr Objekte kollidiert sind. Dies wird als Kollisionserkennung bezeichnet. Zu den gängigen Methoden zur Kollisionserkennung gehören:

• Bounding Volume Hierarchies (BVH): Hierarchische Strukturen, die einfache Volumina (wie Kugeln oder AABB - Axis-Aligned Bounding Boxes) um komplexe Objekte gruppieren. Die Kollisionserkennung wird effizient durch Rekursion innerhalb der Hierarchie durchgeführt.
• Sweep and Prune: Eine algorithmische Technik, bei der Objekte basierend auf ihren Positionen entlang einer Achse sortiert und nur benachbarte Objekte auf Kollisionen überprüft werden.
• SAT (Separating Axis Theorem): Ein geometrisches Verfahren, das prüft, ob es eine Achse gibt, entlang derer die Projektionen der beiden Objekte nicht überlappen. Falls eine solche Achse existiert, gibt es keine Kollision.

2. Kollisionsbehandlung

Sobald eine Kollision erkannt wurde, muss sie behandelt werden, um die Reaktion der kollidierenden Objekte zu berechnen. Dies umfasst die Berechnung von Kollisionspunkten, -normalen und -kräften sowie die Anwendung der physikalischen Gesetze der Impuls- und Energieerhaltung.

Die Schritte zur Kollisionsbehandlung sind:

• Bestimmung der Kollisionsnormalen: Die Kollisionenormale \( \textbf{n} \) ist der Einheitsvektor, der senkrecht zur Kollisionsfläche steht.
• Berechnung der relativen Geschwindigkeit: Die relative Geschwindigkeit \( \textbf{v}_\text{rel} \) an der Kollisionsstelle wird berechnet als:

 \( \textbf{v}_\text{rel} = \textbf{v}_A - \textbf{v}_B \) 

• Berechnung des Impulses: Der Impulswechsel während der Kollision kann unter der Annahme berechnet werden, dass die Kollision elastisch ist (d. h. kein Energieverlust). Der Impulsübertragung erfolgt durch:

 \( J = \frac{- (1 + e) \textbf{v}_\text{rel} \cdot \textbf{n}}{ \frac{1}{m_A} + \frac{1}{m_B} } \) 

• Hierbei ist \( e \) der Rückprallkoeffizient, der den Anteil der Relativgeschwindigkeit beschreibt, der nach der Kollision erhalten bleibt. Bei einer vollkommen elastischen Kollision ist \( e = 1 \), und bei einer vollkommen inelastischen Kollision ist \( e = 0 \).
• Anwendung der Impulsänderung: Die Geschwindigkeiten der beiden Objekte werden entsprechend aktualisiert:

 \( \textbf{v}_A' = \textbf{v}_A + \frac{J \cdot \textbf{n}}{m_A} \)  \( \textbf{v}_B' = \textbf{v}_B - \frac{J \cdot \textbf{n}}{m_B} \) 

• Korrektur von Überschneidungen: Da numerische Ungenauigkeiten oder Zeitschritte zu einer Überschneidung der Objekte führen können, müssen die Positionen korrigiert werden, um die Objekte auseinander zu bewegen.

Durch die systematische Identifizierung und Behandlung von Kollisionen in Simulationen unter Verwendung dieser Schritte und mathematischen Gesetze kann eine realistische Darstellung der Dynamik von physikalischen Objekten erreicht werden.

Aufgabe 2)

Numerische Integrationstechniken zur Annäherung von Lösungen differentieller Gleichungen in physikalisch-basierter Simulation. Fehleranalyse ist zentral für die Stabilität und Genauigkeit numerischer Verfahren. Berücksichtige bei Deinen Antworten folgende Punkte:

• Explizite Verfahren: direkt, schnell, aber oft instabil bei großen Zeitsschritten
• Implizite Verfahren: indirekt, stabiler, erfordern jedoch iteratives Lösen
• Fehlerarten: Rundungsfehler und Diskretisierungsfehler
• Stabilitätsanalyse, insbesondere das Courant-Friedrichs-Lewy (CFL)-Kriterium
• Beispiele der Verfahren: Euler-Verfahren, Runge-Kutta-Verfahren, Verlet-Integration
• Fehlerschätzung durch Taylorreihe und Konvergenzrate

a)

1. Euler-Verfahren

• a) Implementiere das explizite Euler-Verfahren zur Lösung der Differentialgleichung \(\frac{dy}{dt} = f(t, y)\) in Python.
• b) Erkläre den grundlegenden Unterschied zwischen explizitem und implizitem Euler-Verfahren.
• c) Diskutiere, unter welchen Bedingungen das explizite Euler-Verfahren stabil ist. Erwähne dabei das CFL-Kriterium (Courant-Friedrichs-Lewy-Kriterium).
• d) Berechne den Diskretisierungsfehler des expliziten Euler-Verfahrens mithilfe der Taylorreihe und bestimme die Ordnung des Fehlers.

Lösung:

Euler-Verfahren

• a) Implementiere das explizite Euler-Verfahren zur Lösung der Differentialgleichung \(\frac{dy}{dt} = f(t, y)\) in Python:

   # Implementierung des expliziten Euler-Verfahrens in Python def euler_explizit(f, y0, t0, tf, h):  t = t0  y = y0  ys = [y0]  ts = [t0]  while t < tf:   y = y + h * f(t, y)   t = t + h   ys.append(y)   ts.append(t)  return ts, ys # Beispielhafte Verwendung import math  def f(t, y):  return math.sin(t) - y  t0 = 0 y0 = 1 h = 0.1 tf = 2  ts, ys = euler_explizit(f, y0, t0, tf, h) print(ts) print(ys) 

• b) Erkläre den grundlegenden Unterschied zwischen explizitem und implizitem Euler-Verfahren:Das explizite Euler-Verfahren berechnet den neuen Wert \( y_{n+1} \) direkt durch Anwenden des bekannten Werts \( y_n \) und der Steigung \( f(t_n, y_n) \). Dagegen erfordert das implizite Euler-Verfahren das Lösen einer Gleichung, da \( y_{n+1} \) auf beiden Seiten der Gleichung vorkommt:
  • Explizit: \( y_{n+1} = y_n + h f(t_n, y_n) \)
  • Implizit: \( y_{n+1} = y_n + h f(t_{n+1}, y_{n+1}) \)
  Implizite Verfahren sind stabiler für größere Schrittweiten, erfordern jedoch iterative Methoden wie das Newton-Verfahren zum Lösen der impliziten Gleichung.
• c) Diskutiere, unter welchen Bedingungen das explizite Euler-Verfahren stabil ist. Erwähne dabei das CFL-Kriterium (Courant-Friedrichs-Lewy-Kriterium): Das explizite Euler-Verfahren ist stabil, wenn die Schrittweite klein genug ist. Das CFL-Kriterium gibt eine Begrenzung für die Schrittweite an, um Stabilität zu gewährleisten, typischerweise für partielle Differentialgleichungen. Für eine Differentialgleichung wie \(\frac{dy}{dt} = f(t, y)\) sollte die Schrittweite \( h \) so gewählt werden, dass
  • \[ |1 + h \frac{\partial f}{\partial y}| < 1 \]
  Ein Beispiel wäre der Einsatz des expliziten Euler-Verfahrens zur Lösung eines einfachen harmonischen Oszillators, wo eine zu große Schrittweite zu instabilen Schwingungen führen kann.
• d) Berechne den Diskretisierungsfehler des expliziten Euler-Verfahrens mithilfe der Taylorreihe und bestimme die Ordnung des Fehlers: Verwenden wir die Taylorreihe von \( y(t) \):
  • \( y(t + h) = y(t) + hy'(t) + \frac{h^2}{2} y''(t) + \mathcal{O}(h^3) \)
  Das explizite Euler-Verfahren nutzt nur die ersten zwei Terme der Taylorreihe:
  • \( y_{n+1} = y_n + h f(t_n, y_n) \)
  Der Diskretisierungsfehler entsteht durch die Vernachlässigung der höheren Ordnungs-Terme:
  • \( E = y(t + h) - y_{n+1} = \frac{h^2}{2} y''(t_n) + \mathcal{O}(h^3) \)
  Daraus folgt, dass der Diskretisierungsfehler des expliziten Euler-Verfahrens von der Ordnung \( \mathcal{O}(h^2) \) ist. Das bedeutet, dass sich der Fehler quadratisch mit der Schrittweite \( h \) verhält.

b)

2. Rundungs- und Diskretisierungsfehler

• a) Beschreibe die Unterschiede zwischen Rundungsfehlern und Diskretisierungsfehlern und deren Ursachen.
• b) Gib ein konkretes Beispiel für einen Rundungsfehler in einem numerischen Verfahren und erläutere, wie sich dieser Fehler auf das Resultat auswirkt.
• c) Diskutiere, warum die Fehlerschätzung durch die Taylorreihe eine wichtige Rolle in der Fehleranalyse numerischer Methoden spielt. Verwende dabei die Taylorreihe zur Fehlerabschätzung des impliziten Euler-Verfahrens.
• d) Erläutere die Bedeutung der Konvergenzrate bei der numerischen Integration und zeige, wie diese berechnet wird.

Lösung:

Rundungs- und Diskretisierungsfehler

• a) Beschreibe die Unterschiede zwischen Rundungsfehlern und Diskretisierungsfehlern und deren Ursachen:
  • Rundungsfehler: Diese Fehler entstehen durch die begrenzte Genauigkeit, mit der Computer Gleitkommazahlen speichern. Da Computer Zahlen nur mit einer begrenzten Anzahl von Nachkommastellen darstellen können, kann es bei arithmetischen Operationen zu kleinen Fehlern kommen, die sich summieren können. Ursachen: Begrenzte Anzahl an Ziffern, numerische Instabilität, Auslöschung (cancellation error), aufeinanderfolgende mathematische Operationen.
  • Diskretisierungsfehler: Diese Fehler treten auf, weil kontinuierliche mathematische Modelle durch diskrete numerische Verfahren angenähert werden. Der Unterschied zwischen der genauen Lösung einer Differentialgleichung und der numerisch berechneten Lösung ist der Diskretisierungsfehler. Ursachen: Verwendung einer endlichen Schrittweite (z.B. Zeit- oder Raumdiskretisierung), Vernachlässigung höherer Terme in der Taylorreihe, Wahl des numerischen Integrationsverfahrens.
• b) Gib ein konkretes Beispiel für einen Rundungsfehler in einem numerischen Verfahren und erläutere, wie sich dieser Fehler auf das Resultat auswirkt: Ein klassisches Beispiel für einen Rundungsfehler ist die Subtraktion zweier sehr naher Zahlen mit begrenzter Präzision. Betrachten wir die Berechnung des Differenzenquotienten, um die Ableitung einer Funktion numerisch zu approximieren: \[\frac{f(x + h) - f(x)}{h}\] Angenommen, \(f(x) = x^2\), und wir möchten die Ableitung bei \(x = 1\) mit einem sehr kleinen \(h\) berechnen, z.B. \(h = 10^{-10}\). Wegen der begrenzten Präzision der Gleitkommaarithmetik kann der Ausdruck \(1.0000000001^2 - 1^2\) ungenau werden, da der Rechner nicht genug signifikante Stellen hat, um die Differenz präzise zu berechnen. Dies führt zu einem erheblichen Fehler im Resultat der Ableitung. Der Rundungsfehler kann zu einer erheblichen Abweichung vom wahren Wert der Ableitung führen, insbesondere bei sehr kleinen Schrittweiten \(h\).
• c) Diskutiere, warum die Fehlerschätzung durch die Taylorreihe eine wichtige Rolle in der Fehleranalyse numerischer Methoden spielt. Verwende dabei die Taylorreihe zur Fehlerabschätzung des impliziten Euler-Verfahrens: Die Taylorreihe ermöglicht es, den Diskretisierungsfehler eines numerischen Verfahrens zu quantifizieren, indem man die nicht berücksichtigten höheren Terme der Reihe untersucht. Dies hilft zu verstehen, wie der Fehler mit der Schrittweite zusammenhängt und wie er minimiert werden kann. Für das implizite Euler-Verfahren wird \(y_{n+1}\) durch Lösen der Gleichung: \[y_{n+1} = y_n + h f(t_{n+1}, y_{n+1})\] Die Taylorreihe von \(y(t)\) bei \(t = t_n\) lautet: \[y(t_{n+1}) = y(t_n) + h y'(t_n) + \frac{h^2}{2} y''(t_n) + O(h^3)\] Da \(y'(t_n) = f(t_n, y_n)\) und \(y''(t_n) = f_t + f_y f\), können wir schreiben: \[y(t_{n+1}) = y_n + h f(t_n, y_n) + \frac{h^2}{2} (f_t + f_y f) + O(h^3)\] Im Vergleich zum impliziten Euler-Verfahren zeigt uns dies, dass der Diskretisierungsfehler des impliziten Euler-Verfahrens von der Ordnung \(O(h^2)\) ist.
• d) Erläutere die Bedeutung der Konvergenzrate bei der numerischen Integration und zeige, wie diese berechnet wird: Die Konvergenzrate misst, wie schnell die numerische Lösung einer Differentialgleichung mit abnehmender Schrittweite gegen die exakte Lösung konvergiert. Sie ist ein Indikator für die Effizienz eines numerischen Verfahrens. Die Konvergenzrate \(p\) kann durch den Vergleich der numerischen Lösungen bei zwei unterschiedlichen Schrittweiten \(h\) und \(\frac{h}{2}\) berechnet werden. Sei \(E(h)\) der Fehler bei Schrittweite \(h\) und \(E(\frac{h}{2})\) der Fehler bei Schrittweite \(\frac{h}{2}\), dann gilt: \[\frac{E(h)}{E(\frac{h}{2})} \approx 2^p\] Daraus folgt: \[p \approx \frac{\log(E(h)) - \log(E(\frac{h}{2}))}{\log(2)}\] Die Konvergenzrate hilft dabei zu verstehen, wie genau ein Verfahren wird, wenn die Schrittweite verkleinert wird. Verfahren mit höheren Konvergenzraten liefern genauere Ergebnisse für kleinere Schrittweiten und sind daher bevorzugt, wenn hohe Genauigkeit erforderlich ist.

c)

3. Runge-Kutta-Verfahren

• a) Erkläre die grundsätzliche Idee des Runge-Kutta-Verfahrens zweiter Ordnung zur Lösung von Differentialgleichungen.
• b) Implementiere das Runge-Kutta-Verfahren zweiter Ordnung in Python zur Lösung der Differentialgleichung \(\frac{dy}{dt} = f(t, y)\).
• c) Vergleiche die Stabilität und Genauigkeit des Runge-Kutta-Verfahrens mit dem Euler-Verfahren unter Verwendung einer geeigneten Test-Differentialgleichung und unterschiedlicher Zeitschrittgrößen.
• d) Führe eine Fehleranalyse des Runge-Kutta-Verfahrens zweiter Ordnung unter Verwendung der Taylorreihe durch. Bestimme die Konvergenzrate des Verfahrens.

Lösung:

Runge-Kutta-Verfahren

• a) Erkläre die grundsätzliche Idee des Runge-Kutta-Verfahrens zweiter Ordnung zur Lösung von Differentialgleichungen:Das Runge-Kutta-Verfahren zweiter Ordnung (RK2), auch als verbesserte Euler-Methode oder Heun-Verfahren bekannt, verbessert die Annäherung an die Lösung von Differentialgleichungen im Vergleich zum einfachen Euler-Verfahren. Es nutzt eine gewichtete Kombination von Steigungen zu Beginn und Ende des Intervalls, um eine genauere Schätzung für den nächsten Wert zu erhalten. Im Wesentlichen berechnet RK2 zwei Zwischenwerte:
  • \(k_1\): Berechnet die Steigung am Anfang des Intervalls.
  • \(k_2\): Berechnet die Steigung am Ende des Intervalls unter Verwendung von \(k_1\).
  Die Formel zur Aktualisierung ist dann:
  • \(k_1 = hf(t_n, y_n)\)
  • \(k_2 = hf(t_n + h, y_n + k_1)\)
  • \(y_{n+1} = y_n + \frac{1}{2}(k_1 + k_2)\)
• b) Implementiere das Runge-Kutta-Verfahren zweiter Ordnung in Python zur Lösung der Differentialgleichung \(\frac{dy}{dt} = f(t, y)\):

  # Implementierung des Runge-Kutta-Verfahrens zweiter Ordnung in Pythondef runge_kutta_2(f, y0, t0, tf, h):    t = t0    y = y0    ys = [y0]    ts = [t0]    while t < tf:        k1 = h * f(t, y)        k2 = h * f(t + h, y + k1)        y = y + 0.5 * (k1 + k2)        t = t + h        ys.append(y)        ts.append(t)    return ts, ys# Beispielhafte Verwendungimport mathdef f(t, y):    return math.sin(t) - yt0 = 0y0 = 1h = 0.1tf = 2ts, ys = runge_kutta_2(f, y0, t0, tf, h)print(ts)print(ys)

• c) Vergleiche die Stabilität und Genauigkeit des Runge-Kutta-Verfahrens mit dem Euler-Verfahren unter Verwendung einer geeigneten Test-Differentialgleichung und unterschiedlicher Zeitschrittgrößen:Um die Stabilität und Genauigkeit zu vergleichen, nutzen wir die Differentialgleichung \( \frac{dy}{dt} = -2y \) mit der Anfangsbedingung \( y(0) = 1 \). Diese Gleichung hat die analytische Lösung \( y(t) = e^{-2t} \).Wir vergleichen beide Verfahren für zwei Zeitschrittgrößen: \( h = 0.5 \) und \( h = 0.1 \).

  # Vergleich der Methodenimport numpy as npimport matplotlib.pyplot as plt# Differentialgleichungdef f(t, y):    return -2 * y# Analytische Lösungdef analytical_solution(t):    return np.exp(-2 * t)# Euler-Verfahren Implementierungdef euler_explizit(f, y0, t0, tf, h):    t = t0    y = y0    ys = [y0]    ts = [t0]    while t < tf:        y = y + h * f(t, y)        t = t + h        ys.append(y)        ts.append(t)    return ts, ys# Parametert0 = 0y0 = 1tf = 2h1 = 0.5h2 = 0.1# Euler-Verfahren Ergebnisset_euler1, y_euler1 = euler_explizit(f, y0, t0, tf, h1)t_euler2, y_euler2 = euler_explizit(f, y0, t0, tf, h2)# Runge-Kutta 2 Ergebnisset_rk2_1, y_rk2_1 = runge_kutta_2(f, y0, t0, tf, h1)t_rk2_2, y_rk2_2 = runge_kutta_2(f, y0, t0, tf, h2)# Analytische Lösung berechnent_values = np.linspace(t0, tf, 100)analytical_values = analytical_solution(t_values)# Plottingplt.plot(t_values, analytical_values, 'k-', label='Analytische Lösung')plt.plot(t_euler1, y_euler1, 'r--', label='Euler h=0.5')plt.plot(t_euler2, y_euler2, 'r-', label='Euler h=0.1')plt.plot(t_rk2_1, y_rk2_1, 'b--', label='Runge-Kutta 2 h=0.5')plt.plot(t_rk2_2, y_rk2_2, 'b-', label='Runge-Kutta 2 h=0.1')plt.xlabel('t')plt.ylabel('y')plt.legend()plt.show()

  Analyse: Typischerweise zeigt der Vergleich, dass das Runge-Kutta-Verfahren zweiter Ordnung eine viel genauere Annäherung an die analytische Lösung bietet, insbesondere bei größeren Zeitschrittgrößen. Das Euler-Verfahren wird mit zunehmender Schrittweite instabiler und ungenauer.
• d) Führe eine Fehleranalyse des Runge-Kutta-Verfahrens zweiter Ordnung unter Verwendung der Taylorreihe durch. Bestimme die Konvergenzrate des Verfahrens: Die Taylorreihe von \( y(t) \) um \( t_n \) lautet:
  • \( y(t + h) = y(t) + hy'(t) + \frac{h^2}{2} y''(t) + O(h^3) \)
  Für das Runge-Kutta-Verfahren zweiter Ordnung berechnen wir:
  • \(k_1 = h f(t_n, y_n)\)
  • \(k_2 = h f(t_n + h, y_n + k1)\)
  • \(y_{n+1} = y_n + \frac{1}{2}(k_1 + k_2)\)
  Setzen wir \(f(t, y) = y'\) und \( y''(t) = f_t + f_y f\) in k1 und k2 ein:
  • \(k_1 = h y'(t_n)\)
  • \(k_2 = h y'(t_n + h, y_n + hy'(t_n))\approx h (y'(t_n) + h y''(t_n)) = h y'(t_n) + h^2 y''(t_n)\
  Der neue Wert von y ist dann:\(y_{n+1} = y_n + \frac{1}{2}(h y'(t_n) + h y'(t_n) + h^2 y''(t_n))\approx y_n + h y'(t_n) + \frac{1}{2}h^2 y''(t_n)\) Der Vergleich dieser Berechnung mit der Taylorreihe zeigt, dass der Diskretisierungsfehler des Runge-Kutta-Verfahrens zweiter Ordnung von der Ordnung \(O(h^3)\) ist. Konvergenzrate: Die Konvergenzrate eines Verfahrens misst, wie schnell die numerische Lösung gegen die exakte Lösung konvergiert, wenn die Schrittweite kleiner wird. Für das Runge-Kutta-Verfahren zweiter Ordnung gilt:\[ \frac{E(h)}{E(\frac{h}{2})} \approx 2^p \]Da das RK2-Verfahren eine Fehlerordnung von \(O(h^3)\) aufweist, ist die Konvergenzrate \(p = 2\).

d)

4. Verlet-Integration

• a) Beschreibe das Prinzip der Verlet-Integration und deren Anwendung in der physikalisch-basierten Simulation.
• b) Implementiere die Verlet-Integration zur Lösung der Bewegungsgleichung eines Partikels im Gravitationsfeld, beschrieben durch \(a = -g\), mit Python.
• c) Diskutiere die Vor- und Nachteile der Verlet-Integration im Vergleich zu expliziten und impliziten Euler-Verfahren hinsichtlich der Stabilität und Genauigkeit, insbesondere für große Zeitschritte.
• d) Führe eine Stabilitätsanalyse der Verlet-Integration und vergleiche diese mit den stabilitätskritischen Aspekten des CFL-Kriteriums.

Lösung:

Verlet-Integration

• a) Beschreibe das Prinzip der Verlet-Integration und deren Anwendung in der physikalisch-basierten Simulation:Verlet-Integration ist eine numerische Methode zur Integration der Bewegungsgleichungen in der klassischen Mechanik. Sie ist besonders nützlich in der Simulation von Systemen, bei denen die Erhaltung der Energie wichtig ist, wie z.B. bei Molekulardynamik-Simulationen. Diese Methode ist aufgrund ihrer Struktur symplektisch, d.h., sie neigt dazu, die Energie der simulierten Systeme besser zu erhalten als einfache Euler-Methoden.Ein einfaches Verlet-Integrationsverfahren kann folgendermaßen beschrieben werden:
  • Berechne den neuen Ort aus dem aktuellen Ort und der Geschwindigkeit der vorherigen Zeitstufe.
  • Berechne die neue Geschwindigkeit aus dem Mittelwert der Geschwindigkeiten der vorherigen und aktuellen Zeitstufe.
  Die grundlegende Formel für die Position lautet:
  • \(x(t + \text{dt}) = 2x(t) - x(t - \text{dt}) + \text{dt}^2 a(t)\)
  Die Geschwindigkeit wird oft aus dem Mittelwert der Geschwindigkeiten geschätzt:
  • \(v(t) = \frac{x(t) - x(t - \text{dt})}{\text{dt}}\)
• b) Implementiere die Verlet-Integration zur Lösung der Bewegungsgleichung eines Partikels im Gravitationsfeld, beschrieben durch \(a = -g\), mit Python:

  # Implementierung der Verlet-Integration in Pythonimport numpy as npimport matplotlib.pyplot as plt# Parameterg = 9.81  # Gravitationsbeschleunigungdt = 0.01  # Zeitschrittgrößet_max = 2  # maximale Zeitn_steps = int(t_max / dt)  # Anzahl der Zeitschritte# Anfangsbedingungeny0 = 10  # Anfangshöhev0 = 0  # Anfangsgeschwindigkeit# Arrays für Position und Geschwindigkeitpositions = np.zeros(n_steps)velocities = np.zeros(n_steps)# Anfangswerte setzenpositions[0] = y0positions[1] = y0 + v0 * dt - 0.5 * g * dt**2# Verlet-Integrationfor i in range(1, n_steps - 1):    positions[i + 1] = 2 * positions[i] - positions[i - 1] - g * dt**2    velocities[i] = (positions[i + 1] - positions[i - 1]) / (2 * dt)# Letzte Geschwindigkeit berechnenvelocities[-1] = (positions[-1] - positions[-2]) / dt# Zeit-Arraytime = np.linspace(0, t_max, n_steps)# Plotten der Ergebnisseplt.plot(time, positions, label='Höhe Verlet')plt.xlabel('Zeit (s)')plt.ylabel('Höhe (m)')plt.title('Bewegung eines Partikels im Gravitationsfeld')plt.legend()plt.show()

• c) Diskutiere die Vor- und Nachteile der Verlet-Integration im Vergleich zu expliziten und impliziten Euler-Verfahren hinsichtlich der Stabilität und Genauigkeit, insbesondere für große Zeitschritte:
  • Vorteile:Verlet-Integration ist symplektisch, was bedeutet, dass sie die Energie in konservativen Systemen gut erhält. Dies macht sie besonders nützlich in der physikalisch-basierten Simulation, z.B. bei Molekulardynamik-Simulationen. Sie ist auch einfacher zu implementieren als implizite Verfahren.
  • Nachteile:Die Verlet-Integration ist weniger stabil als implizite Verfahren und erfordert kleine Zeitschritte, um genaue Ergebnisse zu liefern. Anders als das explizite Eulerverfahren ist Verlet auch nicht allgemein anwendbar auf steife Probleme und kann in solchen Fällen instabil sein.
  Im Vergleich zu expliziten Euler-Verfahren bleibt Verlet stabiler bei konservativen Systemen und erhält die Energie besser, was zu einer realistischeren Simulation über lange Zeiträume führt. Im Vergleich zu impliziten Euler-Verfahren ist es jedoch weniger stabil bei großen Zeitschritten und weniger geeignet für steife Systeme.
• d) Führe eine Stabilitätsanalyse der Verlet-Integration und vergleiche diese mit den stabilitätskritischen Aspekten des CFL-Kriteriums:Die Stabilität der Verlet-Integration kann analysiert werden, indem man untersucht, wie kleine Störungen im System vergrößert oder gedämpft werden. Für das Verlet-Verfahren ergibt sich die Bedingung für die Stabilität aus den Eigenwerten der Systemmatrix:
  • Die Eigenwerte müssen innerhalb des Einheitskreises liegen.
  Das Courant-Friedrichs-Lewy (CFL)-Kriterium wird typischerweise bei der Lösung partieller Differentialgleichungen angewendet und gibt eine Bedingung für die Wahl der Zeitschrittweite \( \text{dt} \) in Abhängigkeit von der Gittergröße \( \text{dx} \) und der maximalen Wellenfortpflanzungsgeschwindigkeit \( u \) an:
  • \( u \frac{\text{dt}}{\text{dx}} \leq C \)
  Hier ist \(C\) eine Konstante, die vom konkreten Problem abhängt. Für die Stabilitätsanalyse des Verlet-Verfahrens bedeutet dies, dass die Zeitschrittgröße klein genug gewählt werden muss, um oszillatorische Lösungen stabil zu halten.Zusammenfassend kann gesagt werden, dass Verlet-Integration zwar die Energieerhaltung in konservativen Systemen besser handhabt als explizite Methoden, aber spezielle Sorgfalt bezüglich der Wahl der Zeitschrittgröße erforderlich ist, um Stabilität zu gewährleisten. Während das CFL-Kriterium primär für partielle Differentialgleichungen verwendet wird, ist dessen Kernidee der Zusammenhang zwischen Diskretisierungsgrößen und numerischer Stabilität auch für andere numerische Integrationsmethoden wie Verlet wichtig.

Aufgabe 3)

Du arbeitest an der Entwicklung einer 3D-Simulationssoftware und musst effiziente Kollisionserkennung implementieren. Dein Ziel ist es, durch die Nutzung von Bounding Volumes und hierarchischen Strukturen die Anzahl der durchzuführenden Kollisionstests zu minimieren und die Effizienz des Systems zu maximieren.

a)

Erkläre den Vorteil der Verwendung von einfacheren geometrischen Formen wie AABBs (Axis-Aligned Bounding Boxes), Sphere (Kugeln) und OBBs (Oriented Bounding Boxes) in der Kollisionserkennung. Welche Rolle spielen diese einfachen Formen bei der Reduktion der Berechnungskomplexität?

Lösung:

• Axis-Aligned Bounding Boxes (AABBs) AABBs sind rechteckige Boxen, die immer entlang der Achsen des Koordinatensystems ausgerichtet sind. Ihre Hauptvorteile bei der Kollisionserkennung sind:
• Einfachheit: Es ist sehr einfach zu berechnen, ob zwei AABBs kollidieren, da nur die minimalen und maximalen Koordinaten verglichen werden müssen.
• Effizienz: Kollisionstests mit AABBs sind extrem schnell, da sie nur eine geringe Anzahl von Vergleichen und keine komplexen mathematischen Operationen erfordern.
• Kugeln (Spheres) Kugeln sind ebenfalls einfache geometrische Formen, die durch ihren Mittelpunkt und ihren Radius definiert werden. Ihre Vorteile umfassen:
• Symmetrie: Kugeln sind rotationssymmetrisch, was bedeutet, dass ihre Kollisionseigenschaften unabhängig von der Orientierung sind.
• Schnelle Berechnung: Ein einfacher Kollisionstest zwischen zwei Kugeln besteht darin, den Abstand zwischen ihren Mittelpunkten mit der Summe ihrer Radien zu vergleichen.
• Oriented Bounding Boxes (OBBs) OBBs sind rechteckige Boxen, die in beliebiger Orientierung im Raum ausgerichtet sein können. Ihre Vorteile sind:
• Flexibilität: OBBs passen oft besser zu der tatsächlichen Form eines Objekts als AABBs, was zu weniger falschen positiven Kollisionen führt.
• Verbesserte Präzision: Da sie nicht an die Achsen des Koordinatensystems gebunden sind, können sie engere und präzisere Bounding Volumes darstellen.
• Reduktion der Berechnungskomplexität Die Verwendung dieser einfachen geometrischen Formen reduziert die Berechnungskomplexität auf mehrere Weisen:
• Vorab-Sortierung: Bounding Volumes wie AABBs und Kugeln können genutzt werden, um schnell zu entscheiden, welche Paare von Objekten sich überhaupt potenziell nahe genug sind, um zu kollidieren.
• Hierarchische Strukturen: Komplexe Objekte können in hierarchischen Bounding Volumes verpackt werden, sodass die Kollisionserkennung zuerst auf höheren Ebenen durchgeführt wird, bevor tiefergehende Tests erfolgen.
• Weniger Detailtests: Indem einfache, schnelle Tests genutzt werden, um eine Vielzahl von potenziellen Kollisionen auszuschließen, verbleibt nur eine kleine Anzahl von wirklich potenziellen Kollisionen, die detaillierter überprüft werden müssen.

Durch die Implementierung dieser Techniken in der 3D-Simulationssoftware kann die Anzahl der durchzuführenden Kollisionstests erheblich reduziert und die Effizienz des Systems maximiert werden.

b)

Implementiere eine einfache Bounding Volume Hierarchy (BVH) für eine gegebene Szene in pseudocode. Erläutere dabei die Unterschiede und Vorzüge zwischen einem Top-Down- und einem Bottom-Up-Ansatz für den Aufbau der BVH. Zeige anhand von Beispielen, wie die rekursive Unterteilung der Szene im Top-Down-Ansatz funktioniert.

Lösung:

• Bounding Volume Hierarchy (BVH) Eine Bounding Volume Hierarchy (BVH) ist eine hierarchische Struktur, die verwendet wird, um die Anzahl der Kollisionstests zu reduzieren. Die Basisidee ist, komplexe Szenen in einfachere Bounding Volumes zu unterteilen und diese dann hierarchisch zu organisieren.
• Top-Down-Ansatz Beim Top-Down-Ansatz beginnt man mit der gesamten Szene als einem einzigen Bounding Volume und unterteilt dieses rekursiv in kleinere Bounding Volumes. Vorteile dieses Ansatzes sind:
• Schnelle Strukturierung: Der Top-Down-Ansatz kann schneller als der Bottom-Up-Ansatz sein, da er nicht die genauen Kollisionspaare am Anfang berücksichtigt.
• Rekursive Unterteilung: Die Szene wird in kleinere Teile aufgeteilt und jede dieser Teile wird wieder rekursiv in noch kleinere Teile unterteilt.
• Beispiel: Für eine Szene mit mehreren Objekten könnte der Algorithmus so aussehen:

 BVHNode buildBVH (Object[] objects) { if (objects.length <= 1) { return new LeafNode(objects); } // Teile die Objekte in zwei Gruppen auf int mid = objects.length / 2; Object[] leftObjects = objects.slice(0, mid); Object[] rightObjects = objects.slice(mid, objects.length); // Erstelle Nodes für beide Gruppen BVHNode leftChild = buildBVH(leftObjects); BVHNode rightChild = buildBVH(rightObjects); // Erstelle einen neuen inneren Knoten und setze die Bounding Volumes BVHNode node = new BVHNode(); node.left = leftChild; node.right = rightChild; node.boundingVolume = merge(leftChild.boundingVolume, rightChild.boundingVolume); return node; } 

• Genauere Struktur: Der Bottom-Up-Ansatz kann eine genauere hierarchische Struktur erzeugen, da er die genauen Positionen und Größen der Objekte von Anfang an berücksichtigt.
• Beispiel: Der Pseudocode könnte so aussehen:

 // Erstelle Leaf Nodes für jedes Objekt BVHNode[] leafNodes = objects.map(obj -> new LeafNode(obj)); while (leafNodes.length > 1) { // Finde die Paarweise nächsten Leaf Nodes und merge sie BVHNode[] newNodes = []; for (int i = 0; i < leafNodes.length; i += 2) { BVHNode left = leafNodes[i]; BVHNode right = leafNodes[i+1]; BVHNode node = new BVHNode(); node.left = left; node.right = right; node.boundingVolume = merge(left.boundingVolume, right.boundingVolume); newNodes.push(node); } leafNodes = newNodes; } // Der letzte verbleibende Node ist die Wurzel return leafNodes[0]; 

Durch die Implementierung einer BVH in der 3D-Simulationssoftware kann die Effizienz der Kollisionserkennung erheblich gesteigert werden.

Aufgabe 4)

Stelle Dir vor, Du implementierst ein System zur Kollisionserkennung in einer 2D-Spieleumgebung. Der Sweep and Prune Algorithmus wird verwendet, um die Kollisionen der Spielobjekte effizient zu erkennen. Jedes Spielobjekt wird durch seine Achsenprojektionen auf einer bestimmten 1D-Achse repräsentiert, und diese Projektionen werden verwendet, um potenzielle Kollisionen zu identifizieren.

a)

Teilaufgabe a: Erkläre, wie der Sweep and Prune Algorithmus funktioniert. Beschreibe jeden Schritt des Algorithmus im Detail, angefangen bei der Projektion der Objekte auf eine 1D-Achse bis hin zur Überprüfung potenzieller Überschneidungen.

Lösung:

Der Sweep and Prune Algorithmus ist ein effizienter Algorithmus zur Kollisionserkennung in 2D- oder 3D-Spieleumgebungen. Hier ist eine detaillierte Erklärung, wie der Algorithmus funktioniert:

• Projektion der Objekte auf eine 1D-Achse: Jedes Spielobjekt wird zunächst auf eine 1D-Achse, wie z.B. die x-Achse, projiziert. Dies geschieht, indem die minimalen und maximalen Grenzen der Objekte entlang dieser Achse bestimmt werden.
• Sortieren der Grenzen: Als nächstes werden alle Grenzen der Objekte (d.h. alle minimalen und maximalen Werte) in einer Liste zusammengefasst und nach ihrem Wert sortiert. Diese Liste enthält sowohl den Anfangspunkt als auch den Endpunkt jedes Objekts auf der Achse.
• Sweep durch die Liste: Nachdem die Liste sortiert wurde, wird sie durchlaufen (gesweept), um potenzielle Überschneidungen zu finden. Ein Objekt wird als in einem Intervall 'aktiv' betrachtet, wenn dessen Anfangspunkt durchlaufen wurde und bevor dessen Endpunkt durchlaufen wird.
• Identifizierung potenzieller Kollisionen: Während des Sweep-Vorgangs werden alle aktiven Intervalle verfolgt. Wenn ein Anfangspunkt eines neuen Intervalls gefunden wird, wird es in die Liste der aktiven Intervalle aufgenommen. Wenn ein Endpunkt gefunden wird, wird dieses Intervall aus der Liste der aktiven Intervalle entfernt. Jedes Mal, wenn ein Intervall aktiv wird, wird es mit allen anderen aktiven Intervallen verglichen, um mögliche Kollisionen zu identifizieren.

Auf diese Weise ermöglicht der Sweep and Prune Algorithmus eine effiziente Überprüfung von Kollisionen, da er nur potenziell kollidierende Paare untersucht und so die Anzahl der tatsächlich zu überprüfenden Kollisionen reduziert.

b)

Teilaufgabe b: Gegeben sind vier rechteckige Spielobjekte mit den folgenden Koordinaten (in Form von \((x_{\text{min}}, y_{\text{min}}) - (x_{\text{max}}, y_{\text{max}})\)):

• Objekt A: \((1, 1) - (3, 4)\)
• Objekt B: \((2, 3) - (5, 6)\)
• Objekt C: \((4, 2) - (6, 5)\)
• Objekt D: \((5, 1) - (7, 3)\)

Projiziere diese Objekte auf die x-Achse und sortiere die Projektionsintervalle. Bestimme die potenziellen Kollisionen zwischen den Objekten.

Lösung:

Teilaufgabe b: Um die Kollisionen der angegebenen rechteckigen Spielobjekte auf der x-Achse zu bestimmen, folgen wir den unten beschriebenen Schritten:

• Projektion der Objekte auf die x-Achse: Jedes rechteckige Spielobjekt wird durch seine Minimal- und Maximalwerte der x-Koordinaten auf die x-Achse projiziert.

Die Projektionsintervalle sind wie folgt:

• Objekt A: \[ (x_{\text{min}}, x_{\text{max}}) = (1, 3) \]
• Objekt B: \[ (x_{\text{min}}, x_{\text{max}}) = (2, 5) \]
• Objekt C: \[ (x_{\text{min}}, x_{\text{max}}) = (4, 6) \]
• Objekt D: \[ (x_{\text{min}}, x_{\text{max}}) = (5, 7) \]

Sortieren der Projektionsintervalle: Wir sortieren die Start- und Endpunkte der Projektionsintervalle.

• Liste der Intervallgrenzen: \[ [1, 2, 3, 4, 5, 5, 6, 7] \]

Die sortierten Grenzen mit Objektbezeichnung:

• 1: Start von A
• 2: Start von B
• 3: Ende von A
• 4: Start von C
• 5: Ende von B
• 5: Start von D
• 6: Ende von C
• 7: Ende von D

Sweep durch die sortierte Liste und Identifizierung potenzieller Kollisionen: Wir durchsuchen die sortierte Liste und verfolgen aktive Intervalle während des Sweep-Vorgangs:

• Bei 1: Start von A, Aktive Intervalle: [A]
• Bei 2: Start von B, Aktive Intervalle: [A, B] - Potenzielle Kollision: A-B
• Bei 3: Ende von A, Aktive Intervalle: [B]
• Bei 4: Start von C, Aktive Intervalle: [B, C] - Potenzielle Kollision: B-C
• Bei 5: Ende von B, Aktive Intervalle: [C]
• Bei 5: Start von D, Aktive Intervalle: [C, D] - Potenzielle Kollision: C-D
• Bei 6: Ende von C, Aktive Intervalle: [D]
• Bei 7: Ende von D, Aktive Intervalle: []

Zusammenfassung der potenziellen Kollisionen: Die potenziellen Kollisionen basierend auf der x-Achse sind:

• A-B
• B-C
• C-D

c)

Teilaufgabe c: Implementiere in Python eine Funktion, die die Projektionen von rechteckigen Objekten auf eine 1D-Achse berechnet und sortiert. Die Funktion sollte die potenziellen Kollisionen basierend auf den sortierten Projektionsintervallen bestimmen. Verwende dabei die folgenden Eingabeparameter: objects (eine Liste von Rechtecken, wobei jedes Rechteck durch ein Tupel von \(x_{\text{min}}, x_{\text{max}}\) beschrieben wird).

def sweep_and_prune(objects):    # Deine Implementierung hier    pass

Lösung:

Teilaufgabe c: Um die Funktion \texttt{sweep_and_prune} in Python zu implementieren, die die Projektionen von rechteckigen Objekten auf eine 1D-Achse berechnet und sortiert, sowie die potenziellen Kollisionen identifiziert, gehen wir wie folgt vor:

• Erstelle eine Liste mit allen Start- und Endpunkten der Intervalle: Jedes Rechteck wird durch seine \texttt{x_min} und \texttt{x_max} Werte repliziert und beide werden als Ereignisse (Start oder Ende) markiert.
• Sortiere die Liste nach den x-Werten: Wir stellen sicher, dass Startpunkte vor Endpunkten sortiert sind, wenn sie denselben x-Wert haben.
• Sweep durch die sortierte Liste: Verfolge aktive Intervalle und identifiziere potenzielle Kollisionen.

 def sweep_and_prune(objects): # initialisiere die Liste der Ereignisse events = [] for i, (x_min, x_max) in enumerate(objects): events.append((x_min, 'start', i)) events.append((x_max, 'end', i)) # sortiere die Ereignisse nach ihren x-Werten events.sort() collisions = [] active_intervals = set() for event in events: x, event_type, index = event if event_type == 'start': for other in active_intervals: collisions.append((index, other)) active_intervals.add(index) elif event_type == 'end': active_intervals.remove(index) return collisions # Beispiel-Eingabe: objects = [(1, 3), (2, 5), (4, 6), (5, 7)] print(sweep_and_prune(objects)) # Ausgabe: [(1, 0), (2, 1), (3, 2)] 

Diese Funktion \texttt{sweep_and_prune} nimmt eine Liste von Rechtecken als Eingabe, sortiert die Projektionsintervalle und gibt eine Liste der potenziellen Kollisionen zurück. Jedes Rechteck wird durch ein Tupel von \texttt{x_min} und \texttt{x_max}-Koordinaten beschrieben.

d)

Teilaufgabe d: Angenommen, Du hast die Objekte aus Teilaufgabe b und verwendest den Code aus Teilaufgabe c. Bestimme alle potenziellen Kollisionen manuell und vergleiche sie mit den Ergebnissen aus Deinem Python-Programm. Diskutiere etwaige Unterschiede und mögliche Gründe für diese Unterschiede.

Lösung:

Teilaufgabe d: Um die potenziellen Kollisionen sowohl manuell als auch mithilfe des Python-Codes zu bestimmen, befolgen wir zuerst die Schritte aus Teilaufgabe b und c.

Gegeben sind die Objekte:

• Objekt A: \((1, 1) - (3, 4)\) \((x_{\text{min}} = 1, x_{\text{max}} = 3)\)
• Objekt B: \((2, 3) - (5, 6)\) \((x_{\text{min}} = 2, x_{\text{max}} = 5)\)
• Objekt C: \((4, 2) - (6, 5)\) \((x_{\text{min}} = 4, x_{\text{max}} = 6)\)
• Objekt D: \((5, 1) - (7, 3)\) \((x_{\text{min}} = 5, x_{\text{max}} = 7)\)

Manuelle Bestimmung der potenziellen Kollisionen:

• Projektionen auf x-Achse:
  • Objekt A: \((1, 3)\)
  • Objekt B: \((2, 5)\)
  • Objekt C: \((4, 6)\)
  • Objekt D: \((5, 7)\)
• Sortierte Liste der Projektionswerte: \([1, 2, 3, 4, 5, 5, 6, 7]\)
• Sweep durch die sortierte Liste:
  • Bei 1: Start von A, Aktive Intervalle: [A]
  • Bei 2: Start von B, Aktive Intervalle: [A, B] - Potenzielle Kollision: A-B
  • Bei 3: Ende von A, Aktive Intervalle: [B]
  • Bei 4: Start von C, Aktive Intervalle: [B, C] - Potenzielle Kollision: B-C
  • Bei 5: Start von D, Aktive Intervalle: [B, C, D] - Potenzielle Kollision: B-D, C-D
  • Bei 5: Ende von B, Aktive Intervalle: [C, D]
  • Bei 6: Ende von C, Aktive Intervalle: [D]
  • Bei 7: Ende von D, Aktive Intervalle: []
• Manuelle potenzielle Kollisionen:
  • A-B
  • B-C
  • B-D
  • C-D

 def sweep_and_prune(objects): events = [] for i, (x_min, x_max) in enumerate(objects): events.append((x_min, 'start', i)) events.append((x_max, 'end', i)) events.sort() collisions = [] active_intervals = set() for event in events: x, event_type, index = event if event_type == 'start': for other in active_intervals: collisions.append((index, other)) active_intervals.add(index) elif event_type == 'end': active_intervals.remove(index) return collisions objects = [(1, 3), (2, 5), (4, 6), (5, 7)] print(sweep_and_prune(objects)) # Erwartete Ausgabe: [(1, 0), (2, 1), (3, 1), (3, 2)] 

Ergebnisse aus dem Python-Programm:

• [(1, 0), (2, 1), (3, 1), (3, 2)]

Vergleich und Diskussion: Die manuell bestimmten potenziellen Kollisionen lauten:

• A-B
• B-C
• B-D
• C-D

Die Kollisionen aus der Python-Implementierung sind:

• (1, 0) entspricht A-B
• (2, 1) entspricht B-C
• (3, 1) entspricht B-D
• (3, 2) entspricht C-D

Beide Ergebnisse stimmen überein, was zeigt, dass der Python-Code korrekt funktioniert. Es gibt keine Unterschiede zwischen den manuell bestimmten und programmierten Kollisionen.