3D-Ray-Quad-intersection-test in java

Hier ist ein überblick über die Lösung:

1. Berechnen Sie die Gleichung der Ebene das Quadrat (vorausgesetzt, die vier Punkte sind coplanar),

2. Tun ray /ebenenschnitt, diese gibt Ihnen entweder nichts (ray, die parallel zu dem Platz und ich ignorieren den Fall, wo der Strahl ist eingebettet in der Ebene) oder ein Punkt,

3. Sobald Sie den Schnittpunkt, Projekt auf einem lokalen 2D-basis in der Ebene des Quadrates, wird diese 2D-Koordinaten (u, v) der Punkt auf der Ebene,

4. Prüfen Sie, ob der 2D-Koordinaten (u, v) im Quadrat (vorausgesetzt, die vier Punkte bilden ein Parallelogramm, und Sie wählte zwei benachbarten Kanten für den lokalen 2D-basis), wenn ja, dann gibt es Kreuzung (und die u/v-Koordinaten).

Nun mit der eigentlichen Gleichungen, vorausgesetzt, die vier quadratischen Eckpunkte sind wie folgt platziert:

   S1 +------+ S2
      |      |
      |      |
   S3 +------+ S4

1. Durch die normale der Ebene ist: n = (S2 - S1) x (S3 - S1)

   Einen Punkt M gehört zu dieser Ebene iff-es erfüllt die folgende Gleichung: n . ( M - S1 ) = 0

2. Einen Punkt M gehört die ray-iff, geschrieben werden kann: M = R1 + t * dR mit dR = R2 - R1

   Berechnen Sie die ray - /ebenenschnitt (gleichsetzen der beiden vorherigen Gleichungen):

   n . ( M - S1 ) = 0 = n . ( R1 + t * dR - S1 ) = n . (R1 - S1) + t * n . Dr.

   Wenn n ein . dR ist 0, dann ist die Ebene ist nicht parallel zu dem Strahl, und es gibt keinen Schnittpunkt (wieder ignoriert den Fall, wo der Strahl ist eingebettet in der Ebene).

   Else t = -n . (R1 - S1) /n . Dr. und Sie dieses Ergebnis in die Vorherige Gleichung M = R1 + t * dR gibt die 3D-Koordinaten der Schnittpunkt M.

3. Projekt der Vektor M - S1 auf die beiden Vektoren S2 - S1 S3 - S1 (die eckigen Kanten ab S1), dies gibt beiden zahlen (u, v):

   u = (M - S1) . (S2 - S1)

   v = (M - S1) . (S3 - S1)

4. Wenn 0 <= u <= |S2 - S1|^2 und 0 <= v <= |S3 - S1|^2 ist, dann ist der Schnittpunkt M liegt innerhalb des Quadrats, sonst ist es außerhalb.

Und schließlich ein Beispiel für ein Java-Implementierung von der vorherigen Gleichungen (optimiert für das Lesen erleichtern...):

public class Test {
    static class Vector3 {
        public float x, y, z;

        public Vector3(float x, float y, float z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        public Vector3 add(Vector3 other) {
            return new Vector3(x + other.x, y + other.y, z + other.z);
        }

        public Vector3 sub(Vector3 other) {
            return new Vector3(x - other.x, y - other.y, z - other.z);
        }

        public Vector3 scale(float f) {
            return new Vector3(x * f, y * f, z * f);
        }

        public Vector3 cross(Vector3 other) {
            return new Vector3(y * other.z - z * other.y,
                               z - other.x - x * other.z,
                               x - other.y - y * other.x);
        }

        public float dot(Vector3 other) {
            return x * other.x + y * other.y + z * other.z;
        }
    }

    public static boolean intersectRayWithSquare(Vector3 R1, Vector3 R2,
                                                 Vector3 S1, Vector3 S2, Vector3 S3) {
        //1.
        Vector3 dS21 = S2.sub(S1);
        Vector3 dS31 = S3.sub(S1);
        Vector3 n = dS21.cross(dS31);

        //2.
        Vector3 dR = R1.sub(R2);

        float ndotdR = n.dot(dR);

        if (Math.abs(ndotdR) < 1e-6f) { //Choose your tolerance
            return false;
        }

        float t = -n.dot(R1.sub(S1)) / ndotdR;
        Vector3 M = R1.add(dR.scale(t));

        //3.
        Vector3 dMS1 = M.sub(S1);
        float u = dMS1.dot(dS21);
        float v = dMS1.dot(dS31);

        //4.
        return (u >= 0.0f && u <= dS21.dot(dS21)
             && v >= 0.0f && v <= dS31.dot(dS31));
    }

    public static void main(String... args) {
        Vector3 R1 = new Vector3(0.0f, 0.0f, -1.0f);
        Vector3 R2 = new Vector3(0.0f, 0.0f,  1.0f);

        Vector3 S1 = new Vector3(-1.0f, 1.0f, 0.0f);
        Vector3 S2 = new Vector3( 1.0f, 1.0f, 0.0f);
        Vector3 S3 = new Vector3(-1.0f,-1.0f, 0.0f);

        boolean b = intersectRayWithSquare(R1, R2, S1, S2, S3);
        assert b;

        R1 = new Vector3(1.5f, 1.5f, -1.0f);
        R2 = new Vector3(1.5f, 1.5f,  1.0f);

        b = intersectRayWithSquare(R1, R2, S1, S2, S3);
        assert !b;
    }
}