Hallo Leute ich brüte schon seit Tagen über das Tutorial Kollisionserkennung herum, welche im DGL Wiki existiert. Ich hätte da nur eine Frage
Die Formel für den Kürzesten Abstand zur einer Linie macht irgendwie keinen Sinn.
Ich habe Beispiele gefunden wo diese Gleichung nur noch falsche Ergebnisse produziert.

Meine Frage dazu ist einfach, wie ist diese Gleichung hergeleitet.

Gruß

Kannst du mal die Formel hier angeben? Ich finde sie auf der schnelle nicht im Artikel.

_________________
Steppity,✲steppity,✴step,❆step,✳step!
❆ ❄ ❄ ❄ ❅ ❄ ❆ ❄ ❅ ❄ ❅ ❄ ❅ ❄ ❄
❅ ☃ ❄ ❄ ❄ ❅ ❄ ❄ ❄ ❅ ❄ ☃ ❄ ❆ ❄ ❄

Natürlich
(|(R-M)|^2 - ((S-R)*(R-M))^2 ) / |S-R| = r^2

Ich hoffe man kann es erkennen
R ist der eine Eckpunkt
S ist der Zeite Eckpunkt
M der Position der Kugel

Also in meiner Herleitung (die nicht vollständig ist) tauchen auch Terme auf, die so einfach nicht wegfallen.
Von daher würde ich spontan auch sagen, dass die Formel so nicht stimmt.
Hast du schon mal versucht mit dem Autor in Kontakt zu kommen?

_________________
Steppity,✲steppity,✴step,❆step,✳step!
❆ ❄ ❄ ❄ ❅ ❄ ❆ ❄ ❅ ❄ ❅ ❄ ❅ ❄ ❄
❅ ☃ ❄ ❄ ❄ ❅ ❄ ❄ ❄ ❅ ❄ ☃ ❄ ❆ ❄ ❄

Ich hab erin mal auf diesen Thread hingewiesen.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Ich hätte für die Kantenkollision einen anderen Vorschlag, ihr könnt mal was dazu sagen

Die Bedingung dass eine Kollision auftritt falls der Abstand des Kugelmittelpunktes zur Strecke der Kante gleich dem Radius ist, wird weiter gebraucht.
Nur dass hier nicht die gesamte Linie in Betracht gezogen wird, sondern die Strecke zwischen den 2 Eckpunkten. Ich nenne den ersten Eckpunkt P1 und den zweiten Eckpunkt P2

Also erstes berechnet man den Vektor a = P2-P1
Als nächsten den Ortsvektor vom Mittelpunkt der Kugel zu P1 b = P1 - M

Als nächste wird der Winkel zwischen b und a berechnet mit alpha = acos((a * b) / ( | a| * |b|))
Nun lässt sich mittels der Höhenformel

h = |b| * sin alpha
der Abstand bestimmen.

Der durch stoß Punkt lässt sich nun wie folgt bestimmen:

Aufstellen der Gradengleichung
A + t * v

Der Parameter t lässt sich nach folgender Gleichung bestimmen

(b * c)/ c = t

Diese Gleichung ist wie folgt bestimmt:

wir suchen die Ankatete des Dreiecks zwischen b und h
dieser lässt sich Mittels des Tangens Satz so bestimmen


tan alpha = h / Ank

umgestellt

Ank = h / tan alpha

die Formel für h eingesetzt

ergibt

|b| * sin ( acos( (b*c)/(|b| *| c|)) / tan ( acos( (b*c)/(|b| *| c|) )

Durch die definition von tangens bleibt am ende durch kürzen

A + ( (b*c)/ |c| ) * V

Was haltet ihr davon

Hallo,

Flash und Phobeus haben mich drauf hingewiesen, dass in meinem Tutorial eine Macke entdeckt wurde. Bin leider zur Zeit etwas raus aus der Sache und stark mit anderen Dingen beschäftigt, ich werde mich in den nächsten Tagen aber mal drum kümmern.

Die Kantenkollision ist sicher die schwierigste und aufwendigste, und grundsätzlich will ich nicht ausschließen, dass ein Fehler darin steckt. Andererseits funktioniert die Kollision (als Ganzes) schon seit geraumer Zeit in meiner Überarbeitung von Tuxracer, ohne dass es ein einziges Mal zu einer Störung kam (was Kollisionen angeht). Und dabei geht es kollisionsmäßig ziemlich robust zu, weil es in dem rubbeligen Gelände permanent zu Kollisionen aller Art kommt. Doch wie gesagt, der Sache muss auf den Grund gegangen werden, es kann ja auch sein, dass Fehler in der Kantenkollision von anderen Umständen aufgefangen werden.

Hallo erin
Die Kantenkollision kann ja auch stimmen, nur ich kriege die Herleitung deiner Gleichung nicht hin. Wenn du diese mal erläutern könntest, kann man ja einsehen dass die Kantenkollision korrekt ist.

Aber da in deinem sehr guten Tutorial, die Herleitung der Gleichung nicht da ist. Ist es schwierig die richtigkeit einzusehen.


Es ist ja nie ausszuschliessen, dass die Beispiele die ich mir ausgedacht hatte, Aufgrund von Fehlern in der Berechnung nicht geklappt hatte.
Gruß

@ALL

Was haltet ihr denn von meiner Idee der Kantenkollision

Ich geb' mal eine vorläufige Antwort.

Die Herleitung der Gleichung ist ein mehr als wüstes Unterfangen. Ich hatte damals in mehreren Matheforen vergeblich nach einer Lösung gefragt, und es wurden die tollsten und umständlichsten Algorithmen vorgeschlagen, die alle eines gemeinsam hatten: sie funktionierten nicht. Das Problem, die Intersektion einer Kugel mit einer irgenwie positionierten und gerichteten Geraden (oder Strecke) im Raum ist also alles andere als trivial. Dazu kam, dass der Algorithmus nach Möglichkeit ohne Winkelfunktionen auskommen sollte, weil Kantenkollisionen sehr häufig gestestet werden müssen und Performance kosten.

Dann fand ich bei Jorrit Rouwe (Link im Tutorial) einen Algorithmus, der genau dieses Problem anging, aber in der bestehenden Form nicht zu gebrauchen war. Ich habe den Algorithmus zurechtgebogen und dann versucht, ihn zu verstehen. Den relativ kurzen Code findest du ja in der Werkzeugkiste. Das nächste Problem war nun, das Ganze in eine Formel zu bringen, wobei der Aufsatz von Kasper Fauerby behilflich war. Aber ich war mir von Anfang an nicht sicher, ob es sinnvoll war, die Formel überhaupt zu bringen, denn sie arbeitet mit etlichen Substitionen, um sie auflösen zu können. Direkt ist sie kaum umzusetzen. Ich hab's einmal geschafft, die Formel herzuleiten, aber die Herleitung ist dermaßen komplex, dass man etliche Seiten Papier dazu braucht. So hab' ich mich entschieden, es bei den groben Formelgerüsten zu belassen. Vielleicht wäre es wirklich besser gewesen, einfach nur den Code zu bringen, denn die Formel kann in der bestehenden Form nur ein Anstoß sein, in welcher Richtung man denken muss. Um ehrlich zu sein: Auf Anhieb kann ich das Ganze selber nicht mehr nachvollziehen.

Den Code selbst habe ich an diversen Fallbeispielen getestet, deshalb wurde ich etwas unruhig, als du erwähntest, dass falsche Ergebnisse produziert werden. Wie auch immer, ich werde mich noch mal damit auseinandersetzen, es braucht nur etwas Zeit. Und kein Tutorial ist so gut, dass man es nicht gelegentlich verbessern sollte.

Hi !
Erstmal dein Tutorial ist wirklich sehr gut !!!!!!!!!!!!!!!!!!!!!!!
So ich habe meine Gleichungen jetzt ohne Trigometrische Funktionen
Die Herleitung sieht wie folgt aus

Die höhe also distanz
ist gegeben als

h = |b| * sin( acos ( ( a *b) /( | a| * |b | )) )

durch substitution ersetzen wir ( ( a *b) /( | a| * |b | ) ) = x

h = |b| * sin ( acos( x) )

durch Anwendung des Funktionalen zusammenhangs zwischen sin und acos
erhalten wir

h = |b| * sqrt ( 1 - x^2)

Jetzt wird quadriert denn wie im Tutorial erwähnt reicht auch die quadratische Distanz

h^2 = |b| ^2 * ( 1- x^2)

Jetzt wird Rücksubstituiert

Wir erhalten jetzt die Gleichung

h^2 = |b|^2 - |b|^2 * (( c *b )^2 / ( ( | c | *| b|)^2))

Durch auf einen Nenner bringen und kürzen erhalten wir nun die engültige Gleichung


h^2 = (( |c| * |b|) ^2 - ( c * b) ^2) / |c|^2

Gruß





[/wiki]

Also, wenn ich das Problem jetzt richtig verstanden habe, dann würde ich das so lösen:

Eine Strecke besteht aus einem Stützvektor S und einem Richtungsvektor R, desweiteren gibt es eine Kugel mit einem Mittelpunkt M und einem Radius r:

Stützvektor = S
RichtungsVektor = R
KugelMittelPunkt = M
Radius = r

um das Problem allgemein gültig betrachten zu können, würde ich das gesamte Gebilde zunächst in den Koordinatenursprung verschieben. Dazu reicht es M - S zu berechnen. Das Ergebnis ist ein vom Koordinatenursprungzeigender Richtungsvektor und ein dazu Ausgerichteter Kugelmittelpunkt. Die Distanz zwischen der Strecke und dem Punkt bleibt dabei die gleiche, womit der Fall nicht verändert wurde.
Im nächsten Schritt ist es nötig das Punktprodukt aus den beiden Vektoren zu errechnen. Wichtig dafür ist, dass R normiert wird und der KugelMittelpunkt nicht. Der normierte Richtungsvektor heißt jetzt R', Das Punktprodukt b.

M' = M - S
R' = norm(R)
b = <R' , M'>

das Punktprodukt ist allgemein der Cosinus des Winkels zwischen zwei Vektoren. In diesem Fall ist b' der Abstand zum Ursprung des kürzesten Schnittpunktes zwischen R und M.
an dieser Stelle kann man 3 Fälle unterscheiden:

1. b' < 0 : das heißt, dass der Kollisionstest nur mit r und |M'| durchgeführt werden muss, da die Kugel definitiv den Ursprung schneiden muss um überhaupt die Kante schneiden zu können. Die Kollisionsbedingung ist dann r >= |M'|
2. b' > |R| : das heißt, dass die Kugel mindestens R schneiden muss um die Kante schneiden zu können. die Kollisionsbedingung ist dann: r >= | R - M' |
3. b' liegt zwischen |R| und 0 (also alle übrigen Fälle). In diesem Fall ist nu wieder etwas Köpfchen gefragt, da man den kürzesten Schnittpunkt zwischen M und R braucht. Dieser lässt sich anhand von b' aber leicht errechnen, denn der Schnittpunkt Sp ist einfach ein Punkt mit der Distanz b' vom Ursprung, der auf R' liegt. Hierrauß kann man den genauen Schnittpunkt Sp errechnen:

Sp = b' * R'

Hier ist es notwendig mit R' zu rechnen, da es normiert ist. Rechnet man mit einem Vektor =! der Länge 1 ist das Ergebnis nicht mehr der kürzeste Schnittpunkt. Aus dem kürzesten Schnittpunkt und dem Kugelmittelpunkt kann die kürzeste Distanz d zwischen der Strecke und dem Kugelmittelpunkt bestimmt werden.

d = | Sp - M' |

Die Kollisionsbedingung ist jetzt, dass der Radius größer ist als die kürzeste Distanz von M zu R, d.h.: r >= d
Zuammengefast ergibt sich also für die kürzeste Distanz zwischen einem Punkt und einer Geraden ( keine Strecke! )

d = | ( <norm(R) , ( M - S ) > * ( M - S ) * norm(R) ) - ( M - S ) |

Allerdings sollte man nicht die gesamte Formel aufeinmal berechnen, sondern so wie beschrieben in häppchen zerteilen, da man ersteinmal wiederholte Rechnungen wie norm(R) und M-S etc. seperat machen kann um Zeit zu sparen. Desweiteren muss an der Stelle ab der b bekannt ist die Fallunterscheidung gemacht werden.

Das ganze ist nur ein Hirngespinnst und nicht getestet worden im Programm, aber das kann ich demnächst nachholen. viele Grüße und viel Spaß beim ausprobieren.

_________________
Klar Soweit?

Um was genau geht es hier eigentlich?
Wo die Schnittpunkte von Kugel und Gerade liegen?

Ich hab so etwas vor kurzem erst hergeleitet...
Wenn es sich also wirklich darum handelt kann ich das ganze einmal posten...


Andreas

ursprünglich ging es um eine Formel, die im Kollisionstutorial verwendet wurde, deren Herleitung nicht nachvollziehbar war. Der Tutorialautor kriegt das momentan auch nicht mehr zusammen, also versuchen wir nachvollziehbare Vorschläge zu posten, da es laut threadersteller einen Fehler in der Formel geben soll.

Übrigens habe ich die von mir gepostete Version jetzt geprüft und sie funktioniert reibungslos. Ich lade das Beispielprogramm inklusive kommentierten Code gleich einmal hoch.

_________________
Klar Soweit?

Ich schlag mich auch gerade mit Kollisionserkennung und -behandlung rum, bzw. es funktioniert jetzt schon ganz gut.
Das im Tutorial hab' ich aber auch nicht so ganz verstanden.

Also ich mach das wie folgt:
Um den/die Berührungspunkt(e) auszurechnen, setze ich die Geradengleichung der Kugel in die Zylindergleichung der Kante ein. Ob nun der Zylinder um die Kante oder die Kugeln drum ist, spielt ja keine Rolle.

Ein Punkt P ist auf dem Zylinder wenn die Gleichungen erfüllt sind:

(Z+t1*T-P)*T = 0
(Z+t1*T-P)^2 = r^2

Z ist der Stützvektor des Zylinders, T der Richtungsvektor, r der Radius
t1 muss dann zwischen 0 und 1 liegen, ansonsten liegt der Berührungspunkt jenseits der Eckpunkte.

So ich hab das Programm fertig. sieht aber etwas voll gerümpelt aus. Das wichtigste steht in der kollision.pas bei TKreis.kollision(bla);
Das Programm ist recht einfach, mit gedrückte B-taste kann man mit zwei Mausklicks Kanten setzen und die Kanten und der Kreis verändern bei Kollision die Farbe.

hier noch einmal die kollision.pas, für die, die nicht daran interessiert sind sich das Programm anzusehen:


add3 ist eine Addition zweier 3d-Vektoren
len3 gibt den Betrag eines 3d-Vektors zurück
norm3 normiert einen 3d-Vektor
smul3 multipliziert einen 3d-Vektor mit einem Skalar
dot3 bildet das Punktprodukt zweier 3d-Vektoren

die nötigen Konstruktoren, Setter und Getter hab ich weggelassen, da die nichts besonderes tun.

Edit : Attachment vergessen^^, dglopengl.pas ist nicht mit drin

_________________
Klar Soweit?