4. Line-Plane-Intersection funktioniert nur an 2 von 3 Kanten eines Dreiecks

Line-Plane-Intersection funktioniert nur an 2 von 3 Kanten eines Dreiecks

  • O

    Hallo,

    ich habe folgendes implementiert: http://en.wikipedia.org/wiki/Line-plane_intersection

    Ich habe ein Dreieck mit den Punkten

    x   y   z
p1   0   0  -5
p2  -2  -1  -3
p3   1   -1  -3

    Dann eine Linie die vom Punkt 0, 0, 0 ausgeht und bei 0, 0, -5 endet.
    x und y kann ich beim Zielpunkt mit den Cursortasten aendern.

    In der ersten Zeile der letzte Wert (0, 1) gibt den Rueckgabewert von der Funktion an.
    http://xccv.de/jing/2011-09-08_1732.swf

    Problem ist dass die Funktion immer true zurueck gibt im Bereich der von 2 Seiten aufgespannt wird (im Video die untere und linke Seite des Dreiecks).
    Kommt die Linie ausserhalb von der rechten Seite des Dreiecks wird weiterhin true zurueckgegeben.

    Jetzt meine Frage: Ist das Verhalten so korrekt und ich habe den Wikipediaartikel falsch verstanden? Oder sollte wirklich nur wahr herauskommen wenn die Linie und das Dreieck sich kreuzt?

    /edit: Habe gerade noch einmal nachgelesen und es steht ja da:

    [...]then the intersection point is in the plane inside the triangle spanned by the three points[...]

    Dann jetzt die Frage warum geht es nur bei 2 von 3 Seiten?

    Vielen Dank!

    Oliver

    0
  • K

    Problem ist dass die Funktion immer true zurueck gibt im Bereich der von 2 Seiten aufgespannt wird

    Wahrscheinlich hast du sie falsch implementiert. Ohne Code zu sehen, kann dir hier wohl keiner helfen. Oder sollen wir raten, welchen Fehler du vielleicht gemacht hast?

    Ausserdem geht es einfacher: http://paulbourke.net/geometry/planeline/ . Danach muss nur noch geprueft werden, ob der Schnittpunkt im Dreieck liegt. Das ist mit 3x leftOf-Test erledigt.

    0
  • O

    Hier der Code (ganz vergessen, gehoert natuerlich dazu):

    Die ersten 6 Parameter sind die beiden Punkte auf der Linie.
    Die restlichen das Dreieck.

    inline bool lineplane_intersect(
	double xa, double ya, double za,
	double xb, double yb, double zb,
	double x0, double y0, double z0,
	double x1, double y1, double z1,
	double x2, double y2, double z2)
{
	double
		m11 = xa-xb, m12 = x1-x0, m13 = x2-x0,
		m21 = ya-yb, m22 = y1-y0, m23 = y2-y0,
		m31 = za-zb, m32 = z1-z0, m33 = z2-z0;

	double
		n11 = m22*m33 - m23*m32, n12 = m13*m32 - m12*m33, n13 = m12*m23 - m13*m22,
		n21 = m23*m31 - m21*m33, n22 = m11*m33 - m13*m31, n23 = m13*m21 - m11*m23,
		n31 = m21*m32 - m22*m31, n32 = m12*m31 - m11*m32, n33 = m11*m22 - m12*m21;

	double det = 1.0 / (n11*n22*n33 + n12*n23*n31 + n13*n21*n32 + n13*n22*n31 + n12*n21*n33 + n11*n23*n32);

	n11 *= det; n12 *= det; n13 *= det;
	n21 *= det; n22 *= det; n23 *= det;
	n31 *= det; n32 *= det; n33 *= det;

	m11 = xa - x0;
	m21 = ya - y0,
	m31 = za - z0;

	double
		t = n11*m11 + n12*m21 + n13*m31,
		u = n21*m11 + n22*m21 + n23*m31,
		v = n31*m11 + n32*m21 + n33*m31;

	if(t < 0 || t > 1)
		return false;
	if(u < 0 || u > 1)
		return false;
	if(v < 0 || v > 1)
		return false;

	return u + v <= 1;
}

    Den Link hatte ich auch gefunden, aber nicht so ganz durchgestiegen. Da fand' ich das bei Wikipedia erst einmal ein wenig einfacher.

    Hier noch mal ein Video mit Ausgabe von t, u, v und u+v:
    http://xccv.de/jing/2011-09-08_1827.swf

    u < 0 wenn ausserhalb der linken Seite
    v < 0 wenn ausserhalb der unteren Seite

    Und ich vermute mal u+v sollte groesser als 1 sein, wenn ausserhalb der rechten Seite, was es aber nicht tut.

    0
Anmelden zum Antworten