3D Kollisionsberechnung Dreieckspolygon & Strahl

[thekiller]

Hallo,

ich versuche seit ein paar Tagen ein gutes Beispiel für Ermittlung eines Kollisionspunktes zwischen einem 3-Dimensionalen Dreieckspolygon und einem Strahl.
Meine Suchmaschinenkünste sind anscheinend nicht so ausgeprägt, denn ich finde nicht ein einziges Beispiel. Nur immer verschiedene Möglichkeiten zur Berechnung und deren Formeln dazu ABER NIE ist eine Beispielrechnung dabei...

Könnte mir vielleicht jemand anhand eines Beispiels erklären wie die Rechnung funktioniert?

Gegeben ist z.B. ein Dreieck und ein Strahl mit folgenden Punkten

// Triangle
V1.X = -1.0;
V1.Y = -0.5;
V1.Z = 2.0;

V2.X = -2.0;
V2.Y = 1.5;
V2.Z = -1.0;

V3.X = 1.5;
V3.Y = 0.5;
V3.Z = 0.0;

// Ray:
Ray_V1.X = 0.0;
Ray_V1.Y = 3.0;
Ray_V1.Z = -0.5;

Ray_V2.X = 0.2;
Ray_V2.Y = -3.0;
Ray_V2.Z = 0.0;

Wie ermittle ich ob es einen Schnitt gibt und wenn ja, wo der Strahl auf die Fläche trifft?

MfG Manuel

EDIT.: Die beste Seite die ich dazu gefunden habe ist diese (http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm)
Dort gibt es zwar sogar C++ Quellcode dafür, den ich aber leider nicht übersetzt bekomme

 

[sheel]

Hi

Wenn du den Code überhemne willst, brauchst du Klassen für Triabgle, Vector, Ray...
Vor allem Vektor braucht auch Überladungen für +- und * für das Kreuzprodukt.

Generelles Verfahren:
1) Nimm einen Punkt des Dreiecks als Startpunkt
2) Vektor u=Vektor vom Startpunkt zum Punkt 2 des Dreiecks ermitteln
3) Vektor v=Vektor vom Startpunkt zum Punkt 3 des Dreiecks ermitteln
4) Vektor n=Kreuzprodukt von u und v
5) Wenn die Länge von n 0 ist, waren die drei Dreickspunkt gar kein Dreieck. Ende
6) Vektor dir=Vektor vom Streckenanfang bis zum Streckenende
7) Vektor w0=Vektor vom Dreiecksstartpunkt bis zum Streckenanfang
Das sog. Dotprodukt zweier Vekotren ist x1*x2+y1*y2+z1*z2
8) float a=negatives Dotprodukt von n und w0; float b=Dotprodukt von n und dir
9) Wenn b ungefähr 0 ist (zB zw. -0.000001 und 0.00001) und a==0 ist, liegt die Linie komplett im Dreieck. Ende.
10) Wenn b ungefähr 0 ist und a nicht 0 ist, gibts keinen Schnittpunkt. Ende.
11) float r=a/b
12a) Falls die Linie am Startpunkt bginnt, aber durch den "Endpunkt" weiter ins Unendliche geht: Wenn r negativ ist, gibts keinen Schnittpunkt. Ende.
12b) Falls die Linie wirklich nur vom Start- bis zum Endpunkt geht: Wenn r negativ oder größer als 1 ist, gibts keinen Schnittpunkt. Ende.
13) Punkt x (xyz-Koordinaten)=Streckenanfangspunkt + r*dir
14) float uu, uv, vv=Dot(u,u), (u,v), (v,v)
15) Vektor w=x-Dreiecksstartpunkt
16) float wu, wv=Dot(w,u), (w,v)
17) float D=uv^2-uu*vv
18) float s= (uv*wv-vv*wu)/D
19) float t= (uv*wu-uu*wv)/D
20) Wenn s kleiner 0 oder größer 1 oder t kleiner 0 ist: Kein Schnitt. Ende
21) Wenn s+t größer als 1 ist: Auch kein Schnitt. Ende.
22) X ist der Schnittpunkt

Vielleicht hilfts ja noch mal irgendwem, der über Google hier landet

Gruß

 

[thekiller]

Hallo sheel,

ich glaube du hilfst mir ungemein weiter danke =)

Aber was meinst du mit "negativem Dotprodukt"?

Wenn

a > 0

dann

 a = a * (-1)

?


Und wie ist die Rechnung bei Punkt 13?
Ist diese hier korrekt?

x.x = Streckenanfangspunkt.x + r * dir.x
x.y = Streckenanfangspunkt.y + r * dir.y
x.z = Streckenanfangspunkt.z + r * dir.z

MfG Manuel

EDIT.: Die Klassen kann man auf der Seite auch runterladen. Aber wie gesagt, der Source lässt sich nicht übersetzen

 

[sheel]

Hi

die Klassen gibts auch? Sowas, hab ich gar nicht gesehen...

Zum negativen Dot: Genau das hab ich gemeint. Einfach mal -1.

Zum P. 13: Auch richtig. Wenn man das in Klassen hat, kann man es natürlich in + reinstopfen und dann wirklich nur noch addieren.

Gruß

PS: Etwas ist mir noch aufgefallen: Willst du wirklich ein "Ray" verwenden? Laut Def. fängt dieses bei einem Punkt an und geht dann durch den anderen Punkt weiter ins Unendliche. Soll die Linie nicht beim zweiten Punkt aufgören? Dafür ist der Code nämlich minimal anders. Werd ich noch reinändern.

 

[thekiller]

Ähm ja entschuldige. Er soll nicht ins unendliche gehen. Also ein Segment mit Anfangspunkt und Endpunkt.
Ich hab mal ein Programm geschrieben um deinen Algorithmus zu testen und es scheint nicht ganz zu klappen.

Ich habe im Programm die 3 Punkte für das Dreieck und dem SEGMENT fest definiert. Ich habe bei dem Dreieck und dem Segment darauf geachtet, dass sie sich schneiden.

Laut Programm tun sie dass aber nicht und die Koordinaten für den Schnittpunkt können auch nicht stimmen. Habe ich irgendwo einen Fehler drin?

#include <Windows.h>
#include <math.h>

struct Vertex {
	double	X;
	double	Y;
	double	Z;
};

struct Vector {
	double	X;
	double	Y;
	double	Z;
	double	W;
};

int main() {
	// Dreieck
	Vertex	D1;
	Vertex	D2;
	Vertex	D3;

	// Strecke
	Vertex	R1;
	Vertex	R2;

	// 
	Vector	u;
	Vector	v;
	Vector	n;
	Vector	dir;
	Vector	w0;
	Vector	w;
	double	a;
	double	b;
	double	r;
	double	uu;
	double	uv;
	double	vv;
	double	wu;
	double	wv;
	double	D;

	Vertex	Distance;
	Vertex	x;

	// Initialisierungen
	// Dreieck
	D1.X	= -1.0;
	D1.Y	= -0.5;
	D1.Z	= 2.0;

	D2.X	= -2.0;
	D2.Y	= 1.5;
	D2.Z	= -1.0;
 
	D3.X	= 1.5;
	D3.Y	= 0.5;
	D3.Z	= 0.5;

	// Strecke/Ray
	R1.X	= -0.5;
	R1.Y	= 3.0;
	R1.Z	= 0.5;
 
	R2.X	= -0.5;
	R2.Y	= -3.0;
	R2.Z	= 0.0;
	
	// Originalwerte ausgeben
	printf("Dreieck\n");
	printf("D1.X: %f\n", D1.X);
	printf("D1.Y: %f\n", D1.Y);
	printf("D1.Z: %f\n\n", D1.Z);
	printf("D2.X: %f\n", D2.X);
	printf("D2.Y: %f\n", D2.Y);
	printf("D2.Z: %f\n\n", D2.Z);
	printf("D3.X: %f\n", D3.X);
	printf("D3.Y: %f\n", D3.Y);
	printf("D3.Z: %f\n\n", D3.Z);

	printf("Strecke/Ray\n");
	printf("R1.X: %f\n", R1.X);
	printf("R1.Y: %f\n", R1.Y);
	printf("R1.Z: %f\n\n", R1.Z);
	printf("R2.X: %f\n", R2.X);
	printf("R2.Y: %f\n", R2.Y);
	printf("R2.Z: %f\n\n", R2.Z);

	////////////////////////////////////////////////////////////////////////////////
	// 2) Vektor u=Vektor vom Startpunkt zum Punkt 2 des Dreiecks ermitteln
	u.X	= D1.X + D2.X;
	u.Y	= D1.Y + D2.Y;
	u.Z	= D1.Z + D2.Z;

	Distance.X	= D1.X - D2.X;
	Distance.Y	= D1.Y - D2.Y;
	Distance.Z	= D1.Z - D2.Z;

	if(Distance.X < 0.0)
		Distance.X *= -1.0;
	if(Distance.Y < 0.0)
		Distance.Y *= -1.0;
	if(Distance.Z < 0.0)
		Distance.Z *= -1.0;

	u.W	=	sqrt(
				(((Distance.X * Distance.X) + (Distance.Y * Distance.Y)) / 2) +
				(((Distance.X * Distance.X) + (Distance.Z * Distance.Z)) / 2) +
				(((Distance.Y * Distance.Y) + (Distance.Z * Distance.Z)) / 2)
			);

	printf("u=Vektor\n");
	printf("u.X: %f\n", u.X);
	printf("u.Y: %f\n", u.Y);
	printf("u.Z: %f\n", u.Z);
	printf("u.W: %f\n\n", u.W);

	////////////////////////////////////////////////////////////////////////////////
	// 3) Vektor v=Vektor vom Startpunkt zum Punkt 3 des Dreiecks ermitteln
	v.X	= D1.X + D3.X;
	v.Y	= D1.Y + D3.Y;
	v.Z	= D1.Z + D3.Z;

	Distance.X	= D1.X - D3.X;
	Distance.Y	= D1.Y - D3.Y;
	Distance.Z	= D1.Z - D3.Z;

	if(Distance.X < 0.0)
		Distance.X *= -1.0;
	if(Distance.Y < 0.0)
		Distance.Y *= -1.0;
	if(Distance.Z < 0.0)
		Distance.Z *= -1.0;

	v.W	=	sqrt(
				(((Distance.X * Distance.X) + (Distance.Y * Distance.Y)) / 2) +
				(((Distance.X * Distance.X) + (Distance.Z * Distance.Z)) / 2) +
				(((Distance.Y * Distance.Y) + (Distance.Z * Distance.Z)) / 2)
			);

	printf("v=Vektor\n");
	printf("v.X: %f\n", v.X);
	printf("v.Y: %f\n", v.Y);
	printf("v.Z: %f\n", v.Z);
	printf("v.W: %f\n\n", v.W);

	////////////////////////////////////////////////////////////////////////////////
	// 4) Vektor n=Kreuzprodukt von u und v
	n.X	= (u.Y * v.Z) - (u.Z * v.Y);
	n.Y	= (u.Z * v.X) - (u.X * v.Z);
	n.Z	= (u.X * v.Y) - (u.Y * v.X);

	Distance.X	= u.X - v.X;
	Distance.Y	= u.Y - v.Y;
	Distance.Z	= u.Z - v.Z;

	if(Distance.X < 0.0)
		Distance.X *= -1.0;
	if(Distance.Y < 0.0)
		Distance.Y *= -1.0;
	if(Distance.Z < 0.0)
		Distance.Z *= -1.0;

	n.W	=	sqrt(
				(((Distance.X * Distance.X) + (Distance.Y * Distance.Y)) / 2) +
				(((Distance.X * Distance.X) + (Distance.Z * Distance.Z)) / 2) +
				(((Distance.Y * Distance.Y) + (Distance.Z * Distance.Z)) / 2)
			);

	printf("n=Vektor\n");
	printf("n.X: %f\n", n.X);
	printf("n.Y: %f\n", n.Y);
	printf("n.Z: %f\n", n.Z);
	printf("n.W: %f\n\n", n.W);

	////////////////////////////////////////////////////////////////////////////////
	// 5) Wenn die Länge von n 0 ist, waren die drei Dreickspunkt gar kein Dreieck. Ende
	if(n.W == 0.0) {
		printf("Kein Dreieck\n\n");
		system("PAUSE");
		return 0;
	}

	////////////////////////////////////////////////////////////////////////////////
	// 6) Vektor dir=Vektor vom Streckenanfang bis zum Streckenende
	dir.X	= R1.X + R2.X;
	dir.Y	= R1.Y + R2.Y;
	dir.Z	= R1.Z + R2.Z;

	Distance.X	= R1.X - R2.X;
	Distance.Y	= R1.Y - R2.Y;
	Distance.Z	= R1.Z - R2.Z;

	if(Distance.X < 0.0)
		Distance.X *= -1.0;
	if(Distance.Y < 0.0)
		Distance.Y *= -1.0;
	if(Distance.Z < 0.0)
		Distance.Z *= -1.0;

	dir.W	=	sqrt(
					(((Distance.X * Distance.X) + (Distance.Y * Distance.Y)) / 2) +
					(((Distance.X * Distance.X) + (Distance.Z * Distance.Z)) / 2) +
					(((Distance.Y * Distance.Y) + (Distance.Z * Distance.Z)) / 2)
				);

	printf("dir=Vektor\n");
	printf("dir.X: %f\n", dir.X);
	printf("dir.Y: %f\n", dir.Y);
	printf("dir.Z: %f\n", dir.Z);
	printf("dir.W: %f\n\n", dir.W);

	////////////////////////////////////////////////////////////////////////////////
	// 7) Vektor w0=Vektor vom Dreiecksstartpunkt bis zum Streckenanfang
	w0.X	= D1.X + R1.X;
	w0.Y	= D1.Y + R1.Y;
	w0.Z	= D1.Z + R1.Z;

	Distance.X	= D1.X - R1.X;
	Distance.Y	= D1.Y - R1.Y;
	Distance.Z	= D1.Z - R1.Z;

	if(Distance.X < 0.0)
		Distance.X *= -1.0;
	if(Distance.Y < 0.0)
		Distance.Y *= -1.0;
	if(Distance.Z < 0.0)
		Distance.Z *= -1.0;

	w0.W	=	sqrt(
					(((Distance.X * Distance.X) + (Distance.Y * Distance.Y)) / 2) +
					(((Distance.X * Distance.X) + (Distance.Z * Distance.Z)) / 2) +
					(((Distance.Y * Distance.Y) + (Distance.Z * Distance.Z)) / 2)
				);

	printf("w0=Vektor\n");
	printf("w0.X: %f\n", w0.X);
	printf("w0.Y: %f\n", w0.Y);
	printf("w0.Z: %f\n", w0.Z);
	printf("w0.W: %f\n\n", w0.W);

	////////////////////////////////////////////////////////////////////////////////
	// Das sog. Dotprodukt zweier Vekotren ist x1*x2+y1*y2+z1*z2
	// 8) float a=negatives Dotprodukt von n und w0
	a	= (n.X * w0.X + n.Y * w0.Y + n.Z * w0.Z);
	if(a > 0.0)
		a *= -1.0;

	printf("a=negatives Dotprodukt von n und w0: %f\n\n", a);

	////////////////////////////////////////////////////////////////////////////////
	// 8) float b=Dotprodukt von n und dir
	b	= (n.X * dir.X + n.Y * dir.Y + n.Z * dir.Z);
	printf("b=Dotprodukt von n und dir: %f\n\n", b);

	////////////////////////////////////////////////////////////////////////////////
	// 9) Wenn b ungefähr 0 ist (zB zw. -0.000001 und 0.00001) und a==0 ist, liegt die Linie komplett im Dreieck. Ende.
	if((b > -0.000001 && b < 0.000001) && a == 0.0) {
		printf("Ray liegt komplett im Dreieck\n\n");

		system("PAUSE");
		return 0;
	}

	////////////////////////////////////////////////////////////////////////////////
	// 10) Wenn b ungefähr 0 ist und a nicht 0 ist,gibts, keinen Schnittpunkt. Ende.
	if((b > -0.000001 && b < 0.000001) && a != 0.0) {
		printf("Ray schneidet das Dreieck nicht\n\n");

		system("PAUSE");
		return 0;
	}

	////////////////////////////////////////////////////////////////////////////////
	// 11) float r=a/b
	r	= a / b;

	printf("r=a/b: %f\n\n", r);

	////////////////////////////////////////////////////////////////////////////////
	// 12) Wenn r negativ ist, gibts keinen Schnittpunkt. Ende.
	if(r < 0.0) {
		printf("Ray schneidet das Dreieck nicht\n\n");

		system("PAUSE");
		return 0;
	}

	////////////////////////////////////////////////////////////////////////////////
	// 13) Punkt x (xyz-Koordinaten)=Streckenanfangspunkt + r*dir
	x.X	= R1.X + r * dir.X;
	x.Y	= R1.Y + r * dir.Y;
	x.Z	= R1.Z + r * dir.Z;

	printf("x=Vektor\n");
	printf("x.X: %f\n", x.X);
	printf("x.Y: %f\n", x.Y);
	printf("x.Z: %f\n\n", x.Z);

	////////////////////////////////////////////////////////////////////////////////
	// 14) float uu, uv, vv=Dot(u,u), (u,v), (v,v)
	uu	= (u.X * u.X) + (u.Y * u.Y) + (u.Z + u.Z);
	uv	= (u.X * v.X) + (u.Y * v.Y) + (u.Z + v.Z);
	vv	= (v.X * v.X) + (v.Y * v.Y) + (v.Z + v.Z);

	printf("uu, uv, vv\n");
	printf("uu.X: %f\n", uu);
	printf("uv.X: %f\n", uv);
	printf("vv.Z: %f\n\n", vv);

	////////////////////////////////////////////////////////////////////////////////
	// 15) Vektor w=x-Dreiecksstartpunkt
	w.X	= x.X - D1.X;
	w.Y	= x.Y - D1.Y;
	w.Z	= x.Z - D1.Z;

	printf("Vektor w=x-Dreiecksstartpunkt\n");
	printf("w.X: %f\n", w.X);
	printf("w.Y: %f\n", w.Y);
	printf("w.Z: %f\n\n", w.Z);

	////////////////////////////////////////////////////////////////////////////////
	// 16) float wu, wv=Dot(w,u), (w,v)
	wu	= (w.X * u.X) + (w.Y * u.Y) + (w.Z + u.Z);
	wv	= (w.X * v.X) + (w.Y * v.Y) + (w.Z + v.Z);

	printf("float wu, wv\n");
	printf("wu: %f\n", wu);
	printf("wv: %f\n\n", wv);

	////////////////////////////////////////////////////////////////////////////////
	// 17) float D=uv^2-uu*vv
	D	= (uv * uv) - (uu * vv);

	printf("float D=uv^2-uu*vv\n");
	printf("D: %f\n\n", D);

	////////////////////////////////////////////////////////////////////////////////
	// 18) float s= (uv*wv-vv*wu)/D
	double	s;

	s	= ((uv * wv) - (vv * wu)) / D;

	printf("float s= (uv*wv-vv*wu)/D\n");
	printf("s: %f\n\n", s);

	////////////////////////////////////////////////////////////////////////////////
	// 19) float t= (uv*wu-uu*wv)/D
	double	t;

	t	= ((uv * wu) - (uu * wv)) / D;

	printf("float t= (uv*wu-uu*wv)/D\n");
	printf("t: %f\n\n", t);

	////////////////////////////////////////////////////////////////////////////////
	// 20) Wenn s kleiner 0 oder größer 1 oder t kleiner 0 ist: Kein Schnitt. Ende
	if(s < 0.0 || s > 1.0 || t < 0.0) {
		printf("Ray schneidet das Dreieck nicht\n\n");

		system("PAUSE");
		return 0;
	}
	
	////////////////////////////////////////////////////////////////////////////////
	// 21) Wenn s+t größer als 1 ist: Auch kein Schnitt. Ende.
	printf("s + t: %f\n", s + t);
	if((s + t) > 1.0) {
		printf("Ray schneidet das Dreieck nicht\n\n");

		system("PAUSE");
		return 0;
	}
	printf("\n");
	
	////////////////////////////////////////////////////////////////////////////////
	// 22) X ist der Schnittpunkt

	system("PAUSE");
	return 0;
}

 

[sheel]

Hi

// Assume that classes are already given for the objects:
// Point and Vector with
// coordinates {float x, y, z;}
// operators for:
// == to test equality
// != to test inequality
// (Vector)0 = (0,0,0) (null vector)
// Point = Point ± Vector
// Vector = Point - Point
// Vector = Scalar * Vector (scalar product)
// Vector = Vector * Vector (cross product)
// Line and Ray and Segment with defining points {Point P0, P1;}
// (a Line is infinite, Rays and Segments start at P0)
// (a Ray extends beyond P1, but a Segment ends at P1)
// Plane with a point and a normal {Point V0; Vector n;}
// Triangle with defining vertices {Point V0, V1, V2;}
// Polyline and Polygon with n vertices {int n; Point *V;}
// (a Polygon has V[n]=V[0])

0: Laut dieser Erklärung auf der Seite hast du mit Vertex schonmal einen Point.
Als Vector werden aber auch nur diese drei Koordinaten verwendet, nur mit einem anderen Namen (damit man den Sinn unterscheiden kann).
Du könntest also auch für den Vektor die struct Vertex verwenden und W einfach weglassen.

2 und 3: Was ist das? Meiner Meinung nach musst du doch nur Jeweils x y und z subtrahieren...

4: Die Längenberechnung kannst du weglassen, da du sie nicht brauchst. Durch die struct-Änderungen fällt er ja auch schon weg.

5: Da W ja weg ist, prüf, ob x y und z alle gleich 0 sind.

6 und 7: Gleich wie 2 und 3

8: Es soll nicht unbedingt eine negative Zahl werden, sondern das Verzeichen umgedreht werden, wie es ein math. Minus eben macht. Wenn beim Dot eine negaive Zahl als Ergebnis kommt, soll die positiv gemacht werden.
Einfach a=-a

12: Da du ja ein Segment statt einer Ray willst, fehlt noch das ||>1.0

Und am Ende fehlt noch die Ausgabe von x

Gruß

 

[thekiller]

Ich versteh grad nur Bahnhof...

2 und 3:
Was ist was?

4: Warum kann ich die Längenberechnung weglassen? Du hast doch bei Punkt 2 und 3 geschrieben, dass ich die Vektoren vom Startpunkt des Dreiecks zu Punkt 2 und 3 errechnen soll. Und ein Vektor hat ne Richtung un einen Betrag...



Die Werte die ich für das Dreieck und das Segment festgelegt habe sind ja die absoluten Punkte im Koordinatensystem.

 

[sheel]

2 und 3: Mit "Was ist das" meinte ich den Code.
Du addierst die Koordinaten und rechnest eine Länge aus.
Dabei müsstest du doch nur x y und z von D2 bzw. D3 minus denen vom D1 rechnen.

Einen 3D-Vektor kann man zwar mit zwei Winkeln und einer Länge angeben.
Hier reicht es aber auch (und ist schneller als sqrt...), wenn man einfach sagt: ... Unterschied auf der x-Achse, ... auf Y, ... auf Z.

Damit sollte auch 4 klar werden.

Gruß

 

[sheel]

Hi

hier der Code.
stdio.h ist nur für printf, und aus math.h brauch ich nur die Wurzel sqrt.
Im Main werden nur Werte zugewiesen und später wieder ausgegeben.

Die Klasse coord ist vergleichbar mit Punkt/Point/Vertex. Einfach xyz-Koordinaten (float).
Dazu:
-Konstruktor für 0-0-0, ints, floats und coords und er Destruktor natürlich (obwohl er leer ist)
-Die Operatoren =, ==, +, -, +=, -= jeweils für coord, float und int
-circa0 überprüft, ob x y und z alle jeweils zwischen -0.0001 und 0.0001 sind
-Operaotr ! für den Betrag/die Länge des Vektors
-Castmöglichkeiten in float und int, ergeben beide auch wieder den Vektorbetrag
-Ops. *, *=, /, /= für float und int (x y und z alle damit multiplizieren/dividieren)
-Ops. * und *= für coords: Berechnet das Skalarprodukt (bzw. Dotprodukt im engl. Artikel)
-Ops. / und /=: Für das Kreuzprodukt/Vektorprodukt. Ein x kann man ja als Operator nicht nehmen, deshalb /.
-Op. ~ für den Einheitsvektor (Gleiche Richtung, aber Länge 1)
Vieles von dem Zeug wird gar nicht gebraucht und ist nur der Vollständigkeit halber da.

Die Klasse line: Ziemlich unspektakulär: Zwei coords, a und b, für Anfang und Ende

Klasse triangle: coord a b und c für die Eckpunkte und der Methode intersect.

intersect:
Parameter: Die Line und ein coord zum Speichern der Schnittpunktskoordinaten
Returnwert: 1=OK, 0=Kein Schnitt oder kein gültiges Dreieck, -1=Linie liegt komplett im Dreieck

#include<stdio.h>
#include<math.h>

class coord
{
public:
	float x,y,z;

	coord(){x=y=z=0;}
	coord(int v){x=y=z=(float)v;}
	coord(int xx,int yy,int zz){x=(float)xx;y=(float)yy;z=(float)zz;}
	coord(float v){x=y=z=v;}
	coord(float xx,float yy,float zz){x=xx;y=yy;z=zz;}
	coord(coord &cc){x=cc.x;y=cc.y;z=cc.z;}
	~coord(){}

	coord operator +(coord &a){return coord(x+a.x,y+a.y,z+a.z);}
	coord operator +(int a){return coord(x+(float)a,y+(float)a,z+(float)a);}
	coord operator +(float a){return coord(x+a,y+a,z+a);}
	coord operator -(coord &a){return coord(x-a.x,y-a.y,z-a.z);}
	coord operator -(int a){return coord(x-(float)a,y-(float)a,z-(float)a);}
	coord operator -(float a){return coord(x-a,y-a,z-a);}
	coord &operator +=(coord &a){x+=a.x;y+=a.y;z+=a.z;return *this;}
	coord &operator +=(int a){x+=(float)a;y+=(float)a;z+=(float)a;return *this;}
	coord &operator +=(float a){x+=a;y+=a;z+=a;return *this;}
	coord &operator -=(coord &a){x-=a.x;y-=a.y;z-=a.z;return *this;}
	coord &operator -=(int a){x-=(float)a;y-=(float)a;z-=(float)a;return *this;}
	coord &operator -=(float a){x-=a;y-=a;z-=a;return *this;}
	coord &operator =(coord &a){x=a.x;y=a.y;z=a.z;return *this;}
	bool operator ==(coord &a){if(x!=a.x)return 0;if(y!=a.y)return 0;if(z!=a.z)return 0;return 1;}
	coord &operator =(int a){x=(float)a;y=(float)a;z=(float)a;return *this;}
	bool operator ==(int a){if(x!=(float)a)return 0;if(y!=(float)a)return 0;if(z!=(float)a)return 0;return 1;}
	coord &operator =(float a){x=a;y=a;z=a;return *this;}
	bool operator ==(float a){if(x!=a)return 0;if(y!=a)return 0;if(z!=a)return 0;return 1;}

	operator float(){return !(*this);}
	operator int(){return ((int)(!(*this)));}
	float operator!(){return (float)sqrt(x*x+y*y+z*z);}
	float operator *(coord &a){return x*a.x+y*a.y+a.z*z;}
	coord &operator *=(coord &a){x=y=z=x*a.x+y*a.y+a.z*z;return *this;}
	coord operator *(int a){return coord(x*(float)a,y*(float)a,z*(float)a);}
	coord &operator *=(int a){x*=(float)a;y*=(float)a;z*=(float)a;return *this;}
	coord operator *(float a){return coord(x*a,y*a,z*a);}
	coord &operator *=(float a){x*=a;y*=a;z*=a;return *this;}
	coord operator /(int a){return coord(x/(float)a,y/(float)a,z/(float)a);}
	coord &operator /=(int a){x/=(float)a;y/=(float)a;z/=(float)a;return *this;}
	coord operator /(float a){return coord(x/a,y/a,z/a);}
	coord &operator /=(float a){x/=a;y/=a;z/=a;return *this;}
	coord operator /(coord &a){return coord(y*a.z-z*a.y,z*a.x-x*a.z,x*a.y-y*a.x);}
	coord& operator /=(coord &a)
	{
		float xx,yy,zz;
		xx=y*a.z-z*a.y;
		yy=z*a.x-x*a.z;
		zz=x*a.y-y*a.x;
		x=xx;y=yy;z=zz;
		return *this;
	}

	coord operator ~(){float len=!(*this);return coord(x/len,y/len,z/len);}
	bool circa0()
	{
		if(x<(-0.0001)||x>0.0001||y<(-0.0001)||y>0.0001||z<(-0.0001)||z>0.0001)return 0;
		return 1;
	}
};

class line
{
public:
	coord a,b;
};

class triangle
{
public:
	coord a,b,c;

	//ret: 1 wenn ok, 0 wenn kein Schnitt oder dreieck, -1 wenn linie komplett im dreieck
	int intersect(line &L,coord &C)
	{
		//1-4
		coord u=a-c;
		coord v=b-c;
		coord n=u/v;

		//5-7
		if(n==0)return 0;
		coord dir=L.b-L.a;
		coord w0=L.a-a;

		//8-10
		float _a=-(n*w0),_b=n*dir;
		if(_b>=(-0.0001)&&_b<=0.0001)
		{
			if(_a>=(-0.0001)&&_a<=0.0001)return -1;
			return 0;
		}

		//11-12
		float r=_a/_b;
		if(r<0.00||r>1.00)return 0;

		//13-16
		C=L.a;
		C+=(dir*r);
		float uu=u*u,uv=u*v,vv=v*v;
		coord _w=C-c;
		float wu=_w*u,wv=_w*v;

		//17-19
		float D=uv*uv-uu*vv;
		float _s=(uv*wv-vv*wu)/D,_t=(uv*wu-uu*wv)/D;

		//20-22
		if(_s<0.00||_t<0.00||_s>1.00)return 0;
		_s+=_t;
		if(_s>1.00)return 0;
		return 1;
	}
};

int main()
{
	triangle d;
	line l;

	d.c=coord(0,0,0);
	d.a=coord(10,0,0);
	d.b=coord(0,10,0);
	l.a=coord(3,3,-10);
	l.b=coord(1,1,10);
	//Sollten sch in 2|2|0 schneiden

	coord x;
	printf("Returnwert: %d\n",d.intersect(l,x));
	printf("S=%f|%f|%f\n",x.x,x.y,x.z);
	return 0;
}

Gruß

 

[thekiller]

Hi sheel,

also ich bin dir sehr dankbar dafür, dass du mal deinen Code dazu zeigst aber der Code is echt ma beschissen formatiert^^ Zumindest in der "coord"-Klasse ;-)

MfG Manuel