在Java中的3D Ray-Quad交叉测试

Question

在3D空间中,我试图确定光线/线是否与正方形相交,如果是,则它与相交的正方形上的x和y位置相交.

我有两点代表的光线:

R1 = (Rx1, Ry1, Rz1) and 
R2 = (Rx2, Ry2, Rz2)

正方形由四个顶点表示:

S1 = (Sx1, Sy1, Sz1), 
S2 = (Sx2, Sy2, Sz2), 
S3 = (Sx3, Sy3, Sz3) and 
S4 = (Sx4, Sy4, Sz4).

我在网上找到了很多代数方程,但似乎没有一个完全符合这个问题.理想情况下,我想在Java代码中得到答案,但是我可以轻松转换为代码的等式也可以.

所有帮助将不胜感激.

Answer 1

以下是该解决方案的概述:

1. 计算平方的平面方程(假设四个点是共面的),

2. 做一个光线/平面交叉点,这给你什么都没有(光线平行于正方形,我忽略光线嵌入平面的情况)或点,

3. 一旦有了交点,在广场平面上以局部二维投影,这将给出平面上点的二维坐标(u,v),

4. 检查2D坐标(u,v)是否在正方形内(假设四个点形成平行四边形,并为局部2D基础选择两个相邻边),如果是,则存在交点(并且您具有u/v坐标) ).

现在用实际方程,假设四个方形顶点放置如下:

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

1. 平面的法线是:n =(S2-S1)x(S3-S1)

   如果满足这个等式,则点M属于该平面:n.(M-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)/ n.dR并将该结果插入前面的等式M = R1 + t*dR给出交点M的3D坐标.

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