Intersection of Ray and Rectangle in C++

Question

I need the intersection between a ray and a rectangle. So far I have followed the answer here, but after testing it (as explained below) I realized that the implementation is wrong.

bool checkRayLightIntersection(Vec Origin, Vec Dir) {

    //(-10,20,9) is Hard-code of the light position and we add (5.0f) on X and Z axis to
    //make it an area instead of a vertex
    //"Origin" is the position of the eye. Hard coded: (-25, 8, 5)
    //"Dir" is LightPosition - Origin

    float randX = 5.0f; //in the future it will be random, that's why this name
    float randZ = 5.0f;

    Vec P1 = Vec(-10 - randX, 20, 9 + randZ);
    Vec P2 = Vec(-10 + randX, 20, 9 + randZ);
    Vec P3 = Vec(-10 + randX, 20, 9 - randZ);
    Vec P4 = Vec(-10 - randX, 20, 9 - randZ);

    //the majority of the methods first find out where the ray intersects the
    //plane that the rectangle lies on, Ax + By + Cz + D = 0
    //in our case the equation of that plane is easy (I think) -> D = 20

    float t = -(-Origin.y + 20) / (-Dir.y);
    if (t > 0) {
        Vec hitPoint = Origin + Dir * t;
        Vec V1 = (P2 - P1).norm();
        Vec V3 = (P4 - P3).norm();
        Vec V4 = (hitPoint - P1).norm();
        Vec V5 = (hitPoint - P3).norm();
        float V1dotV4 = V1.dot(V4);
        float V3dotV5 = V3.dot(V5);
        if (V1dotV4 > 0 && V3dotV5 > 0) {
            return true;
        }
    }
    return false;
 }

My Vec is a struct defined as follows:

struct Vec {
    double x, y, z;                  // position, also color (r,g,b)
    Vec(double x_ = 0, double y_ = 0, double z_ = 0){ x = x_; y = y_; z = z_; }
    Vec operator+(const Vec &b) const { return Vec(x + b.x, y + b.y, z + b.z); }
    Vec operator-(const Vec &b) const { return Vec(x - b.x, y - b.y, z - b.z); }
    Vec operator-() const { return Vec(-x, -y, -z); }
    Vec operator*(double b) const { return Vec(x*b, y*b, z*b); }
    Vec operator/(double b) const { return Vec(x / b, y / b, z / b); }
    Vec mult(const Vec &b) const { return Vec(x*b.x, y*b.y, z*b.z); }
    Vec& norm(){ return *this = *this * (1 / sqrtf(x*x + y*y + z*z)); }
    double dot(const Vec &b) const { return x*b.x + y*b.y + z*b.z; }
    // cross:
    Vec operator%(Vec&b){ return Vec(y*b.z - z*b.y, z*b.x - x*b.z, x*b.y - y*b.x); }
    double max() const { return x>y && x>z ? x : y > z ? y : z; }
};

I tested the method. So what I tried to do is creating a ray from my Origin to a point that should be outside the Rectangle such as (-10, 20, 19), I added 9 to the Z-axis while the rectangle should be only 5 units larger in each direction (X,-X,Z,-Z). Therefore in my case:

Dir = (-10, 20, 19) - Orig

The method returns true when instead it should return false. Can you please help me understand what I am doing wrong? Thanks in advance.

This is very slow and potentially unstable. Calculating the intersection of a triangle and a ray is a very common problem in computer graphics, check out link, note: your rectangle consists of two triangles — Jonas
I wonder if you used two triangles whether you could have failures along the diagonal. A point might not be inside either triangle. Care would need to be taken so as to guarantee overlap at all points. — stark

lobudge lobudge · Accepted Answer · 2016-03-23T18:32:03

It looks like you are pretty close here, but I'd be curious what results you get for V1dotV4 and V3dotV5.

That said, it looks like you are correctly solving for t since your plane equation comes out to -y + 20 = 0 (i.e. a flat plane at y = 20 with normal [0, -1, 0]).

You can verify that you got a reasonable hitPoint by plugging it back into the equation for your plane and checking that the result is 0.

Assuming hitPoint is correctly on the plane, it looks like your check that hitPoint is inside the rectangle is wrong. You are using the dot product to ensure that the projection of hitPoint onto the edges [P1,P2] and [P4,P3] lies inside that edge. The issue is that [P1,P2] and [P4,P3] are opposite/parallel edges of the rectangle, so your check doesn't tell you anything about where hitPoint is relative to edges [P2,P3] and [P4,P1].

Since you know this is a rectangle, I think it should be sufficient to compute

Vec hitPoint = Origin + Dir * t;
Vec V1 = (P2 - P1).norm();
Vec V2 = (P3 - P2).norm();
Vec V3 = (P4 - P3).norm();
Vec V4 = (P1 - P4).norm();
Vec V5 = (hitPoint - P1).norm();
Vec V6 = (hitPoint - P2).norm();
Vec V7 = (hitPoint - P3).norm();
Vec V8 = (hitPoint - P4).norm();
if (V1.dot(V5) < 0.0) return false;
if (V2.dot(V6) < 0.0) return false;
if (V3.dot(V7) < 0.0) return false;
if (V4.dot(V8) < 0.0) return false;
return true;

Edit My initial assertion was to check two edges for a range of [0,1], but this isn't actually correct. Updated the example code to check all 4 edges.

Another Note You can do this by checking hitPoint against just two perpendicular edges of the rectangle by

Vec hitPoint = Origin + Dir * t;
Vec V1 = P2 - P1;
float lengthV1 = V1.length();
Vec normV1 = V1.norm();

Vec V2 = P4 - P1;
float lengthV2 = V2.length();
Vec normV2 = V2.norm();

Vec hitVec = P - P1;
a = normV1.dot(hitVec);
b = normV2.dot(hitVec);
return (0.0f <= a && a <= lengthV1 && 0.0f <= b && b <= lengthV2);

Intersection of Ray and Rectangle in C++

1 Answers