Das Thema Kollisionsprüfung im Bereich Computer-Animation ist etwas komplizierter als man denkt.
Normalerweise würde man eine Kollision zwischen zwei Objekten prüfen, indem man feststellt ob sie sich überschneiden. Also Ort und Geometrie ermitteln und dan prüfen, ob sich eine überschneidung zwischen diesen feststellen läßt.
Dieser Ansatz ist bei bestimmten Problemstellungen und Vereinfachungen auch sehr erfolgreich und wird vielfach eingesetzt. Die hohe Kunst berücksichtigt allerdings den Faktor "Zeit" bei den Berechnungen - und somit die Bewegung der Objekte.

Schnittpunkte

Der einfachste Fall sind zwei Punkte (P1 und P2). Soll ermittelt werden, ob diese kollidieren, reicht es den Abstand zu ermitteln:

P1 * \ \ Abstand \ * P2

Dieser einfache Fall lässt sich in 2D und 3D einfach feststellen. Da Punkte Aufgrund ihrer Abmessung nur selten kollidieren sind meist komplexere Körper wie Linien und Kreise (oder Flächen und Kugeln in 3D) zu betrachten. Alles einfache Berechnungen die sich mit Vektor- und Schnittpunktberechnungen erledigen lassen.

Bewegung

Kommt der Faktor Bewegung in der Zeit hinzu, wird es schwieriger.
Wenn diese Prüfung mit einer genügend hohen "Samplerate" ausgeführt wird, können Kollisionen recht zuverläsig erkannt werden. Wenn ein wenig getrickst wird, kann bei Kollisionen entsprechend reagiert werden, in dem z.B. die Objekte wieder auf die ursprüngliche Position vor der Kollision zurückgesetzt werden. "Explodieren" sie dabei oder so etwas, kann diese Prüfung bereits ausreichen.
Problematisch wird es,

wenn die Samplerate (aufgrund fehlender Rechenleistung) nicht hoch genug ist. Es kann dann passieren, das die Objekte "durcheinander hindurch fliegen" ohne sich je zu berühren.
wenn die Objekte vonenander abprallen sollen. Es ist werder der genaue Ort, noch die genaue Zeit der Kollision bekannt, das sie sich schon "inneinander" befinden und eine exakte Berechnung des "Aufpralls" nicht mehr möglich ist.

Zeitpunkt der Kollision

Da die Zeitskala in digitalen Projekten nun einmal "gesamplelt" abläuft (eine kontinuierliche Zeitskala würde analoge Computer vorraussetzen), muss dieses Konstrukt beibehalten werden.
Die Idee ist es, den frühesten Zeitpunkt einer Kollision zweier Objekte zu ermitteln. Zurück zu unseren zwei Punkten (P1 und P2) die sich innerhalb eines Zeitsamples (40ms, entspricht 1s/25) mit unterschiedlicher Geschwindigkeit zu den Orten P1' und P2' bewegen:

* P2' / P1 *-------+-* P1' / / / * P2

Die Bahnen dieser zwei Punkte schneiden sich zwar, aber kollidieren die zwei Punkte auch zu einem Zeitpunkt t miteinander? Oder fliegen sie einfach aneinander vorbei?
Angenommen, es kann eine Kollision zum Zeitpunkt tk festgestellt werden. Dann haben wir einen Ort und eine Zeit der Kollision, wissen woher die Punkte mit welcher Geschwindigkeit kamen und können exakt berechnen wohin sie bei einem Aufprall "fliegen" werden.

Angenehmer Seitenefekt der ganzen Arbeit: Sind mehr als zwei Objekte beteiligt, kann systematisch ermittelt werden, welche Objekte zuerst miteinander kollidieren und ab diesem Zeitpunkt weitergerechnet werden.
Es bleibt nur der Spezialfall zu berücksichtigen, das mehr als zwei Objekte gleichzeitig kollidieren. Dieser kann recht einfach erkannt werden und ist immer noch extrem schwierig zu behandeln, tritt aber auch sehr selten auf.

Algorithmen

Wenn zwei 3D-Kugeln sich von einem gegebenen Punkt pos1, pos2 in einer gegebenen Richtung (und Geschwindigkeit) dir1, dir2 bewegen, WANN kollidieren ihre Oberflächen?
Und (am besten, wegen der Performance, unter Benutzung der vorherigen Ergebnisse), WO kollierdieren sie?

 double runningTime

 Vector pos1

 Vector pos2

 Vector dir1

 Vector dir2

 double radius1

 double radius2

  Von pos1 bewegt sich Sphere1 innerhalb runningTime in Richtung dir1, sie hat radius1.
  Von pos2 bewegt sich Sphere2 innerhalb runningTime in Richtung dir2, sie hat radius2.

WANN

  Die Positionenen zu einen Zeitpunkt t sind folgende:
 g1 = pos1 + dir1 * t
 g2 = pos2 + dir2 * t
 
  Der Abstands Vektor/ Gerade zu dem Zeitpunkt ist:

 a = g1 - g2

 

  Was wir wissen wollen ist, wann ist der Abstand der Kugeln der Betrag
 (Skalarprodukt) der Positionenen:
 |a| = radius1 + radius2
 
 Nun kann ich das Ding also so auflösen:
 |(pos1 + dir1 * t) - (pos2 + dir2 * t)| = radius1 + radius2
 
 Die Frage ist, kann ich das nun in dieser Schreibweise nach t (dem Zeitpunkt
 der Kollision der uns interessiert) auflösen?
 t = ???

==WO==
 ???

=Links=
* http:www.xtremevbtalk.com/archive/index.php/t-229121.html

http:forum.java.sun.com/thread.jspa?threadID=351763&messageID=1471482 * http:compsci.ca/v3/printview.php?t=9706&start=0
http:www-hades.gsi.de/~dbertini/Geant45Doc/classG4BinaryCascade.html * http:www.hep.okayama-u.ac.jp/~naitou/sct/geant4/geant452_html/G4BinaryCascade_8cc-source.html
http:www.opensourcephysics.org/develop/source-code/csm/harddisks.java/view -- * zurück zu [[raytrace]]