Kollisionen feststellen bevor sie auftreten

[spyboot]

Hallo Forum! Hallo Community!

Ich hab mir mal wieder über etwas den Kopf zerbrochen bei dem es sich meines Erachtens nur um ein Mathematisches Problem der 10. Klasse handelt!

Es geht darum Kollisionen festzustellen bevor sie auftreten.

Naja, dann will ich das Problem zuerst näher beschreiben:

Ich habe 2 Objekte die es auf eine Anstehende Kollision zu prüfen gilt.
Sie bestehen aus Polygonen und befinden sich im 2-Dreidimensionalem Raum.
jedes Objekt kann Rotieren und hat eine Bewegungsrichtung (Rigid Body Dynamics).

Nun zu meiner Idee einer Lösung in Form einer Gleichung:

Von einem Objekt nehme ich mir eine Linie (zwischen 2 Punkten) und vom anderen jeweils einen Punkt.
Der Punkt erbt zuerst einmal die Bewegungsrichtung und die Rotation um den Mittelpunkt seines Objektes und anschließend wird davon wieder die Bewegungsrichtung der Linie Abgezogen.

Jetzt hat der Punkt die relative Bewegungsgeschwindigkeit zwischen den beiden Objekten und die Linie stellt gewissermaßen den Nullpunkt dar. Dummerweise besteht die Linie aus 2 Punkten und jeder Besitz noch immer eine Rotation und eine Rotationsgeschwindigkeit um den Mittelpunkt (Die Bewegungsrichtung wurde vom einzelnem Punkt und von diesen Beiden abgezogen)!

Nun sind dass denke ich 2 Quadratische Gleichungen von denen es den Schnittpunkt zu bestimmen gilt. Dummerweise habe ich leider keine Ahnung wie ich aus Richtung und Rotation eine Gleichung machen soll.

Das ganze ist (immer noch) für meine Physik-Engiene.

Ich bin für jeden Hinweis dankbar!

m.f.G. Spyboot

Edit: vielleicht wäre dass eher was fürs Mathe-Forum gewesen

 

[Marco13]

Wenn du da wirklich die Rotation berücksichtigen willst... joa, könnt' aufwändiger werden. Üblicherweise wird die Bewegung aber doch linearisiert - d.h. es gibt Zeitschritte, und in jedem Schritt bewegen sich alle Punkte ("linear") von ihrer alten auf die neue Position. Wenn du den Kollisionszeitpunkt rausfinden willst, wird man da zwar ein Polynom vom grad 2 oder 3 lösen müssen, aber an sich ... gibt's da schon Ansätze...

 

[spyboot]

Also hohle ich mir die relative Bewegung zwischen zwei Zeitschritten und sehe ob es auf dieser "Linie" Überschneidungen mit einer anderen gibt.

Ich kann dass ja einmal versuchen und wenn es nicht dass von mir gewünschte Ergebnis bringt setzte ich mich einmal mit diesen "Polynomen" auseinander.

Danke für deinen Denkanstoß!

 

[Steev]

Wenn du Rotation, Skalierung, Scheerung usw. verwenden willst, dann würde ich das so machen, dass ich erst die (absolute) Position der Punkte berechne. Dies würde ich mithilfe von Matrizen berechnen.
Wenn du erst einmal die absolute Position deiner Punkte hast, dann kannst du zum Beispiel mithilfe von Triangulierung und einem Überschneidungsalgorithmus die Kollisionen zwischen deinen Objekten ermitteln.

 

[Marco13]

Welche "Relative Bewegung" du da verwenden willst, ist mir nicht ganz klar. So als Tipp: Für den Fall der Kollision Kante/Kante bzw. Punkt/Dreieck in 3D wurde das von Moore, Provot etc. so gelöst: realtimecollisiondetection.net - the blog Coplanarity is teH eVil!!!11!1!!

Übertragen auf 2D hätte man dann den einzelnen Punkt v, den Start- und Endpunt der Linie s und e, die Positionen der Punkte am Anfang und am Ende des Zeitschrittes, und die Bewegung der Punkte im Zeitschritt (also s(t), e(t) und v(t), rein linear), und würde dann den Zeitpunkt t suchen, bei dem die Punkte s(t), e(t) und v(t) auf einer Linie liegen. Da kommt irgendein ziemliches Gleichungsmonster raus, wenn man's rein analytisch lösen will.

Einfacher wäre natürlich sowas wie Bisektion: Man macht sich eine Methode, die die Vorzeichenbehaftete Distanz des Punktes zur Linie berechnet, und berechnet den Zeitpunkt der Kollision dann mit sowas wie

float t0 = startTime;
float t1 = endTime;
if (sign(distanceBefore) == sign(distanceAfter)) return NO_COLLISION;
int iterations = 10;
while (iterations-- > 0)
{
    float distanceBefore = signedDistance(t0);
    float distanceAfter = signedDistance(t1);
    if (sign(distanceBefore) != sign(distanceAfter))
    {
        float tc = (t1-t0) / 2;
        float distanceCenter = signedDistance(tc);
        if (distanceCenter < someEpsilon) return tc;
        if (sign(distanceBefore) != sign(distanceCenter))
        {
            t1 = tc;
        }
        else if (sign(distanceCenter) != sign(distanceAfter))
        {
            t0 = tc;
        }
    }
}
return (t1-t0) / 2;

Das ist schnell hingeschrieben, trivial im Vergleich zur rein analytischen Lösung (bei der wirklich eklige Formeln rauskommen können), und dürfte für die allermeisten denkbaren (2D-) Anwendungsfälle effizient genug sein.

 

[spyboot]

Die Lösung von Marco klingt sehr interessant ich werde mich damit wohl nun auseinandersetzten und hoffe dass es tatsächlich noch Performant bleibt.

Danke für eure Hilfe!

 

[Spacerat]

Der Vorschlag von Marco13 ist unheimlich interessant. Aber nur mal rein interessehalber: Was ist, wenn zum Start- und Endzeitpunkt keine, jedoch zwischen beiden Zeitpunkten irgendwann eine Kollision auftritt, also wenn Eintritts- und Austrittspunkt innerhalb dieses Zeitraumes liegen (bei kreisförmiger Bewegung einer der beiden Punkte)?

 

[Marco13]

Die idee ist auch unheimlich alt Die analytische Lösung ist halt "cooler" und u.U. effizienter, aber der Aufwand, sie (mathematisch) zu formulieren und schön in Code zu gießen ist schon deutlich höher.
Die Bisektion geht übrigens (wie auch jede mit IMHO zumindest vertretbarem Aufwand erstellabre analytische Lösung) davon aus, dass die Punkte sich innerhalb eines Zeitschrittes linear bewegen. Ehrlich gesagt kenne ich aber keine physikalisch basierte Simulation, wo das anders ist Für die reine Kollisionserkennung zwischen.. ich glaube.. zwei Dreiecken gibt es auch Ansätze, die bestimmte Formen von Drehbewegungen ("Screw motion") zulassen, aber ... wie sinnvoll das tatsächlich ist, und ob und wie man das (überhaupt (sinnvoll)) in 2D übertragen könnte, weiß ich nicht.