#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;
}