Kollision verhindern

[Degush]

Hey,

ich stehe vor einem Problem, bei dem ich nicht weiterkomme.
Folgende Situation: Ich habe eine Spielwelt, in der periodisch neue Positionen für alle möglichen Objekte berechnet werden. Vor jeder neuen Positionsberechnung wird geprüft, ob die Objekte nach der nächsten Positionsänderung durch ihre Geschwindigkeit kollidieren würden. Wenn ja, möchte ich den Vektor berechnen, um den beide Körper in Geschwindigkeitsrichtung verschoben werden müssten, damit sie "gerade" nicht kollidieren.

Mein Ansatz dazu ist folgender:
Drawing #1001
Ich berechne die gemeinsame Fläche beider Körper. Dann schaue ich, wo in dieser Fläche in Geschwindigkeitsrichtung die größte Distanz ist und bewege den Körper in Richtung des Gegenvektors.
Ich möchte die größtmögliche Performance!
Deshalb wäre es eigentlich günstig, wenn ein Körper alle Punkte gespeichert hätte, die ganz außen liegen.
Wenn jedem Körper also quasi ein Skelett zugeordnet wäre.
Das Skelett kann man als Linie auffassen, die an den Rändern des Körpers entlangläuft, und müsste die Schnittpunkte der Skelette kennen.

Hat jemand einen Vorschlag, wie ich eine Datenstruktur realisieren könnte, die die Skelette der Körper angibt und mit der sich mein Ansatz performant realisieren lassen könnte?
Oder hat jemand einen anderen Vorschlag zur Kollisionsprävention?

MfG,
Malte

 

[Marco13]

Teschner & Co haben ein bißchen was geschrieben, was in diese Richtung geht ( http://www.matthiasmueller.info/publications/heidelberger_vmv04.pdf ) - allerdings für deformierbare 3D-Objekte. Wenn man die Überschneidung erstmal hat, kann man ja i.a. ausrechnen, wie weit jeder einzelne Punkt eines Körpers vom Rand des anderen entfernt ist (d.h. wie tief er drin ist). Wie du in dem Bild auf den blauen Pfeil kommst, ist mir aber nicht ganz klar.

 

[Spacerat]

Wenn du schon weisst, wie du es berechnest, fehlen eigentlich nur noch die Flächengrenzen. Diese bekommst du, wenn du beim Iterieren über die Punkte von der Position des Objektes (pVot) für jede Dimension jeweils Maximal- und Minimalwerte speicherst. Bei deformierbaren Objekten muss das für jeden Frame wiederholt werden, bei allen anderen genügt einmal, so früh wie möglich.