Kollision zwischen bewegender Linie und einen Punkt

[hustbaer]

XMAMan schrieb:

Problem daran: Ich weiß gerade noch nicht, wie man die Drehpunkt von ein sich bewegenden Stift berechnet.

Habt ihr noch eine Idee, wie ich die Kollisionsabfrage zwischen einer bewegenden Linie und einen festen Punkt machen kann?

Idee: Du machst den Timestep so klein dass die Rotation nicht berücksichtigt werden muss.

Dann kannst du z.B. alles so transformieren dass der Stift immer von (0, 0) bis (1, 0) geht. So bekommst du eine Transformation für vor der Verschiebung des Stifts und eine nach der Verschiebung.

Mit den beiden Transformationen transformierst du den Punkt.

Dann hast du zwei Linien.
Eine fix von (0, 0) nach (1, 0) (=der Stift) und eine zweite mit den beiden transformierten Positionen des Punkts (=die Linie anhand derer sich der Punkt in der transformierten Welt mit statischem Stift bewegt) - nennen wir diese P1 und P2.

Dann kannst du gucken ob es einen Schnittpunkt gibt und diesen ggf. berechnen.

Anhand der Koordinaten von Schnittpunkt, P1 und P2 kannst du dann auf alles zurückrechnen was du als Ergebnis haben willst. Also z.B. auf den genauen Zeitpunkt wann die Kollision erfolgt, die Position wo die Kollision erfolgt, die Position/Ausrichtung des Stifts zu diesem Zeitpunkt etc.

[rapso]

befindet sich ein punkt innerhalb eines shapes das durch 4 punkte definiert wird...

[MFK]

XMAMan schrieb:

Der Punkt bewegt sich Geradelinig, wenn die beiden Translationsvektoren (B1 - A1 und B2-A2) gleich sind oder er bewegt sich auf einer Kreisbahn, wenn die Endpunkte der Linie sich in unterschiedliche Richtungen bewegt. Ich berechne dann den Schnittpunkt zwischen zwei Linien oder zwischen einen Kreissegmetn und einer Linie.

Gibt es da eine ungenannte Nebenbedingung, dass die Punkte der Startposition dieselbe Entfernung haben wie die Punkte der Endposition? Die Stift-Analogie legt das nahe, aber das muss ja nicht so sein.

Bewegen sich beide Punkte gleichförmig, oder wird immer ein fester Abstand eingehalten?

[dot]

rapso schrieb:

befindet sich ein punkt innerhalb eines shapes das durch 4 punkte definiert wird...

Wenn es sich bei den zwei Endpositionen wirklich um beliebig verschoben und rotierte Versionen der Anfangspunkte handeln kann, wird es vermutlich kompliziert, zu definieren, was genau "innerhalb" für dieses Shape bedeutet (es kann sich ja um eine beliebig überschlagene, konkave Figur handeln). Es wird, wie von hustbaer angedeutet, wohl notwendig sein, zumindest gewisse Einschränkungen bezüglich Simulation-Timestep und maximalen Geschwindigkeiten/Winkelgeschwindigkeiten zu treffen, ansonsten wird man das Problem allgemein als finden des 3d Schnittpunktes der durch Extrusion entlang der Zeitachse entstehenden Gebilde (Fläche ∩ Strahl) betrachten müssen. Ein solcher Ansatz ist vermutlich aber selbst wenn man einige Vereinfachungen wie z.B. nur geradlinige Bewegungen machen kann eine gute Lösung, da dieser Schnittpunkt dann ebenfalls sehr einfach zu bestimmen wird (z.B. ebenes Parallelogramm ∩ achsparalleler Strahl) und man sofort auch den genauen Zeitpunkt der Kollision bekommt...

[XMAMan]

rapso schrieb:

befindet sich ein punkt innerhalb eines shapes das durch 4 punkte definiert wird...

Der Abstand der Punkte bleibt nicht zwangsweise gleich. Es kann sein, dass der die Linie, wärend sie sich bewegt, dabei länger/kürzer wird. Außerdem es das Gebildte, was durch die Punkte A1,A2,B1,B2 entsteht nicht zwangsweise ein Viereck. Wenn sich der Stift dreht, dann ist das Gebilde, was dadurch entsteht zwei Dreiecke, die sich mit einer Ecke berühren.

Der Fall auf der rechten Seite beschreibt, was ich meine.

http://fs5.directupload.net/images/160901/l7wf68eh.png

Mir ist vorhin noch eine Idee eingefallen, wie man das vielleicht machen kann.

Ich tue so, als ob die Grüne Linie (Siehe in mein Bild) gerade ist. Ich berechne dann durch eine Gleichung den Roten Punkt.

[XMAMan]

hustbaer schrieb:

XMAMan schrieb:

Problem daran: Ich weiß gerade noch nicht, wie man die Drehpunkt von ein sich bewegenden Stift berechnet.

Habt ihr noch eine Idee, wie ich die Kollisionsabfrage zwischen einer bewegenden Linie und einen festen Punkt machen kann?

Idee: Du machst den Timestep so klein dass die Rotation nicht berücksichtigt werden muss.

Dann kannst du z.B. alles so transformieren dass der Stift immer von (0, 0) bis (1, 0) geht. So bekommst du eine Transformation für vor der Verschiebung des Stifts und eine nach der Verschiebung.

Mit den beiden Transformationen transformierst du den Punkt.

Dann hast du zwei Linien.
Eine fix von (0, 0) nach (1, 0) (=der Stift) und eine zweite mit den beiden transformierten Positionen des Punkts (=die Linie anhand derer sich der Punkt in der transformierten Welt mit statischem Stift bewegt) - nennen wir diese P1 und P2.

Dann kannst du gucken ob es einen Schnittpunkt gibt und diesen ggf. berechnen.

Anhand der Koordinaten von Schnittpunkt, P1 und P2 kannst du dann auf alles zurückrechnen was du als Ergebnis haben willst. Also z.B. auf den genauen Zeitpunkt wann die Kollision erfolgt, die Position wo die Kollision erfolgt, die Position/Ausrichtung des Stifts zu diesem Zeitpunkt etc.

Ich verstehe nicht, wie diese Koordinationtransformation aussehen soll. Kannst du bitte in die Grafik hier die X- und Y-Achse(n) von den Koordinatensystem mal eintragen, damit ich verstehe, wo und wie das Koordinatensystem definiert ist?

http://fs5.directupload.net/images/160901/l7wf68eh.png

[XMAMan]

MFK schrieb:

XMAMan schrieb:

Der Punkt bewegt sich Geradelinig, wenn die beiden Translationsvektoren (B1 - A1 und B2-A2) gleich sind oder er bewegt sich auf einer Kreisbahn, wenn die Endpunkte der Linie sich in unterschiedliche Richtungen bewegt. Ich berechne dann den Schnittpunkt zwischen zwei Linien oder zwischen einen Kreissegmetn und einer Linie.

Gibt es da eine ungenannte Nebenbedingung, dass die Punkte der Startposition dieselbe Entfernung haben wie die Punkte der Endposition? Die Stift-Analogie legt das nahe, aber das muss ja nicht so sein.

Bewegen sich beide Punkte gleichförmig, oder wird immer ein fester Abstand eingehalten?

Die Linie ist als Druck/Zug-Stab gebaut. D.h. er kann sich sehr wohl von der Länge verändert, wärend er sich bewegt. Ich berechne für die Endpunkte von diesen Druckstab, welche Kräfte auf diese wirken. Daraus resultiert dann die Geschwindigkeit und sommit die Positionsveränderung. Die Punkte bewegen sich also nach jeden Time-Step sprunghaft zu der neuen Position. Dabei muss aber trotdzem die Kollision mit einen Punkt möglich sein.

[hustbaer]

XMAMan schrieb:

Ich verstehe nicht, wie diese Koordinationtransformation aussehen soll. Kannst du bitte in die Grafik hier die X- und Y-Achse(n) von den Koordinatensystem mal eintragen, damit ich verstehe, wo und wie das Koordinatensystem definiert ist?

http://fs5.directupload.net/images/160901/l7wf68eh.png

Ich kanns auch beschreiben.
A1 ist der Ursprung des neuen Koordinatensystems.
Die X-Achse geht von A1 nach A2, wobei dieser Abschnitt genau Länge 1 hat.
Die Y-Achse liegt normal darauf und ist im gleichen Verhältnis skaliert (=so dass rechte Winkel bei der Transformation erhalten bleiben).

Das ist die Transformation für den Anfang des Timesteps.
Nennen wir die Koordinaten des Punkts nach dieser Transformation PA.

Das selbe dann nochmal mit B1/B2 statt A1/A2.

Das ist dann die Transformation für das Ende des Timesteps.
Nennen wir die Koordinaten des Punkts nach dieser Transformation PB.

Dadurch geht die Linie immer fix von (x=0, y=0) nach (x=1, y=0), d.h. die Linie bewegt sich jetzt nicht mehr.
Dafür bewegt sich jetzt der Punkt von PA nach PB.

Du musst dann nur mehr checken ob der Punkt bei seiner Bewegung die X-Achse quert, und wo das passiert. Passiert es zwischen x=0 und x=1 hast du ne Kollision.
Passiert es nahe bei 0 dann liegt der Kollisionspunkt entsprechend nahe bei A1/B1, passiert es nahe bei 1 dann liegt der Kollisionspunkt entsprechend nahe bei A2/B2. Einfach linear zwischen den Endpunkten der Linie interpolieren.

Den genauen Zeitpunkt der Kollision rauszubekommen ist dann auch easy: t = PA.y / (PA.y - PB.y)

[XMAMan]

hustbaer schrieb:

XMAMan schrieb:

Ich verstehe nicht, wie diese Koordinationtransformation aussehen soll. Kannst du bitte in die Grafik hier die X- und Y-Achse(n) von den Koordinatensystem mal eintragen, damit ich verstehe, wo und wie das Koordinatensystem definiert ist?

http://fs5.directupload.net/images/160901/l7wf68eh.png

Ich kanns auch beschreiben.
A1 ist der Ursprung des neuen Koordinatensystems.
Die X-Achse geht von A1 nach A2, wobei dieser Abschnitt genau Länge 1 hat.
Die Y-Achse liegt normal darauf und ist im gleichen Verhältnis skaliert (=so dass rechte Winkel bei der Transformation erhalten bleiben).

Das ist die Transformation für den Anfang des Timesteps.
Nennen wir die Koordinaten des Punkts nach dieser Transformation PA.

Das selbe dann nochmal mit B1/B2 statt A1/A2.

Das ist dann die Transformation für das Ende des Timesteps.
Nennen wir die Koordinaten des Punkts nach dieser Transformation PB.

Dadurch geht die Linie immer fix von (x=0, y=0) nach (x=1, y=0), d.h. die Linie bewegt sich jetzt nicht mehr.
Dafür bewegt sich jetzt der Punkt von PA nach PB.

Du musst dann nur mehr checken ob der Punkt bei seiner Bewegung die X-Achse quert, und wo das passiert. Passiert es zwischen x=0 und x=1 hast du ne Kollision.
Passiert es nahe bei 0 dann liegt der Kollisionspunkt entsprechend nahe bei A1/B1, passiert es nahe bei 1 dann liegt der Kollisionspunkt entsprechend nahe bei A2/B2. Einfach linear zwischen den Endpunkten der Linie interpolieren.

Den genauen Zeitpunkt der Kollision rauszubekommen ist dann auch easy: t = PA.y / (PA.y - PB.y)

Ok. PA wäre dann also

(P.X) (A2.X - A1.X -(A2.Y - A1.Y))
(P.Y)*(A2.Y - A1.Y (A2.X - A1.X))

Will ich ein Punkt zwischen PA und PB berechnen, dann berechne ich anstelle von

A1 und A2 dann

G1 = (t-1)*A1 + t*B1
G2 = (t-1)*A2 + t*B2

P(t) =

(P.X) (G2.X - G1.X -(G2.Y - G1.Y))
(P.Y)*(G2.Y - G1.Y (G2.X - G1.X))

Nun muss ich noch schauen, ob P(t).Y == 0 wird, wenn t von 0 bis 1 läuft.

Habe ich dass alles so richtig verstanden?

[XMAMan]

hustbaer schrieb:

XMAMan schrieb:

Ich verstehe nicht, wie diese Koordinationtransformation aussehen soll. Kannst du bitte in die Grafik hier die X- und Y-Achse(n) von den Koordinatensystem mal eintragen, damit ich verstehe, wo und wie das Koordinatensystem definiert ist?

http://fs5.directupload.net/images/160901/l7wf68eh.png

Ich kanns auch beschreiben.
A1 ist der Ursprung des neuen Koordinatensystems.
Die X-Achse geht von A1 nach A2, wobei dieser Abschnitt genau Länge 1 hat.
Die Y-Achse liegt normal darauf und ist im gleichen Verhältnis skaliert (=so dass rechte Winkel bei der Transformation erhalten bleiben).

Das ist die Transformation für den Anfang des Timesteps.
Nennen wir die Koordinaten des Punkts nach dieser Transformation PA.

Das selbe dann nochmal mit B1/B2 statt A1/A2.

Das ist dann die Transformation für das Ende des Timesteps.
Nennen wir die Koordinaten des Punkts nach dieser Transformation PB.

Dadurch geht die Linie immer fix von (x=0, y=0) nach (x=1, y=0), d.h. die Linie bewegt sich jetzt nicht mehr.
Dafür bewegt sich jetzt der Punkt von PA nach PB.

Du musst dann nur mehr checken ob der Punkt bei seiner Bewegung die X-Achse quert, und wo das passiert. Passiert es zwischen x=0 und x=1 hast du ne Kollision.
Passiert es nahe bei 0 dann liegt der Kollisionspunkt entsprechend nahe bei A1/B1, passiert es nahe bei 1 dann liegt der Kollisionspunkt entsprechend nahe bei A2/B2. Einfach linear zwischen den Endpunkten der Linie interpolieren.

Den genauen Zeitpunkt der Kollision rauszubekommen ist dann auch easy: t = PA.y / (PA.y - PB.y)

Ok. PA wäre dann also

(P.X) (A2.X - A1.X -(A2.Y - A1.Y))
(P.Y)*(A2.Y - A1.Y (A2.X - A1.X))

-> Das soll eine Matrix sein, wo die erste Spalte der Vektor A2-A1 ist und die zweite Spalte ist A2-A1 um 90 Grad gedreht. Also (-Y, X). Diese Matrix wird mit den Vektor P multipliziert.

Will ich ein Punkt zwischen PA und PB berechnen, dann berechne ich anstelle von

A1 und A2 dann

G1(t) = (1-t)*A1 + t*B1
G2(t) = (1-t)*A2 + t*B2

P(t) =

(P.X - G1(t).X) (G2(t).X - G1(t).X -(G2(t).Y - G1(t).Y))
(P.Y - G1(t).Y)*(G2(t).Y - G1(t).Y (G2(t).X - G1(t).X))

Nun muss ich noch schauen, ob P(t).X >=0 && P(t).X <=1 && P(t).Y == 0 wird, wenn t von 0 bis 1 läuft.

Habe ich dass alles so richtig verstanden?

Edit: Ich habe P(t).Y == 0 gesetzt und dadurch dann t ausgerechnet. Mit diesen t habe ich dann P(t).X ausgerechnet. Das Ausrechnen von t war die übelste Arbeit. Ich habe eine Gleichung aufstellen müssen, welche über 4 Zeilen ging. Aber zumindest scheint der Ansatz mit der parametrisierten Koordinationtransformation zu funktionieren. Wenn jemand fragt, kann ich ja dann mal die Funktion posten.

@Edit: Entschuldigugn für den Doppelpost. Ich habe statt bearbeiten zitieren geklickt. Meiner zweiter Post ist der Richtige.