Kollision von 2 Dreiecken - Seite 2

08.08.2005, 00:09

jovi

Ja - das Problem mit den ineinander liegenden Dreiecken habe ich auch gesehen, und war deshalb
heilfroh als Simeon so vorbildlich Freude

seine Problemstellung klargestellt hat.
Das war wohl auch der Grund dafür, dass ich mich überwinden konnte ihn mitten in der Nacht
zu Helfen obwohl er noch keine Ahnung von Vektorrechnung hatte Augenzwinkern

08.08.2005, 00:20

Simeon

Auf diesen Beitrag antworten »

Also vll hab ich da auch n Denkfehler aber wenn eine Seite des Dreiecks z.b. den Vector (0,4) hat dann gehts ab dem Ortvector einfach nur 4 nach oben, was is daran ungewöhnlich? Also wenn P1P2.x = 0 dann find ich schon das da noch ne Linie ist. Nur halt eine Senkrechte.

EDIT:
Also das bezog sich auf jovis Post bevor er ihn editierte *g*

08.08.2005, 00:30

jovi

Auf diesen Beitrag antworten »

ich sehe was du meinst. Das ist glaube ich nur ein Problem, da du deine
Formeln etwas ungeschcikt formuliert hast
Bei mir steht da:

$\begin{eqnarray*} t = \frac{x2y3 - x3y2 + x1y2 - x2y1}{x4y2-x2y4} \end{eqnarray*}$

$\begin{eqnarray*} s = \frac{x3-x1+tx4}{x2} = \frac{y3-y1+ty4}{y2} \end{eqnarray*}$

also bei der ersten Formel kürzt sich x2 = P1P2.x raus und bei der 2. kannst du dann die Alternative nehmen, da x2 und y2 nicht gleichzeitig Null werden können.
errätst du was meine Variablen sind, oder soll ich übersetzen ?
x1 = 0P1.x und y1 = 0P1.y
x2 = P1P2.x und y2 = P1P2.y
x3 = 0Q1.x und y3 = 0Q1.y
x4 = Q1Q2.x und y4 = Q1Q2.y

08.08.2005, 00:41

Simeon

Auf diesen Beitrag antworten »

Also deine Formel sieht so viel anders aus, das ich mir sorgen mache ob meine wirklich richtig ist. Bist du dir sicher das meine richtig ist? Wenn ja hab ich eine andere Idee. Ich seh erlich gesagt nicht wo ich da was rauskürzen kann, aber noch bevor du deinen Post geschrieben hast, bin ich auch drauf gekommen, das ja nicht beides 0 sein darf. D.h. ich frag ab ob P1P2.x 0 ist, und wenn ja stell ich die Formel einfach so um das ich alle x und y Werte vertausche, also anstatt P1P2.x schreib ich P1P2.y und umgekehrt und das halt bei allen Vektoren, dann sieht die Formel so aus wie sie aussehen würde wenn ich die "s =" gleichung nicht aus der x sondern aus der y Formel umgestellt hätte. Ich hoffe man versteht mich *g*

08.08.2005, 00:46

jovi

Auf diesen Beitrag antworten »

Zitat:

Also deine Formel sieht so viel anders aus, das ich mir sorgen mache ob meine wirklich richtig ist

Na ja sicher kann man da nie sein Augenzwinkern

, aber ich hatte das gestern schon überprüft.

08.08.2005, 01:39

Simeon

Auf diesen Beitrag antworten »

Hab noch n Problem -.-

Unzwar sagte ich ja zu Anfang was von Rotation. Bis hierher konnte man das zwar ignorieren, aber jetzt wo ich den Test mit meinem Programm durchgeführt habe und gemerkt habe das die Abfrage manchmal Perfekt funktioniert und manchmal garnicht, muss man sie beachten.
Unzwar da sich die Dreiecke ja drehen (nicht wärend der Abfrage aber zwischen den Abfragen) muss ich irgendwie rausfinden welcher der Punkte dem Stützvektor/Ortsvektor gleich ist. Ich hab mir da überlegt das ich einfach mit dem Pythagoras die Entfernung zum Mittelpunkt von beiden Punkten die die Linie bilden errechne, und gucke welcher Abstand kleiner ist und somit ist der dann der Stützvector/Ortsvector. Ersmal: Funktioniert das so wie ichs mir vorgestellt habe? Und zweitens, ist das ein vernünftiger Weg oder gibts da was besseres? verwirrt

08.08.2005, 06:21

Simeon

Auf diesen Beitrag antworten »

Hmm auch das Hilft nicht viel, manchmal kommt die Kollision ein bischen zu spät, und manchmal/meistens n halben Zentimeter zu früh. Ich hab das Programm mal so eingestellt das es stopt wenn es ne Kollision gibt, damit ich n Screenshot machen kann:
http://www.ppc-zone.de/drei4.jpg
http://www.ppc-zone.de/drei5.jpg
http://www.ppc-zone.de/drei6.jpg
http://www.ppc-zone.de/drei7.jpg
http://www.ppc-zone.de/drei8.jpg
Das sind alles Kollisionen. (Einige davon sind ja auch Kollisionen, aber da man das eine Dreieck bewegen kann, kamen sie halt viel zu spät)

@Jovi:
Jo unsere beiden Gleichungen scheinen identisch zu sein, da bei beiden das gleiche Problem auftaucht.

08.08.2005, 08:44

Egal

Auf diesen Beitrag antworten »

Was mich bei den genannten Beispielen interessieren würde ist welche der Kanten zum Schnitt (Programmabruch) geführt haben. Kannst du das irgendwie rausfinden und/oder die Kollisionsabfrage mal hier einstellen? Vielleicht lässt sich so ein Fehler finden, die Rechnung sieht nämlich eigentlich sehr gut aus.

08.08.2005, 09:35

Simeon

Auf diesen Beitrag antworten »

http://www.ppc-zone.de/drei4.jpg
http://www.ppc-zone.de/drei5.jpg
http://www.ppc-zone.de/drei6.jpg
http://www.ppc-zone.de/drei7.jpg
http://www.ppc-zone.de/drei8.jpg

Habe an den Kollisionslinien jeweils 3 Punkte gemacht. Da meint das Programm das sie Kollidieren. Bei 5 und 8 bin ich mir nicht sicher, da ich diese Kollisionen nicht genau nachstellen konnte.

EDIT: Jetzt wo ich die Funktion eingebaut hab das ich seh wo sie Kollidieren, is mir was ganz komisches aufgefallen unzwar das hier:
http://www.ppc-zone.de/drei9.jpg

08.08.2005, 09:40

Egal

Auf diesen Beitrag antworten »

Das sieht mir irgendwie extrem nach einem Fehler im Code Verständnis aus.

08.08.2005, 09:52

Simeon

Auf diesen Beitrag antworten »

Jain, ich versteh den Code natürlich ich hab ihn schließlich auch selber gecodet, auch wenn er zugegeben etwas Kompliziert mit den vielen Schleifen ist. Aber ich versteh wirklich nicht wieso der vorher schon Kollidiert und dann an so komsichen nichtbetroffenen Geraden. Und ich vertraue eher meinem Code als den Formeln *g*
Ich finds auch nur komisch das die Kollision ja scheinbar nach diesem ausgeben total falsch ist, aber trotzdem eben nur in der nähe des Dreiecks ne Kollision ist. Sonst nirgends, also kann das ja nicht soo falsch sein egal ob Code oder Formel. Aber ich werde den Code nochmal genau analysieren und ihn dann in einen verständlichen Text umwandeln, vll. hab ich ja auch einfach was wichtiges vergessen abzufragen oder mach was was ich dochnet soll.

08.08.2005, 09:57

Egal

Auf diesen Beitrag antworten »

Möglicherweise hast du auch die Punkte die du gegeben bekommst falsch verstanden und kommst deswegen zu so seltsamen Kollisionsdetektionen.

08.08.2005, 10:56

jovi

Auf diesen Beitrag antworten »

Kannst du den Codebereich des Kollisionstests mal irgendwie zugänglich machen. Sonst wirds schwierig dir zu helfen fürchte ich.

08.08.2005, 12:36

Simeon

Auf diesen Beitrag antworten »

Ja ich hab vorhin schon geschrieben das ich den Code nachher in etwas verständlicherem Syntax poste. Aber jetzt mussich erstmal ins Bett, bin hunde müde. Gn8 Leute.

09.08.2005, 03:28

Simeon

Auf diesen Beitrag antworten »

Ok kommen wir nun zu meinem Programmcode. Da ich sicher nicht das Glück habe das einer von euch ein C Coder ist (falls doch entschuldige ich mich, dann sag bescheid und ich poste nochmal den richtigen SourceCode), werd ich einfach erklären was das Programm wann, wie, macht.

Ich vergleiche jeweils 3 mal 3 Linien. Also habe ich entsprechend 3 mal die Vektoren vOP1, vP1P2, vOQ1 und vQ1Q2. Da die nicht alle den gleichen Namen haben können hab ich sie mit einem Index von 0 bis 2 gekennzweichnet. So dann habe ich noch die fest bekannten Punkte vom ersten Dreieck (das graue). Da Punkte immer dem Ortsvektor gleich sind habe ich sie auch als Vektor gespeichert (das hat eigentlich nichts zu sagen, bloß das mein Programm dann später die gleichen Rechenregeln benutzt und es so einfacher ist) Diese drei Punkte/Ortsvektoren hab ich also vDreieck genannt, und auch einen index von 0 bis 2 hinzugefügt. Dann habe ich noch den Vektor um den der Nullpunkt des anderen, des roten Dreiecks, verschoben ist. Dieser Vektor heißt vR. Da es den nur einmal gibt bekommt er keinen Index. Und dann wären da noch die Punkte des roten Dreiecks von dem, um den vR Vektor verschobenen, Nullpunkt aus gesehen. Auch diese Punkte habe ich im Programm als Vektoren gespeichert wegen den Rechenregeln. Genannt hab ich sie vSchiff (Der Name weil man das rote Dreieck ja verschieben kann). Auch vSchiff hat einen index von 0 bis 2 da es ja 3 Punkte sind.
So die Bewegung ist ja aber unwichtig für die eigentlich Rechnung, da sich das Dreieck nicht wärend der Berechnung bewegen kann. Es leuft eher so: Das Rote bewegt sich indem man vR verändert und es auch rotieren lassen kann. Man bewegt also das Schiff, dann wird gerechnet ob es eine Kollision gibt, und dann bewegt es sich weiter, dann wird wieder getestet usw usw usw das wird halt ca. 200 mal in der Sekunde gemacht. ACH DAMN SHIT lol ich glaub ich hab jetzt den Fehler. Die Rotation um den, um den vR Vektor verschobenen, Nullpunkt wird nur visuell dargestellt aber geht in keinster Weise mit in die Rechnung ein, daher die komischen Kollisionen, das Programm rechnet immer nur damit das zwar das Raumschiff um vR verschoben wurde, aber das es trotzdem noch "gerade" ist und nicht rotiert um seinen, um den vR Vektor veschobenen, Nullpunkt. Daher sieht es visuell natührlich merkwürdig aus wenn das Schiff auf dem Monitor gedreht ist, aber das Programm mit einem nicht gedretem Objekt rechnet. Naja aber erstmal weiter im Text was das Programm sonst noch macht außer das es ein paar wie oben beschrieben Vektoren kennt.
So, was mir vor der Berechnung bekannt ist ist also vR, vSchiff[index] und vDreieck[index].
Aber ich weiß nicht weiler Punkt der Ortsvektor/Stützvektor von diesen insgesammt 6 Linien und welcher der Richtungsvektor ist. Also mache ich eine Schleife die 3 mal durchlaufen wird. Erst für diese Linie der beiden Dreiecke "/" für die P Linie (P ist fürs rote Dreieck) bestehend aus vOP1[0] und vP1P2[0] und für Q Linie (Q fürs graue) aus vOQ1[0] und vQ1Q2[0]. Daher nenne ich sie Linie 0. Dann für diese Linie "_" der beiden Dreiecke für die P Linie bestehend aus vOP1[1] und vP1P2[1] und für Q Linie aus vOQ1[1] und vQ1Q2[1].
Und zum Schluss für diese Linie der beiden Dreiecke "\" für die P Linie bestehend aus vOP1[2] und vP1P2[2] und für Q Linie aus vOQ1[2] und vQ1Q2[2].
Ox ist natürhlich immer der Orts/Stützvektor und x1x2 der Richtungsvektor.
Da ich aufgrund der Bewegung/Rotation aber nicht weiß welcher Stütz und welcher Richtungsvektor ist, muss ich das erstmal herausfinden. Der Orts/Stützvektor ist immer der Punkt, der die geringste Entfernung vom Nullpunkt hat. Also prüfe ich mit dem Pythagoras welcher der beiden Punkte die geringere Entfernung hat indem ich erstmal für das rote Dreieck, das ja von vR abhänig ist den Punkt bilde indem ich vR + vSchiff[index] nehme; dann berechne ich die Entfernung zum Nullpunkt und vergleiche sie mit der Entfernung von vR+vSchiff[(index+1)%3]. Lasst mich kurz dieses (index+1)%3 erläutern. Ich vergleiche hier den Punkt[index] mit dem Punkt[index+1]. Ich sagte das der index von 0 bis 2 geht. Wenn er also 2 ist, würde ja mit Punkt[2+1] verglichen werden. Und da es den Punkt[3] nicht gibt weil das dann der 4.Punkt wäre, nehme ich (index+1)%3 das bedeutet, dass das in der Klammer durch 3 geteilt wird, und der Rest, also das was übrig bleibt ist dann das was zwischen [] steht. Wobei hier eben nur Ganzzahlen relevant sind. D.h. das z.b. 2%3=2 , da wenn man 2durch3 teilen will da 0 Rest 2 rauskommt. Und bei Punkt[(2+1)%3] kommt eben 0 raus weil 3%3 = 0, weil 3 durch 3, 1 Rest 0 ist. Somit wird die letzte Linie aus Punkt 2 und 0 gebildet, was den Kreis oder besser gesagt das Dreieck schließt. So jetzt weiß ich welcher der Stütz und welcher der Richtungsvektor ist. Und mache deshalb entweder das:
vOP1[index]=vR+vSchiff[index];
vP1P2[index]=(vR+vSchiff[(index+1)%3])-(vR+vSchiff[index]);
oder eben:
vOP1[index]=vR+vSchiff[(index+1)%3];
vP1P2[index]=(vR+vSchiff[index])-(vR+vSchiff[(index+1)%3]);
Nun das gleiche nochmal für die Punkte vom graue Dreieck, das muss ich jedoch nicht mit irgend einem Vektor addieren weil ich ja die genauen Koordinaten kenne. So vergleiche ich also wieder die Entfernung zum Nullpunkt von vDreieck[i] und vDreieck[(i+1)%3] und mache dann entweder:
vOQ1[i]=vDreieck[i];
vQ1Q2[i]=vDreieck[(i+1)%3]-vDreieck[i];
oder:
vOQ1[i]=vDreieck[(i+1)%3];
vQ1Q2[i]=vDreieck[i]-vDreieck[(i+1)%3];
Dessshalb meinte ich vorhin das es leichter ist die Punkte auch als "Vektoren" zu speichern, weil bei diesen Rechnungen dann nicht die normalen sondern gleich die Vektorrechenregeln angewand werden, was mir viel Schreibarbeit erspart.

So nun habe ich alles was ich brauche um die Kollision zu berechnen. Also vergleiche ich jetzt jede Seite vom roten Dreieck mit jeder vom grauen Dreieck.
Das mache ich wieder mit einer Schleife. Bzw. der einfachheithalber mit 2 ineinander verschachtelten Schleifen. Die große Schleife leuft 3 mal durch, für alle P Seiten. Die Schleife in dieser Schleife läuft dann auch 3 mal durch um halt die eine P Seite mit allen 3 Q Seiten zu vergleichen bzw. auf Überschneidung zu prüfen. Wenn eine Überschneidung gefunden wurde, wird natührlich sofort gestopt mit den restlichen noch übrigen Berechnungen, weil diese dann nichtmehr nötig sind, wie hier schon von LOED erwähnt wurde.
So die Kollision prüf ich dann einfach mit der Formel, ich kann das Vollständigkeitshalber nochmal posten:
Wir befinden uns jetzt innerhalb der kleinen Schleife, die sich innerhalb der großen Schleife befindet.
i ist der index der von der großen Schleife verändert wird und ist für P gedacht. j ist der index der von der kleinen Schleife verändert wird und ist für Q gedacht:
Wenn also noch keine Kollision gefunden wurde, mache das:
KollZaeler=vP1P2[i].x*vOQ1[j].y-vOQ1[j].x*vP1P2[i].y + vOP1[i].x*vP1P2[i].y-vP1P2[i].x*vOP1[i].y;
KollNenner=vQ1Q2[j].x*vP1P2[i].y - vP1P2[i].x*vQ1Q2[j].y;
Wenn KollNenner nicht 0 ist mache das:
t=KollZaeler/KollNenner;
Wenn vP1P2[i].y nicht 0 ist dann mache das:
s=(vOQ1[j].y-vOP1[i].y+vQ1Q2[j].y*t)/vP1P2[i].y;
Wenn doch mache das:
s=(vOQ1[j].x-vOP1[i].x+vQ1Q2[j].x*t)/vP1P2[i].x;
Wenn jetzt s und t beide zwischen 0 und 1 sind dann wurde eine Kollision entdeckt.

PUH das wars. Ich hoffe das man es versteht. Bis auf den Fehler den ich ganz oben festgestellt habe, sollte alles richtig sein. Doch wie kann ich jetzt noch die Rechnung abhänig von der Rotation(0°-360°) um die Z-Achse (also im Kreis drehen) machen? Diese Rotation beeinflusst nicht vR sondern sie muss in dem Fall irgendwie vSchiff beeinflussen, da sich ja durch die Rotation nur die Koordinaten der Punkte um den, um den vR Vektor veschobenen, Nullpunkt ändern. Das dürfte eigentlich nicht so schwierig sein diese vSchiff[index] Punkte nochmal von der Rotation abhänig zu verändern. Aber irgendwie fällt mir jetzt nicht ein wie. Und da ihr ja auch den Code erstmal haben wollt schick ich das jetzt so erstmal ab. Wenn mir eine Lösung einfällt poste ich sie. Wenn ihr (wie ich vermute) schneller auf ne Lösung kommt schreibt sie mir bitte Gott

mfg
Simeon

PS: Ich entschuldige mich für meine vielen Rechtschreibfehler!

09.08.2005, 12:40

jovi

Auf diesen Beitrag antworten »

Gehts jetzt oder hakt es noch irgendwo ?
Falls Du noch ein Problem in deinem C-Code vermutest, dann kannst du ja einen Link auf den entsprechenden Programmteil hier reinstellen.
Willst Du wissen, wie man ein Dreieck bzw. die Eckpunkte davon um einen Festen Punkt rotiert, oder
willst Du das dein Programm auch eine mögliche Kollision erkennt (falls sich das Dreieck drehen würde, was es aber nicht tut) ?

09.08.2005, 12:56

Simeon

Auf diesen Beitrag antworten »

Nein ich vermute nirgends einen Fehler, ich habe eben nur die Rotation nicht beachtet.
Ja ich möchte wissen wie man einen Punkt um einen anderen Rotiert, da ich ja die Punkte des roten Dreiecks abhänig von der Gradzahl der Rotation um den vom vR Vektor verschobenen Nullpunkt rotieren lassen muss.

09.08.2005, 13:05

Auf diesen Beitrag antworten »

Dass du mögliche Translationen und Rotationen der Figuren mit in deinen Kollisionsalgorithmus aufnimmst, macht die Sache meiner Meinung nach nur unübersichtlich. Warum lässt du das in diesem Algorithmus nicht außen vor, und verlagerst das in getrennte Prozeduren, also

$\begin{eqnarray*} \begin{pmatrix} x_T\\ y_T \end{pmatrix} = \begin{pmatrix} x\\ y \end{pmatrix} + \begin{pmatrix} \Delta x\\ \Delta y \end{pmatrix} \end{eqnarray*}$

für Translation und

$\begin{eqnarray*} \begin{pmatrix} x_R\\ y_R \end{pmatrix} = \begin{pmatrix} \cos\varphi & -\sin\varphi\\ \sin\varphi & \cos\varphi\end{pmatrix} \cdot \begin{pmatrix} x\\ y \end{pmatrix} \end{eqnarray*}$

für Rotation um den Ursprung (Rotation um andere Punkte lässt sich ja durch eine Sequenz "Translation/Rotation um Ursprung/Rück-Translation" ersetzen) ?

09.08.2005, 13:36

Simeon

Auf diesen Beitrag antworten »

Erstmal danke für die Formel für die Rotation, aber ich nehme an da fehlt ein "-" zwischen sin und cos oder?
Zu deiner Idee: Wer sagt das ich das mit in den "Kollisionsalgorithmus" integriere? Ich weiß jetzt nicht was du von den 3 Teilen des Codes (oder alle 3?) Kollisionsalgorithmus nennst. Die Zuweisung der Werte, das Bestimmen/Unterscheiden von Stütz und Richtungsvektor, oder das Berechnen des Schnittpunktes. Natürlich muss die Rotationsberechnung einfach in die Wertezuweisung eingebaut werden, da alles andere programmiertechnisch sehr abominal aussehen würde *g*

09.08.2005, 13:47

jovi

Auf diesen Beitrag antworten »

da ich befürchte, dass du nicht weisst, dass das Ding in der Mitte in Arthurs Formel eine Matrix ist schreibe ich das nochmal anders hin:

$\begin{eqnarray*} x_R = x\cos\varphi - y\sin\varphi \end{eqnarray*}$
$\begin{eqnarray*} y_R = x\sin\varphi + y\cos\varphi \end{eqnarray*}$

09.08.2005, 13:55

Simeon

Auf diesen Beitrag antworten »

Da hast du Recht jovi Freude

Vielen Dank! Mit Matrizen hab ich mich noch nicht beschäftigt. Aber eins könnt ihr mir glauben, wenn die Ferien vorbei sind mach ich unserem Mathelehrer mal Beine smile

10.08.2005, 04:57

Simeon

Auf diesen Beitrag antworten »

JUHUU es funzt perfekt!!!! Danke nochmal an alle die mir geholfen haben vorallem jovi, LOED und Arthur Dent!!! Freude

mfg
Simeon Wink

« vorherige Seite 12

Neue Frage »

Antworten »

Kollision von 2 Dreiecken - Seite 2

Verwandte Themen