Wie prüft man Kollision mit Hilfe von SAT?

SFandler

Hallo,
ich habe schon vor 1-2 Wochen einen Thread erstellt, wo ich gefragt habe, wie SAT funktioniert. Habe jedoch für mein damaliges Problem nur eine Point-in-Triangle Prüfung durchführen brauchen.

Ich möchte jetzt ein Programm schreiben, dass nur die Kollision zwischen zwei Polygonen prüft. Und dazu brauche ich Separating Axis Theorem.

Wie es funktioniert habe ich bereits auf mehreren Seiten gelesen, aber leider finde ich nie einen verständlichen Source Code, wo ich nachsehen kann, wie die "Schatten" auf die Axe ( normale Axe zu einer Seite des Polygons ) projieziert werden.

Ein sehr gutes Tutorial habe ich hier gefunden: http://www.sevenson.com.au/actionscript/sat/
Den Source Code habe ich mir auch angeguckt, hat mir aber leider nicht weitergeholfen.

Kann mir bitte jemand ein einfaches Beispiel geben?

Danke im voraus!

Lg
SFandler

Diese beiden Tutorials sollten dir weiterhelfen:

http://www.codezealot.org/archives/55

http://www.metanetsoftware.com/technique/tutorialA.html

Beide imo sehr gut bebildert.

Yu deiner Frage mit den Projektionen: Du solltest dir vielleicht nochmal anschauen, was das Skalarprodukt ist bzw. wie man es geometrisch deuten kann. Und wenn das immernoch nichts hilft, hinsetzen mit Stift und Papier (und Taschenrechner wenn Skalarprodukt in 2D ausrechnen zu schwer ist ) und wirklich ein paar Fälle durchzeichnen.

knivil

Suche im Netz mal nach der Datei Polycolly.zip . Dort sollte SAT erklaert sein. Gleichzeitig gibt es COde. Leider ist dieser aus softwaretechnischer Sicht grausam.

SFandler

Danke für deinen Beitrag.
Aber ich weiß noch immer nicht, was ich mit dem Skalarprodukt anfangen soll bzw. was es macht.

( In der Schule haben wir leider noch nichts über Vektoren gelernt, deshalb weiß ich recht wenig über sie. )
Könntest du mir vielleicht irgendein Beispiel geben? Und erklären was das Skalarprodukt ist?

Wäre sehr hilfreich!

Lg
SFandler

life

Und ich dachte hier würde eine Kollisionsabfrage auf ein SAT-Problem zurückgeführt werden.

SFandler schrieb:

Danke für deinen Beitrag.
Aber ich weiß noch immer nicht, was ich mit dem Skalarprodukt anfangen soll bzw. was es macht.

( In der Schule haben wir leider noch nichts über Vektoren gelernt, deshalb weiß ich recht wenig über sie. )
Könntest du mir vielleicht irgendein Beispiel geben? Und erklären was das Skalarprodukt ist?

Wäre sehr hilfreich!

Lg
SFandler

Das Skalarprodukt ist eine mathematische Operation zwischen 2 Vektoren. Das wird dir nichts helfen.

(Das ist nicht böse gemeint, aber) Ich schätze, hier wird niemand die Zeit und/oder Lust dazu haben, dir die Grundlagen der Linearen Algebra beizubringen. Grade weil es dazu so viel im Internet (und natürlich in Büchern, aber das wäre für dich sicher Overkill) gibt.

Ich rate dir dringend, dich ein wenig in Vektorrechnung einzuarbeiten.

Ich persönlich kenne grade keine Tutorials, die ich dir empfehlen könnte, also befrag Google am besten mal zu "Einführung in lineare Algebra", "Mathematik für Spieleprogrammierer", "Einführung in Vektorrechnung" etc. Gegebenenfalls in Englisch, falls du das schon gut genug kannst.

SFandler

Ich habe mir jetzt ein paar Tutorials durchgelesen und weiß jetzt wie man mit
Vektoren rechnet, wofür das Skalarprodukt gut ist usw., aber wie die separating
axis theorem funktioniert weiß ich noch immer nicht.
Es muss doch irgendwo ein Tutorial geben, wo einem das genau erklärt wird, Schritt für Schritt.

knivil

Was passt dir nicht an Polycolly.zip ?

SFandler

Naja da ich kein Java programmiere musste ich die Funktion zur Kollisionsprüfung in C++ übersetzen und da ich keinen Schimmer von SAT habe, konnte ich nur alles abschreiben. Funktioniert leider nicht.

Vielleicht gibt's jemanden, der sich ein wenig Zeit nimmt und nachsieht, wo hier der Fehler ist:

// Function to check if two polygons intercept
bool vPolyPoly2 ( Polygon2 vp1, Polygon2 vp2, const Vec2 offset )
{
	bool result = true;
	int index;
	Vec2 E, E0, E1;
	Vec2 xAxis[VEC_POLYGON_POINTS];
	float tAxis[VEC_POLYGON_POINTS];

	int iNumAxis = 0;

	E1 = vp1.point[vp1.size-1];

	for ( index = 0; index < vp1.size -1; index ++ )
	{
		E0 = vp1.point[index];

		E.x = E1.x - E0.x;
		E.y = E1.y - E0.y;

		xAxis[iNumAxis].x = -E.y;
		xAxis[iNumAxis].y = E.x;

		if ( !IntervalIntersect ( vp1, vp2, offset, xAxis[iNumAxis], tAxis[iNumAxis] ) )
		{
			result = false;
		}

		iNumAxis ++;

		E1 = E0;
	}

	E1 = vp2.point[vp2.size-1];

	for ( index = 0; index < vp2.size; index ++ )
	{
		E0 = vp2.point[index];

		E.x = E1.x - E0.x;
		E.y = E1.y - E0.y;

		xAxis[iNumAxis].x = -E.y;
		xAxis[iNumAxis].y = E.x;

		if ( !IntervalIntersect ( vp1, vp2, offset, xAxis[iNumAxis], *tAxis[iNumAxis] ) )
		{
			result = false;
		}

		iNumAxis ++;

		E1 = E0;
	}

        // ----- Hier würde noch nach dem Punkt, wo die Polygone sich treffen gesucht, habe ich aber auslassen, da ich es nicht wissen muss.

	return result;
}

bool IntervalIntersect ( const Polygon2 A, const Polygon2 B, const Vec2 xOffset, const Vec2 xAxis, float *tAxis )
{
	bool result;
	float min0 = 0, max0 = 0,
		  min1 = 0, max1 = 0,
		  h = 0,
		  d0 = 0, d1 = 0;

	getInterval ( A, xAxis, &min0, &max0 );
	getInterval ( B, xAxis, &min1, &max1 );

	h = vDotProduct2 ( xOffset, xAxis );

	min0 = min0 + h;
	max0 = max0 + h;

	d0 = min0 - max1;
	d1 = min1 - max0;

	if ( ( d0 > 0.0 ) || ( d1 > 0.0 ) )
	{
		result = false;
	}
	else
	{
		if ( d0 > d1 )
		{
			*tAxis = d0;
		}
		else
		{
			*tAxis = d1;
		}

		result = true;
	}

	return result;
}

void getInterval ( const Polygon2 P, const Vec2 xAxis, float *min, float *max )
{
	int i;
	float d;

	*min = vDotProduct2 ( P.point[0], xAxis );
	*max = *min;

	for ( i = 1; i < P.size; i ++ )
	{
		d = vDotProduct2 ( P.point[i], xAxis );

		if ( d < *min )
			*min = d;
		else
			if ( d > *max )
				*max = d;
	}
}

Naja, ich war mir ziemlich sicher, dass die Funktion true zurückschickt, wenn sich die Polygone treffen. Auf jeden Fall schickt sie mir immer false.
Ist bestimmt irgendwo ein ganz einfacher Fehler, den ich eingebaut habe.

Wäre echt toll, wenn sich das wer anschauen würde.

LG
SFandler

Bitte ein Bit

Und ich dachte hier würde eine Kollisionsabfrage auf ein SAT-Problem zurückgeführt werden.

Grrrr

Daran habe ich zuerst auch gedacht. Fluch der TLA.