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?

Dramamine

did you resolved, in the end? – Snuffbox

Answer 1

I could be wrong about this, but there are a few spots in the code that seem very suspicious. To begin, consider this line:

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

Here, your value d corresponds to the dot product between the plane normal (a vector) and a point in space (a point on the plane). This seems wrong. In particular, if you have any plane passing through the origin and use the origin as the coordinate point, you will end up computing

d = Dot(normal, (0, 0, 0)) = 0

And immediately returning false. I'm not sure what you intended to do here, but I'm pretty sure that this isn't what you meant.

Another spot in the code that seems suspicious is this line:

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

Note that you're computing the dot product between the plane's normal vector (a vector) and the ray's origin point (a point in space). This seems weird because it means that depending on where the ray originates in space, the scaling factor you use for the ray changes. I would suggest looking at this code one more time to see if this is really what you meant.

Hope this helps!

Blindheim

my mistake that should have been if (Dot(normal, ray) == 0), as in the plane is perpandicular to the ray, and thus possibility of no intersection. As for float t = (d - Dot(normal, rayOrigin)) / Dot(normal, ray); thats the equation given in the book – Dramamine

The scaling factor used for the ray changes based on the ray origin to compensate for the corresponding scaling in the denominator, noting that the line vector ray is not a unit vector but the whole line segment. – Andriaandriana

@Keith- Ah, I didn't catch that. That makes sense. – Blindheim

@user785259: with that mistake corrected, does the test work? – Desolation

Yes - it works with that corrected. – Kemppe

Answer 2

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

Alvera

I think that you shouldn't normalize ray at the end. – Heptarchy

Answer 3

This version worked for me in OpenGL C# application.

bool GetLinePlaneIntersection(out vec3 contact, vec3 ray_origin, vec3 ray_end, vec3 normal, vec3 coord)
{
    contact = new vec3();
    vec3 ray = ray_end - ray_origin; 

    float d = glm.dot(normal, coord);
    if (glm.dot(normal, ray) == 0)
    {
        return false; 
    }
    
    float t = (d - glm.dot(normal, ray_origin)) / glm.dot(normal, ray);
    
    contact = ray_origin + ray * t; 
    return true;
}

Pomfret

Answer 4

This all looks fine to me. I've independently checked the algebra and this looks fine for me.

As an example test case:

A = (0,0,1)
B = (0,0,-1)
coord = (0,0,0)
normal = (0,0,1)

This gives:

d = Dot( (0,0,1), (0,0,0)) = 0
Dot( (0,0,1), (0,0,-2)) = -2 // so trap for the line being in the plane passes.
t = (0 - Dot( (0,0,1), (0,0,1) ) / Dot( (0,0,1), (0,0,-2)) = ( 0 - 1) / -2 = 1/2
contact = (0,0,1) + 1/2 (0,0,-2) = (0,0,0) // as expected.

So given the emendation following @templatetypedef's answer, the only area where I can see a problem is with the implementation of one of the other operations, be it Dot(), or the Vector operators.

Andriaandriana