Öhm, wie wär's mit der Standardlösung? Eine Ableitung ist dabei: http://mo.mathematik.uni-stuttgart.de/inhalt/erlaeuterung/erlaeuterung235/

So, ich melde mich wieder. Mir ist in der Tat ein Fehler unterlaufen, nicht mit dem Code, sondern mit der oben zitierten Formel. Die Formel, die im wesentlichen von Gerrit Rouwe stammt, bezieht sich gar nicht auf den absoluten Abstand von der Geraden, sondern liefert einen Wert, der erst bei Verrechnung mit anderen Parametern, z.B. dem Velocity-Vektor, brauchbar wird. So wie ich die Formel angegeben habe, kann der Eindruck entstehen, man könnte damit den Abstand zur Geraden bestimmen. Da war ich doch zu oberflächlich. Schon der Nenner hätte mich stutzig machen müssen, denn was hat das Quadrat der Kantenlänge mit dem Abstand zu dieser Kante zu tun? Ich erinnere mich vage, dass ich annahm, dadurch solle das Skalarprodukt im Zähler "normalisiert" werden, was in dieser Form allerdings Unsinn ist. Ich bitte also um Entschuldigung und habe das Tutorial entsprechend geändert.

Die Koeffizienten für die Normalform stimmen aber, und der Algorithmus arbeitet schnell und sauber. Trotz meiner Zerknirschung sehe ich auch etwas Positives in dem Patzer. Endlich mal Leute, die nicht nur blind den Code reinhacken, sondern sich Gedanken über die Gesetzmäßigkeiten machen. Ich habe im Augenblick leider nicht die Zeit, die Alternativvorschläge zu prüfen, aber ich werde mir diesen Thread merken.

Hallo,

ich muss doch noch einmal kurz nachhaken. Bei aller Begeisterung, den Stein des Weisen gefunden zu haben, gibt es was zu bedenken. Für eine Kollisionserkennung reicht es nicht, den Abstand der Kugel von der Geraden zu berechnen, sondern es muss der genaue Berührungspunkt berechnet werden. Aber das ist nur die eine Seite der Medaille, denn zusätzlich muss die Bewegungsrichtung der Kugel einkalkuliert werden. Damit stellt sich die Frage, ob ein noch unbekannter Berührungspunkt im Bewegungsintervall erreicht wird. Zwei Gleichungen also, die zusammengeführt werden müssen.

Hmm... also in der Lösung von mir geh ich ansatz weiße den Weg, den Traude gepostet hat, nur mit dem Unterschied, dass ich das in Häppchen mache und wichtige Daten wie den genauen Schnittpunkt abspeicher, damit man diesen wieder verwenden kann, wodurch ich die Formel nicht in die Form mit dem Kreuzprodukt bringen kann.

Ich denke, dass ein Bewegungsintervall nicht allzu schwer sein sollte, denn die Geschwindigkeit eines Objektes kann ja durchaus als Vektor bekannt sein, sollte die Kugel noch nicht kollidieren projeziert man einfach vom Kugelmittelpunkt aus den Bewegungsvektor auf den Abstandsvektor zwischen Gerade und Kreis. Der Wert, den man dann erhält braucht man nur mit dem Abstandsvektor zu vergleichen, ist er größer als die Länge des Abstandsvektors, dann schneiden sich der Weg der Kugel und die Gerade. Ist der Wert kleiner als die Länge des Abstandsvektors, schneiden sie sich nicht. Als Spezialität des Hauses (und irrelevante Info), steht fest, dass die Kugel sich von der Geraden entfernt, wenn der Wert negativ ist.
Dieser Teil der Detection ist wichtig, damit Objekte nicht durch eine Gerade hindurchfliegen, weil sie im einen Frame zu weit weg waren und im nächsten Frame aufgrund ihrer Geschwindigkeit schon auf der anderen Seite der Geraden stehen.

Für die Kollisionsreaktion wäre es evtl. wünschenswert zu wissen nach welcher zeit der bewegunsphase sich die Gerade und der Kreisschneiden um zu bestimmen mit welcher Geschwindigkeit die Kugel abprallt. Das kann man indem man die Distanz des Kugelmittelpunktes zur Geraden durch die Länge des projezierten Bewegungsvektors teilt und anschließend die Länge des Bewegungsvektors mit diesem Wert multipliziert. Zieht man den resultierenden wert von der Länge des aktuellen Bewegungsvektors ab, erhält man die übrige Bewegung und kann diese nun von der Geraden reflektieren.

Auch das könnte ich evtl. noch in ein Programm packen.. falls das wen interessiert.

_________________
Klar Soweit?

Ok, es besteht die Gefahr, dass man sich verrennt. Ich glaube nicht, dass das bei deinen Überlegungen der Fall ist, trotzdem sollte ich noch einmal präzise umreißen, was die Kollisionserkennung exakt leisten muss:

Gegeben ist die Position der Kugel mit dem Radius r. Klar.
Gegeben ist der Geschwindigkeitsvektor, der die Richtung und Länge des anstehenden Bewegungsschrittes angibt. Auch klar.
Gegeben ist schließlich eine irgendwo im Raum stehende Strecke mit den beiden Endpunkten. Auch das ist klar.

Die Kollisionsroutine muss nun folgendes mit den Parametern machen, wenn sie für eine Kollisionserkennung tauglich sein soll:

Bevor der Bewegungsschritt durchgeführt wird, muss festgestellt werden, ob und an welcher Stelle die Oberfläche (!) der Kugel die Strecke berühren wird. Falls das der Fall ist, muss die Weglänge bis zu diesem Berührungspunkt berechnet werden. Ohne Kollision wird der volle Bewegungsschritt durchgeführt, mit Kollision wird die Kugel nur bis zum Berührungspunkt bewegt. Hier kann nun der zweite Teil, die Kollisionsbehandlung einsetzen. Aus der Kollisionsposition der Kugel (Mittelpunkt) und dem Berührungspunkt mit der Strecke (Oberfläche) lässt sich der Gleit- oder Reflexionswinkel berechnen, und damit kann der Bewegungsschritt vervollständigt werden, sofern nun der Weg frei ist. Dinge wie Geschwindigkeitsreduzierung, Abflachung des Reflexionswinkels bei "weichen Kugeln" usw. kommen natürlich noch dazu, sind aber Details, die sich noch nachträglich einbauen lassen.

Ich denke, man muss etwas aufpassen, dass man sich nicht auf vorschnelle Lösungen versteift. Dazu gehören evtl. die gängigen Intersektions-Routinen. Ich kann z.B. problemlos ausrechnen, ob eine Kugel an einer bestehenden Position von einer Geraden geschnitten wird, und wo auf der Oberfläche die Schnittpunkte liegen (klassische sphere line intersection), doch für eine saubere Kollisionsbehandlung ist es dann schon zu spät. Die Kugel taucht über die Kante in das Polygon ein und muss an die Oberfläche zurückgeholt werden, was m.E. nur bei sehr (!) kleinschrittigen Bewegungen, z.B. in einem ODE-Solver, sinnvoll und machbar ist. Dasselbe gilt natürlich auch für die Kollision an Ecken und Flächen. Eine "Schnittkollision" ist im Gegensatz zur "Berührungskollision" also auf Korrekturmaßnahmen angewiesen, die aber nicht immer nachteilig sein müssen. Die Bewegung auf holprigem Gelände wirkt oft weicher, wenn man nicht exakt den Polygonen folgt, sondern auch mal eine konvexe Kante einfach durchschneidet.

Testen kann man das Ganze sehr schön in einer einfachen Szenerie. Irgendwo baut man eine farbige Linie auf und schickt die Kugel mit einem konstanten Bewegungsvektor los. Sollte die Kugel auf die Linie treffen, wird die Bewegung angehalten, und die Kugel bleibt praktisch kleben. Wenn man nun noch eine steuerbare Kamera eingebaut hat, kann man die Kollisionsstelle genau untersuchen.

na gut, dann bastel ich das mal und zeig dir, dass das, was du gerade beschrieben hast quasi das ist was ich auch schon beschrieben hab.

_________________
Klar Soweit?

Ok, ok, ich halt mich ja nun zurück. Viel Erfolg.

gut, ich hab mich wohl etwas patzig ausgedrückt^^ , entschuldigung an der Stelle. Deine Antwort klang nur so, als hättest du meinen post nur grob überflogen, weil du im Prinzip grob umrissen hast was ich selbst vorher geschrieben habe. Mir ist übrigens noch ein kleiner Fehler darin aufgefallen und zwar habe ich vergessen bei dem Test des Bewegungsintervalls den Radius der Kugel zu berücksichtigen.

Heute hab ich relativ wenig Zeit an einer Demo dafür zu schreiben, aber Kameraklassen etc. hab ich schon zurecht gelegt, daher glaube ich das relativ schnell umsetzen zu können. Ich würde das dann so machen, dass man sich die einzelnen Berechnungs Schritte als Step-by-Step anschauen kann und die in 3d auch betrachten kann um zu sehen welche zusammenhänge sich da ergeben.

Da ich das auch möglichst korrekt machen möchte würd ich gerne einmal kurz durchkauen wie der Ablauf wohl am besten rüberkommen würde. Ich dachte an folgendes:

1. Ausgangssituation inklusive Einleitungstext, bestehend aus einem Gebilde von Geraden und einer Kugel, die still stehen.
2. Die Kugel bewegt sich in großen Schritten auf die Geraden zu und man kann in einzelnen Schrittanweisungen die einzelnen Berechnungen anschauen (bestimmte Berechnungen werden mit farbigen Geraden dargestellt) und als Text erklärt bekommen.
3. Gleichzeitig soll die Kamera frei bewegbar sein, als würde man schweben, damit man sich auch optisch von einer Kollision überzeugen kann.

Würde das als eine Erklärung für Collisiondetection reichen, ist das zu viel, oder würdet ihr das ganz anders machen? (tut es überhaupt not, so etwas zu schreiben?)

_________________
Klar Soweit?

Bist du wirklich so sicher, dass wir dasselbe meinen?

Zugegeben, ganz verstanden habe ich deine Erklärung nicht, aber schon die Parameter machen mich - sagen wir mal - etwas stutzig. Was meinst du mit "Strecke"? Die Kante, mit der die Kugel evtl. kollidieren kann? Gut, die kann man natürlich in der Linienform mit Positionsvektor und Richtungsvektor beschreiben. Aber wo ist dann der Vektor, der die Bewegung der Kugel beschreibt? Oder gehst du einfach von einer statischen Situation aus und prüfst nur, ob die Kugel sich an einer bestimmten Position mit der Strecke oder Kante schneidet? Wenn das so ist, fürchte ich, dass du meine Auslassungen nur grob überflogen hast.

Egal, wir sind natürlich gespannt auf dein Demoprogramm. (Muss man das unbedingt in ein rar-Archiv packen?)

Also in dem ersten Beispielprogramm hab ich die Bewegung nicht berücksichtigt, in dem zweiten Beispiel habe ich dann erklärt wie man aus meinem vorherigen Beispiel eine Methode schreiben kann, die auch den Bewegungsvektor prüft.

Um das noch einmal kurz zusammen zufassen:

Es gibt eine Strecke die als potenzielles Kollisionsopfer einer bewegten Kugel gilt. Die Strecke hat einen Stütz- und Richtungsvektor, die Kugel hat eine Position, einen Bewegungsvektor und einen Radius. Ich rede in dem Beispiel von einer Strecke im mathematischen Sinne, da wir ja einen Startpunkt (Stützvektor) und Endpunkt(Richtungsvektor) für diese Linie haben. Das Beispiel lässt sich aber auch auf Geraden und Halbgeraden anwenden, wenn man zwei Fallunterscheidungen weg lässt. Desweiteren hab ich ebenfalls erklärt wie man die Restbewegung errechnen kann, in dem man den Bewegungsvektor mit auf die Streckeprojeziert.

Dass ich das Programm als .rar file hochgeladen habe, lag daran, dass ich einmal das Programm vorkompiliert beigelegt habe, für die, die sich nur das Programm anschauen wollen und dazu die nötigen Projektdateien, mit Ausnahme der dglopengl.pas, weil ich ebenfalls den Code der Kollisionsmethode zurverfügung stellen wollte. Ich kann das ganze natürlich auch getrennt hochladen, so das die .exe einzeln ist und wahlweiße der Programmcode in einem archiv liegt.

_________________
Klar Soweit?

Hm, ich muss doch mal kurz nachfragen, da ich unheimlich gespannt auf deine Lösung bin. Du hast ja gesagt, dass es für deinen Ansatz eine Demo gibt. Nur funktioniert das Programm bei mir nicht. Kompilieren kann ich's nicht, weil eine fehlende kollision.pas angemeckert wird. (Ich vermute, darin steckt neben dem Code die Erklärung, von der du sprachst) Die kompilierte Exe bringt auch nichts, denn da wird nur ein Kreis über den Viewport geschleppt. Könntest du das noch mal überprüfen und ggfs. eine aktualisierte Version zum Download hochladen?

oh entschuldigung, jetzt hab ich den thread hier völlig vergessen!! peinlich ...

ähm, also in der exe muss man b gedrückt halten und dann kann man mit der maus linien setzen mit der die Kollisions erkennung durchgeführt wird. der erste klick ist immer ein Startpunkt und der zweite der endpunkt. die Linie wird auch erst sichtbar, wenn man den zweiten klick gemacht hat. Lässt man zwischen durch die B taste los, dann "vergisst" das Programm den alten startpunkt. die erklärung hätte ich wohl noch mit hinein stellen sollen. auch dafür nochmal entschuldigung. Ich mach mich dann gleich einmal dran und versuch was "interaktiveres mit frei bewegenden Kreisen zu gestalten an der man dann den anderen Ansatz sehen kann mit der vollständigen Kollision.pas. In der alten war tatsächlich nur line-sphere intersection drin ( ... und dann hab ich auch noch vergessen die mit einzufügen ... )

Wenn es heute nichts mehr wird, kommts morgen abend. Versprochen!

_________________
Klar Soweit?

Hmm.. Es ist mal wieder etwas Zeit vergangen. Das liegt daran, dass ich während der Umsetzung auf ein Problem gestoßen bin, für dass ich momentan keine Lösung parat habe und auch nicht groß daran interessiert bin den Aufwand zu betreiben es zu lösen. Es geht darum, dass Ich nur den kürzesten Abstand zwischen zwei Geraden errechnen kann. Ob dieser kürzeste Abstand noch auf der Kante liegt ist allerdings fragwürdig, da ich nicht weiß wo sich dieser kürzeste Abstand auf der Geraden, bzw. auf der Kugelbahn befindet. Das Problem tritt auch nur im 3dimensionalen Raum auf. Im 2dimensionalen ist es ohne weiteres möglich mit dem von mir beschriebenen Weg eine Kollision fast nahtlos zu simulieren.
Da ich selbst nicht an realistischen 3d-Anwendungen interessiert bin trete ich erstmal vor der Problemstellung beiseite.

Entschuldigt, dass ich euch enttäuschen muss, grüße!

_________________
Klar Soweit?

Macht nichts, ich hatte sowieso den Eindruck, dass du allzu optimistisch an eine schnelle, griffige Lösung gedacht hast. Wie ich oben schon sagte, haben sich bereits etliche Leute die Zähne dran ausgebissen, und wer auf die vollständige mathematische Herleitung verzichten kann, hat ja die Möglichkeit, den in dem Tutorial beschriebenen Algorithmus zu verwenden. Der arbeitet zuverlässig und genau, und wenn ich demnächst mal etwas mehr Zeit und Luft habe, werde ich versuchen, ihn noch einmal Schritt für Schritt zu erklären.

Darf ich es auch mal versuchen?

Ich würde mit zwei windschiefen Geraden anfangen: die eine Gerade ist der Richtungsvektor der Kugel, die andere ist der Richtungsvektor der Kante: http://de.wikipedia.org/wiki/Windschiefe

Wenn man den Richtungsvektor des Abstands der beiden Geraden hätte, könnte man eine Ebene errichten, die folgendermaßen definiert ist: Normalvektor ist der Abstandsvektor der beiden Geraden und die Kantengerade liegt in dieser Ebene (liefert den noch notwendigen Punkt). Das kann man sich leicht vorstellen, oder? Die Ebene wäre ohne den Abstandsvektor frei um die Kantengerade drehbar, aber der Abstandsvektor fixiert sie in iher Lage, sozusagen. Damit ließe sich dann die einfachere Kollision Kugel/Ebene durchführen. Vielleicht fällt Dir aufgrund meiner Beschreibung auch etwas Besseres ein.

Wie kriegt man den Abstandsvektor? Zunächst würde ich mal den kleinsten Abstand der beiden ausrechnen (siehe oben Wikipedia); wenn der kleinste Abstand größer ist als der Radius, dann ist schon gesichert, dass die Kugel nicht kollidiert und wir sind hier schon zu Ende. Sollte der Abstand kleiner als der Radius sein, dann müssen wir weitermachen.

Im oben zitierten Wikipedia-Artikel steht: "Das Gemeinlot, zu beiden Geraden senkrecht" und das bedeutet, dass der Abstandsvektor auf BEIDE Geraden senkrecht ist. Diesen Abstandsvektor müssen wir also haben, er ist definiert durch die beiden Punkte, mit denen die Abstandsgerade die Kugelrichtungs-Gerade und die Kantengerade schneidet.

Wie man die beiden gesuchten Punkte berechnet, habe ich hier gefunden: http://www.wer-weiss-was.de/theme50/article897954.html (weil ich zu faul war nachzudenken, da hätte ich aber auch selber draufkommen können *schäm*)
Damit können wir die oben geforderte Ebene aufstellen.

Ist ziemlich umständlich, aber mir fällt nichts Besseres ein.
Viele Grüße,
Traude