Bounding box collision - Richtung ermitteln

Hallo,

weiß jemand zufälligerweise, wie man bei einer Bounding Box Kollision die Richtung der Kollision ermitteln kann? Ich habe das bisher so gelöst:

bool intersects(const SDL_Rect& rect) const{
        SDL_Rect bounds = get_global_bounds();
        return !(bounds.w < rect.x || bounds.x > rect.w || bounds.h < rect.y || bounds.y > rect.h);
    }

    bool intersects_from_right(const SDL_Rect& rect) const{
        return intersects(rect) && get_global_bounds().w > rect.x;
    }

Was auch irgendwo funktioniert, nur wenn man mehrere der intersects_from_x() Funktionen in einer Schleife benutzt, dann klappt es nicht mehr richtig. Hat jemand einen Lösungsvorschlag?

Anhand deiner exakten Fehlerbeschreibung (klappt nicht mehr richtig) werden die meisten direkt wissen was zu tun ist.

sitztwackeltpassthatluft schrieb:

Anhand deiner exakten Fehlerbeschreibung (klappt nicht mehr richtig) werden die meisten direkt wissen was zu tun ist.

Das Problem ist, dass meine intersects_from_x() Funktionen uneindeutig sind. intersects_from_right() liefert auch true zurück, wenn ein Objekt ein anderes Objekt von z.B. oben kollidiert. Oder von einer anderen Seite. Drum wollte ich nach einem Weg fragen, der ganz sicher funktioniert, auch wenn das Objekt quer durch ein anderes fliegt.

SeppJ

Für Leute, die mit SDL nicht vertraut sind: Könntest du mal erläutern, was du hast und was du möchtest? So wie ich das verstehe, hast du zwei Rechtecke gegeben (Frage: Die sind parallel zu den Koordinatenachsen orientiert? Oder beliebig?) und möchtest nun zwei Dinge wissen:
a) Gibt es eine Überschneidung? Diese Frage hast du gelöst.
b) Für eines der Rechtecke: Welche Seite(n) bedeckt das andere Rechteck? Dies ist die Frage mit der du Probleme hast.

Habe ich dies richtig verstanden?

SeppJ schrieb:

Für Leute, die mit SDL nicht vertraut sind: Könntest du mal erläutern, was du hast und was du möchtest?

Ich habe zwei Objekte. Eines (Objekt A) steht einfach so mitten im Raum. Das andere (Objekt kann man mit den Arrow-Keys bewegen. Wenn das Objekt B das Objekt A von oben kollidiert, soll Objekt A - pluff - einfach verschwinden. Andernfalls wird Objekt B eine neue Position bekommen.

(Frage: Die sind parallel zu den Koordinatenachsen orientiert? Oder beliebig?)

Und genau hier fangen meine Mathe-Kenntnisse an zu schwanken. Ich versuchs mal zu erklären: Ein Objekt steht einfach bewegungslos da, und das andere kann man seitlich und diagonal mit den Arrow-Tasten bewegen.

b) Für eines der Rechtecke: Welche Seite(n) bedeckt das andere Rechteck? Dies ist die Frage mit der du Probleme hast.

Habe ich dies richtig verstanden?

Ja. Es soll ermittelt werden, ob das Objekt von oben, unten, links oder rechts kollidiert und dann dementsprechend handeln. Das Problem bei meinem Code ist halt, dass es noch zu uneindeutig ist, von welcher Seite kollidiert wird. Kleines Beispiel:

if(obj1.intersects_from_right(obj2.get_global_bounds()) || obj1.intersects_from_left(obj2.get_global_bounds()))
    dostuff1();

else if(obj1.intersects_from_up(obj2.get_global_bounds()))
    dostuff2();

Als ich das ausgetestet habe, musste ich feststellen, dass intersects_from_right/left true zurückliefert, obwohl die Kollision von oben stattfindet und ich weiß nicht, womit ich die if-Bedingung in meinen intersects_from_x() Funktionen noch ergänzen muss.

Ansonsten gibt es vielleicht noch irgendwelche Buchempfehlungen die unter anderem solche (ziemlich mathematische) Themen behandeln?

SeppJ

Du hast viel geschrieben, aber leider keine der Fragen beantwortet. Ich war an der mathematischen Formulierung des Problems interessiert.

Boxer schrieb:

Ansonsten gibt es vielleicht noch irgendwelche Buchempfehlungen die unter anderem solche (ziemlich mathematische) Themen behandeln?

Das ist Geometrie der Mittelstufe. Dementsprechend vermutlich ein Mathebuch für die entsprechenden Klassen.

SeppJ schrieb:

Du hast viel geschrieben, aber leider keine der Fragen beantwortet. Ich war an der mathematischen Formulierung des Problems interessiert.

Nungut, ich versuchs nochmal:

Gegeben sind zwei Rechtecke A und B. Um eine Bounding-Box-Kollision zu testen, mache ich wie folgt:

NOT (A.right < B.left || A.left > B.right || A.bottom < B.top || A.top > B.bottom)

Soweit funktioniert das auch. Nun gehe ich einen Schritt weiter und sage Bounding-Box-Kollision-from-Right:

NOT (A.right < B.left || A.left > B.right || A.bottom < B.top || A.top > B.bottom) AND A.right > B.left

Das soll heißen: Wenn (im Allgemeinen) kollidiert UND die rechte Seite von A größer ist als die linke Seite von B, somit die rechte Seite von A in B liegt, dann hat eine Kollision von rechts stattgefunden.

Und nun muss ich wissen, warum das nicht so tut, wie beschrieben.

Womit muss ich meine Bedingung ergänzen, damit ganz eindeutig erkannt wird, von welcher Seite die Kollision stattgefunden hat?

Danke für die Geduld.

SeppJ

Boxer schrieb:

NOT (A.right < B.left || A.left > B.right || A.bottom < B.top || A.top > B.bottom)

Soweit funktioniert das auch.

Der Fall, dass ein Rechteck das andere umschließen kann, kann nicht vorkommen?

Nun gehe ich einen Schritt weiter und sage Bounding-Box-Kollision-from-Right:

NOT (A.right < B.left || A.left > B.right || A.bottom < B.top || A.top > B.bottom) AND A.right > B.left

Das soll heißen: Wenn (im Allgemeinen) kollidiert UND die rechte Seite von A größer ist als die linke Seite von B, somit die rechte Seite von A in B liegt, dann hat eine Kollision von rechts stattgefunden.

Und nun muss ich wissen, warum das nicht so tut, wie beschrieben.

Weil bei einer Kollision von oben trotzdem die rechte Seite innerhalb des anderen Rechtecks liegen kann, ja sogar muss. Du solltest lieber gucken, welche der Seiten noch außerhalb liegen.

SeppJ schrieb:

Weil bei einer Kollision von oben trotzdem die rechte Seite innerhalb des anderen Rechtecks liegen kann, ja sogar muss. Du solltest lieber gucken, welche der Seiten noch außerhalb liegen.

Haha, stimmt.
Dass ich da nicht selbst drauf gekommen bin.
Dankeschön.

Bengo

Wenn man das ganze etwas allgemeiner machen möchte, kann man sich ja den Methoden der Vectoranalysis bedienen. Anstatt die Kollision zu analysieren, bestimmst du die Flugrichtung des kollidierenden Objekts. Im Prinzip kannst du einfach 2-3 Wertepaare aus der Vergangenheit nehmen und daraus eine Richtig machen (Einfach Vektoren subtrahieren, dann vielleicht noch mit dem dritten Wert mitteln), dann hast du etwas mehr Informationen als Unten, Oben, Links, Rechts und es funktioniert mit beliebigen Objekten.

Wenn man die Kollision eines Punktes zu einem Dreieck testen will, muss man auch feststellen, wie die Drei Geraden des Dreiecks zueinander stehen.

Also, ob man jeweils bei den Geraden abfragen muss, ob der Punkt links, rechts, oben oder unterhalb der Gerade ist.

Dies klappt nicht immer, wenn man vom Mittelpunkt des Dreiecks ausgeht. Aber es klappt, wenn man vom übrig geblieben Punkt ausgeht, also von jeweils dem Punkt des Dreiecks, der jeweils nicht auf der Geraden liegt. Bei diesen übrig gebliebenen Punkten kann man abfragen, ob sie jeweils links, rechts, oberhalb oder unterhalb der jeweiligen Gerade liegen.

So kann man dann den drei Geraden die Vergleichszeichen (> oder <) zuordnen und dann testen, ob der Punkt im Dreieck liegt oder nicht.

SeppJ schrieb:

(Frage: Die sind parallel zu den Koordinatenachsen orientiert? Oder beliebig?)

Wenn man dann ein Rechteck testen möchte, das nicht parallel zu den Koordinatenachsen orientiert ist, teilt man das Rechteck einfach in zwei Dreiecke auf.

muemmel

Hi,

wenn man wissen will, von wo die Kollision erfolgt, könnte es praktisch sein, nicht mit den Außengrenzen zu arbeiten, sondern mit den Schwerpunkten/Mittelpunkten und der Richtung in die sie sich bewegen.

Gruß Mümmel

Sorry, mir ist glaube ich ein Fehler unterlaufen. Es ist auch schon lange her, dass ich mich damit befasst habe.

Multipost schrieb:

Dies klappt nicht immer, wenn man vom Mittelpunkt des Dreiecks ausgeht.

Dies stimmt glaube ich doch nicht ganz. Aber wenn man aus zwei Punkten des Dreiecks eine Gerade bildet und dann vom übrig gebliebenen Punkt ausgeht, spart man sich zumindest die Berechnung für den Mittelpunkt/Schwerpunkt.

Für den ganzen Algorithmus muss man noch den Punkt-Geraden-Abstand implementieren. Dabei sollte der Abstand auch positiv oder negativ angeben, damit die Vergleichszeichen funktionieren.

Und die Geraden die sich aus dem Dreieck ergeben (und die entsprechenden Abfragen) in zwei Gruppen aufteilen (horizontale oder vertikale) für den Fall, dass eine Gerade genau horizontal bzw. vertikal ist. Also dies glaube ich nur dann, wenn man den Punkt-Geraden-Abstand so implementiert, dass es den vertikalen oder horizontalen Abstand von der Geraden ausgibt.