Intersection of a Ray and a Line Segment in 3D

This page contains methods for performing various intersection tests. Although it does not have an entry for ray vs. line segment intersection, I tried the suggested ray vs. ray intersection test (page 782 of Real-Time Rendering 3rd Edition) and it did not work in my case.

I looked around quite a bit and based on an adaptation of this answer, I finally found a method that works fine. Given a ray (with a start point, an end point and direction) and a line segment with the defined start and end points, we perform the 3D line intersection test. However, note that in various graphics APIs, there is always some error when converting screen points to lines (because there is no 1-1 mapping from screen pixels to exact 3D points in space). Therefore, when performing intersection tests, some degree of tolerance must be considered. This is especially important in the early rejection step of the intersection test algorithm. The early rejection test, checks to see whether the two 3D lines are co-planer. If they aren’t, then no intersection will be reported.

After finding the intersection point, we must check and see if this point lies between the start and end points of the line segment. This can be done by comparing the length of the line segment with the sum of distances of the intersection point from the start point and end point of the line segment respectively. If the length is “almost” equal, then it means that the original ray will intersect with the line segment.

Here is the pseudo-code of the described process (adapted from the original answer):

const double coPlanerThreshold = 0.7; // Some threshold value that is application dependent
const double lengthErrorThreshold = 1e-3;

bool intersection(Ray ray, LineSegment segment)
{
	Vector3 da = ray.End - ray.Origin;	// Unnormalized direction of the ray
	Vector3 db = segment.End - segment.Start;
	Vector3 dc = segment.Start - ray.Origin;
	
	if (Math.Abs(dc.Dot(da.Cross(db))) >= coPlanerThreshold) // Lines are not coplanar
		return false;
		
	double s = dc.Cross(db).Dot(da.Cross(db)) / da.Cross(db).LengthSquared;

	if (s >= 0.0 && s <= 1.0)	// Means we have an intersection
	{
		Vector3 intersection = ray.Origin + s * da;
		
		// See if this lies on the segment
		if ((intersection - segment.Start).LengthSquared + (intersection - segment.End).LengthSquared <= segment.LengthSquared + lengthErrorThreshold)
		return true;
	}

	return false;
}

 

5 comments

Skip to comment form

    • none on February 1, 2016 at 5:49 PM
    • Reply

    The above code declares the variable “da” twice and never declares “db”. It looks like the second one should probably be “db”?

    1. Apologies for the mistake! Yes you are correct and the post is now corrected.
      Thank you for pointing it out.

  1. Is it just me or should the Vector “ca” variable be “dc”?

    1. Good catch! Fixed 🙂
      Thanks!

    • Shreedhar Sureshrao Wattamwar on August 19, 2017 at 8:07 AM
    • Reply

    can you drop the code for 3d line segment intersection with A(x1,y1,z1) and B(x2,y2,z2)
    i need that code
    please let me know

Leave a Reply

Your email address will not be published.