java - 射线平方交集

Question

在 2D 中，我有一个起点 (x_1, y_1)、一个终点 (x_2, y_2) 和代表正方形三个顶点(左上角、右上角和右下角顶点)的三个点。

我的目标是如果从 (x_1, y_1) 出发并穿过 (x_2, y_2) 的光线与三个顶点给出的平面(或正方形)相交，则返回 true。最终，我想将其扩展到 3D - 与立方体的交集 - 这就是我目前使用 3D vector 的原因。

在回顾了许多其他 SO 问题后，我用 Java 编写了以下代码:

// Determines if a given ray intersects a given square
// R1, R2 are two points on the ray
// S1 (upper left vertex), S2 (upper right vertex), and S3 (lower left vertex)
public static boolean intersectRayWithSquare(Vector3 R1, Vector3 R2, Vector3 S1, Vector3 S2, Vector3 S3) {

    Vector3 dS21 = S2.sub(S1); // Subtract S1 from S2
    Vector3 dS31 = S3.sub(S1);
    Vector3 n = dS21.cross(dS31); // Take the cross product of two vectors
    Vector3 dR = R1.sub(R2);

    double ndotdR = n.dot(dR);

    if (Math.abs(ndotdR) < 1e-25f) {
        return false;
    }

    double t = -n.dot(R1.sub(S1)) / ndotdR;

    Vector3 M = R1.add(dR.scale(t));
    Vector3 dMS1 = M.sub(S1);

    double u = dMS1.dot(dS21);
    double v = dMS1.dot(dS31);

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

这非常适用于查找通过 R1 和 R2 的直线是否与正方形相交。但是，请考虑以下情况:

UPDATED: More accurate picture to better demonstrate the problem

Direct link to imgur as I don't have enough rep to post images D:

如果我们两次调用此函数，每个方 block 一次，它们都会返回 true。我需要调用 (R1, R2, S1) 返回 true 但调用 (R1, R2, S2) 返回 false。

PS:这是我的第一篇文章(但潜伏了很长时间)所以如果需要任何其他信息或者您有任何意见可以帮助我改进我的问题，请告诉我。

Answer 1

所以这个问题可以通过为 boolean 语句添加额外的要求来解决。

return (u >= 0.0 && u <= dS21.dot(dS21) && v >= 0.0 && v <= dS31.dot(dS31) && t < 0);
// t < 0 to eliminate squares behind the ray