Kollisionserkennung mit Kurven

Ich arbeite an einem 2D-Spiel, in dem ich eine Kollisionserkennung zwischen einem sich bewegenden Kreis und einer Art statischer Kurven (vielleicht Bezier-Kurven) durchführen möchte.

Derzeit werden in meinem Spiel nur gerade Linien als statische Geometrie verwendet. Die Kollisionserkennung wird durchgeführt, indem der Abstand zwischen dem Kreis und den Linien berechnet und der Kreis aus der Linie projiziert wird, falls der Abstand kleiner als der Radius des Kreises ist.

Wie kann ich diese Art der Kollisionserkennung relativ einfach durchführen? Ich weiß zum Beispiel, dass Box2D Kollisionserkennung mit Bezier-Kurven bietet. Ich brauche keinen voll ausgestatteten Kollisionserkennungsmechanismus, nur etwas, das das kann, was ich beschrieben habe.

UPDATE: Vielen Dank für die tollen Antworten! Ich muss die Bezier-Kurven nachlesen, um die von Ihnen beschriebene Methode vollständig zu verstehen. Dann melde ich mich wieder bei dir.

29/09/2012 - 23:20

Ich habe hier ein Git-Repo erstellt: https://github.com/ArthurWulfWhite/Bezier-Distance/

Sie können die Quelldateien auch als Zip von dort herunterladen. Es enthält auch eine Demo, die Sie mit FlashDevelop kompilieren können. Um die Demo zu verwenden, öffnen Sie das Projekt in Flash Develop und klicken Sie auf „Projekt testen“. Klicken Sie beim Ausführen der Demo auf die LMB, um eine neue Bézier-Kurve und einen neuen Kreis zufällig auszuwählen.

Viel Glück!

Der Zip-Link ist schwer zu erkennen - verwenden Sie einfach Strg + F und geben Sie zip ein. Diese Quelle repräsentiert ein paar Wochen Forschung und Programmierung, ich hoffe es gefällt euch.

Wenn Sie vorhaben, den Bezier rekursiv in Segmente zu unterteilen und nach Kollisionen mit ihnen zu suchen, empfehle ich, ein 100.100-Array (Gitter) zu erstellen und jedes Segment auf den vier nächstgelegenen Quadraten zu platzieren, sodass Sie nur mit 4 / 10.000 der auf Kollisionen prüfen müssen segmentiert jeden Frame.

Ich denke, Sie werden sowohl als Programmierer als auch als Spieleentwickler von box2d profitieren, da es viele versteckte kleine Hürden gibt, eine "einfache" Physik-Engine zu entwickeln, die die Bewegung etwas holpriger und weniger flüssig erscheinen lässt, als sie sein könnte.

Alte Antwort: Der reine Weg.

Sie können tatsächlich feststellen, ob ein Kreis mit einer Bezier-Kurve kollidiert, indem Sie den Abstand zwischen dem Mittelpunkt des Kreises und dem nächstgelegenen Punkt auf der Kurve überprüfen.

Die Gleichung für die Entfernung (im Allgemeinen)

erklärt:

Bezier-Gleichung:

q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))

Dies kann summiert werden zu (mit etwas Algebra) - ich werde (x, y) für die Lesbarkeit weglassen (sie sind immer noch Punkte, nicht eine Zahl)

q(t) = (start -2 * cont + end) t^2 + (-2 * start + 2 * control) + start

Die Entfernung vom Punkt (x, y) beträgt:

sqrt ((q(t).x - point.x)^2 + (q(t).y - point.y)^2)

Um den dem Ball am nächsten gelegenen Punkt auf dem Bezier zu finden, müssen Sie alle Punkte ableiten und finden, an denen die Ableitung gleich Null ist (die Wurzeln). Da es sich um ein Polynom dritten Grades handelt, können Sie eine geschlossene Formel verwenden, die jedoch möglicherweise unzuverlässig ist, da die Genauigkeit der vom Computer dargestellten Gleitkomma-Brüche möglicherweise nicht ausreicht. Es ist weitaus besser, Newton oder ähnliches zu verwenden.

Das Derivat, für das Sie die Wurzeln finden müssen, ist:

Angenommen: a = Start b = Kontrolle c = Ende d = Wirbelmittelpunkt

Der schwierige Teil ist das Multiplizieren dieser Punkte. Sie müssen das Skalarprodukt verwenden.

Wenn Sie möchten, habe ich den Code dafür und kann ihn hier in Form einer Funktion weitergeben, die einfach einen Booleschen Wert zurückgibt, wenn eine Kollision vorliegt oder nicht und einen Kollisionswinkel. Einige Probleme könnten bei der naiven Implementierung einer Kollisionsmaschine wie dieser auftreten, z. B. könnte ein sich schnell bewegender Ball zwischen zwei Kurven hängen bleiben.

Ich empfehle, es vorerst zu vermeiden, fasse einfach die Koeffizienten für die x-Achse und für die y-Achse zusammen und addiere sie.

Verwenden Sie eine zuverlässige Methode wie Newton, um die Wurzeln zu finden, überprüfen Sie den Abstand von den Wurzelpunkten auf dem Bezier, 0 <= t <= 1 zur Kreismitte, und überprüfen Sie den Abstand für die beiden Enden des Beziers (Start und Ende) zum Kreismittelpunkt, welcher am nächsten ist, zeigt an, ob eine Kollision vorliegt.

Ist der Radius kleiner als der Mindestabstand, liegt eine Kollision vor.

Der Winkel ist ungefähr derjenige zwischen dem Mittelpunkt des Kreises und dem nächstgelegenen Punkt auf dem Bezier.

Abgesehen davon, wenn Sie wirklich ein Spiel mit Kollisionsphysik machen möchten, schlage ich vor, dass Sie einfach über den Bézier iterieren

    q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))

Teilen Sie jedes Teil rekursiv in die Mitte, bis es klein genug ist, sagen wir 10 Pixel oder weniger. Bilden Sie dann den Bezier grob aus Boxen und verwenden Sie Box2d für die Physik, da es möglich ist, dass sich das Schreiben dieses gesamten Kollisionserkennungscodes als großartig herausstellt Zeitverschwendung, die das Gameplay nicht wesentlich verbessert. Der Einsatz von Box2d hat sich in der Vergangenheit in unzähligen Projekten bewährt.

Dazu würde ich:

• Teilen Sie die Bezierkurve in mehrere Liniensegmente auf und speichern Sie diese.

• Platzieren Sie alle diese Segmente in einem achsenausgerichteten Begrenzungsrahmen für die gesamte Kurve.

Kollisionserkennung :

1) Überprüfen Sie, ob sich die Kugel innerhalb des Begrenzungsrahmens befindet. Wenn nein, keine Kollision.

2) Anderenfalls prüfen Sie, ob eines der oben berechneten einzelnen Segmente mit der Kugel kollidiert. Siehe Artikel zu Linien-Kugel-Schnittpunkten aus Wikipedia .

BEARBEITEN: Wenn Sie eine hohe Präzision benötigen und eine gute Leistung erzielen möchten, können Sie auch einen Hauptbegrenzungsrahmen für die gesamte Kurve erstellen und dann die Kurve in zwei Segmente unterteilen (z . B.: [0.0 - 0.5]und [0.5 - 1.0]). Erstellen Sie für jedes von ihnen eine Bouding-Box und unterteilen Sie dann jedes dieser Segmente erneut in zwei Segmente (geben Sie also [0 - 0.25], [0.25 - 0.5]und [0.5 - 0.75], [0.75 - 1.0]). Fahren Sie so fort, bis Sie eine ausreichende Präzision erreicht haben. binary treeAm Ende haben Sie einen Begrenzungsrahmen mit einem Begrenzungsrahmen für die Hauptkurve an der Wurzel und Liniensegmenten an den Blättern. Durch Suchen in der Baumstruktur erhalten Sie O(log n)anstelle von O(n)(wobei n= Anzahl der Liniensegmente für die Kurve)

Der Schnittpunkt zwischen einer Linie und einer Bezier-Kurve wird mathematisch durch Unterteilen der Kurve erreicht. Dies bedeutet, dass Sie sich auf die Eigenschaft der konvexen Hülle der Kurve verlassen und diese in kleinere Bögen mit verschiedenen Steuerpolygonen auf eine Art von Divide-et-Impera aufteilen.

Dieser Artikel behandelt es bis zu einem gewissen Punkt: http://students.cs.byu.edu/~tom/557/text/cic.pdf .

Das Schöne daran ist, dass der Algorithmus mit jeder Linie funktioniert. Sie müssen lediglich eine starre Transformation auf die Kurve anwenden, damit Sie Ihre Ziellinie als parallel zur Ox-Achse betrachten können.

Ebenso können Sie den Kreis und das Polygon eines solchen Bezier-Bogens überprüfen, wenn Sie einen Bezier-Bogen in zwei Teilbögen unterteilen. Der Kreis sollte das Steuerpolygon eines Bogens schneiden, damit ein Test von Kurve zu Kreis Sinn ergibt.