4. Kollision von drehbaren Rechtecken

Kollision von drehbaren Rechtecken

  • F

    Hallo,
    ich bin dabei mein Abschlussprojekt für die Computergrafik zu schreiben.

    Es gibt da zur Zeit leider ein kleineres Problem: Die Kollisionsberechnung.

    Ich habe zwei Rechteck (zwei Autos), die sich bewegen und drehen lassen. Nun wollte ich die Kollision berechnen.

    Ich habe da dieses Tut genutzt: http://www.gamedev.net/reference/articles/article2604.asp (englisch)

    herausgekommen ist dieser Quelltext (nur ein Ausschnitt):

    axis[0][0] = myCar[0].rahmen[0][0] - myCar[0].rahmen[1][0] + myCar->pos[0];
axis[0][1] = myCar[0].rahmen[0][1] - myCar[0].rahmen[1][1] + myCar->pos[2];
axis[1][0] = myCar[0].rahmen[0][0] - myCar[0].rahmen[2][0] + myCar->pos[0];                
axis[1][1] = myCar[0].rahmen[0][1] - myCar[0].rahmen[2][1] + myCar->pos[2];
axis[2][0] = myCar[1].rahmen[1][0] - myCar[1].rahmen[3][0] + myCar->pos[0];
axis[2][1] = myCar[1].rahmen[1][1] - myCar[1].rahmen[3][1] + myCar->pos[2];
axis[3][0] = myCar[1].rahmen[1][0] - myCar[1].rahmen[0][0] + myCar->pos[0];
axis[3][1] = myCar[1].rahmen[1][1] - myCar[1].rahmen[0][1] + myCar->pos[2];

                    /*
                    UR - 0
                    UL - 1
                    LR - 2
                    LL - 4
                    */
                    for (int c = 0; c < 2; c++)//Auto 1/2
                    {
                        for (int k = 0; k < 4; k++)//Achsen 1-4
                        {
                            min_proj[c][k] = 1000000; //Startwert für die Min-Berechnung
                            max_proj[c][k] = 0; //Startwert für die Max-Berechnung

                            //errechne Punkte
                            for (int j = 0; j < 4; j++)//Projektionspunkte 1-4
                            {
                                temp_data = ((myCar[k].rahmen[0][0] * axis[k][0] + myCar[k].rahmen[0][1] * axis[k][1])/
                                             (axis[k][0]*axis[k][0] + axis[k][1]*axis[k][1]));     
                                projector[j][0] = temp_data * axis[k][0]; //Projektor auf Achse k - x-Wert
                                projector[j][1] = temp_data * axis[k][1]; //Projektor auf Achse k - y-Wert

                                //Min/Max ermitteln
                                temp_data = projector[j][0]*axis[k][0] + projector[j][1]*axis[k][1];
                                if (min_proj[c][k] > temp_data)
                                {
                                    min_proj[c][k] = temp_data;
                                }
                                if (max_proj[c][k] < temp_data)
                                {
                                    max_proj[c][k] = temp_data;
                                }

                            }
                        }
                    }
                    //Punkte überprüfen
                    collision = true; //erstmal von einer Kollision ausgehen

                    for (int i = 0; i < 4; i++) //Überprüfen ob ein Wert außerhalb des Rechtecks liegt ->wenn ja: keine Kollision
                    {
                        if (min_proj[1][i] <= max_proj[0][i] && max_proj[1][i] >= min_proj[0][i])
                        {
                            collision = false;
                            break;
                        }
                    }
                    if (collision)
                        std::cout << "Collision detectet" << std::endl;

    Leider funktioniert das ganze nicht wie gewollt...es wird eigentlich nie eine Kollision erkannt...
    Ich habe beim Debuggen gemerkt das die Variable temp_value sehr kleine Werte erhält...

    Ich habe nun schon sehr lange mit suchern verbracht, aber den Fehler nicht gefunden. Ich hoffe auch alles aus dem englischen Artikel richtig verstanden zu haben...

    Bin für jegliche Hilfe dankbar,
    firecooler90

    der Post ist leider sehr lang gworden...ich hab aber leider auch nix für nen Spoiler gefunden...

    0
  • M

    Ein genereller Tipp:

    Generiere dir mal mehrere Fälle mit Papier und Bleistift, die Kollisionen verursachen und welche die es nicht tun. Versuche nun mit diesen mal den Algorithmus nachzuvollziehen (ich nehme an, dass das der "Seperating Axis" ist) dann wirst du auf den Fehler kommen...

    Erläutere mal was denn die Variablen axis, projector und temp_data bedeuten, dann kann ich vielleicht mehr dazu sagen.

    Viel Erfolg

    0
  • F

    Danke für deine Antwort...

    megaweber schrieb:

    ich nehme an, dass das der "Seperating Axis" ist

    da liegst du goldrichtig 😉

    erstmal kurz die Variablen erklärt:
    axis: 4 Achsen mit jeweils 2 Koordinaten

    ist im Tutorial so beschrieben:

    Axis1.x = A.UR.x - A.UL.x
Axis1.y = A.UR.y - A.UL.y
Axis2.x = A.UR.x - A.LR.x
Axis2.y = A.UR.y - A.LR.y
Axis3.x = B.UL.x - B.LL.x
Axis3.y = B.UL.y - B.LL.y
Axis4.x = B.UL.x - B.UR.x
Axis4.y = B.UL.y - B.UR.y

    also A und B sind die beiden Rechtecke, U steht für oben, L für unten und R und L stehen jeweils für links und rechts:
    http://images.gamedev.net/features/programming/2dRotatedRectCollision/fig4.png

    projector:
    Die Achsen werden auf eine Achse projeziert. Die jeweils längsten und kürzesten Projketionen werden gespeichert (nur die Länge)

    temp_data:
    2 mal zwischenspeicher um doppelte Berechnungen zu vermeiden:

    temp_data = ((myCar[k].rahmen[0][0] * axis[k][0] + myCar[k].rahmen[0][1] * axis[k][1])/(axis[k][0]*axis[k][0] + axis[k][1]*axis[k][1]));

    -> Projektionsberechnung

    temp_data = projector[j][0]*axis[k][0] + projector[j][1]*axis[k][1];

    -> Längenberechnung der Projektion

    Ich werde nun mal probieren das alles manuell durchzurechnen...hoffe das bringt was (bin nicht so das Mathe-Genie).

    EDIT: Hab oben mal noch ein paar Kommentare hinzugefügt...

    0
  • S

    Hallo,

    Wenn deine Kollision nicht allzu genau sein muss, kannst du deine Rechtecke als Kreise interpretieren und so eine leichte Kollisionsberechnung benutzen.

    Du könntest ein Rechteck auch in zwei Vierecke aufteilen und diese als Kreise interpretieren, damit das ganze etwas genauer wird.

    0
  • F

    Das mit den Kreisen habe ich bis jetzt auch schon so...
    (also jedes Auto ein Kreis)

    Das ganze ist von der Berechnung sehr einfach, aber auch relativ ungenau. Deshalb wollte ich ja etwas genaueres.

    Aber da die Zeit drängt werde ich vielleicht auch damit vorlieb nehmen müssen.
    Ich muss mir scheinbar auch noch was überlegen was bei einer Kollision passiert. Bis jetzt habe ich einfach die Werte wieder auf den letzten Wert ohne Kollision zurückgesetzt...das ist allerdings ein totales geruckel...

    EDIT:
    ich habe auch noch etwas fertiges gefunden:
    http://www.codeproject.com/KB/GDI-plus/PolygonCollision.aspx

    leider ist das ganze in C# und ich muss das irgendwie umschreiben...
    es wäre auch schon eine Lösung für den Fall der Kollision vorhanden.
    Ich mag es sonst eigentlich nicht bei anderen abzukupfern, aber da ich unter starkem Zeitdruck stehe belibt mir wohl nicht viel übrig...

    0
Anmelden zum Antworten