Pixelgenaue Kollisionsdetektion

[Degush]

Hey,
ich habe leider kein passendes Thema zu meinem Problem hier im Forum gefunden. Es geht um eine pixelgenaue Kollisionsdetektion für eine Spieleengine, die ich schreibe, um in Zukunft leicht Spiele entwickeln zu können, speziell für android.
Es soll der Kollisionspunkt von zwei Polygon arrays festgestellt werden, wenn es einen gibt.

Mein Ansatz dafür ist folgender:

java-Code #5103 public static Point getCollisionPoint(Collidable ac, Collidable bc)

Diese Methode soll überprüfen, ob und wo sich zwei Körper berühren. Später werde ich noch einfügen, dass diese komplexe Kollisionsabfrage nur gemacht wird, wenn sich die Bounding boxes der Körper schneiden. Mein Ansatz ist der, dass zwischen je 2 Koordinaten einer Figur eine Linie gezeichnet wird und der theoertische Schnittpunkt beider Linien gefunden wird. Also so:

Drawing #976

Das geschieht mithilfe einer linearen Funktion und mithilfe von Sonderfällen für senkrechte oder waagerechte Linien. Wenn der x-Wert des Schnittpunktes größer gleich A.x, kleiner gleich B.x, größer gleich D.x und kleiner gleich C.x ist, dann wird der Schnittpunkt als Kollisionspunkt betrachtet.
java-Code #5104 class Line

Drawing #977

In diesem Bild sieht man, wie es gehen sollte. Der Schnittpunkt liegt zwischen den x-Werten der Strecken AB und CD.
Was allerdings ist meiner Testumgebung passiert ist folgendes:
Kostenloser Bilder Upload Service - Gratis Bilder hochladen / uploaden ohne Anmeldung

Oft klappt es allerdings auch. Hier im Anhang ist mal die Demo, aus der ihr vielleicht einige Informationen ziehen könnt.

TIG_2.jar - Speedy Share - upload your files here

Ich bin ratlos. Was eigentlich geschehen sollte, ist dass der Würfel abprallt (elastische Kollision).

 

[Marco13]

Viele Links, viele Bilder, eine obskure JAR, aber keine Frage...

Die Polygone als einzelne Linien anzusehen ist wohl schonmal nicht verkehrt, Details muss man sich noch überlegen. Aber das mit der linearen Funktion ist mit ziemlicher Sicherheit Unfug. Vielleicht hilft sowas wie http://www.java-forum.org/awt-swing...-zwischen-objekt-kante-finden.html#post837614 , aber ... eigentlich glaube ich, dass man in 2D eigentlich nur den Fall prüfen muss, dass ein Punkt mit einer Linie kollidiert. Wenn man das wirklich kontinuierlich machen will, hilft einem so ein trivialer Schnitttest genausowenig weiter, wie eine Methode, die zu einem gegebenen Punkt und einer gegebenen Linie den Punkt auf der Linie bestimmt, die dem gegebenen Punkt am nächsten liegt. Wenn man das mit diskreter Kollisionserkennung machen will, muss man sich überlegen, wie. Bei einem bewegten Punkt und einem starren Objekt also nicht-bewegten linien würde schon der verlinkte Schnitttest reichen. Aber die Frage, wie die Kollisionsantwort aussieht, stellt sich in allen Fällen, und ist alles andere als einfach zu beantworten.

 

[Degush]

Hmm,
danke erst einmal für deine Antwort.
Ich habe glaube ich nicht gut genug erklärt, was ich möchte.
Ich habe eine Kollisionsdetektion geschrieben, die allerdings nicht zuverlässig funktioniert und möchte Untersützung bei der Fehlersuche / einen anderen Ansatz, der vielleicht schneller ist.

Hier noch mal mein Ansatz:
Die Polygone der Figuren werden als eine Menge von Linien betrachtet. Ich berechne für jede Linie der Figur A den Schnittpunkt mit jeder Linie der Figur B. Drawing #978
Wenn einer dieser Schnittpunkte auf einem gemeinsamen Abschnitt der beiden zu vergleichenden Linien bildet, wird eine Kollision erkannt.
Drawing #979
Das heißt: Wenn der x-Wert des Schnittpunktes größer ist als der x-Wert des linken Punktes der Linie im linken Körper und kleiner als der x-Wert im rechten Punkt und größer als der x-Wert des linken Punktes im rechten Körper und kleiner als der x-Wert des rechten Punktes im rechten Körper, dann zähle ich die Figuren als kollidiert. Also
Drawing #980
Das macht es wohl am verständlichsten.

Vielen Dank für jede Hilfe

edit: Meine Punkt Klasse nutzt übrigens double

edit 2: Habe im englischen Wikipedia etwas über Polygonkollision gefunden. Die nutzt einen anderen Ansatz. Ich werde mich mal einlesen und dann entscheiden, ob ich meinen Ansatz ändern soll.
Polygon Collision - GPWiki

 

[Marco13]

Das heißt: Wenn der x-Wert des Schnittpunktes größer ist als der x-Wert des linken Punktes der Linie im linken Körper und kleiner als der x-Wert im rechten Punkt und größer als der x-Wert des linken Punktes im rechten Körper und kleiner als der x-Wert des rechten Punktes im rechten Körper, dann zähle ich die Figuren als kollidiert.

Wann kann es einen Schnittpunkt der Liniensegmente geben, ohne, dass eine Kollision vorliegt? Und warum soll nur x dabei eine Rolle spielen?

Das Separating Axis Theorem kam mir bei deinen Zeichnungen auch in den Sinn, aber ich habe es selbst noch nicht angewendet (in 2D könnte es aber sogar vergleichsweise einfach umsetzbar sein)