"Separating Axis Theorem"-Kollisionerkennung?



  • Hallo,

    ich mache gerade ein 3D-Spiel, indem man mit dem Ball über Plattformen bis ins Ziel rollt.

    Die Plattformen sollen hauptsächlich Polygone sein, also Flächen mit 3-4 Ecken. Da gerade Plattformen nicht wirklich toll aussehen ( damit meine ich z.B. so ein Rechteck: ( 4, 2), (4, 4), ( 2, 4), ( 2, 2) ), will ich auch schräge hinzufügen ( also Oriented Bounding Boxes ). Aber ich habe leider keine Ahnung, wie bei denen die Kollisionsabfrage funktioniert.

    Habe schon gegoogelt und keinen Code gefunden, bei dem ich nachsehen könnte, wie es funktioniert...

    Ich müsste eigentlich nur überprüfen, ob sich der Ball auf der Plattform befindet.

    Was ich weiß: Man muss das schräge Rechteck nur so drehen, dass es gerade ist. Leider kenne mich da überhaupt nicht aus ...
    Wenn ich dann das Rechteck und die Position vom Ball gedreht habe, weiß ich allein weiter.

    Könnte mir das vielleicht jemand erklären?
    Und am besten auch ein einfaches Beispiel! 👍
    Wäre sehr nett! 🙂

    Lg
    SFandler



  • Polygon als Ebene in HNF darstellen. In jedem schritt:
    Sei c der Kugelmittelpunkt. c auf Ebene projizieren -> c'.
    Testen, ob der projizierte Punkt c' innerhalb des Polygons liegt (baryzentrische Koordinaten). Wenn ja, prüfen ob Abstand zwischen c und c' (einfach c in HNF einsetzten) kleiner dem Kugelradius ist. Wenn ja, Kollision. Wenn nein, nicht.

    Du brauchst also kein Separating Axes Theorem (das brauchst du nur, wenn du OOBB vs. OOBB Kollisionserkennung machst)



  • Das klingt erstmal wie ein 2D Problem: Deine Plattform ist ein 2D Polygon und dein Ball ein Kreis. Das geht gut, solange deine Plattform keine Rampen oder dergleichen hat und die Umrandung mindestens so hoch ist wie der Radius des Balles.

    In 2D würde ich das dann so ausrechnen:

    Erstmal feststellen, ob der Ball überhaupt auf deiner Plattform ist. Dazu guckst du, ob der Mittelpunkt des Balles auf deiner Plattform ist (google --> point in polygon problem).

    Wenn du das schon vorher weisst, kannst du den ersten Test auch weglassen.

    Dann für jedes Segment deines Polygons den Abstand zu dem Mittelpunkt des Kreises rausfinden. Dazu musst du zuerst das Segment wie eine Linie behandeln und den dichtesten Punkt auf der Linie zum Mittelpunkt finden. Dann schauen, ob dieser Punkt auch auf dem Segment liegt. Wenn ja, hast du den Abstand zwischen Kreis und Segment. Falls nein, ist der dichteste Punkt einer der beiden Endpunkte.
    Falls der Abstand kleiner als der Kreisradius ist, gibt es eine Kollision.



  • Ok danke für die Antworten! 👍

    Hört sich schon gut an, aber wie finde ich den dichtesten Punkt auf dem Polygon bzw. auf der Linie zum Mittelpunkt des Kreises?

    Lg
    SFandler

    EDIT:
    Habe doch eine Lösung gefunden! 🙂
    Für die, die es wissen wollen:

    t = ( ( point_x - line_x1 ) * dx + ( point_y - line_y1 ) * dy ) / ( dx * dx + dy * dy );
    x0 = line_x1 + t * dx;
    y0 = line_y1 + t * dy;
    

    Point ( x0 | y0 ) ist dann der dichteste Punkt auf der Linie zum Kreis!



  • @Gast_02525:

    Polygon als Ebene in HNF darstellen. In jedem schritt:
    Sei c der Kugelmittelpunkt. c auf Ebene projizieren -> c'.
    Testen, ob der projizierte Punkt c' innerhalb des Polygons liegt (baryzentrische Koordinaten). Wenn ja, prüfen ob Abstand zwischen c und c' (einfach c in HNF einsetzten) kleiner dem Kugelradius ist. Wenn ja, Kollision. Wenn nein, nicht.

    Ich glaube in dem folgenden Fall geht dein Algorithmus schief.

    Polygon P = {
    (0.0; 0.0; 0.0),
    (1.0; 0.0; 0.0),
    (0.0; 1.0; 0.0)
    }

    Keis K = {
    Mittelpunkt = (1.0; 1.0; 0.0}
    Radius = 5
    }



  • Bitte ein Bit schrieb:

    Ich glaube in dem folgenden Fall geht dein Algorithmus schief.

    Polygon P = {
    (0.0; 0.0; 0.0),
    (1.0; 0.0; 0.0),
    (0.0; 1.0; 0.0)
    }

    Keis K = {
    Mittelpunkt = (1.0; 1.0; 0.0}
    Radius = 5
    }

    [/quote]

    Stimmt, zumindest bei

    Polygon P = {
    (0.0; 0.0; 0.0),
    (1.1; 0.0; 0.0),
    (0.0; 1.1; 0.0)
    }

    Dann brauchen wir doch einen vollständigen "Point - Triangle distance" test

    float getDistanceBetweenPointAndTriangle(const Point& pt, const int triID) const {
    
    		const vec3i& tri = m_meshTriangles[triID];
    		const Point& n = m_meshTriangleNormals[triID];
    
    		// Project point onto triangle plane
    		Point dir = m_meshVertices[tri.x]-pt;
    		float dist = dir|n;
    
    		Point posOnPlane = pt+n*dist;
    
    		Point barys = getBarysOfPointWithinTriangle(pt, triID);
    
    		if (barys.x >= 0 && barys.y >= 0 && barys.z >= 0) { // Closest point is in triangle
    			return dist;
    		}
    
    		if ((barys.x * barys.y * barys.z) > 0) { // Two are negative, closest point lies on a vertex of the triangle
    			if (barys.x > 0) {
    				return (m_meshVertices[tri.x].dist(pt));
    			} else if (barys.y > 0) {
    				return (m_meshVertices[tri.y].dist(pt));
    			} else {
    				return (m_meshVertices[tri.z].dist(pt));
    			}
    		}
    
    		// We have only one negative bary
    		if (barys.x < 0) {
    			std::pair<float, float> ret = getParameterOfPointClosestToLine(pt, tri.y, tri.z);
    			h.barys = Point(0, ret.first, ret.second);
    			Point closest = getPointWithBarys(h.barys, triID);
    			return (closest.dist(pt));
    		} else if (barys.y < 0) {
    			std::pair<float, float> ret = getParameterOfPointClosestToLine(pt, tri.x, tri.z);
    			h.barys = Point(ret.first, 0, ret.second);
    			Point closest = getPointWithBarys(h.barys, triID);
    			return (closest.dist(pt));
    		} else {
    			assert(barys.z < 0);
    			std::pair<float, float> ret = getParameterOfPointClosestToLine(pt, tri.x, tri.y);
    			h.barys = Point(ret.first, ret.second, 0);
    			Point closest = getPointWithBarys(h.barys, triID);
    			return (closest.dist(pt));
    		}
            // Never arrive here
    	}
    


  • @Gast_0025:
    Kann es sein das du dein Alg. folgendermaßen erweitert hast ?

    Def.:
    Sei T ein Dreieck mit den Ecken TP1, TP2 und TP3. 
    Die Dreieckslinien werden mit TL1, TL2 und TL3 
    gekennzeichnet.
    
    K sei ein Kreis mit Mittelpunkt KM und Radius R.
    
    Alg.:
    1.) Kreismittelpunkt KM auf Dreiecksebene projizieren -> KM'
    2.) Test ob KM' innerhalb der Dreiecksfläche liegt
      2.1) Wenn JA teste ob Distanz (KM' KM) kleiner ist als R
        2.11) Wenn JA -> Ausgabe SCHNEIDET
        2.11) Wenn NEIN -> Ausgabe SCHNEIDET NICHT
      2.2) Ende
    3.) Für jede Dreieckseite S in {TP1, TP2, TP3} tue
      3.1) Bestimme Fusspunkt F von KM und S
      3.2) Teste ob Distanz (F KM) kleiner ist als R
        3.2.1) Wenn JA -> Ausgabe SCHNEIDET -> Ende
    4.) Ausgabe SCHNEIDET NICHT
    


  • Bitte ein Bit schrieb:

    @Gast_0025:
    Kann es sein das du dein Alg. folgendermaßen erweitert hast ?

    Ja, nur dass ich nicht alle Dreieckskanten prüfen muss sondern immer die gleich die richtige prüfe (bzw. gar keine falls dern nächste Punkt ein Eckpunkt ist)


Log in to reply