c++ - 3D Line Segment and Plane Intersection

Question

I'm trying to implement a line segment and plane intersection test that will return true or false depending on whether or not it intersects the plane. It also will return the contact point on the plane where the line intersects, if the line does not intersect, the function should still return the intersection point had the line segmenent had been a ray. I used the information and code from Christer Ericson's Real-time Collision Detection but I don't think im implementing it correctly.

The plane im using is derived from the normal and vertice of a triangle. Finding the location of intersection on the plane is what i want, regardless of whether or not it is located on the triangle i used to derive the plane.

The parameters of the function are as follows:

contact = the contact point on the plane, this is what i want calculated
ray = B - A, simply the line from A to B
rayOrigin = A, the origin of the line segement
normal = normal of the plane (normal of a triangle)
coord = a point on the plane (vertice of a triangle)

Here's the code im using:

bool linePlaneIntersection(Vector& contact, Vector ray, Vector rayOrigin, Vector normal, Vector coord) {

    // calculate plane
    float d = Dot(normal, coord);

    if (Dot(normal, ray)) {
        return false; // avoid divide by zero
    }

    // Compute the t value for the directed line ray intersecting the plane
    float t = (d - Dot(normal, rayOrigin)) / Dot(normal, ray);

    // scale the ray by t
    Vector newRay = ray * t;

    // calc contact point
    contact = rayOrigin + newRay;

    if (t >= 0.0f && t <= 1.0f) {
        return true; // line intersects plane
    }
    return false; // line does not
}

In my tests, it never returns true... any ideas?

Answer 1

I am answering this because it came up first on Google when asked for a c++ example of ray intersection :)

The code always returns false because you enter the if here :

if (Dot(normal, ray)) {
   return false; // avoid divide by zero
}

And a dot product is only zero if the vectors are perpendicular, which is the case you want to avoid (no intersection), and non-zero numbers are true in C.
Thus the solution is to negate ( ! ) or do Dot(...) == 0.
In all other cases there will be an intersection.

On to the intersection computation : All points X of a plane follow the equation

Dot(N, X) = d

Where N is the normal and d can be found by putting a known point of the plane in the equation.

float d = Dot(normal, coord);

Onto the ray, all points s of a line can be expressed as a point p and a vector giving the direction D :

s = p + x*D

So if we search for which x s is in the plane, we have

Dot(N, s) = d
Dot(N, p + x*D) = d

The dot product a.b is transpose(a)*b.
Let transpose(N) be Nt.

Nt*(p + x*D) = d
Nt*p + Nt*D*x = d (x scalar)
x = (d - Nt*p) / (Nt*D)
x = (d - Dot(N, p)) / Dot(N, D)

Which gives us :

float x = (d - Dot(normal, rayOrigin)) / Dot(normal, ray);

We can now get the intersection point by putting x in the line equation

s = p + x*D

Vector intersection = rayOrigin + x*ray;

The above code updated :

bool linePlaneIntersection(Vector& contact, Vector ray, Vector rayOrigin, 
                           Vector normal, Vector coord) {
    // get d value
    float d = Dot(normal, coord);

    if (Dot(normal, ray) == 0) {
        return false; // No intersection, the line is parallel to the plane
    }

    // Compute the X value for the directed line ray intersecting the plane
    float x = (d - Dot(normal, rayOrigin)) / Dot(normal, ray);

    // output contact point
    *contact = rayOrigin + normalize(ray)*x; //Make sure your ray vector is normalized
    return true;
}

Aside 1:
What does the d value mean ?
For two vectors a and b a dot product actually returns the length of the orthogonal projection of one vector on the other times this other vector.
But if a is normalized (length = 1), Dot(a, b) is then the length of the projection of b on a. In case of our plane, d gives us the directional distance all points of the plane in the normal direction to the origin (a is the normal). We can then get whether a point is on this plane by comparing the length of the projection on the normal (Dot product).

Aside 2:
How to check if a ray intersects a triangle ? (Used for raytracing)
In order to test if a ray comes into a triangle given by 3 vertices, you first have to do what is showed here, get the intersection with the plane formed by the triangle.
The next step is to look if this point lies in the triangle. This can be achieved using the barycentric coordinates, which express a point in a plane as a combination of three points in it. See Barycentric Coordinates and converting from Cartesian coordinates