Тест пересечения 3D Ray-Quad в java

Вот обзор решения:

1. Вычислите плоское уравнение квадрата (при условии, что четыре точки лежат в одной плоскости),

2. Сделайте пересечение луча/плоскости, это даст вам либо ничего (луч параллелен квадрату, и я игнорирую случай, когда луч встроен в плоскость), либо точку,

3. Получив точку пересечения, спроецируйте ее на локальную 2D-основу на плоскость квадрата, это даст 2D-координаты (u, v) точки на плоскости,

4. Проверьте, находятся ли 2D-координаты (u, v) внутри квадрата (при условии, что четыре точки образуют параллелограмм, и вы выбрали два соседних ребра для локального 2D-базиса), если да, то есть пересечение (и у вас есть координаты u/v ).

Теперь с реальными уравнениями, предполагая, что четыре квадратные вершины расположены следующим образом:

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

1. Нормаль к плоскости: n = (S2 - S1) x (S3 - S1)

   Точка M принадлежит этой плоскости тогда и только тогда, когда она удовлетворяет следующему уравнению: n . ( М - S1 ) = 0

2. Точка M принадлежит лучу тогда и только тогда, когда можно записать: M = R1 + t * dR, где dR = R2 - R1

   Вычислите пересечение луча/плоскости (приравняйте два предыдущих уравнения):

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

   Если н . dR равно 0, тогда плоскость параллельна лучу и пересечения нет (опять же, игнорируя случай, когда луч вложен в плоскость).

   В противном случае t = -n . (R1 - S1)/н. dR и подстановка этого результата в предыдущее уравнение M = R1 + t * dR дает трехмерные координаты точки пересечения M.

3. Проецируйте вектор M - S1 на два вектора S2 - S1 и S3 - S1 (квадратные ребра, начинающиеся с S1), это дает два числа (u, v):

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

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

4. Если 0 ‹= u ‹= |S2 - S1|^2 и 0 ‹= v ‹= |S3 - S1|^2, то точка пересечения M лежит внутри квадрата, иначе — снаружи.

И, наконец, пример Java-реализации предыдущих уравнений (оптимизированный для удобства чтения...):

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