Kollision von Linen

[Halan]

Hey Leute,

in meinem Programm benutze ich verschieden Primitive zur Kollisionsberechnung. Darunter sind auch Linien, dies können aber eine bestimmte dicke haben.

Zurzeit benutze ich folgendes Verfahren um heuristisch eine Kollisionberechung durchzuführen. "tolerance" gibt hierbei die Dicke der Linie an.
Das funktioniert auch ganz gut, ist aber für lange Linien sehr problematisch.

Code: Alles auswählen

bool geometryTest(const line2d& l1, const line2d& l2, const f32 tolerance)
{
    // TODO : Improve speed e.g. remove square roots..
    // TODO : this is optimised for short lines. Fix it for longer ones

	f32 len1 = l1.getLength();
	f32 len2 = l2.getLength();

	vector2df d1 = (l1.End-l1.Start) / len1;
	vector2df d2 = (l2.End-l2.Start) / len2;

	for(f32 i = 0; i <= len1; i += 0.1f)
		for(f32 j = 0; j <= len2; j += 0.1f)
		{
			vector2df p1 = l1.Start + d1 * i;
			vector2df p2 = l2.Start + d2 * j;

			if(distanceSquared(p1, p2) < sqr(0.1f+tolerance))
				return true;
		}

	return false;
}

Ich habe im Netz nun u.A. folgende Methode gefunden die um einiges schneller aussieht: http://flassari.is/2008/11/line-line-in ... cplusplus/. Bei dieser wird aber nicht die Dicke der Linie in Betracht gezogen.

Hat jemand Ideen das ganze zu verbessern? Habe mir auch schonmal überlegt die Linie in ein rotiertes Viereck umzuwandeln. Aber das scheint mir mehr Aufwand zu sein als nötig.

[simbad]

Deine Linien als Vierecke betrachten. Das sind sie ja eigentlich auch. Dann kannst du die gleiche Methode verwenden wie bei Vierecken.

[Matthias Gubisch]

Sollten die Linien nicht eher Zylinder sein als Vierecke (Quader)

Wenn du nur ein TRUE/FALSE benötigst würde ich die Distanz zwischen den Linien berechnen und testen ob dieser kleiner als LinenestärkeA + LinenstärkeB ist. Wenn ja treffen sich die beiden Linien.

Schau mal auf http://www.geometrictools.com dort solltest du Methoden für beinah alle erdenklichen Anwenungen im 3D Grafikbereich finden.
Ein Distanzfunktion für 3D linen gibt es dort auf alle Fälle, hab dich auch selber schon mal verwendet und funktioniert ganz gut. Die sollte auch deutlich schneller sind als deine Methode mit der for-Schleife und zudem unabhängig von der Länge der Geraden, bzw. des Strahls

[Halan]

Deine Linien als Vierecke betrachten. Das sind sie ja eigentlich auch. Dann kannst du die gleiche Methode verwenden wie bei Vierecken.

Diese Vierecke wären aber nicht axis-aligned was das ganze um einiges komplexer machen würde.

[eXile]

Code: Alles auswählen

for(f32 i = 0; i <= len1; i += 0.1f)
    for(f32 j = 0; j <= len2; j += 0.1f)
    {
        vector2df p1 = l1.Start + d1 * i;
        vector2df p2 = l2.Start + d2 * j;

        if(distanceSquared(p1, p2) < sqr(0.1f+tolerance))
            return true;
    }

Bitte nicht sowas. Als Rechtecke modellieren und einfach einen separierenden Achsentest durchführen.

[Jonathan]

Bestimme eine Verbindungslinie die senkrecht auf beiden Strahlen steht. Vergleich die Länge damit mit der Summe der breiten der Linien und du bist fertig.
Ich bin mir grad nicht ganz sicher, aber bei SAT von 2 beliebigen Boxen hast du eine ganze Reihe an möglichen separierenden Ebenen. Außerdem sind es ja in der Tat Zylinder und keine Boxen.

[eXile]

In diesem Thread:

• Leute, die den Eingangspost nicht richtig lesen können
• Leute, die den Unterschied zwischen Gerade und Liniensegment nicht kennen
• Leute, die nicht die Äquivalenz zwischen 2D-OBB-Intersektion und 2D-Liniensegment-mit-Dicke-Intersektion erkennen

„Eine ganze Reihe“ ist hier übrigens bis zu 8 Achsen mit jeweils 4 Punkten testen.

[Alexander Kornrumpf]

Komm, direkt im 2. Post steht die Lösung doch schon.

Außerdem sind in dem Stackoverflow Thread auch ein Million obscurer Lösungen. Da sind wir relativ gar nicht so schlecht dran.

[Jonathan]

Ok, ich gebe zu, den ersten Post nur überflogen zu haben und dachte somit, es wäre ein 3D Problem. Ja, naja, der Rest ergibt sich dann ja.

[Halan]

Mit SAT hab ich das ganze jetzt erstmal so umgesetzt. Code ist nicht sonderlich hübsch, hab ich grad in 20 minuten geschrieben. Funktionieren tuts ja. Aber iwie bin ich nicht wirklich zufrieden damit.
Sind schon ein paar kleine Optimierungen drin. So sorgt "getDirections()" zB dafür dass keine Richtungen/Normalen doppelt vorkommen.

Zeitlich komme ich auf eine Spanne von 15 bis 200 Mikrosekunden. Wobei die Ausgabe der Messergebnisse das ganze natürlich verfälscht ("wer misst, misst Mist").

Erstmal erzeuge ich die rotierten Vierecke ( hier einfach nur ein vector von linien)

Code: Alles auswählen

vector2df getNormal(const line2d& line)
{
    vector2df dir = line.getDirection();
    vector2df normal(-dir.Y, dir.X);
    normal.normalize();

    return normal;
}

vector<line2d> toLines(const line2d& line, f32 border)
{
    vector2df normal = getNormal(line);

    vector2df p1 = line.Start + normal * border;
    vector2df p2 = line.Start - normal * border;
    vector2df p3 = line.End + normal * border;
    vector2df p4 = line.End - normal * border;

    return {line2d(p1, p2), line2d(p2, p3), line2d(p3, p4), line2d(p4, p1)};
}

Dann der eigentlich collisioncode

Code: Alles auswählen

bool geometryTest(const vector<line2d>& lines1, const vector<line2d>& lines2)
{
    // start of the projection ray,
    // doesn't actually matter where it is
    vector2df ray_start(0,0);

    vector<vector2df> directions = getDirections(lines1, lines2);

    for(auto direction: directions)
    {
        vector2df normal = getNormal(direction);
        ray2d proj_ray(ray_start, normal);

        vector<vector2df> points1;
        vector<vector2df> points2;

        for(auto it : lines1)
        {
            ray2d cur_ray1(it.Start, direction);
            ray2d cur_ray2(it.End, direction);

            pair<bool, vector2df> int1 = cur_ray1.intersection(proj_ray);
            pair<bool, vector2df> int2 = cur_ray2.intersection(proj_ray);

            if(int1.first)
                points1.push_back(int1.second);

            if(int2.first)
                points1.push_back(int2.second);

        }

        for(auto it : lines2)
        {
            ray2d cur_ray1(it.Start, direction);
            ray2d cur_ray2(it.End, direction);

            pair<bool, vector2df> int1 = cur_ray1.intersection(proj_ray);
            pair<bool, vector2df> int2 = cur_ray2.intersection(proj_ray);

            if(int1.first)
                points2.push_back(int1.second);

            if(int2.first)
                points2.push_back(int2.second);
        }

        rect2df bounds1 = getBoundaries(points1);
        rect2df bounds2 = getBoundaries(points2);

        if(!geometryTest(bounds1, bounds2))
            return false;
    }

    // no gap found
    return true;
}

[CrystalCoder]

Hi,

ich hab dein Ergebnis eben erstmal nur überflogen, kann daher nicht viel dazu sagen.

Zeitlich komme ich auf eine Spanne von 15 bis 200 Mikrosekunden

Du weisst aber schon, dass ein einzelner Durchlauf im Prinzip nichts aussagt?


Ich würde es wahrscheinlich wie folgt machen:

Code: Alles auswählen

bool KollisionstestLinienMitDicke(CLinie *linie1, CLinie *linie2)
{
	// Schritt 1: Linien als Geraden betrachten
	CGerade *gerade1 = new CGerade(linie1->richtung, linie1->startpunkt);
	CGerade *gerade2 = new CGerade(linie2->richtung, linie2->startpunkt);
	if(gerade1->ParallelZu(gerade2))
	{
		if(gerade1->AbstandZu(gerade2) > (linie1->dicke+linie2->dicke))
		{
			delete gerade1;
			delete gerade2;
			return false;
		}
	}
	else // Geraden schneiden sich => prüfen ob auch die Linien das auch tun
	{
		float fAbstand1, fAbstand2, fMinAbstand;
		bool bKollision = false;

		// ------------------------------------------------
		// gerade1 und linie2 auf Kollision prüfen
		fAbstand1 = gerade1->AbstandZuPunkt(linie2->startpunkt);
		fAbstand2 = gerade1->AbstandZuPunkt(linie2->Endpunkt);

		// Punkte müssen auf beiden Seiten der Gerade liegen
		if(fAbstand1 <= 0 && fAbstand2 >= 0 || fAbstand1 >= 0 && fAbstand2 <= 0)
			bKollision = true; // Sagt noch nicht so viel aus

		// jetzt noch Dicke beachten
		if(!bKollision)
		{
			fMinAbstand = min(abs(fAbstand1), abs(fAbstand2));
			// Wenn hier keine Kollision stattgefunden hat, dann kann man direkt aussteigen
			if(fMinAbstand > linie1->dicke + linie2->dicke * 0.5f)
			{
				delete gerade1;
				delete gerade2;
				return false;
			}
		}

		// ------------------------------------------------------------------------------------------------------------------------
		// gerade1 und linie2 ergaben eine Kollision, jetzt noch umgekehrten Fall prüfen (linie1 mit gerade2)
		fAbstand1 = gerade2.AbstandZuPunkt(linie1.startpunkt);
		fAbstand2 = gerade2.AbstandZuPunkt(linie1.Endpunkt);

		// Punkte müssen auf beiden Seiten der Gerade liegen
		if(fAbstand1 <= 0 && fAbstand2 >= 0 || fAbstand1 >= 0 && fAbstand2 <= 0)
			bKollision = true; // Sagt noch nicht so viel aus

		// jetzt noch Dicke beachten
		if(!bKollision)
		{
			fMinAbstand = min(abs(fAbstand1), abs(fAbstand2));
			// Wenn hier keine Kollision stattgefunden hat, dann kann man direkt aussteigen
			if(fMinAbstand > linie1.dicke*0.5f + linie2.dicke)
			{
				delete gerade1;
				delete gerade2;
				return false;
			}
		}
	}

	delete gerade1;
	delete gerade2;

	// Da der Kollisionstest nicht vorzeitig beendet wurde schneiden sich die Linien (oder berühren sich zumindest)
	return true;
}

EDIT: Mhm, irgendwie werden die Tabs ignoriert

[Sternmull]

So was wie new und delete hat aber nichts in einer performance-kritischen und wahrscheinlich sehr oft ausgeführten Funktion wie der Kollisionserkennung zu suchen.

[CrystalCoder]

Wollte nur sicherstellen, dass es die Objekte gibt. Dass das noch optimierbar ist, ist mir bewusst. Es ging nur um das Verfahren als solches.

[Halan]

Hey Leute ich bins nochmal!

Erstmal danke, der separierende Achsentest funktioniert bei mir jetzt und ich hab malwieder nen nützlichen Algorithmus gelernt.

Leider brauch ich nochmal euere Hilfe. Ich will überprüfen ob ein Form (bzw eine Gruppe von Formen) in einer anderen Form (bzw Gruppe von Formen) enthalten ist. Das geht ja mit dem Achsentest afaik nicht, da er nur collision/nicht-colllison testet.

Tipps?

mfg
Halan

[dot]

Was genau meinst du mit "enthalten sein"?

[Halan]

Was genau meinst du mit "enthalten sein"?

Dass die eine Form sich *vollständig* in der Anderen befindet.

[dot]

Wenn es sich bei den Formen um konvexe Polygone handelt, dann musst du nur prüfen, ob die Vertices der einen alle innerhalb der anderen Form liegen. Ansonsten wirds wohl komplizierter...