3D Line Fitting in 5 Easy Steps with SVD

Least squares fit is used for 2D line fitting. In 3D space, the line is called 3D Orthogonal Distance Regression (ODR) line. The line can be easily found in 3D using SVD (singular value decomposition).

Assuming that we have a bunch of 3D points (x0, y0, z0) to (xn, yn, zn), the algorithm (in MATLAB) is as follows:

 

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):