Ray-square intersection

Question

In 2D, I have a starting point (x_1, y_1), an ending point (x_2, y_2), and three points which represent three vertices of a square (upper left, upper right, and lower right vertices.)

My goal is to return true if the ray that originates at (x_1, y_1) and goes through (x_2, y_2) intersects with the plane (or square) given by the three vertices. Eventually, I would like to expand this to 3D - intersection with a cube - which is why I am currently using 3D vectors.

After reviewing many other SO questions I have come up with the following code in 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));
}

This works very well to find if the LINE that goes through R1 and R2 intersects with the square. However, consider the following case:

UPDATED: More accurate picture to better demonstrate the problem

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

If we called this function twice, once for each square, they both would return true. I need the call (R1, R2, S1) to return true but the call (R1, R2, S2) to return false.

PS: This is my first post (but a LONG time lurker) so if there is any additional information needed or you have any comments that would help me improve my question please let me know.

Answer 1

So this problem can be fixed by adding an additional requirement for the Boolean statement.

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

Answer 2

Essentially your ray has a starting point, and a direction but no ending point.

All you need to do is after your check to see if any point in the square satisfies the formula of the line check that the direction is correct.

i.e. just looking at the x dimension for simplicity:

if (x1<x2) {
  points_in_square.x must be >= x1
} else if (x1>x2) {
  points_in_square.x must be <= x1 
} else {
  // line is vertical, handle this case
}

You could look at already existing implementations of similar things. For example jMonkeyEngine is an open source Java 3d engine that contains intersections for Rays with Axis Aligned Bounding Boxes - which is essentially exactly what you are looking for. I don't have a link handy but try searching using the keywords I just gave.